編譯原理試題(2009-2010-1).doc

編譯原理試題A1名詞解釋短語(yǔ)LL（1）文法語(yǔ)法分析無(wú)環(huán)路有向圖(DAG)語(yǔ)法制導(dǎo)翻譯2 Pascal語(yǔ)言無(wú)符號(hào)數(shù)的正規(guī)定義如下：num digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無(wú)符號(hào)數(shù)的確定有限自動(dòng)機(jī)。3下面兩個(gè)文法中哪一個(gè)不是LR（1）文法？對(duì)非LR（1）的那個(gè)文法。給出那個(gè)有移進(jìn)歸約沖突的規(guī)范的LR（1）項(xiàng)目集。S aAcS aAcA bbA | bA bAb | b4構(gòu)造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e5 C語(yǔ)言是一種類型語(yǔ)言，但它不是強(qiáng)類型語(yǔ)言，因?yàn)榫幾g時(shí)的類型檢查不能保證所接受的程序沒(méi)有運(yùn)行時(shí)的類型錯(cuò)誤。例如，編譯時(shí)的類型檢查一般不能保證運(yùn)行時(shí)沒(méi)有數(shù)組越界。請(qǐng)你再舉一個(gè)這樣的例子說(shuō)明C語(yǔ)言不是強(qiáng)類型語(yǔ)言。6把表達(dá)式-(a+b)*(c+d)+(a+b+c)翻譯成三元式。7為下面文法添加語(yǔ)義規(guī)則（或叫動(dòng)作子程序），輸出S產(chǎn)生的二進(jìn)制數(shù)的值，如輸入是101時(shí)，輸出5。S SS S B | BB 0 | 18一個(gè)C語(yǔ)言的函數(shù)如下：func(c,l)char c;long l; func(c,l);在X86/Linux機(jī)器上編譯生成的匯編代碼如下：.fileparameter.c.version01.01gcc2_compiled.:.text.align 4.globl func.type func,functionfunc:pushl %ebp 將老的基地址指針壓棧movl %esp,%ebp 將當(dāng)前棧頂指針作為基地址指針subl $4,%esp 分配空間movl 8(%ebp),%eaxmovb %al,-1(%ebp)movl 12(%ebp),%eaxpushl %eaxmovsbl -1(%ebp),%eaxpushl %eaxcall funcaddl $8,%esp.L1:leave 和下一條指令一起完成恢復(fù)老的基地址指針，將棧頂ret 指針恢復(fù)到調(diào)用前參數(shù)壓棧后的位置，并返回調(diào)用者.Lfe1:.size func,.Lfe1-func.identGCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)(a) 請(qǐng)指出對(duì)應(yīng)源程序第5行的函數(shù)調(diào)用func(c,l)的匯編指令是哪幾條。(b) 請(qǐng)說(shuō)明字符型參數(shù)和長(zhǎng)整型參數(shù)在參數(shù)傳遞和存儲(chǔ)分配方面有什么區(qū)別。（小于長(zhǎng)整型size的整型參數(shù)的處理方式和字符型參數(shù)的處理方式是一樣的。）9程序的文法如下：P DD D ; D | id : T | proc id ; D ; S（1）寫一個(gè)語(yǔ)法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id。（2）寫一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。編譯原理試題B1名詞解釋句柄LR（1）文法無(wú)環(huán)路有向圖(DAG)語(yǔ)法制導(dǎo)翻譯局部?jī)?yōu)化2某操作系統(tǒng)下合法的文件名為device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，長(zhǎng)度不限，但至少為1，畫出識(shí)別這種文件名的確定有限自動(dòng)機(jī)。3下面兩個(gè)文法中哪一個(gè)不是LR（1）文法？對(duì)非LR（1）的那個(gè)文法。給出那個(gè)有移進(jìn)歸約沖突的規(guī)范的LR（1）項(xiàng)目集。S aAcS aAcA bbA | bA bAb | b4程序的文法如下：P DD D ; D | id : T | proc id ; D ; S（1）寫一個(gè)語(yǔ)法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id。（2）寫一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。5在PASCAL語(yǔ)言中，簡(jiǎn)單類型的變量的聲明例舉如下：m, n : integerp, q, r : real為這樣的聲明寫一個(gè)LR（1）文法（為簡(jiǎn)單起見(jiàn)，變量標(biāo)識(shí)符都用id表示），并根據(jù)你的文法寫一個(gè)語(yǔ)法制導(dǎo)定義（或叫做為你的文法加上語(yǔ)義動(dòng)作），它將變量的類型填入符號(hào)表。6下面程序在SUN工作站上運(yùn)行時(shí)陷入死循環(huán)，試說(shuō)明原因。如果將第8行的long *p改成short *p，并且將第23行l(wèi)ong k 改成short k后，loop中的循環(huán)體執(zhí)行一次便停止了。試說(shuō)明原因。main()addr();loop();long *p;loop()long i,j;j=0;for(i=0;i10;i+)(*p)-;j+;addr()long k;k=0;p=&k;7一個(gè)C語(yǔ)言函數(shù)如下：main()int i,j,k;i=5;j=1;while(j100)k=i+1;j=j+k;經(jīng)優(yōu)化編譯后，生成的代碼如下：.file“optimize.c” gcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function _func:pushl %ebpmovl %esp,%ebpmovl $1,%eaxmovl $6,%edx.align 2,0x90L4:addl %edx,%eaxcmpl $99,%eaxjle L4leaveretLfe1:.size_func,Lfe1-_func試說(shuō)明編譯器對(duì)這個(gè)程序作了哪些種類的優(yōu)化（只需要說(shuō)復(fù)寫傳播、刪除公共子表達(dá)式等，不需要說(shuō)怎樣完成這些優(yōu)化的）。8