1、編譯原理復習題集1名詞解釋短語句柄文法上下文無關文法LL（1）文法LR（1）文法語法分析無環路有向圖(DAG)后綴式語法制導翻譯遍局部優化詞法分析語法分析語義分析源語言源程序目標語言中間語言（中間表示）2簡答題(1) 編譯程序和高級語言有什么區別? (2) 編譯程序的工作分為那幾個階段? (3) 簡述自下而上的分析方法。(4) 目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？(5) 何謂優化？按所涉及的程序范圍可分為哪幾級優化？ (6) 簡述代碼優化的目的和意義。3敘述下面的正規式描述的語言，并畫出接受該語言的最簡DFA的狀態轉換圖。( 1 | 01 )* 0*4Pascal語言無符

2、號數的正規定義如下：num ® digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示數字，用狀態轉換圖表示接受無符號數的確定有限自動機。5畫出Pascal中實數(不帶正負號，可帶指數部分)的狀態轉換圖。 6用狀態轉換圖表示接收(a|b)*aa的確定的有限自動機。7處于/* 和 */之間的串構成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態轉換圖。8某操作系統下合法的文件名為device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，

3、長度不限，但至少為1，畫出識別這種文件名的確定有限自動機。9構造一個DFA，它接受å=0, 1上0和1的個數都是偶數的字符串。10設有非確定的有自限動機 NFA M=(A，B，C，0，1，A，C)，其中： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。請畫出狀態轉換距陣和狀態轉換圖。11設 LÍ a,b,c* 是滿足下述條件的符號串構成的語言： (1)若出現 a ，則其后至少緊跟兩個 c ； (2)若出現 b ，其后至少緊跟一個 c 。 試構造識別 L 的最小化的 DFA ，并給出描述 L 的正規表達式。 12寫出字母表 = a, b上語言L = w

4、| w的最后兩個字母是aa或bb的正規式，并畫出接受該語言的最簡DFA。13有窮自動機M接受字母表0,1上所有滿足下述條件的串：串中至少包含兩個連續的0或兩個連續的1。請寫出與M等價的正規式。14有正規式 b*abb*(abb*)* ，(1) 構造該正規式所對應的 NFA(畫出狀態轉換圖) 。(2) 將所求的 NFA 確定化(畫出確定化的狀態轉換圖)。 (3) 將所求的 NFA 最小化. (畫出最小化后的狀態轉換圖)。15求出下列文法所產生語言對應的正規式. SàbS|aA AàaA|bB BàaA|bC|b CàbS|aA 16給出與下圖的NFA等價的

5、正規式。S0S1S3S217把下面的NFA確定化。123456101110118下面兩個文法中哪一個不是LR（1）文法？對非LR（1）的那個文法。給出那個有移進歸約沖突的規范的LR（1）項目集。S ® aAcS ® aAcA ® bbA | bA ® bAb | b0123aababba,b19將下面的DFA化成最簡形式。20為語言L w | w Î (a | b)*并且在w的任何前綴中，a的個數不少于b的個數寫一個LR（1）文法，不準超過6個產生式。21寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。 22考查文法G(s): S( T )

6、 | a + S | aTT, S | S(1) 消除文法的左遞歸；(2) 提取公共左因子；(3) 對每個非終結符，寫出不帶回朔的遞歸子程序。23設文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和回溯； (2)計算每個非終結符的FIRST和FOLLOW； (3)構造預測分析表。 24消除下列文法的左遞歸. SàSaP|Sf|P PàQbP|Q QàcSd|e 25已知文法 G ：AàaABe|a BàBb|d 給出與上述文法等價的 LL(1)文法 G'。26已知文法GA：A aAB | a B Bb | d（1）構

7、造與GA等價的LL(1)文法；（2）構造GA的預測分析表。27程序的文法如下：P ® DD ® D ; D | id : T | proc id ; D ; S（1）寫一個語法制導定義，打印該程序一共聲明了多少個id。（2）寫一個翻譯方案，打印該程序每個變量id的嵌套深度。28構造下面文法的LL（1）分析表。D ® TLT ® int | realL ® id RR ® , id R | e29考慮下文法：D à TVT à int floatV à id , V | ida. 在該文法中提取左公因子。b

8、. 為所得文法的非終結符構造First和Follow集合。c. 說明所得的文法是LL(1)文法。d. 為所得文法構造LL(1)分析表。e. 假設有輸入串int x , y , z 寫出相應LL(1)分析程序的動作。 30說明如下文法是否是LL（1）文法，若不是，將其轉換為LL（1）文法。最后給出該文法的LL（1）分析表。 A à B e B à B b | a 31設有文法：Pbegin XYendXXd;Xd;YY;sYs(1) 該文法含有左遞歸嗎？若有，消除它。(2) 改造后的文法是LL(1)文法嗎？若是，給出其預測分析表。(3) 寫出句子 begin d；s end的

9、分析過程。32已給文法 GS ： S SaP | Sf | P P qbP | q 將 GS 改造成 LL （ 1 ）文法，并給出 LL （ 1 ）分析表。 33設文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯； (2) 計算每個非終結符的FIRST和FOLLOW； (3) 構造預測分析表。 34給定文法 GS ： S Aa|dAb|Bb|dBa A c B c 構造文法 GS 的 LR （ 1 ）分析表。 35已知文法G(S) Sa|(T) TT，S|S 寫出句子(a，a)，a)的規范歸約過程及每一步的句柄。 36已知文法G(E) ET|ET TF|T *F F

10、(E)|i 給出句型(T *Fi)的最右推導及畫出語法樹； 37說明下面的文法不是SLR(1)文法，并重寫一個等價的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

11、.aM ® d .bd因為a是M的后繼符號之一，因此在上面最右邊一個項目集中有移進-歸約沖突。等價的SLR(1)文法是S ® d a | b d c | d c | b d a38在PASCAL語言中，簡單類型的變量的聲明例舉如下：m, n : integerp, q, r : real為這樣的聲明寫一個LR（1）文法（為簡單起見，變量標識符都用id表示），并根據你的文法寫一個語法制導定義（或叫做為你的文法加上語義動作），它將變量的類型填入符號表。39一個非LR（1）的文法如下：L ® MLb | aM ® e請給出所有有移進歸約沖突的LR（1）項目集，

12、以說明該文法確實不是LR（1）的。40若有文法 G(S)的產生式如下：SàL=R SàR Là*R Lài RàL,構造識別所有項目集規范族的 DFA.，判斷該文法是否是 SLR(1)文法，說明理由。 41現有句型g ba lb 和產生式A® ba，分別指出LL（1）方法和LR（1）方法在掃描到此句型的什么位置決定用此產生式？42為下面的算術表達式文法寫一個語法制導的翻譯方案，它將每個子表達式E的符號（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數都不為零，這樣就不用擔心零的符號

13、。E ® E *E | +E | -E | unsigned_integer43一個文法如下： S ® ( S ) S ® a 請給出該文法中對活前綴(有效的LR (1)項目。44為下面文法添加語義規則（或叫動作子程序），輸出S¢產生的二進制數的值，如輸入是101時，輸出5。S¢ ® SS ® S B | BB ® 0 | 145寫出表達式(ab*c)/(ab)d的逆波蘭表示及三元式序列。 46把表達式- (a+b)*(c+d)+(a+b+c)翻譯成三地址碼序列。47設布爾表達式的文法為 E E1E2 E E1E2

14、 E i 假定它們將用于條件控制語句中，請 (1)改寫文法，使之適合進行語法制導翻譯； (2)寫出改寫后的每個產生式的語義動作。 48將語句 if (A<X Ù B>0) while ( C>0 ) C=C+D; 翻譯成三地址碼序列。49設有基本塊如下：T1=S+RT2= 3T3= 12/T2T4=S/RA=T1-T4T5=S+RB=T5T6=T5*T3B=T6(1) 畫出中間代碼的流圖；(2) 設A、B是出基本塊后的活躍變量，請給出優化后的三地址碼序列。50設已構造出文法G(S)：(1) S ® BB (2) B ® aB (3) B®

15、; b的LR分析表如下ACTIONGOTO狀態ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab，請給出LR分析過程(即按照步驟給出狀態，符號，輸入串的變化過程)。51給出活動記錄空間結構。并給出各部分的存儲對象。52將下面程序段翻譯成四元式序列。while( A<CB<D )if ( A=1) C=C+1 ; else while ( A<D ) A=A+2; 53有一語法制導翻譯如下所示：S bAb print(“1”) A (B print(“2”) A a print(“3”) B Aa) p

16、rint(“4”) 若對輸入序列b(aa)a)a)b 進行自底向上分析，請寫出輸出序列。54畫出IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1)的翻譯方案圖。55下面是一個C語言程序：main()long i;long a04;long j;i = 4; j = 8;printf(“%d, %dn”, sizeof(a), a00);雖然出現long a04這樣的聲明，在X86/Linux機器上該程序還是能通過編譯并生成目標代碼。請回答下面兩個問題：（1）sizeof(a)的值是多少，請說明理由。（2）a00的值是多少，請說明理由。（1）按照數組size的計算公式

17、，sizeof(a)的值一定是0。（2）a00的值是4。雖然a的size是0，但它仍然有起始地址，并且a00的地址等于a的起始地址。由于X86/Linux機器上，活動記錄棧向低地址方向增長，另外由于低地址放低位字節，因此a00的地址和i的地址一致，其值和i的值一樣，等于4。56將下面的條件語句表示成三地址碼序列： if ( a>b ) 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

18、 goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9（1）在該代碼中用水平的橫線將代碼分成基本塊，并給每個基本塊一個序號。（2）畫出該代碼的控制流圖，每個基本塊就用（1）的序號表示。（3）若有循環的話，列出構成每個循環的結點。（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

19、L1（7）L5:h := 9（8）（3）結點5、7和3構成一個循環，其中5是入口結點。58一個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工作站上

20、的運行結果如下：Addresses of i1,i2,i3 = 35777773634,35777773640,35777773644Addresses of j1,j2,j3 = 35777773524,35777773520,35777773514從上面的結果可以看出，func 函數的3個形式參數的地址依次升高，而3個局部變量的地址依次降低。試說明為什么會有這個區別。由于實參表達式是反序進入活動記錄，而局部變量是順序在活動記錄中分配。59一個C語言程序如下：void fun(struct int x; double r; val) main()struct int x; double r;

21、 val;fun(val);該程序在X86/Linux機器上的用cc命令編譯時，報告的錯誤信息如下：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 f

22、un 請問，報告最后一行的錯誤的原因是什么？如何修改程序，使得編譯時不再出現這個錯誤信息。60一個C語言程序如下：main()func();printf("Return from funcn");func()char s4;strcpy(s,"12345678");printf("%sn",s);該程序在PC機linux操作系統上的運行結果如下：12345678Segmentation fault (core dumped)試分析為什么會出現這樣的運行錯誤。61一個C語言函數如下：func(i)long i;long j;j=i-1;

23、func(j);該函數在PC機linux操作系統上編譯生成的匯編代碼如下：.file"stack.c"gcc2_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,

24、Lfe1-_func試畫出該函數的一個活動記錄的內容，包括活動記錄的每個單元存放什么東西、執行movl 8(%ebp),%edx指令時棧頂指針所指的的位置、與活動記錄有關的另一個指針所指的位置和地址增長方向。62一個C語言的函數如下：func(c,l)char c;long l; func(c,l);在X86/Linux機器上編譯生成的匯編代碼如下：.file"parameter.c".version"01.01"gcc2_compiled.:.text.align 4.globl func.type func,functionfunc:pushl %e

25、bp 將老的基地址指針壓棧movl %esp,%ebp 將當前棧頂指針作為基地址指針subl $4,%esp 分配空間movl 8(%ebp),%eaxmovb %al,-1(%ebp)movl 12(%ebp),%eaxpushl %eaxmovsbl -1(%ebp),%eaxpushl %eaxcall funcaddl $8,%esp.L1:leave 和下一條指令一起完成恢復老的基地址指針，將棧頂ret 指針恢復到調用前參數壓棧后的位置，并返回調用者.Lfe1:.size func,.Lfe1-func.ident"GCC: (GNU) egcs-2.91.66 19990

26、314/Linux (egcs-1.1.2 release)"(a) 請指出對應源程序第5行的函數調用func(c,l)的匯編指令是哪幾條。(b) 請說明字符型參數和長整型參數在參數傳遞和存儲分配方面有什么區別。（小于長整型size的整型參數的處理方式和字符型參數的處理方式是一樣的。）63一個C語言程序及其在某種機器linux操作系統上的編譯結果如下。根據所生成的匯編程序來解釋程序中四個變量的作用域、生存期和置初值方式等方面的區別。static long aa = 10;short bb = 20;func() static long cc = 30; short dd = 40;編

27、譯生成的匯編代碼如下：.file"static.c".version"01.01"gcc2_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,%eb

28、psubl $4,%espmovw $40,-2(%ebp).L1:leaveret.Lfe1:.size func,.Lfe1-func.ident"GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"aa是靜態外部變量，而bb是外部變量，它們都分配在靜態數據區（由.data偽指令開始），但是bb由偽指令.globl指明為全局的，用來解決其它文件中對bb的外部引用，而aa只能由本文件引用。cc是靜態局部變量，同aa和bb一樣，它的生存期是整個程序并分配在靜態數據區。由于cc在源程序中的作用域是函數func

29、的體，而在目標文件中，它的作用域至少已是整個文件了，為避免同源文件中外部變量和其它函數的靜態局部變量的名字沖突，所以要對它進行改名，成了cc.2。由于cc不是全局的，因此cc.2前面沒有偽指令.globl。dd是自動變量，其作用域是函數func的體，其生存期是該函數激活期間，因此它分配在棧區，并且置初值是用運行時的賦值來實現。64 C語言是一種類型語言，但它不是強類型語言，因為編譯時的類型檢查不能保證所接受的程序沒有運行時的類型錯誤。例如，編譯時的類型檢查一般不能保證運行時沒有數組越界。請你再舉一個這樣的例子說明C語言不是強類型語言。例如聯合體的類型檢查一般也不可能在編譯時完成，雖然下面例子是可靜態判斷類型錯誤的。union U int u1; int *u2; u;int *p;u.u1 = 10;p = u.u2;*p = 0;65下面程序在SU