1、編譯原理課后習(xí)題答案第一章 第4題 對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段（詞法分析、語(yǔ)法分析、語(yǔ)義分析、 代碼生成）報(bào)告的。 （1）else沒(méi)有匹配的if （2）數(shù)組下標(biāo)越界 （3）使用的函數(shù)沒(méi)有定義 （4）在數(shù)中出現(xiàn)非數(shù)字字符 答案： （1）語(yǔ)法分析 （2）語(yǔ)義分析 （3）語(yǔ)法分析 （4）詞法分析 編譯原理課后習(xí)題答案第三章 第1題 文法G(A,B,S,a,b,c,P,S)其中P為： SAc|aB Aab Bbc 寫(xiě)出L(GS)的全部元素。 答案： L(GS)=abc 第2題 文法GN為： ND|ND D0|1|2|3|4|5|6|7|8|9 GN的語(yǔ)言是什么？ 答案: GN的語(yǔ)言是V

2、+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD.=NDDDD.D=D.D 或者：允許0開(kāi)頭的非負(fù)整數(shù)？ 第題 為只包含數(shù)字、加號(hào)和減號(hào)的表達(dá)式，例如9-25，3-1，等構(gòu)造一個(gè)文法。 答案： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7|8|9 第4題 已知文法GZ： ZaZb|ab 寫(xiě)出L(GZ)的全部元素。 答案： Z=aZb=aaZbb=aaa.Z.bbb=aaa.ab.bbb L(GZ)=anbn|n=1 第5題 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求： (1)允許0打頭； (2)不允許0打頭。 答案： (1)允許0開(kāi)頭的偶正整數(shù)集合的文法 E

3、NT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不允許0開(kāi)頭的偶正整數(shù)集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第6題 已知文法G： := :=* :=（）i 試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹(shù)。 （）i+(i+i) （）i+i*i 答案： + + i i i （) (5) = = =（） =（） =（） =（i） =（i） =（i） =（ii） =（ii） =（ii） =i（ii） + * i i i (6) = =* =*i =*i =i*i =i*i =i*i =ii*i 第7題 證明下述文法G表達(dá)式是二義

4、的。 表達(dá)式=a|(表達(dá)式)|表達(dá)式運(yùn)算符表達(dá)式 運(yùn)算符=+|-|*|/ 答案： 可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo): 最右推導(dǎo)1表達(dá)式表達(dá)式運(yùn)算符表達(dá)式 表達(dá)式運(yùn)算符a 表達(dá)式*a 表達(dá)式運(yùn)算符表達(dá)式*a 表達(dá)式運(yùn)算符a*a 表達(dá)式+a*a a+a*a 最右推導(dǎo)2表達(dá)式表達(dá)式運(yùn)算符表達(dá)式 表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符表達(dá)式 表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符a 表達(dá)式運(yùn)算符表達(dá)式*a 表達(dá)式運(yùn)算符a*a 表達(dá)式+a*a a+a*a 第8題 文法GS為： SAc|aB Aab Bbc 該文法是否為二義的？為什么？ 答案： 對(duì)于串a(chǎn)bc (1)S=Ac=abc(2)S=aB=abc 即存在兩不同的最右推

5、導(dǎo)。所以，該文法是二義的。 或者： 對(duì)輸入字符串a(chǎn)bc，能構(gòu)造兩棵不同的語(yǔ)法樹(shù)，所以它是二義的。 S aB bc S Ac ab 第9題 考慮下面上下文無(wú)關(guān)文法： SSS*|SS+|a (1)表明通過(guò)此文法如何生成串a(chǎn)a+a*，并為該串構(gòu)造語(yǔ)法樹(shù)。 S SS* SS+a aa (2)GS的語(yǔ)言是什么？ 答案： (1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a* (2)該文法生成的語(yǔ)言是：*和+的后綴表達(dá)式，即逆波蘭式。 第10題 文法SS(S)S| (1)生成的語(yǔ)言是什么？ (2)該文法是二義的嗎？說(shuō)明理由。 答案： （）嵌套的括號(hào) （）

6、是二義的，因?yàn)閷?duì)于（）（）可以構(gòu)造兩棵不同的語(yǔ)法樹(shù)。 第11題 令文法GE為： ET|E+T|E-T TF|T*F|T/F F(E)|i 證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。 答案： 此句型對(duì)應(yīng)語(yǔ)法樹(shù)如右，故為此文法一個(gè)句型。 或者：因?yàn)榇嬖谕茖?dǎo)序列:E=E+T=E+T*F，所 以E+T*F句型 此句型相對(duì)于E的短語(yǔ)有:E+T*F；相對(duì)于T的短語(yǔ) 有T*F 直接短語(yǔ)為：T*F 句柄為：T*F 第13題 一個(gè)上下文無(wú)關(guān)文法生成句子abbaa的推導(dǎo)樹(shù)如下： (1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。 (2)該文法的產(chǎn)生式集合P可能有哪些元素？ (3)找出該句子的所

7、有短語(yǔ)、直接短語(yǔ)、句柄。 B a S ABS a SBA bba 答案： (1)串a(chǎn)bbaa最左推導(dǎo): S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推導(dǎo)： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)產(chǎn)生式有：SABS|Aa|AaBSBB|b 可能元素有：aaababbaaaaabbaa (3)該句子的短語(yǔ)有： a是相對(duì)A的短語(yǔ)是相對(duì)S的短語(yǔ) b是相對(duì)B的短語(yǔ) bb是相對(duì)B的短語(yǔ) aa是相對(duì)S的短語(yǔ) abbaa是相對(duì)S的短語(yǔ) 直接短語(yǔ)有：ab 句柄是：a 編譯原理課后習(xí)題答案第四章 第1題

8、 構(gòu)造下列正規(guī)式相應(yīng)的DFA. （）1(0|1)*101 （）(1010*|1(010)*1）*0 （）a(a|b)*|ab*a)*b （）b(ab)*|bb)*ab 答案： (1)先構(gòu)造NFA： 用子集法將NFA確定化 .01 X.A AAAB ABACAB ACAABY ABYACAB 除X，A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D，因?yàn)镈含有Y（NFA 的終態(tài)），所以D為終態(tài)。 .01 X.A AAB BCB CAD DCB DFA的狀態(tài)圖：: (2)先構(gòu)造NFA： X1A B 1C0D1E 0 F1G0H1I0J1K L 0 Y 用子集法將NFA確定化 01 XX T0

9、=XA AABFL T1=ABFLYCG YY CGCGJ T2=Y T3=CGJDHK DHDH KABFKL T4=DHEI EIABEFIL T5=ABFKLYCG T6=ABEFILEJYCG EJYABEFGJLY T7=ABEFGJLYEHYCGK EHYABEFHLY CGKABCFGJKL T8=ABEFHLYEYCGI EYABEFLY CGICGJI T9=ABCFGJKLDHYCGK DHYDHY T10=ABEFLYEYCG T11=CGJIDHJK DHJDHJ T12=DHYEI T13=DHJEIK EIKABEFIKL T14=ABEFIKLEJYCG 將T0、

10、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分別用0、 1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因?yàn)?、7、8、10、12中含有Y， 所以它們都為終態(tài)。 01 01 123 2 345 46 523 673 789 81011 9129 10103 11135 126 1314 1473 010 12 12 7 108 3 4 5 6 9 111314 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 01 0 1 0 1 (3)先構(gòu)造NFA： 先構(gòu)造NFA： XaA B a,b DaEaF

11、C Y b b 用子集法將NFA確定化 ab XX T0=XA AABCD T1=ABCDBEBY BEABCDE BYABCDY T2=ABCDEBEFBEY BEFABCDEF BEYABCDEY T3=ABCDYBEBY T4=ABCDEFBEFBEY T5=ABCDEYBEFBEY 將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因?yàn)?、5中含有Y， 所以它們都為終態(tài)。 ab 01 123 245 323 445 545 0a1b3 2 a 5 a4 b a b a b a b (4)先構(gòu)造NFA： XA b B a FbGbH E Y a CDb Ib

12、 用子集法將NFA確定化： ab XX T0=XA AABDEF T1=ABDEFCIG CICI GG T2=CIDY DYABDEFY T3=GH HABEFH T4=ABDEFYCIG T5=ABEFHCIG 將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因?yàn)?中含有Y， 所以它為終態(tài)。 ab 01 123 24 35 423 523 DFA的狀態(tài)圖： 0b1b 2 a 4 5 3 b b a b a b 第題 已知NFA（x,y,z,0,1,M,x,z），其中：M(x,0)=z，M(y,0)=x,y，,M(z,0)=x,z， M(x,1)=x，M(y,

13、1)=，M(z,1)=y，構(gòu)造相應(yīng)的DFA。 答案： 先構(gòu)造其矩陣 01 xzx yx,y zx,zy 用子集法將NFA確定化： 01 xzx zxzy xzxzxy yxy xyxyzx xyzxyzxy 將x、z、xz、y、xy、xyz重新命名，分別用A、B、C、D、E、F表示。因?yàn)锽、C、F 中含有z，所以它為終態(tài)。 01 ABA BCD CCE DE EFA FFE DFA的狀態(tài)圖： A 01 0 F E D 0 B 1 0 1 0 1 0 1 C 第3題 將下圖確定化： 答案： 用子集法將NFA確定化： .01 SVQQU VQVZQU QUVQUZ VZZZ VZ. QUZVZQU

14、Z ZZZ 重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。 .01 SAB ACB BDE CFF DF. ECE FFF DFA的狀態(tài)圖： 第4題 將下圖的（a）和（b）分別確定化和最小化： 答案： 初始分劃得 0：終態(tài)組0，非終態(tài)組1,2,3,4,5 對(duì)非終態(tài)組進(jìn)行審查： 1,2,3,4,5a0,1,3,5 而0,1,3,5既不屬于0，也不屬于1,2,3,4,5 4a0，所以得到新分劃 1：0，4，1,2,3,5 對(duì)1,2,3,5進(jìn)行審查： 1,5b4 2,3b1,2,3,5，故得到新分劃 2：0，4，1,5，2,3 1,5a1,5 2,3a1,3，故狀態(tài)2

15、和狀態(tài)3不等價(jià)，得到新分劃 3：0，2，3，4，1,5 這是最后分劃了 最小DFA： 第5題 構(gòu)造一個(gè)DFA，它接收=0,1上所有滿(mǎn)足如下條件的字符串：每個(gè)1都有0直接跟在 右邊。并給出該語(yǔ)言的正規(guī)式。 答案： 按題意相應(yīng)的正規(guī)表達(dá)式是(0*10)*0*，或0*(0|10)*0*構(gòu)造相應(yīng)的DFA，首先構(gòu)造NFA為 用子集法確定化： II0I1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 2 重新命名狀態(tài)集： S01 1 2 3 4 2 2 4 4 3 3 3 DFA的狀態(tài)圖： 可將該DFA最小化： 終態(tài)組為1,2,4，非終

16、態(tài)組為3，1,2,401,2,4，1,2,413，所以1,2,4為等價(jià)狀 態(tài)，可合并。 第題 設(shè)無(wú)符號(hào)數(shù)的正規(guī)式為： =dd*|dd*.dd*|.dd*|dd*10(s|)dd* |10(s|)dd*|.dd*10(s|)dd* |dd*.dd*10(s|)dd* 化簡(jiǎn)，畫(huà)出的DFA，其中d=0,1,2,9，s=， 答案： 先構(gòu)造NFA： X d .B d FG d H 10 d A C 10 d D s Ed Y d s d 用子集法將NFA確定化： s10d XXA T0=XABFA BB FFG AA T1=BC CC T2=FGGH GG HH T3=ABFA T4=CDC DDE T

17、5=GH T6=HH T7=DEEY EE YY T8=EY T9=YY 將XA、B、FG、A、C、G、H、DE、E、Y重新命名，分別用0、1、2、3、4、5、6、 7、8、9表示。終態(tài)有0、3、4、6、9。 s10d 0123 14 256 3123 474 56 66 789 89 99 DFA的狀態(tài)圖： d 6 25 d 3 d d 47 8 9 0 1 10 d s 10 10 d d s d d d 第7題 給文法GS： SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA EaB|bF FbD|aE|b 構(gòu)造相應(yīng)的最小的DFA。 答案： 先構(gòu)造其N(xiāo)FA： S

18、 a A a Z Q b B D a E b F b b a b a a b bb b a b 用子集法將NFA確定化： ab SAQ AABZ QQDZ BZQD DZAB DAB BQD 將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因?yàn)?、 4中含有z，所以它們?yōu)榻K態(tài)。 ab 012 113 224 325 416 516 625 DFA的狀態(tài)圖： 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b 令P0（0,1,2,5,6,3,4）用b進(jìn)行分割： P1（0,5,6,1,2,3,4）再用b進(jìn)行分割： P2（0,5,6,1

19、,2,3,4）再用a、b進(jìn)行分割，仍不變。 再令為A，1，2為B，3，4為C，5，6為D。 最小化為： A a,b DC a a B b a b b 第題 給出下述文法所對(duì)應(yīng)的正規(guī)式： S0A|1B A1S|1 B0S|0 答案： 解方程組S的解： S=0A|1B A=1S|1 B=0S|0 將A、B產(chǎn)生式的右部代入S中 S=01S|01|10S|10=（01|10）S|（01|10） 所以：S=(01|10)*(01|10) 第9題 將下圖的DFA最小化，并用正規(guī)式描述它所識(shí)別的語(yǔ)言。 1 a 2 6 c 3 c b 5 47 b b ab b b d d a 答案： 令P0（1,2,3,4

20、,5,6,7）用b進(jìn)行分割： P1（1,2,3,4,5,6,7）再用a、b、c、d進(jìn)行分割，仍不變。 再令1,2為A，3，4為B，5為C，6，7為D。 最小化為： A a CD b d B b c a b r=b*a(c|da)*bb*=b*a(c|da)*b+ 編譯原理課后習(xí)題答案第五章 第1題 對(duì)文法GS Sa|(T) TT,S|S (1)給出(a,(a,a)和(a,a),(a),a)的最左推導(dǎo)。 (2)對(duì)文法G，進(jìn)行改寫(xiě)，然后對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序。 (3)經(jīng)改寫(xiě)后的文法是否是LL(1)的?給出它的預(yù)測(cè)分析表。 (4)給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G的

21、句子。 答案： (1)對(duì)(a,(a,a)的最左推導(dǎo)為： S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) 對(duì)(a,a),(a),a)的最左推導(dǎo)為： S(T) (T,S) (S,S) (T),S) (T,S),S) (T,S,S),S) (S,S,S),S) (T),S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),(T),S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a

22、) (2)改寫(xiě)文法為： 0)Sa 1)S 2)S(T) 3)TSN 4)N,SN 5)N 非終結(jié)符FIRST集FOLLOW集 Sa,(#,) Ta,(). N,.). 對(duì)左部為N的產(chǎn)生式可知： FIRST（,SN）=， FIRST（）= FOLLOW（N）=) 由于SELECT(N,SN)SELECT(N)=，)= 所以文法是LL(1)的。 預(yù)測(cè)分析表（PredictingAnalysisTable） a(),# Sa(T) TSNSNSN N,SN 也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。 (3)對(duì)輸入串（a,a）#的分析過(guò)程為： 棧（STACK） 當(dāng)前輸入符 （CUR_CHAR

23、） 剩余輸入符 （INOUT_STRING） 所用產(chǎn)生式 （OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a a , , a a ) ) # a,a)#. a,a)#. ,a)#. ,a)#. ,a)#. a)#. a)#. )#. )#. #. #. S(T) . TSN Sa . N,SN . Sa . N 可見(jiàn)輸入串（a,a）#是文法的句子。 第3題 已知文法GS： SMH|a HLSo| KdML| LeHf MK|bLM 判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。 答案： 文法展

24、開(kāi)為： 0）SMH 1）Sa 2）HLSo 3）H 4）KdML 5）K 6）LeHf 7）MK 8）MbLM 非終結(jié)符FIRST集FOLLOW集 Sa,d,b,e#,o. Md,b.e,#,o. H,e.#,f,o. Le.a,d,b,e,o,# Kd,.e,#,o. 對(duì)相同左部的產(chǎn)生式可知： SELECT(SMH)SELECT(Sa)=d,b,e，#,oa= SELECT(HLSo)SELECT(H)=e#,f,o= SELECT(KdML)SELECT(K)=de,#,o= SELECT(MK)SELECT(MbLM)=d，e,#,ob= 所以文法是LL(1)的。 預(yù)測(cè)分析表： aode

25、fb# SaMHMHMHMHMH MKKKbLMK HLSo LeHf KdML 由預(yù)測(cè)分析表中無(wú)多重入口也可判定文法是LL(1)的。 第7題 對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(1)文法?試對(duì)下面 文法進(jìn)行改寫(xiě)，并對(duì)改寫(xiě)后的文法進(jìn)行判斷。 ()AbaB| BAbb|a (2)AaABe|a BBb|d (3)SAa|b ASB Bab 答案： ()先改寫(xiě)文法為： 0)AbaB 1)A 2)BbaBbb 3)Bbb 4)Ba 再改寫(xiě)文法為： 0)AbaB 1)A 2)BbN 3)Ba 4)NaBbb 5)Nb FIRSTFOLLOW Ab# Bb,a#,b Nb,a#,b 預(yù)測(cè)分析表： ab# AbaB BabN NaBbb