《編譯原理考研真題》由會員分享，可在線閱讀，更多相關(guān)《編譯原理考研真題（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、2003年編譯原理考研真題 1．（10分）敘述下面的正規(guī)式描述的語言，并畫出接受該語言的最簡DFA的狀態(tài)轉(zhuǎn)換圖。 ( 1 | 01 )* 0* 2．（10分）某語言有兩種語句： S ? 過程調(diào)用語句 | 下標(biāo)變量賦值語句 過程調(diào)用語句的形式是：id(id, id, …, id)，即過程名加置于圓括號中的變量表。 下標(biāo)變量賦值語句的形式是：id(id, id, …, id) := id(id, id, …, id)，賦值號兩邊都是數(shù)組名加置于圓括號中的變量表。 (a) 請你完成過程調(diào)用語句和下標(biāo)變量賦值語句的文法設(shè)計(jì)，得到一個(gè)以語句S為開始符號的LR(1)文法。不得超過

2、6個(gè)產(chǎn)生式，不需要給出你的文法是LR(1)文法的證明。 (b) 如果想在LR分析的同時(shí)完成語義分析和中間代碼生成，基于你的文法有什么困難？ 3．（10分） (a) 為下面的算術(shù)表達(dá)式文法寫一個(gè)語法制導(dǎo)的翻譯方案，它將每個(gè)子表達(dá)式E的符號（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔(dān)心零的符號。 E ? E *E | +E | -E | unsigned_integer (b) 為上面的表達(dá)式產(chǎn)生棧機(jī)器代碼。代碼執(zhí)行后，表達(dá)式的值留在棧上。你自己設(shè)計(jì)所需的棧機(jī)器指令，并寫清楚指令的含義。 4．（

3、10分）在C語言的教材上，稱&為地址運(yùn)算符，&a為變量a的地址。但是教材上沒有說明表達(dá)式&a的類型是什么。另外，教材上說，數(shù)組名代表數(shù)組的首地址，但是也沒有說明這個(gè)值的類型。它們所帶來的一個(gè)問題是，如果a是一個(gè)數(shù)組名，那么表達(dá)式a和&a的值都是數(shù)組a的首地址，但是它們的使用是有區(qū)別的，初學(xué)時(shí)很難掌握。 下面我們給出4個(gè)C文件，請你根據(jù)編譯報(bào)錯(cuò)信息和程序運(yùn)行結(jié)果，寫出表達(dá)式a和&a的類型表達(dá)式。若你能掌握它們的類型，那么它們的區(qū)別就清楚了，你也就會正確使用它們了。 （1）文件1： typedef int A[10][20]; A a; A *fun() { retur

4、n(a); } 該函數(shù)在Linux上用gcc編譯時(shí)，報(bào)告的類型錯(cuò)誤如下： 第6行：warning: return from incompatible pointer type （2）文件2： typedef int A[10][20]; A a; A *fun() { return(&a); } 該函數(shù)在Linux上用gcc編譯時(shí)，沒有類型方面的錯(cuò)誤。 （3）文件3： typedef int A[10][20]; typedef int B[20]; A a; B *fun() { return(a); } 該函數(shù)

5、在Linux上用gcc編譯時(shí)，沒有類型方面的錯(cuò)誤。 （4）文件4： typedef int A[10][20]; A a; fun() { printf(“%d,%d,%d\n”, a, a+1, &a+1); } main() { fun(); } 該程序的運(yùn)行結(jié)果是： 134518112, 134518192, 134518912 2004編譯原理部分考研真題 1．（10分）下面的文法是LR(1)文法。請合并該文法LR(1)項(xiàng)目集規(guī)范族中的同心集，以說明該文法不是LALR(1)文法。 S ? a A d

6、 | b B d | a B e | b A e A ? c B ? c 2．（10分）為下面文法寫一個(gè)語法制導(dǎo)的定義，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進(jìn)制數(shù)的值。例如，輸入101.101時(shí)，S. val := 5.625。（不得修改文法。） S ? L . R | L L ? L B | B R ? B R | B B ? 0 | 1 3．（5分）在X86/Linux機(jī)器上，編譯器報(bào)告第15行有錯(cuò)誤： incompatible types in return 在C語言中，數(shù)組和結(jié)構(gòu)都是構(gòu)造類型，為什么下面第2個(gè)函數(shù)有類型錯(cuò)誤，而第1

7、個(gè)函數(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是相同的結(jié)構(gòu)類型，那么賦值a=b是可以的。但是編譯器對這種賦值的實(shí)現(xiàn)方式可能和它們的字節(jié)數(shù)（size）有關(guān)。下面是兩個(gè)C語言程序及在X86/Linux機(jī)器上生成的目標(biāo)代碼（略去了和本題

8、目無關(guān)的部分）。扼要敘述這些目標(biāo)代碼中體現(xiàn)出的實(shí)現(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)

9、 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 —— 設(shè)定方向標(biāo)志，使地址指針自動增量 movl $6,%ecx —— 設(shè)定重復(fù)次數(shù) rep —— 表示重復(fù)下面的指

10、令 movsl —— 傳送指令 .L1: leal -8(%ebp),%esp popl %esi popl %edi leave ret 2005編譯原理考研真題 1．（5分）下面是用正規(guī)式表示的變量聲明： ( int | float ) id (, id )* ; 請改用上下文無關(guān)文法表示，也就是寫一個(gè)上下文無關(guān)文法，它和該正規(guī)式等價(jià)。 2．（10分）在C語言中，3++和( id + id )++這樣的表達(dá)式被編譯時(shí)，編譯器都會報(bào)告如下的錯(cuò)誤： invalid lvalue in increment 現(xiàn)有如下簡化的C語言表

11、達(dá)式文法： E ? E + E | ( E ) | E ++ | id | num 請你寫一個(gè)語法制導(dǎo)定義或翻譯方案，它檢查++的運(yùn)算對象是否合法。 3．（10分）下面是一個(gè)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機(jī)器上的運(yùn)行結(jié)果

12、如下： f1 = 0, f2 = 100 請解釋為什么用同樣的實(shí)在參數(shù)調(diào)用這兩個(gè)函數(shù)的結(jié)果不一樣。 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

13、, id | id L ? id , L | id 如果用LL(1)分析方法，應(yīng)該選擇哪個(gè)文法？如果用某種LR分析方法，選擇哪個(gè)文法更好？簡要說明理由。 2、（6分）用SLR(1)文法能定義的語言集合、用LR(1)文法能定義的語言集合和用LALR(1)文法能定義的語言集合之間有什么關(guān)系？（不需要給出理由。） 3、（8分）下面是一個(gè)C語言的函數(shù)： void f(char c, long j) { char *p; char ch; long m[3]; p=&c; m[0]=j; } 在x86

14、/Linux機(jī)器上經(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) lea

15、l -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

16、、（6分）兩個(gè)C語言文件link1.c和link2.c的內(nèi)容分別如下： int buf[1] ={100}; 和 extern int *buf; main() { printf(“%d\n”, *buf); } 在X86/Linux經(jīng)命令cc link1.c link2.c編譯后，運(yùn)行時(shí)產(chǎn)生如下的出錯(cuò)信息： Segmentation fault (core dumped) 請說明原因。 2007年編譯原理部分 1、（10分） 描述由正規(guī)式b*(abb*)*(a| e)定義的語言，并畫出接受該語言的最簡DFA。 2、（1

17、0分） 證明文法E ? E + id | id是SLR(1)文法。 3、（10分） 下面是表達(dá)式和賦值語句的文法，其中and的類型是bool ′ bool ? bool，+的類型是int ′ int ? int，=的類型是int ′ int ? bool，:= 要求id 和E的類型都是int或者都是bool。為該文法寫一個(gè)語法制導(dǎo)定義或翻譯方案，它完成類型檢查。 S ? id := E E ? E and E | E + E | E = E |id 4、（5分） 對于下面C語言文件s.c f1(int x) { long x; x = 1;

18、 } f2(int x) { { long x; x = 1; } } 某編譯器編譯時(shí)報(bào)錯(cuò)如下： s.c: In function ‘f1’: s.c:3: warning: declaration of ‘x’ shadows a parameter 請回答，對函數(shù)f2為什么沒有類似的警告錯(cuò)誤。 5、（5分） 下面C語言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是 area=12.566360, addr=-1073743076 經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是 area=12.56

19、6360, addr=-1073743068 請解釋為什么輸出結(jié)果有區(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)生代表正二進(jìn)制數(shù)的0和1的串

20、集： B ? B 0 | B 1 | 1 下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值： B ? B1 0 {B.val := B1.val ′ 2 } | B1 1 {B.val := B1.val ′ 2 +1} | 1 {B.val := 1 } 請消除該基礎(chǔ)文法的左遞歸，再重寫一個(gè)翻譯方案，它仍然計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值。 3、（10分） 在C語言中，如果變量i和j都是long類型，請寫出表達(dá)式&i和表達(dá)式&i-&j的類型表達(dá)式。為幫助你回答問題，下面給出一個(gè)程序作為提示，它運(yùn)行時(shí)輸出1。 main() { long

21、 i, j; printf(“%d\n”, &i-&j); } 4、（10分）一個(gè)C語言的函數(shù)如下： func(i) long i; { long j; j = i – 1; func(j); } 下面左右兩邊的匯編代碼是兩個(gè)不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實(shí)質(zhì)區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點(diǎn)。 func: | func: pushl %ebp | pushl %ebp mov

22、l %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 |