編譯原理復(fù)習(xí)題集

編譯原理復(fù)習(xí)題集1名詞解釋短語句柄文法上下文無關(guān)文法LL（1）文法LR（1）文法語法分析無環(huán)路有向圖(DAG)后綴式語法制導(dǎo)翻譯遍局部?jī)?yōu)化詞法分析語法分析語義分析源語言源程序目標(biāo)語言中間語言（中間表示）2簡(jiǎn)答題(1) 編譯程序和高級(jí)語言有什么區(qū)別? (2) 編譯程序的工作分為那幾個(gè)階段? (3) 簡(jiǎn)述自下而上的分析方法。(4) 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？(5) 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？ (6) 簡(jiǎn)述代碼優(yōu)化的目的和意義。3敘述下面的正規(guī)式描述的語言，并畫出接受該語言的最簡(jiǎn)DFA的狀態(tài)轉(zhuǎn)換圖。( 1 | 01 )* 0*4Pascal語言無符號(hào)數(shù)的正規(guī)定義如下：num digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無符號(hào)數(shù)的確定有限自動(dòng)機(jī)。5畫出Pascal中實(shí)數(shù)(不帶正負(fù)號(hào)，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。 6用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)*aa的確定的有限自動(dòng)機(jī)。7處于/* 和 */之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。8某操作系統(tǒng)下合法的文件名為device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，長(zhǎng)度不限，但至少為1，畫出識(shí)別這種文件名的確定有限自動(dòng)機(jī)。9構(gòu)造一個(gè)DFA，它接受=0, 1上0和1的個(gè)數(shù)都是偶數(shù)的字符串。10設(shè)有非確定的有自限動(dòng)機(jī) NFA M=(A，B，C，0，1，A，C)，其中： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。請(qǐng)畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。11設(shè) L a,b,c* 是滿足下述條件的符號(hào)串構(gòu)成的語言： (1)若出現(xiàn) a ，則其后至少緊跟兩個(gè) c ； (2)若出現(xiàn) b ，其后至少緊跟一個(gè) c 。 試構(gòu)造識(shí)別 L 的最小化的 DFA ，并給出描述 L 的正規(guī)表達(dá)式。 12寫出字母表 = a, b上語言L = w | w的最后兩個(gè)字母是aa或bb的正規(guī)式，并畫出接受該語言的最簡(jiǎn)DFA。13有窮自動(dòng)機(jī)M接受字母表0,1上所有滿足下述條件的串：串中至少包含兩個(gè)連續(xù)的0或兩個(gè)連續(xù)的1。請(qǐng)寫出與M等價(jià)的正規(guī)式。14有正規(guī)式 b*abb*(abb*)* ，(1) 構(gòu)造該正規(guī)式所對(duì)應(yīng)的 NFA(畫出狀態(tài)轉(zhuǎn)換圖) 。(2) 將所求的 NFA 確定化(畫出確定化的狀態(tài)轉(zhuǎn)換圖)。 (3) 將所求的 NFA 最小化. (畫出最小化后的狀態(tài)轉(zhuǎn)換圖)。15求出下列文法所產(chǎn)生語言對(duì)應(yīng)的正規(guī)式. SbS|aA AaA|bB BaA|bC|b CbS|aA 16給出與下圖的NFA等價(jià)的正規(guī)式。S0S1S3S217把下面的NFA確定化。123456101110118下面兩個(gè)文法中哪一個(gè)不是LR（1）文法？對(duì)非LR（1）的那個(gè)文法。給出那個(gè)有移進(jìn)歸約沖突的規(guī)范的LR（1）項(xiàng)目集。S aAcS aAcA bbA | bA bAb | b0123aababba,b19將下面的DFA化成最簡(jiǎn)形式。20為語言L w | w (a | b)*并且在w的任何前綴中，a的個(gè)數(shù)不少于b的個(gè)數(shù)寫一個(gè)LR（1）文法，不準(zhǔn)超過6個(gè)產(chǎn)生式。21寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。 22考查文法G(s): S( T ) | a + S | aTT, S | S(1) 消除文法的左遞歸；(2) 提取公共左因子；(3) 對(duì)每個(gè)非終結(jié)符，寫出不帶回朔的遞歸子程序。23設(shè)文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和回溯； (2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3)構(gòu)造預(yù)測(cè)分析表。 24消除下列文法的左遞歸. SSaP|Sf|P PQbP|Q QcSd|e 25已知文法 G ：AaABe|a BBb|d 給出與上述文法等價(jià)的 LL(1)文法 G。26已知文法GA：A aAB | a B Bb | d（1）構(gòu)造與GA等價(jià)的LL(1)文法；（2）構(gòu)造GA的預(yù)測(cè)分析表。27程序的文法如下：P DD D ; D | id : T | proc id ; D ; S（1）寫一個(gè)語法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id。（2）寫一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。28構(gòu)造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e29考慮下文法：D TVT int floatV id , V | ida. 在該文法中提取左公因子。b. 為所得文法的非終結(jié)符構(gòu)造First和Follow集合。c. 說明所得的文法是LL(1)文法。d. 為所得文法構(gòu)造LL(1)分析表。e. 假設(shè)有輸入串int x , y , z 寫出相應(yīng)LL(1)分析程序的動(dòng)作。 30說明如下文法是否是LL（1）文法，若不是，將其轉(zhuǎn)換為L(zhǎng)L（1）文法。最后給出該文法的LL（1）分析表。 A B e B B b | a 31設(shè)有文法：Pbegin XYendXXd;Xd;YY;sYs(1) 該文法含有左遞歸嗎？若有，消除它。(2) 改造后的文法是LL(1)文法嗎？若是，給出其預(yù)測(cè)分析表。(3) 寫出句子 begin d；s end的分析過程。32已給文法 GS ： S SaP | Sf | P P qbP | q 將 GS 改造成 LL （ 1 ）文法，并給出 LL （ 1 ）分析表。 33設(shè)文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測(cè)分析表。 34給定文法 GS ： S Aa|dAb|Bb|dBa A c B c 構(gòu)造文法 GS 的 LR （ 1 ）分析表。 35已知文法G(S) Sa|(T) TT，S|S 寫出句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。 36已知文法G(E) ET|ET TF|T *F F(E)|i 給出句型(T *Fi)的最右推導(dǎo)及畫出語法樹； 37說明下面的文法不是SLR(1)文法，并重寫一個(gè)等價(jià)的SLR(1)文法。S M a | b M c | d c | b d aM dS S S M a | b M c | d c | b d aM dS .SS .M aS .b M cS . d cS . b d aM .dS b .M cS b .d aM .dS b d .aM d .bd因?yàn)閍是M的后繼符號(hào)之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn)-歸約沖突。等價(jià)的SLR(1)文法是S d a | b d c | d c | b d a38在PASCAL語言中，簡(jiǎn)單類型的變量的聲明例舉如下：m, n : integerp, q, r : real為這樣的聲明寫一個(gè)LR（1）文法（為簡(jiǎn)單起見，變量標(biāo)識(shí)符都用id表示），并根據(jù)你的文法寫一個(gè)語法制導(dǎo)定義（或叫做為你的文法加上語義動(dòng)作），它將變量的類型填入符號(hào)表。39一個(gè)非LR（1）的文法如下：L MLb | aM e請(qǐng)給出所有有移進(jìn)歸約沖突的LR（1）項(xiàng)目集，以說明該文法確實(shí)不是LR（1）的。40若有文法 G(S)的產(chǎn)生式如下：SL=R SR L*R Li RL,構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的 DFA.，判斷該文法是否是 SLR(1)文法，說明理由。 41現(xiàn)有句型g ba lb 和產(chǎn)生式A ba，分別指出LL（1）方法和LR（1）方法在掃描到此句型的什么位置決定用此產(chǎn)生式？42為下面的算術(shù)表達(dá)式文法寫一個(gè)語法制導(dǎo)的翻譯方案，它將每個(gè)子表達(dá)式E的符號(hào)（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔(dān)心零的符號(hào)。E E *E | +E | -E | unsigned_integer43一個(gè)文法如下： S ( S ) S a 請(qǐng)給出該文法中對(duì)活前綴(有效的LR (1)項(xiàng)目。44為下面文法添加語義規(guī)則（或叫動(dòng)作子程序），輸出S產(chǎn)生的二進(jìn)制數(shù)的值，如輸入是101時(shí)，輸出5。S SS S B | BB 0 | 145寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示及三元式序列。 46把表達(dá)式- (a+b)*(c+d)+(a+b+c)翻譯成三地址碼序列。47設(shè)布爾表達(dá)式的文法為 E E1E2 E E1E2 E i 假定它們將用于條件控制語句中，請(qǐng) (1)改寫文法，使之適合進(jìn)行語法制導(dǎo)翻譯； (2)寫出改寫后的每個(gè)產(chǎn)生式的語義動(dòng)作。 48將語句 if (A0) while ( C0 ) C=C+D; 翻譯成三地址碼序列。49設(shè)有基本塊如下：T1=S+RT2= 3T3= 12/T2T4=S/RA=T1-T4T5=S+RB=T5T6=T5*T3B=T6(1) 畫出中間代碼的流圖；(2) 設(shè)A、B是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的三地址碼序列。50設(shè)已構(gòu)造出文法G(S)：(1) S BB (2) B aB (3) B b的LR分析表如下ACTIONGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab，請(qǐng)給出LR分析過程(即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過程)。51給出活動(dòng)記錄空間結(jié)構(gòu)。并給出各部分的存儲(chǔ)對(duì)象。52將下面程序段翻譯成四元式序列。while( ACBD )if ( A=1) C=C+1 ; else while ( A0 THEN x:=x+1 ELSE x:=4*( x- 1)的翻譯方案圖。55下面是一個(gè)C語言程序：main()long i;long a04;long j;i = 4; j = 8;printf(“%d, %dn”, sizeof(a), a00);雖然出現(xiàn)long a04這樣的聲明，在X86/Linux機(jī)器上該程序還是能通過編譯并生成目標(biāo)代碼。請(qǐng)回答下面兩個(gè)問題：（1）sizeof(a)的值是多少，請(qǐng)說明理由。（2）a00的值是多少，請(qǐng)說明理由。（1）按照數(shù)組size的計(jì)算公式，sizeof(a)的值一定是0。（2）a00的值是4。雖然a的size是0，但它仍然有起始地址，并且a00的地址等于a的起始地址。由于X86/Linux機(jī)器上，活動(dòng)記錄棧向低地址方向增長(zhǎng)，另外由于低地址放低位字節(jié)，因此a00的地址和i的地址一致，其值和i的值一樣，等于4。56將下面的條件語句表示成三地址碼序列： if ( ab ) x=a+b*c ; else x=b-a; 57考慮下面的三地址語句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y = z goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9（1）在該代碼中用水平的橫線將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序號(hào)。（2）畫出該代碼的控制流圖，每個(gè)基本塊就用（1）的序號(hào)表示。（3）若有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。（1） （2）14237865b := 1b := 2if w = x goto L2（1）e := bgoto L2（2）L1:goto L3（3）L2:c := 3b := 4c := 6（4）L3:if y = z goto L4（5）goto L5（6）L4:g := g + 1h := 8goto L1（7）L5:h := 9（8）（3）結(jié)點(diǎn)5、7和3構(gòu)成一個(gè)循環(huán)，其中5是入口結(jié)點(diǎn)。58一個(gè)C語言程序如下：func(i1,i2,i3)long i1,i2,i3;long j1,j2,j3; printf(Addresses of i1,i2,i3 = %o,%o,%on,&i1,&i2,&i3);printf(Addresses of j1,j2,j3 = %o,%o,%on,&j1,&j2,&j3);main()long i1,i2,i3;func(i1,i2,i3);該程序在SUN工作站上的運(yùn)行結(jié)果如下：Addresses of i1,i2,i3 = ,Addresses of j1,j2,j3 = ,從上面的結(jié)果可以看出，func 函數(shù)的3個(gè)形式參數(shù)的地址依次升高，而3個(gè)局部變量的地址依次降低。試說明為什么會(huì)有這個(gè)區(qū)別。由于實(shí)參表達(dá)式是反序進(jìn)入活動(dòng)記錄，而局部變量是順序在活動(dòng)記錄中分配。59一個(gè)C語言程序如下：void fun(struct int x; double r; val) main()struct int x; double r; val;fun(val);該程序在X86/Linux機(jī)器上的用cc命令編譯時(shí)，報(bào)告的錯(cuò)誤信息如下：1: warning: structure defined inside parms1: warning: anonymous struct declared inside parameter list1: warning: its scope is only this definition or declaration,1: warning: which is probably not what you want.7: incompatible type for argument 1 of fun 請(qǐng)問，報(bào)告最后一行的錯(cuò)誤的原因是什么？如何修改程序，使得編譯時(shí)不再出現(xiàn)這個(gè)錯(cuò)誤信息。60一個(gè)C語言程序如下：main()func();printf(Return from funcn);func()char s4;strcpy(s,);printf(%sn,s);該程序在PC機(jī)linux操作系統(tǒng)上的運(yùn)行結(jié)果如下：Segmentation fault (core dumped)試分析為什么會(huì)出現(xiàn)這樣的運(yùn)行錯(cuò)誤。61一個(gè)C語言函數(shù)如下：func(i)long i;long j;j=i-1;func(j);該函數(shù)在PC機(jī)linux操作系統(tǒng)上編譯生成的匯編代碼如下：.filestack.cgcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function_func:pushl %ebpmovl %esp,%ebpsubl $4,%espmovl 8(%ebp),%edxdecl %edxmovl %edx, -4(%ebp)movl -4(%ebp),%eaxpushl %eaxcall _funcaddl $4,%espL1:leaveretLfe1:.size_func,Lfe1-_func試畫出該函數(shù)的一個(gè)活動(dòng)記錄的內(nèi)容，包括活動(dòng)記錄的每個(gè)單元存放什么東西、執(zhí)行movl 8(%ebp),%edx指令時(shí)棧頂指針?biāo)傅牡奈恢?、與活動(dòng)記錄有關(guān)的另一個(gè)指針?biāo)傅奈恢煤偷刂吩鲩L(zhǎng)方向。62一個(gè)C語言的函數(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 /Linux (egcs-1.1.2 release)(a) 請(qǐng)指出對(duì)應(yīng)源程序第5行的函數(shù)調(diào)用func(c,l)的匯編指令是哪幾條。(b) 請(qǐng)說明字符型參數(shù)和長(zhǎng)整型參數(shù)在參數(shù)傳遞和存儲(chǔ)分配方面有什么區(qū)別。（小于長(zhǎng)整型size的整型參數(shù)的處理方式和字符型參數(shù)的處理方式是一樣的。）63一個(gè)C語言程序及其在某種機(jī)器linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的作用域、生存期和置初值方式等方面的區(qū)別。static long aa = 10;short bb = 20;func() static long cc = 30; short dd = 40;編譯生成的匯編代碼如下：.filestatic.c.version01.01gcc2_compiled.:.data.align 4.type aa,object.size aa,4aa:.long 10.globl bb.align 2.type bb,object.size bb,2bb:.value 20.align 4.type cc.2,object.size cc.2,4cc.2:.long 30.text.align 4.globl func.type func,functionfunc:pushl %ebpmovl %esp,%ebpsubl $4,%espmovw $40,-2(%ebp).L1:leaveret.Lfe1:.size func,.Lfe1-func.identGCC: (GNU) egcs-2.91.66 /Linux (egcs-1.1.2 release)aa是靜態(tài)外部變量，而bb是外部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)（由.data偽指令開始），但是bb由偽指令.globl指明為全局的，用來解決其它文件中對(duì)bb的外部引用，而aa只能由本文件引用。cc是靜態(tài)局部變量，同aa和bb一樣，它的生存期是整個(gè)程序并分配在靜態(tài)數(shù)據(jù)區(qū)。由于cc在源程序中的作用域是函數(shù)func的體，而在目標(biāo)文件中，它的作用域至少已是整個(gè)文件了，為避免同源文件中外部變量和其它函數(shù)的靜態(tài)局部變量的名字沖突，所以要對(duì)它進(jìn)行改名，成了cc.2。由于cc不是全局的，因此cc.2前面沒有偽指令.globl。dd是自動(dòng)變量，其作用域是函數(shù)func的體，其生存期是該函數(shù)激活期間，因此它分配在棧區(qū)，并且置初值是用運(yùn)行時(shí)的賦值來實(shí)現(xiàn)。64 C語言是一種類型語言，但它不是強(qiáng)類型語言，因?yàn)榫幾g時(shí)的類型檢查不能保證所接受的程序沒有運(yùn)行時(shí)的類型錯(cuò)誤。例如，編譯時(shí)的類型檢查一般不能保證運(yùn)行時(shí)沒有數(shù)組越界。請(qǐng)你再舉一個(gè)這樣的例子說明C語言不是強(qiáng)類型語言。例如聯(lián)合體的類型檢查一般也不可能在編譯時(shí)完成，雖然下面例子是可靜態(tài)判斷類型錯(cuò)誤的。union U int u1; int *u2; u;int *p;u.u1 = 10;p = u.u2;*p = 0;65下面程序在SUN工作站上運(yùn)行時(shí)陷入死循環(huán)，試說明原因。如果將第8行的long *p改成short *p，并且將第23行l(wèi)ong k 改成