編譯原理及實(shí)現(xiàn)課后習(xí)題答案孫悅紅

1、2.1 設(shè)字母表a=a，符號(hào)串x=aaa，寫出下列符號(hào)串及其長度：x0,xx,x5以及a+和a*.x0=(aaa)0= | x0|=0 xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15a+ =a1a2 . a n=a,aa,aaa,aaaa,aaaaa a* = a0 a1 a2 . a n =,a,aa,aaa,aaaa,aaaaa 2.2 令=a，b，c，又令x=abc，y=b，z=aab，寫出如下符號(hào)串及它們的長度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcb

2、abcb | (xy)3 |=122.3 設(shè)有文法gs：s=ss*|ss+|a，寫出符號(hào)串a(chǎn)a+a*規(guī)范推導(dǎo)，并構(gòu)造語法樹。s => ss* => sa* => ss+a* => sa+a* => aa+a*sss*ss+aaa2.4 已知文法gz：z=u0v1 、 u=z11 、 v=z00 ,請寫出全部由此文法描述的只含有四個(gè)符號(hào)的句子。z=>u0=>z10=>u010=>1010z=>u0=>z10=>v110=>0110z=>v1=>z01=>u001=>1001z=>v1=&g

3、t;z01=>v101=>01012.5 已知文法gs： s=ab a=aa b=bbcbc , 寫出該文法描述的語言。a=aa描述的語言: an|n>=0b=bbcbc描述的語言：bncn|n>=1l(gs)=anbmcm|n>=0,m>=12.6 已知文法e=te+te-t 、 t=ft*ft/f 、 f=(e)i，寫出該文法的開始符號(hào)、終結(jié)符號(hào)集合vt、非終結(jié)符號(hào)集合vn。開始符號(hào)：evt=+, - , * , / ,（ , ）, ivn=e , f , tete+fte+ift*t2.7 對2.6題的文法，寫出句型t+t*f+i的短語、簡單短語以及句

4、柄。短語：t+t*f+i t+t*f i i t t*f簡單短語：i t*f t句柄：t2.8 設(shè)有文法gs：s=s*s|s+s|(s)|a，該文法是二義性文法嗎？sss*s+saaasss+s*saaa根據(jù)所給文法推導(dǎo)出句子a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。2.9 寫一文法，使其語言是奇正整數(shù)集合。 a:=1|3|5|7|9|nan:=0|1|2|3|4|5|6|7|8|92.10給出語言anbm|n,m1的文法。 gs: s:=ab a:=aa|a b:=bb|b3.1 有正則文法gz：z:=ua|vb，u:=zb|b，v:=za|a ，畫出該文法的狀態(tài)圖，并檢查

5、句子abba是否合法。解：該文法的狀態(tài)圖如下：suvzaaabbb句子abba合法。3.2 狀態(tài)圖如圖3.35所示，s為開始狀態(tài)，z為終止?fàn)顟B(tài)。寫出相應(yīng)的正則文法以及v，vn和vt。sazabab圖3-35狀態(tài)圖 解： 左線性文法gz: 右線性文法gs:z:=ab|bs:=aa|b a:=aa|aa:=aa|bv=z,a,a,bv=s,a,a,bvn=z,avn=s,avt=a,bvt=a,b3.3 構(gòu)造下列正則表達(dá)式相應(yīng)的nfa： 1(1|0)*|0 1(1010*|1(010)*1)*0解：正則表達(dá)式：1(1|0)*|01、sz1(1|0)*|02、sz1(1|0)*03、saz01014

6、、q0q1010,1q2正則表達(dá)式：1(1010*|1(010)*1)*00135462101010780101101a,baa3.4 將圖3.36的nfa m確定化圖3.36 狀態(tài)圖 解：abq0=00,11q1=0,10,11q2=10dfa:q0q1q2ababa3.5 將圖3.37的dfa化簡。014253aaaaaabbbbbb圖3.37 dfa狀態(tài)圖 解：劃分ab0,112,42,3,4,51,0,3,53,5,2,4劃分ab0,112,42,40,13,53,53,52,4q0=0,1q1=2,4q2=3,5化簡后的dfa：q0q1q2baaabb4.1 對下面文法，設(shè)計(jì)遞歸下降

7、分析程序。 saas|(a) , aab|c解：首先將左遞歸去掉，將規(guī)則aab|c 改成 acb非終結(jié)符號(hào)s的分析程序如下：非終結(jié)符號(hào)a的分析程序如下：過程s inputsym=ainputsym=下一個(gè)符號(hào)yninputsym=(inputsym=下一個(gè)符號(hào)yinputsym=)inputsym=下一個(gè)符號(hào)ynn出口錯(cuò)誤錯(cuò)誤過程a過程s過程a過程a inputsym=cinputsym=下一個(gè)符號(hào)yinputsym=bn錯(cuò)誤inputsym=下一個(gè)符號(hào)y出口n4.2 設(shè)有文法gz： z=(a) , a=a|bb , b=aab若采用遞歸下降分析方法，對此文法來說，在分析過程中，能否避免回溯？

8、為什么？解：若采用遞歸下降分析方法，對此文法來說，在分析過程中不能避免回朔。因?yàn)橐?guī)則a=a|bb和規(guī)則b=aab構(gòu)成了間接左遞歸，不滿足實(shí)現(xiàn)沒有回溯的遞歸下降分析方法的條件（1）（書p67），且規(guī)則 a: := a|bb，first(a)=a，first(bb)=a，即此規(guī)則候選式的首符號(hào)集有相交，不滿足實(shí)現(xiàn)沒有回溯的遞歸下降分析方法的條件（2）（書p67），在分析過程中，將造成回溯。改寫文法可避免回溯：將規(guī)則b=aab代入規(guī)則a=a|bb得：a=a|aabb，再轉(zhuǎn)換成：a=aabb，可避免回溯。4.3 若有文法如下，設(shè)計(jì)遞歸下降分析程序。 <語句><語句><賦值

9、語句>| <賦值語句>id=<表達(dá)式> <表達(dá)式><項(xiàng)>|<表達(dá)式><項(xiàng)>|<表達(dá)式><項(xiàng)> <項(xiàng)><因子>|<項(xiàng)>*<因子>|<項(xiàng)>/<因子> <因子>id|num|(<表達(dá)式>)解：首先，去掉左遞歸<語句><語句><賦值語句>|改為： <語句><賦值語句><表達(dá)式><項(xiàng)> | <表達(dá)式> + <

10、項(xiàng)> | <表達(dá)式> - <項(xiàng)> 改為：<表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)><項(xiàng)><因子> | <項(xiàng)> * <因子> | <項(xiàng)> / <因子> 改為：<項(xiàng)><因子>（* | /）<因子>則文法變?yōu)椋?lt;語句><賦值語句> <賦值語句>id=<表達(dá)式> <表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)> <項(xiàng)><因子>（* | /）&

11、lt;因子> <因子>id|num|(<表達(dá)式>)<語句><賦值語句>非終結(jié)符號(hào) <語句> 的分析程序如下：first(<賦值語句>)=id語句inputsym=idny賦值語句出口<賦值語句>id=<表達(dá)式>非終結(jié)符號(hào) <賦值語句> 的分析程序如下：賦值語句inputsym=id錯(cuò)誤ninputsym=下一個(gè)符號(hào)inputsym=錯(cuò)誤ninputsym=下一個(gè)符號(hào)y表達(dá)式出口<表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)>非終結(jié)符號(hào) <表達(dá)式>

12、 的分析程序如下：表達(dá)式inputsym=+ninputsym=-inputsym=下一個(gè)符號(hào)y出口項(xiàng)ny<項(xiàng)><因子>（* | /）<因子>非終結(jié)符號(hào) <項(xiàng)> 的分析程序如下：項(xiàng)inputsym=*ninputsym=/inputsym=下一個(gè)符號(hào)y出口因子ny項(xiàng)<因子>id|num|(<表達(dá)式>)非終結(jié)符號(hào) <因子> 的分析程序如下：復(fù)值語句的分析程序因子inputsym=idy出口inputsym=numinputsym=下一個(gè)符號(hào)nyninputsym=(inputsym=下一個(gè)符號(hào)y表達(dá)式inputs

13、ym=)錯(cuò)誤ny錯(cuò)誤n4.4 有文法ga：a:=aabe|，b:=bb|b（1）求每個(gè)非終結(jié)符號(hào)的follow集。（2）該文法是ll(1)文法嗎？（3）構(gòu)造ll(1)分析表。解：（1） follow(a)=first(b)#=b,# follow(b)=e,b（2） 該文法中的規(guī)則b:=bb|b為左遞歸，因此該文法不是ll(1)文法（3） 先消除文法的左遞歸（轉(zhuǎn)成右遞歸），文法變?yōu)椋篴:=aabe|，b:=bb，b=bb|，該文法的ll(1)分析表為：aeb#apop ，push(ebaa)poppopbpop ，push(bb)bpoppop ，push(bb)apop,nextsymepo

14、p,nextsymbpop,nextsym#accept更常用且簡單的ll(1)分析表：aeb#aaaabeaabbbbbbbbb4.5 若有文法a(a)a|（1）為非終結(jié)符a構(gòu)造first集合和follow集合。（2）說明該文法是ll(1)的文法。解：（1）first(a)(, follow(a)，#（2）該文法不含左遞歸；first（(a)a）=(，first（）=，first（(a)a）first（）=，且follow(a)，#，first（(a)a） follow(a) =，因此，該文法滿足ll(1)文法的條件，是ll(1)文法。4.6 利用分析表4-1，識(shí)別以下算術(shù)表達(dá)式，請寫出分析

15、過程。（1）i+i*i+i（2）i*(i+i+i)解：（1）i+i*i+i步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#ei+i*i+i#pop,push(et)ete2#eti+i*i+i#pop,push(tf)tft3#etfi+i*i+i#pop,push(i)fi4#etii+i*i+i#pop,nextsym5#et+i*i+i#popt6#e+i*i+i#pop,push(et+)e+te7#et+i*i+i#pop,nextsym8#eti*i+i#pop,push(tf)tft9#etfi*i+i#pop,push(i)fi10#etii*i+i#pop,nextsym11#e

16、t*i+i#pop,push(tf*)t*ft12#etf*i+i#pop,nextsym13#etfi+i#pop,push(i)fi14#etii+i#pop,nextsym15#et+i#popt16#e+i#pop,push(et+)e+te17#et+i#pop,nextsym18#eti#pop,push(tf)tft19#etfi#pop,push(i)fi20#etii#pop,nextsym21#et#popt22#e#pope23#accept（2）i*(i+i+i)步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#ei*(i+i+i)#pop,push(et)ete2#eti*

17、(i+i+i)#pop,push(tf)tft3#etfi*(i+i+i)#pop,push(i)fi4#etii*(i+i+i)#pop,nextsym5#et*(i+i+i)#pop,push(tf*)t*ft6#etf*(i+i+i)#pop,nextsym7#etf(i+i+i)#pop, push()e()f(e)8#et )e(i+i+i)#pop,nextsym9#et )ei+i+i)#pop,push(et)ete10#et ) eti+i+i)#pop,push(tf)tft11#et ) e tfi+i+i)#pop,push(i)fi12#et ) e tii+i+i)

18、#pop,nextsym13#et ) e t+i+i)#popt14#et ) e +i+i)#pop,push(et+)e+te15#et ) et+i+i)#pop,nextsym16#et ) eti+i)#pop,push(tf)tft17#et ) etfi+i)#pop,push(i)fi18#et ) etii+i)#pop,nextsym19#et ) et+i)#popt20#et ) e+i)#pop,push(et+)e+te21#et ) e t+i)#pop,nextsym22#et ) e ti)#pop,push(tf)tft23#et ) e tfi)#pop

19、,push(i)fi24#et ) e tii)#pop,nextsym25#et ) e t)#popt26#et ) e)#pope27#et )#pop,nextsym28#et #popt29#e#pope30#accept4.7 考慮下面簡化了的c聲明文法：<聲明語句><類型><變量表>；<類型>int|float|char<變量表>id,<變量表>|id（1） 在該文法中提取左因子。（2） 為所得的文法的非終結(jié)符構(gòu)造first集合和follow集合。（3） 說明所得的文法是ll(1)文法。（4） 為所得的文法構(gòu)

20、造ll(1)分析表。（5） 假設(shè)有輸入串為“char x，y，z；”，寫出相對應(yīng)的ll(1)分析過程。解：（1） 規(guī)則<變量表>id,<變量表>|id提取公因子如下：<變量表>id（,<變量表>|）增加新的非終結(jié)符<變量表1>，規(guī)則變?yōu)椋?lt;變量表>id<變量表1><變量表1>，<變量表>| c聲明文法改變?yōu)椋?<聲明語句><類型><變量表>；<類型>int|float|char<變量表>id<變量表1><變量表

21、1>，<變量表>|（2） first(<聲明語句>)first(<類型>)int，float，charfirst(<變量表>)idfirst(<變量表1>)，follow(<聲明語句>)#follow(<類型>)first(<變量表>)idfollow(<變量表>)follow(<變量表1>)；（3） 所得文法無左遞歸，且first（int）first（float）first（char）first（，<變量表>）first（）first（，<變量表&g

22、t;）follow(<變量表1>)因此，所得文法為ll(1)文法。（4） 所得的文法構(gòu)造ll(1)分析表如下所示：；intfloatcharid，#<聲明語句>pop ，push(；<變量表><類型>)pop ，push(；<變量表><類型>)pop ，push(；<變量表><類型>)<類型>pop ，push(int)pop ，push(float)pop ，push(char)<變量表>pop ，push(<變量表1>id)<變量表1>poppop

23、 ，push(<變量表>，)；pop,nextsymintpop,nextsymfloatpop,nextsymcharpop,nextsymidpop,nextsym，pop,nextsym#accept更常用且簡單的ll(1)分析表：；intfloatcharid，#<聲明語句><聲明語句><類型><變量表>；<聲明語句><類型><變量表>；<聲明語句><類型><變量表>；<類型><類型>int<類型>float<類型

24、>char<變量表><變量表>id<變量表1><變量表1><變量表1><變量表1>,<變量表>（5） 輸入串“char x，y，z；”相對應(yīng)的ll(1)分析過程如下：步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#<聲明語句>char x，y，z；#pop ，push(；<變量表><類型>)<聲明語句><類型><變量表>；2#；<變量表><類型>char x，y，z；#pop ，push(char)<類型&g

25、t;char3#；<變量表> charchar x，y，z；#pop,nextsym4#；<變量表>x，y，z；#pop ，push(<變量表1>id)<變量表>id<變量表1>5#；<變量表1>xx，y，z；#pop,nextsym6#；<變量表1>，y，z；#pop ，push(<變量表>，)<變量表1>，<變量表>7#；<變量表>，y，z；#pop,nextsym8#；<變量表>y，z；#pop ，push(<變量表1>id)<

26、變量表>id<變量表1>9#；<變量表1>yy，z；#pop,nextsym10#；<變量表1>，z；#pop ，push(<變量表>，)<變量表1>，<變量表>11#；<變量表>，z；#pop,nextsym12#；<變量表>z；#pop ，push(<變量表1>id)<變量表>id<變量表1>13#；<變量表1>zz；#pop,nextsym14#；<變量表1>；#pop<變量表1>15#；#pop,nextsym16

27、#accept5.1 考慮以下的文法：ss;t|tta（1） 為這個(gè)文法構(gòu)造lr(0)的項(xiàng)目集規(guī)范族。（2） 這個(gè)文法是不是lr(0)文法？如果是，則構(gòu)造lr(0)分析表。（3） 對輸入串“a;a”進(jìn)行分析。解：（1）拓廣文法gs： 0：ss 1：ss;t 2：st 3：ta構(gòu)造lr(0)項(xiàng)目集規(guī)范族狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·ss·s;ts·tt·ago0，s1go0，s1go0，t2go0，a31ss·ss·tacceptgo1，;42st·r23ta·r34ss;·tt·ago4，t5go4，

28、a35ss;t·r1（2）該文法不存在“歸約歸約”和“歸約移進(jìn)”沖突，因此是lr(0)文法。lr(0)分析表如下：狀態(tài)actiongoto；a#st0s3121s4accept2r2r2r23r3r3r34s355r1r1r1（3）對輸入串“a;a”進(jìn)行分析如下：步驟狀態(tài)棧符號(hào)棧輸入符號(hào)棧actiongoto00#a;a#s3103#a;a#r32302#t;a#r21401#s;a#s45014#s;a#s360143#s;a#r3570145#s;t#r11801#s#accept5.2 證明下面文法是slr(1)文法，但不是lr(0)文法。saaab|bbabaac|a|aab

29、解：文法gs：0：sa1：aab2：abba3：baac4：ba5：baab構(gòu)造lr(0)項(xiàng)目集規(guī)范族：狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·aa·aba·bbago0，a1go0，a1go0，b21sa·aa·bacceptgo1，b32ab·bab·aacb·ab·aabgo2，b4go2，a5go2，a5go2，a53aab·r14abb·ago4，a65ba·acba·ba·aba·aba·bbago5，a7r4go5，a7go5，a7go5

30、，b26abba·r27baa·cbaa·baa·bgo7，c8go7，b9go7，b98baac·r39baab·aab·r5r1狀態(tài)5存在“歸約移進(jìn)”沖突，狀態(tài)9存在“歸約歸約”沖突，因此該文法不是lr(0)文法。狀態(tài)5：follow(b)a，因此，follow(b)b狀態(tài)9：follow(b)a，follow(a)#，b，c，因此follow(b)follow(a)狀態(tài)5和狀態(tài)9的沖突均可用slr(1)方法解決，構(gòu)造slr(1)分析表如下：狀態(tài)actiongotoabc#ab0s211s3accept2s543r1r1

31、r14s65r4s276r2r2r27s9s88r39r5r1r1r1該slr(1)分析表無重定義，因此該文法是slr(1)文法，不是lr(0)文法。5.3 證明下面文法是lr(1)文法，但不是slr(1)文法。saaab|bbbaab解：拓廣文法gs：0：ss1：saaab2：sbbba3：a4：b構(gòu)造lr(0)項(xiàng)目集規(guī)范族：狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·ss·aaabs·bbbaa·b·go0，s1go0，a2go0，b3r3r41ss·accept2sa·aabgo2，a43sb·bbago3，b54saa

32、3;aba·go4，a6r35sbb·bab·go5，b7r46saaa·bgo6，b87sbbb·ago7，a98saaab·r19sbbba·r2狀態(tài)0存在“歸約歸約”沖突，且follow(a) a,b，follow(b)a,b，即follow(a)follow(b)a,b，所以該文法不是slr(1)文法。構(gòu)造lr(1)項(xiàng)目集規(guī)范族：狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·s，#s·aaab，#s·bbba，#a·，ab·，bgo0，s1go0，a2go0，b3r3r41ss·

33、，#accept2sa·aab，#go2，a43sb·bba，#go3，b54saa·ab，#a·，bgo4，a6r35sbb·ba，#b·，ago5，b7r46saaa·b，#go6，b87sbbb·a，#go7，a98saaab·，#r19sbbba·，#r2lr(1)分析表：狀態(tài)actiongotoab#sab0r3r41231accept2s43s54r365r476s87s98r19r2分析表無重定義，說明該文法是lr(1)文法，不是slr(1)文法。5.4 考慮以下的文法：eeeee

34、e*ea（1）為這個(gè)文法構(gòu)造lr(1)項(xiàng)目集規(guī)范族。（2）構(gòu)造lr(1)分析表。（3）為這個(gè)文法構(gòu)造lalr(1)項(xiàng)目集規(guī)范族。（4）構(gòu)造lalr(1)分析表。（5）對輸入符號(hào)串“aa*a+”進(jìn)行l(wèi)r(1)和lalr(1)分析。解：（1）拓廣文法gs：0：se1：eee2：eee*3：ea構(gòu)造lr(1)項(xiàng)目集規(guī)范族：狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·e ，#e·ee ，a:#e·ee* ，a:#e·a ，a:#go0，e1go0，e1go0，e1go0，a21se· ，#ee·e ，a:#ee·e* ，a:#e·ee ，*:

35、+e·ee* ，*:+e·a ，*:+acceptgo1，e3go1，e3go1，e3go1，e3go1，a42ea· ，a:#r33eee· ，a:#eee·* ，a:#ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go3，5go3，*6go3，e7go3，e7go3，e7go3，e7go3，a44ea· ，*:+r35eee· ，a:#r16eee*· ，a:#r27eee· ，*:+eee·*

36、，*:+ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go7，+8go7，*9go7，e7go7，e7go7，e7go7，e7go7，a48eee· ，*:+r19eee*· ，*:+r2（2）構(gòu)造lr(1)分析表狀態(tài)actiongoto*a#e0s211s4accept32r3r33s5s6s474r3r35r1r16r2r27s8s9s478r1r19r2r2（3）構(gòu)造lalr(1)項(xiàng)目集規(guī)范族:狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)0s·e ，#e·ee ，a:#e

37、3;ee* ，a:#e·a ，a:#go0，e1go0，e1go0，e1go0，a21se· ，#ee·e ，a:#ee·e* ，a:#e·ee ，*:+e·ee* ，*:+e·a ，*:+acceptgo1，e3go1，e3go1，e3go1，e3go1，a22ea· ，a:#:*:+r33eee· ，a:#:*:+eee·* ，a:#:*:+ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go3，4

38、go3，*5go3，e3go3，e3go3，e3go3，e3go3，a24eee· ，a:#:*:+r15eee*· ，a:#:*:+r2（4）構(gòu)造lalr(1)分析表。狀態(tài)actiongoto*a#e0s211s2accept32r3r3r3r33s4s5s234r1r1r1r15r2r2r2r2（5）對輸入符號(hào)串“aa*a+”進(jìn)行l(wèi)r(1)分析:步驟狀態(tài)棧符號(hào)棧輸入串a(chǎn)ctiongoto10#aa*a+#s2202#aa*a+#r3 1301#ea*a+#s44014#ea*a+#r335013#ee*a+#s660136#ee*a+#r21701#ea+#s48014#ea+#r339013#ee+#s5100135#ee+#r111101#e#accept對輸入符號(hào)串“aa*a+”進(jìn)行l(wèi)alr(1)分析:步驟狀態(tài)棧符號(hào)棧輸入串a(chǎn)ctiongoto10#aa*a+#s2202#aa*a+#r31301#ea*a+#s24012#ea*a+#r335013#ee*a+#s560135#ee*a+#r21701#ea+#s28012#ea+#r339013#ee+#s4100134#ee+#r111101#e#accept5.5 說明以下的文法是lr(1)文法