各章練習(xí)題(編譯原理)

1、第三章復(fù)習(xí)重點(diǎn)：1.文法與語(yǔ)言的對(duì)應(yīng)關(guān)系語(yǔ)言L(G)=L(G)文法G文法Gbn | n0BbB | bBBb | bbn | n0PbP |PPb |abn | n0SDBDaBbB | bSaBBBb | bbna | n0TPDDaPbP |TPaPPb |(ab)n | n0UEU | EEabUUab | abambn|m0,n0VABAaA | aBbB | bVaV | aBBbB | bambn|m0,n0WABAaA |BbB | bWaW | BBbB | banbn | n0XaXb | ab(akcd) nbn | k,n0XDXH | DHDAcdAaA |aHba2n

2、+1bn| n=0YaaYb |aYKYH | aKaaHb思路要點(diǎn)：注意結(jié)構(gòu)拆分技巧：如何將表示語(yǔ)言的通用字符串形式作適當(dāng)?shù)摹扒懈睢保坷阂阎Z(yǔ)言：L1 = axb2xcy | x, y = 0，給出此語(yǔ)言的文法，并證明此語(yǔ)言是上下文無(wú)關(guān)語(yǔ)言。提示：該題實(shí)際上要求為相應(yīng)語(yǔ)言設(shè)計(jì)上下文無(wú)關(guān)文法。一個(gè)文法設(shè)計(jì)好后，嚴(yán)格來(lái)說(shuō)應(yīng)當(dāng)證明此文法是否對(duì)應(yīng)于該語(yǔ)言。解：GS： S AB A e | aAbb B e | cB推導(dǎo)過(guò)程：S AB + axAb2xB /*使用A aAbb x次*/ axb2xB /*使用A e 一次*/ axb2xcxB /*使用B cB x次*/ axb2xcx /*使用B

3、e 一次*/舉一反三：已知語(yǔ)言L2 = axb2ycy | x, y = 0，給出此語(yǔ)言的文法，并證明此語(yǔ)言是上下文無(wú)關(guān)語(yǔ)言。解：GS： S AB A e | aA B e | bBcc練習(xí)：14：寫(xiě)出下列語(yǔ)言對(duì)應(yīng)的文法(1).anbnambm|n,m02. 1n0m0m0n|n,m0 3. 1n0m0m0n|n0,m04. anbmck|n,m,k0 G1: SAA G2: SABAaAb| AaAb| BaBb|G: S1S0 SA A0A1 A G: S1S0|A S1S0|0A1 A0A1|01 A0A1|2. 給出文法，證明文法符號(hào)串是否為文法的句型，若是句型，找出這個(gè)句型的所有短語(yǔ)

4、、直接短語(yǔ)、句柄。1. 令文法GE為： ZbMb Ma|(L LMa） 符號(hào)串b(Ma)b是否為該文法的一個(gè)句型，并證明。 若此符號(hào)串是句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)、句柄。1）（5分）證明：S= bMb=b(Lb=b(Ma)b 所以，符號(hào)串b(Ma)b是該文法的一個(gè)句型。（2）（5分）短語(yǔ): Ma)， (Ma)， b(Ma)b直接短語(yǔ): Ma) 句柄: Ma)練習(xí)： （10分）已知文法GT： TT*F | F ；FFP | P ； P(T) | i（1）用最右推導(dǎo)法證明：T*P(T*F) 是GT的一個(gè)句型；（2）畫(huà)出的語(yǔ)法樹(shù)；（3）寫(xiě)出的全部短語(yǔ)、直接短語(yǔ)和句柄。(1) T=T*F=

5、T*FP=T*F(T)= T*F(T*F) =T*P(T*F) 證畢。 (2) 如圖 （3）短語(yǔ)：T*P(T*F) ；P(T*F) ；(T*F) ；T*F ；P 直接短語(yǔ)：T*F ；P 句柄： P3. 證明一個(gè)文法是二義性文法。證明下述文法GS是二義的。 （5分） S-iSeS|iS|i解： S S i S e S i S i S i S e S可見(jiàn)，句型iises有兩種不同的語(yǔ)法樹(shù)，所以GS是二義的。練習(xí)：證明下述文法G：SaSbS|aS|d是二義性文法。解：一個(gè)文法，如果存在某個(gè)句子有不只一棵語(yǔ)法分析樹(shù)與之對(duì)應(yīng)，那么稱這個(gè)文法是二義性文法。SaSSabSdd句子aadbd有兩棵語(yǔ)法樹(shù)。如下

6、圖：dSSabSSad(1) (2)由此可知，SaSbS|aS|d定義的文法是二義性文法。第四章: 重點(diǎn)：1. NFADFA的確定化及DFA的最小化。2. 試寫(xiě)出描述語(yǔ)言L的正規(guī)式，構(gòu)造能識(shí)別該語(yǔ)言L等價(jià)的NFA，再確定化將下圖所示的NFA確定化，再最小化。(2010年出過(guò))X431baaeeaee2Y用子集法確定化如下表:編號(hào)IIaIbAAX,1,2,4B1,2,3,4C1,2,4,YBB1,2,3,4B 1,2,3,4C1,2,4,YCC1,2,4,YB 1,2,3,4C1,2,4,Y由于對(duì)于非終態(tài)的狀態(tài)A和B來(lái)說(shuō)，它們輸入a、b的下一個(gè)狀態(tài)都是一樣的，故狀態(tài)A和B可以合并，將合并后的狀態(tài)

7、重命名為A，而終態(tài)則重命名為B，則合并后的狀態(tài)轉(zhuǎn)換矩陣為： SabAABBAB由此可以得到最小化的DFA，如下圖所示： ABab練習(xí)1：給出接受字母表=a，b，語(yǔ)言為以b開(kāi)頭，以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)狀態(tài)的DFA。（2010年出過(guò)）答：依題意，以b開(kāi)頭，以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式可寫(xiě)為： b(a|b)*aa畫(huà)NFA，如下圖所示 X12baYa0ba 用子集法確定化如下表 IIaIbXA1 B1,2C1,2,YD-1,2C1,2,YD1,2,YD.1B1 B1 B1 BABCbaDababb（10分）將下圖的NFA確定化為DFA。（2011年重修卷A出過(guò)）答：用

8、子集法確定化如下表用子集法對(duì)所給圖的確定化IIaIb狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖第五章重點(diǎn)：1.LL(1)的判別要點(diǎn)：（1）計(jì)算FirstFollowSelect集，然后判斷是否是LL(1)文法。（2）如果是LL(1)文法，則構(gòu)造預(yù)測(cè)分析表。（消除左遞歸和左公共因子也要了解）例：（10分）已給文法 GS ： S PS S aPS| fS |e P qP P bP |e （1）該文法是否是LL（1）文法，并說(shuō)明理由。（2）給出該文法的預(yù)測(cè)分析表。答：（10 分）（1）Select（S P

9、S）=first(P)=qSelect(S aPS)=aSelect(S fS)=fSelect(S e)=follow(S)=follow(S)=#Select(P qP)=qSelect(P bP)=b Select（ P e）=follow(P)=follow(P)=first(S)- efollow(S)=a,f#=a,f,#Select(S aPS) Select(S fS) Select(S e)=Select(P bP) Select（ P e）=所以文法是LL（1）文法。 （7分）（2）預(yù)測(cè)分析表：（3分）a b f q#S PSSaPSfSePqPPebPee(15分)寫(xiě)出下

10、列文法中各候選式的FIRST集和各非終結(jié)符的FOLLOW集,構(gòu)造該文法的LL（1）分析表，并說(shuō)明它是否為L(zhǎng)L（1）文法。（2011年重修卷A出過(guò)） S aA|BAA cB|eB bB|e各候選式的FIRST集 (4分) FIRST（aA）=a FIRST（BA）= b，c，e FIRST（cB）=cFIRST（e）=e FIRST（bB）= b FIRST（e）=e各非終結(jié)符的FOLLOW集 (4分)FOLLOW(S)= # FOLLOW(A)= # FOLLOW(B)= c，#LL（1）分析表 (5分) a b c # S S aA S BA S BA S BA A A cB A e B B

11、 bB B e B e 說(shuō)明它是否為L(zhǎng)L（1）文法 (2分) 判斷1分，理由1分因?yàn)長(zhǎng)L（1）分析表無(wú)沖突，所以該文法是LL（1）文法。2. 設(shè)文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表解：(1)消除左遞，文法變?yōu)镚S：S | a | (T)TST | ST,ST |此文法無(wú)左公共左因子。(2)構(gòu)造相應(yīng)的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，F(xiàn)OLLOW(T)=FIRST(T)=, ，F(xiàn)OLLOW(F)=)(3)構(gòu)造

12、預(yù)測(cè)分析表：a(),#SSaSS(T)TTSTTSTTSTTTT,ST第七章重點(diǎn)：1. 識(shí)別活前綴的有限自動(dòng)機(jī)的構(gòu)造，判斷某個(gè)文法是否是LR(0)文法，或SLR（1）文法或LR（1）文法，若不是，請(qǐng)說(shuō)明理由，若是，構(gòu)造相應(yīng)的LR分析表。2. 查L(zhǎng)R分析表，進(jìn)行句子的識(shí)別。典型例題：文法GS及其LR分析表如下，請(qǐng)給出串baba#的LR分析過(guò)程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表狀態(tài)ACTIONGOTObDa#SBD0r3s3121acc2S43r24r6S5r665r4r46S7r17S88r5r5(注：答案格式為 步驟狀態(tài)棧符號(hào)棧

13、輸入串 ACTION GOTO)答案：步驟狀態(tài)符號(hào)輸入串 ACTION GOTO00#baba# r3 2102#Dbaba# S42024 #Db aba# S530245#Dbaba# r4 640246#DbBba# S7502467#DbBba# S86024678 #DbBba # r5 670246#DbB# r1 1801#S# acc2. （8分） 已知拓廣文法GS：SS SAS AaAb（1）試構(gòu)造以LR（1）項(xiàng)目集為狀態(tài)的識(shí)別活前綴的有窮自動(dòng)機(jī)；ASabbI2I1I5SAS，#I4Ab，a/b/#I3AaA，a/b/#AaA，a/b/#Ab，a/b/#I6I0SAabAaS

14、S，#（2）試判斷文法是否是LR(1)文法，并說(shuō)明理由。( 1 ) I0: I2: I6:SS，#SAS，#S，#AaA，a/b/#Ab，a/b/# SAS，#SAS，#S，#AaA，a/b/#Ab，a/b/# AaA，a/b/# （2）有窮自動(dòng)機(jī)所有的狀態(tài)都不含有“移進(jìn)歸約”、“歸約歸約”沖突，因而該文法是LR(1)文法。練習(xí)：. (20 分 ) 給定文法 GS ： S SaA|a A AbS|b (8 分 ) 請(qǐng)構(gòu)造該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識(shí)別規(guī)范句型活前綴的 DFA 。 (4 分 ) 請(qǐng)構(gòu)造該文法的 LR(0) 分析表。 (4 分 ) 什么是 LR(0) 文法？該文法是 L

15、R(0) 文法嗎？為什么？ (4 分 ) 什么是 SLR(1) 文法？該文法是 SLR(1) 文法嗎？為什么？答：拓廣文法 1 分 GS : S S S SaA S a A AbS A b 該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識(shí)別規(guī)范句型活前綴的 DFA ： 該文法的 LR(0) 分析表： 狀態(tài) ACTION GOTO a b # S A 0 S 2 1 1 S 3 acc 2 r 3 r 3 r 3 3 S 5 4 4 r 2 r 2 /S 6 r 2 5 r 5 r 5 r 5 6 S 2 7 7 r 4 /S 3 r 4 r 4 LR(0) 文法：該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的

16、識(shí)別規(guī)范句型活前綴的 DFA 中沒(méi)有沖突狀態(tài)。 該文法不是 LR(0) 文法 因?yàn)榇嬖跊_突狀態(tài)： I 4 和 I 7 SLR(1) 文法：該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識(shí)別規(guī)范句型活前綴的 DFA 中有沖突狀態(tài)，沖突可用 FOLLOW 集解決。 該文法不是 SLR(1) 文法。 因?yàn)?FOLLOW(S)=a,b,# ，所以無(wú)法解決沖突 。其它練習(xí)可以直接做書(shū)本上我們布置的作業(yè)！第八章：1.給出代碼，寫(xiě)成代碼對(duì)應(yīng)的四元式(三地址碼形式！)重點(diǎn)：（1）. 賦值語(yǔ)句 （2）. For語(yǔ)句 （3）.if then語(yǔ)句 （4）數(shù)組賦值 （5）.while語(yǔ)句例：寫(xiě)出下面語(yǔ)句經(jīng)語(yǔ)法制導(dǎo)翻譯后所生成

17、的四元式代碼序列。 （共10分） if xc do c:=c+1 else x:=x+5 （依次翻譯，再考慮回填！） 解：假設(shè)初始為100，則四元式代碼序列為 100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N109（10分）試完成下列語(yǔ)句翻譯的四元式序列。（2010年出過(guò)）while (AB) do if(CD) then X:=Y*Z else X:=Y+Z;(1) if AB goto (3)(2) goto (11)(3) _(4) goto (8)(5) _(6)X:=T1(7) _ (8)T2:=Y+

18、Z(9)X:=T2(10) _(11)答：(3) if CA-B-B,畫(huà)出程序運(yùn)行到第二個(gè)B過(guò)程的時(shí)刻，棧內(nèi)靜態(tài)鏈、動(dòng)態(tài)鏈的指示情況。Program Demo; Procedure A Procedure B Begin(*B*) If d then B else A; End(*B*) Begin(*A*) B; End(*A*) Begin(*Demo*) A End(*Demo *) 靜態(tài)鏈動(dòng)態(tài)鏈B的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈B的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈A的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈DEMO的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈B的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈B的過(guò)程活動(dòng)記錄靜態(tài)鏈動(dòng)態(tài)鏈A的過(guò)程活動(dòng)記錄靜態(tài)

19、鏈動(dòng)態(tài)鏈DEMO的過(guò)程活動(dòng)記錄練習(xí)1：考慮下面的程序：procedure p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B的值是什么?解：傳地址 A=4, B=16傳值 A=2, B=4第十一章 重點(diǎn)：1、基本塊劃分，并畫(huà)出程序流程圖2.根據(jù)程序流程圖，找出循環(huán)！典型習(xí)題：（8分）將下面程序劃分為基本塊，并畫(huà)出其基本塊程序流圖。(2009年出過(guò))(1) if ab goto (3)(2) halt(3) if cd g

20、oto (5)(4) goto (8)(5) t1:=y+z(6) x :=t1(7) goto (1)(8) t2:=y-z(9) x :=t2(10) goto (1)答: 2. 對(duì)以下給定流圖， （2010年出過(guò)）（1）求出流圖中B3、B4和B5的必經(jīng)結(jié)點(diǎn)集D(n)；（2）求出流圖中的回邊及其對(duì)應(yīng)的循環(huán)。B1B2B3B4B5答：（1）B3的必經(jīng)結(jié)點(diǎn)集是B1, B2 , B3。B4的必經(jīng)結(jié)點(diǎn)集是B1, B2, B4。B5的必經(jīng)結(jié)點(diǎn)集是B1, B2, B4, B5。（2）回邊是B4B2，對(duì)應(yīng)的循環(huán)是 B2, B3, B4。其它的第二章、第九章、第十二章均直接考PL/0的內(nèi)容，所以代碼閱讀很重要重點(diǎn)：1. PL/0符號(hào)表的生成2. PL/0某一個(gè)語(yǔ)法成分的程序填空。典型習(xí)題：練習(xí)1：8分）對(duì)PL/0語(yǔ)言擴(kuò)充單詞: （2009年出過(guò)） + +=請(qǐng)完成下列識(shí)別單詞+，+和+=（設(shè)單詞內(nèi)碼分別為PLUS，PLUSPLUS和PLUSBECOMES）的詞法分析程序段：if ( CH=+ ) if ( ) SYM=PLUSBECOMES; GetCh(); else if ( CH=+