2003年編譯原理考研真題 1．（10分）敘述下面的正規(guī)式描述的語言，并畫出接受該語言的最簡DFA的狀態(tài)轉換圖。 ( 1 | 01 )* 0* 2．（10分）某語言有兩種語句： S ® 過程調用語句 | 下標變量賦值語句 過程調用語句的形式是：id(id, id, …, id)，即過程名加置于圓括號中的變量表。 下標變量賦值語句的形式是：id(id, id, …, id) := id(id, id, …, id)，賦值號兩邊都是數(shù)組名加置于圓括號中的變量表。 (a) 請你完成過程調用語句和下標變量賦值語句的文法設計，得到一個以語句S為開始符號的LR(1)文法。不得超過6個產(chǎn)生式，不需要給出你的文法是LR(1)文法的證明。 (b) 如果想在LR分析的同時完成語義分析和中間代碼生成，基于你的文法有什么困難？ 3．（10分） (a) 為下面的算術表達式文法寫一個語法制導的翻譯方案，它將每個子表達式E的符號（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔心零的符號。 E ® E *E | +E | -E | unsigned_integer (b) 為上面的表達式產(chǎn)生棧機器代碼。代碼執(zhí)行后，表達式的值留在棧上。你自己設計所需的棧機器指令，并寫清楚指令的含義。 4．（10分）在C語言的教材上，稱&為地址運算符，&a為變量a的地址。但是教材上沒有說明表達式&a的類型是什么。另外，教材上說，數(shù)組名代表數(shù)組的首地址，但是也沒有說明這個值的類型。它們所帶來的一個問題是，如果a是一個數(shù)組名，那么表達式a和&a的值都是數(shù)組a的首地址，但是它們的使用是有區(qū)別的，初學時很難掌握。 下面我們給出4個C文件，請你根據(jù)編譯報錯信息和程序運行結果，寫出表達式a和&a的類型表達式。若你能掌握它們的類型，那么它們的區(qū)別就清楚了，你也就會正確使用它們了。 （1）文件1： typedef int A[10][20]; A a; A *fun() { return(a); } 該函數(shù)在Linux上用gcc編譯時，報告的類型錯誤如下： 第6行：warning: return from incompatible pointer type （2）文件2： typedef int A[10][20]; A a; A *fun() { return(&a); } 該函數(shù)在Linux上用gcc編譯時，沒有類型方面的錯誤。 （3）文件3： typedef int A[10][20]; typedef int B[20]; A a; B *fun() { return(a); } 該函數(shù)在Linux上用gcc編譯時，沒有類型方面的錯誤。 （4）文件4： typedef int A[10][20]; A a; fun() { printf(“%d,%d,%d\n”, a, a+1, &a+1); } main() { fun(); } 該程序的運行結果是： 134518112, 134518192, 134518912 2004編譯原理部分考研真題 1．（10分）下面的文法是LR(1)文法。請合并該文法LR(1)項目集規(guī)范族中的同心集，以說明該文法不是LALR(1)文法。 S ® a A d | b B d | a B e | b A e A ® c B ® c 2．（10分）為下面文法寫一個語法制導的定義，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進制數(shù)的值。例如，輸入101.101時，S. val := 5.625。（不得修改文法。） S ® L . R | L L ® L B | B R ® B R | B B ® 0 | 1 3．（5分）在X86/Linux機器上，編譯器報告第15行有錯誤： incompatible types in return 在C語言中，數(shù)組和結構都是構造類型，為什么下面第2個函數(shù)有類型錯誤，而第1個函數(shù)沒有？ typedef int A1[10]; typedef int A2[10]; A1 a; typedef struct {int i;}S1; typedef struct {int i;}S2; S1 s; A2 *fun1() { return(&a); } S2 fun2() { return(s); } 4．（5分）在C語言中，若a和b是相同的結構類型，那么賦值a=b是可以的。但是編譯器對這種賦值的實現(xiàn)方式可能和它們的字節(jié)數(shù)（size）有關。下面是兩個C語言程序及在X86/Linux機器上生成的目標代碼（略去了和本題目無關的部分）。扼要敘述這些目標代碼中體現(xiàn)出的實現(xiàn)方式上的區(qū)別。（在下面匯編程序中給出的注釋僅供參考。） struct {long i,j; double m;}a,b; main() { a=b; } main: pushl %ebp movl %esp,%ebp movl $b,%eax movl $a,%edx movl (%eax),%ecx movl %ecx,(%edx) movl 4(%eax),%ecx movl %ecx,4(%edx) movl 8(%eax),%ecx movl %ecx,8(%edx) movl 12(%eax),%eax movl %eax,12(%edx) .L1: leave ret struct {long i,j; double m,n;}a,b; main() { a=b; } main: pushl %ebp movl %esp,%ebp pushl %edi pushl %esi movl $a,%edi movl $b,%esi cld —— 設定方向標志，使地址指針自動增量 movl $6,%ecx —— 設定重復次數(shù) rep —— 表示重復下面的指令 movsl —— 傳送指令 .L1: leal -8(%ebp),%esp popl %esi popl %edi leave ret 2005編譯原理考研真題 1．（5分）下面是用正規(guī)式表示的變量聲明： ( int | float ) id (, id )* ; 請改用上下文無關文法表示，也就是寫一個上下文無關文法，它和該正規(guī)式等價。 2．（10分）在C語言中，3++和( id + id )++這樣的表達式被編譯時，編譯器都會報告如下的錯誤： invalid lvalue in increment 現(xiàn)有如下簡化的C語言表達式文法： E ® E + E | ( E ) | E ++ | id | num 請你寫一個語法制導定義或翻譯方案，它檢查++的運算對象是否合法。 3．（10分）下面是一個C語言程序： long f1(i) long i; { return(i*10); } long f2(long i) { return(i*10); } main() { printf(“f1 = %d, f2 = %d\n”, f1(10.0), f2(10.0) ); } 其中函數(shù)f1和f2僅形式參數(shù)的描述方式不一樣。該程序在X86/Linux機器上的運行結果如下： f1 = 0, f2 = 100 請解釋為什么用同樣的實在參數(shù)調用這兩個函數(shù)的結果不一樣。 4．（5分）優(yōu)化編譯器對下面程序的局部變量i和j不分配空間，為什么？ main() { long i, j; i = 5; j = i * 2; printf(“%d\n”, i+j); } 2006編譯原理考研真題 1、（10分）下面是int i, j, k這樣的類型聲明的兩種不同語法： D ® T L D ® T L T ® int | real T ® int | real L ® L , id | id L ® id , L | id 如果用LL(1)分析方法，應該選擇哪個文法？如果用某種LR分析方法，選擇哪個文法更好？簡要說明理由。 2、（6分）用SLR(1)文法能定義的語言集合、用LR(1)文法能定義的語言集合和用LALR(1)文法能定義的語言集合之間有什么關系？（不需要給出理由。） 3、（8分）下面是一個C語言的函數(shù)： void f(char c, long j) { char *p; char ch; long m[3]; p=&c; m[0]=j; } 在x86/Linux機器上經(jīng)某版本的編譯器編譯生成的匯編代碼如下： .file "frame.c" .version "01.01" gcc2_compiled.: .text .align 4 .globl f .type f,@function f: 參數(shù)j 參數(shù)c 返回地址 老ebp（控制鏈） esp ® ¬ ebp 棧增長方向 高地址 低地址 pushl %ebp movl %esp,%ebp subl $24,%esp movl 8(%ebp),%eax movb %al,-1(%ebp) leal -1(%ebp),%edx movl %edx,-8(%ebp) movl 12(%ebp),%eax movl %eax,-24(%ebp) .L1: leave ret .Lfe1: .size f,.Lfe1-f .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)" 請將執(zhí)行subl $24,%esp后，esp和ebp指向地址之間的區(qū)域（見上圖）用于存放哪些變量的值，按照這些變量的名字、相對于ebp指向地址的偏移、字節(jié)數(shù)（size）列出來。 4、（6分）兩個C語言文件link1.c和link2.c的內容分別如下： int buf[1] ={100}; 和 extern int *buf; main() { printf(“%d\n”, *buf); } 在X86/Linux經(jīng)命令cc link1.c link2.c編譯后，運行時產(chǎn)生如下的出錯信息： Segmentation fault (core dumped) 請說明原因。 2007年編譯原理部分 1、（10分） 描述由正規(guī)式b*(abb*)*(a| e)定義的語言，并畫出接受該語言的最簡DFA。 2、（10分） 證明文法E ® E + id | id是SLR(1)文法。 3、（10分） 下面是表達式和賦值語句的文法，其中and的類型是bool ´ bool ® bool，+的類型是int ´ int ® int，=的類型是int ´ int ® bool，:= 要求id 和E的類型都是int或者都是bool。為該文法寫一個語法制導定義或翻譯方案，它完成類型檢查。 S ® id := E E ® E and E | E + E | E = E |id 4、（5分） 對于下面C語言文件s.c f1(int x) { long x; x = 1; } f2(int x) { { long x; x = 1; } } 某編譯器編譯時報錯如下： s.c: In function ‘f1’: s.c:3: warning: declaration of ‘x’ shadows a parameter 請回答，對函數(shù)f2為什么沒有類似的警告錯誤。 5、（5分） 下面C語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入2，則結果是 area=12.566360, addr=-1073743076 經(jīng)優(yōu)化編譯后，若運行時輸入2，則結果是 area=12.566360, addr=-1073743068 請解釋為什么輸出結果有區(qū)別。 main() { float s, pi, r; pi=3.14159; scanf("%f", &r); printf("area=%f, addr=%d\n", s=pi*r*r, &r); } 2008年編譯原理考研真題 1、（10分） 描述由正規(guī)式b*a(bb*a) *b*定義的語言，并畫出接受該語言的最簡DFA。 2、（10分） 下面的文法產(chǎn)生代表正二進制數(shù)的0和1的串集： B ® B 0 | B 1 | 1 下面的翻譯方案計算這種正二進制數(shù)的十進制值： B ® B1 0 {B.val := B1.val ´ 2 } | B1 1 {B.val := B1.val ´ 2 +1} | 1 {B.val := 1 } 請消除該基礎文法的左遞歸，再重寫一個翻譯方案，它仍然計算這種正二進制數(shù)的十進制值。 3、（10分） 在C語言中，如果變量i和j都是long類型，請寫出表達式&i和表達式&i-&j的類型表達式。為幫助你回答問題，下面給出一個程序作為提示，它運行時輸出1。 main() { long i, j; printf(“%d\n”, &i-&j); } 4、（10分）一個C語言的函數(shù)如下： func(i) long i; { long j; j = i – 1; func(j); } 下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調用func之前將參數(shù)壓棧，調用結束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點。 func: | func: pushl %ebp | pushl %ebp movl %esp, %ebp | movl %esp, %ebp subl $4, %esp | subl $8, %esp movl 8(%ebp), %edx | movl 8(%ebp), %eax decl %edx | decl %eax movl %edx, -4(%ebp) | movl %eax, -4(%ebp) movl -4(%ebp), %eax | movl -4(%ebp), %eax pushl %eax | movl %eax, (%esp) call func | call func addl $4, %esp | leave leave | ret ret |