編譯原理及實(shí)踐教程黃賢英王柯柯編著習(xí)題答案

1、第2章參考答案:1 , 2, 3:解答：略！4.解答：A:By C:D:5. 解答：用E表示表達(dá)式 ,T表示項(xiàng) ,F表示因子 ,上述文法可以寫為:ET | E+TTF | T*FF(E) | i最左推導(dǎo)：E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T=>i+i+F=>i+i+iE=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i最右推導(dǎo)：E=>E+T=>E+F=>E+i=>E

2、+T+i=>E+F+i=>E+i+i=>T+i+i=>F+i+i=>i+i+iE=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i =>i+i*ii+i+i和i+i*i的語(yǔ)法樹(shù)如下圖所示。i+i+i、i+i*i的語(yǔ)法樹(shù)/ E I T6.解答: (1)終結(jié)符號(hào)為：(or, and, not,(,), true , false 非終結(jié)符號(hào)為：(bexpr,bterm,bfactor開(kāi)始符號(hào)為：bexpr(2) 句子not(true or false)的語(yǔ)法樹(shù)為:bexprIbt

3、ermIbfactortXnotbfactor( bexpr )bexpr orbtermIIbtermbfactorIIbfactorfalseItrue7.解答：(1) 把a(bǔ)nbnci分成anbn和d兩部分，分別由兩個(gè)非終結(jié)符號(hào)生成，因此，生成此文法的 產(chǎn)生式為：S ABA aAb|abB r cB|®(2) 令S為開(kāi)始符號(hào)，產(chǎn)生的 w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號(hào)， 產(chǎn)生含相同個(gè)數(shù)的 a和b的所有串，則產(chǎn)生式如下：S aE|Ea|bSS|SbS|SSbEaEbE|bEaE|&(3) 設(shè)文法開(kāi)始符號(hào)為 S,產(chǎn)生的w中滿足|a|v|b|v 2|a|。因此，可

4、想到S有如下的產(chǎn)生 式(其中B產(chǎn)生1到2個(gè)b):S aSBS|BSaSB b|bb解法一：S 一奇數(shù)頭整數(shù)奇數(shù)尾|奇數(shù)頭奇數(shù)尾|奇數(shù)尾奇數(shù)尾1|3|5|7|9奇數(shù)頭2|4|6|8|奇數(shù)尾整數(shù)整數(shù)數(shù)字|數(shù)字?jǐn)?shù)字0|奇數(shù)頭解法二：文法 G=(S,A,B,C,D,0,1,2,3,4,5,6,7,8,9,P,S)Sr AB | BA r AC | DB r 1|3|5|7|9D r 2|4|6|8|BCr 0|D(5) 文法 G=(N,S,N,M,D,0,1,2,3,4,5,6,7,8,9 ,S,P)Sr N0|N5* MD| ；MR 1|2|3|4|5|6|7|8|9D D0 | DM | ；(6)

5、 GS : S-> aSa | bSb | cSc | a | b | c8.解答：(1) 句子abab有如下兩個(gè)不同的最左推導(dǎo)：S => aSbS => abS=>abaSbS => ababS => ababS => aSbS => abSaSbS=> abaSbS=> ababS=> abab所以此文法是二義性的。(2) 句子abab的兩個(gè)相應(yīng)的最右推導(dǎo)：S => aSbS=> aSbaSbS=> aSbaSb=> aSbab => ababS => aSbS=> aSb=>

6、 abSaSb=> abSab=> abab 句子abab的兩棵分析樹(shù)：(a)(b) 此文法產(chǎn)生的語(yǔ)言是：在a , b上由相同個(gè)數(shù)的a和b組成的字符串。9, 10:解答：略！第3章習(xí)題解答：1. 解答：(1) V (2) V (3) X (4) X (5) V (6) V2. 分析有限自動(dòng)機(jī)分為確定有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)。確定有限自動(dòng)機(jī)的確定性表現(xiàn)在映射& QX VT->q是單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)q Q和輸入字符串a(chǎn) Vt, 6(q,a)唯一確定下一個(gè)狀態(tài)。顯然，本題給出的是一個(gè)確定的有限自動(dòng)機(jī)，它的狀態(tài)轉(zhuǎn)換圖是C中的。它所接受的語(yǔ)言可以用正則表達(dá)式表示

7、為00(0|1) *,表示的含義為由兩個(gè) 0開(kāi)始的后跟任意個(gè)(包含0個(gè))0或1組成的符號(hào)串的集合。2. 解答：A:B:C:D:E:3, 4.解答：略！5.解答：6. 解答:(0|1) 01(1|2|-|9)(0|1|2| *| £)(09)(0|1)*(011)(0|1)* * *(4) 1 |1 0(0|10) (1| ) a b c -z(6) (0|10*1)*1* *(7) (00|11) (01|10)(00|11) (01|10)(00|11)(8) 分析設(shè)S是符合要求的串，|S|=2k+1 (k >0)。貝 U S r S10|S21, |S1|=2k (k>

8、;0 ), |S2|=2k (k > 0)。且S1是0,1上的串，含有奇數(shù)個(gè)0和奇數(shù)個(gè)1。S2是0,1上的串，含有偶數(shù)個(gè) 0和偶數(shù)個(gè)1?？紤]有一個(gè)自動(dòng)機(jī)M接受S1,那么自動(dòng)機(jī) M如下:0111000|11和L(M)等價(jià)的正規(guī)式，即 S為： (00|11)|(01|10)(00|11)*(01|10) *(01|10)(00|11)*類似的考慮有一個(gè)自動(dòng)機(jī)M接受S,那么自動(dòng)機(jī) M如下:位為：*(01|10)和L(M2)等價(jià)的正規(guī)式，即(00|11)|(01|10)(00|11)因此，S為：(00|11)|(01|10)(00|11)(00|11)|(01|10)(00|11)(01|10)

9、 *(01|10)(00|11)0|(01|10) *17. 解答：1組成的符號(hào)串。(1) 以0開(kāi)頭并且以0結(jié)尾的，由(2) 可陌0,1 *(3) 由0和1組成的符號(hào)串，且從右邊開(kāi)始數(shù)第3位為0。含3個(gè)1的由0和1組成的符號(hào)串。叩 0,1+,且a中含有3個(gè)1 (5)包含偶數(shù)個(gè)0和1的二進(jìn)制串，即叩 0,1*,且a中有偶數(shù)個(gè)0和18. 解答:二01Q0Q2Q1Q1Q3Q0Q2Q0Q3Q3Q1Q29.解答: DFA M=(0 , 1, q0, qi, q2, q0, q 2,日其中、定義如下：d(qo，0)=qia (qo, 1)=q05 (qi, 0)=q2d (qi, 1)=q0d(q2, 0

10、)=q2& (q2, 1)=q0狀態(tài)轉(zhuǎn)換圖為：_，一' * * *(2)正規(guī)式:1 01 01 01q0, q3, E),其中6定義如下:DFA M=(0 , 1, 、. (q°, 0)=q 、.(q，0)=q2 ,： (q2, 0)=q3 ,： (q3, 1)=q3 狀態(tài)轉(zhuǎn)換圖為：q°, q，q2, q3,& (q。，1)=q0、(q1, 1)=q1、(q2, 1)=q211110.解答:q3, q°, q 3, 9,其中6定義如下:(1) DFA M=(0 , 、.(q°, 0)=q1 、.(q，0)=q1 、.(q2, 0)

11、=q3 狀態(tài)轉(zhuǎn)換圖為：1, q°, q，q2,d (q°, 1)=q2：.(q，1)=q3、(q2, 1)=q1 DFA M=(0 , 1, (q 0, q0, (q 0, S),其中&定義如下: d(q。，°)=q0d (q。，1)=q0狀態(tài)轉(zhuǎn)換圖為：11解答：(1) (a|b)*a(a|b)求出NFA M:確定化，得到DFA M:DFA M?；?jiǎn)：在第步中求出的DFA M中沒(méi)有等價(jià)狀態(tài)，因此它就是最小化的(2) (a)b)*a(a|b)(a|b)求NFA M :確定化，得到DFA M :DFA M 了。化簡(jiǎn)，在第步中求出的 DFA M中沒(méi)有等價(jià)狀態(tài)，因

12、此它已經(jīng)是最小化的12,解答：對(duì)應(yīng)的NFA為：增加狀態(tài)X、Y,再確定化:II aI bx,5A,T,Y A,T,YA,T,YBB B,T,YB,T,Y T,YT,Y 得到的DFA為:最小化：該自動(dòng)機(jī)已經(jīng)是最小化的DFA 了。13. 解答：其中a代表1元硬幣，b代表5角硬幣14. 解答：正規(guī)式為：(0|1)*(00|01)化簡(jiǎn)：(0|1)*0(0|1)不確定的有窮自動(dòng)機(jī)為：確定化，并最小化得到:,1正規(guī)文法為：Sr 1S | 0AA 0B | 0 | 1C | 1B 0B | 0 | 1C | 1C 1S | 0A15. 解答： 正規(guī)式：(dd ：| dd (.dd |如d代表az的字母 NFA

13、為:E£DFA為：16. 解答：詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)，因此象 C語(yǔ)言的語(yǔ)句fi (a = f (x) ) -中，詞法分析器把 fi當(dāng)作一個(gè)普通的標(biāo)識(shí)符交給編譯的后續(xù)階段，而不會(huì)把它看成是關(guān)鍵字if的拼寫錯(cuò)。PASCAL語(yǔ)言要求作為實(shí)型常量的小數(shù)點(diǎn)后面必須有數(shù)字，如果程序中出現(xiàn)小數(shù)點(diǎn)后面沒(méi)有數(shù)字情況，它由詞法分析器報(bào)錯(cuò)。17. 解答：此時(shí)編譯器認(rèn)為/* then partreturn qelse/* else part */是程序的注釋，因此它不可能再發(fā)現(xiàn)else前面的語(yǔ)法錯(cuò)誤。分析這是注釋用配對(duì)括號(hào)表示時(shí)的一個(gè)問(wèn)題。注釋是在詞法分析時(shí)忽略的，而詞法分析器對(duì)程序采取非常

14、局部的觀點(diǎn)。當(dāng)進(jìn)入第一個(gè)注釋后，詞法分析器忽略輸入符號(hào)，一直到出現(xiàn)注釋的右括號(hào)為止，由于第一個(gè)注釋缺少右括號(hào)，所以詞法分析器在讀到第二個(gè)注釋的 右括號(hào)時(shí)，才認(rèn)為第一個(gè)注釋處理結(jié)束。為克服這個(gè)問(wèn)題，后來(lái)的語(yǔ)言一般都不用配對(duì)括號(hào)來(lái)表示注釋。例如Ada語(yǔ)言的注釋始于雙連字符(-)，隨行的結(jié)束而終止。如果用 Ada語(yǔ)言的注釋格式，那么上面函數(shù)應(yīng)寫 成long gcd(p,q)long p,q;(if (p%q = 0)-then partreturn qelse- else partreturn gcd(q, p%q);18.解答：略！第4章習(xí)題解答:1, 2, 3, 4解答 略！5. 解答：(1)

15、X (2) V (3) X (4) V (5) V (6) V (7) X (8) X6. 解答：(1) A:B:C:D:E:(2) A:B:C:D:E:7. 解答：(1) 消除給定文法中的左遞歸，并提取公因子：bexpr birm (or bterm bterm bfactor (and bfactorbfactor not bfactor | (bexpr) | true |false(2) 用類C語(yǔ)言寫出其遞歸分析程序：void bexpr();(bterm();WHILE(lookahead ='or') ( match ('or');bterm();v

16、oid bterm();(bfactor();WHILE(lookahead ='and')( match ('and'); bfactor();void bfactor();(if (llokahead='not') then ( match ('not');bfactor();else if(lookahead='(') then ( match (');bexpr();match(')');else if(lookahead ='true')then match (&#

17、39;true)else if (lookahead='false')then match ('false');else error;8.解答：消除所給文法的左遞歸，得G:S(L)|aLSL'L ，SL '3實(shí)現(xiàn)預(yù)測(cè)分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制，下面構(gòu)造預(yù)測(cè)分析表：根據(jù)文法G有：First(S) = ( ( , a )First(L) = ( ( , a )First(L ') = ( ,按以上結(jié)果，構(gòu)造預(yù)測(cè)分析表Follow(S) = ( ) , , , # Follow(L) = ( ) Fo

18、llow(L ') = ( ) M如下：4結(jié)符號(hào)輜入暗()a#SS T(L)S T aLLKULTSLLL hSL文法G是LL(1)的，因?yàn)樗腖L(1)分析表不含多重定義入口。預(yù)測(cè)分析器對(duì)輸入符號(hào)串(a,(a,a) 做出的分析動(dòng)作如下：步驟棧剩余輸入串輸出1#S(a,(a,a)#2#)L(a,(a,a)#S (L)3#)La,(a,a)#4#)L'Sa,(a,a)#L r SL'5#)L'aa,(a,a)#S -a6#)L',(a,a)#7#)L'S,(a,a)#L' r SL'8#)L'S(a,a)#9#)L'

19、)L(a,a)#S (L)10#)L')La,a)#11#)L')L'Sa,a)#L r SL'12#)L')L'aa,a)#S -a13#)L')L',a)#14#)L')L'S,a)#L' r ,SL'15#)L')L'Sa)#16#)L')L'aa)#S -a17#)L')L')#18#)L')#L' F19#)L')#20#)#L' F21#9.解答：各非終結(jié)符的First集:First(S)=First(A)於

20、 UFirst(B)涉 U 址 U b=a,b, &First(A)=b U»b, ?First(B) = 時(shí) U a=a,目First(C)=First(A) s U First(D) U First(b) =a,b,cFirst(D)=a U c=a,c各個(gè)候選式的First集為：First(AB)=a,b, First(卻= 0 First(aD)=a First(b)=b First(c)=c 各非終結(jié)符的FollowFirst(bC)=b First(b) = b First(AD)=a,b,c First(aS)=a集的計(jì)算:Follow(S)=# U Follo

21、w(D) =#Follow(A)=(First(B) 即 U Follow(S) U First(D) =a,#,cFollow(B)=Follow(S) =#Follow(C)=Follow(S) =#Follow(D)=Follow(B) U Follow(C) =#10.解答：(1)求 First 和 Follow 集First(E)=First(T)=(,a,b,AFirst(E')=+, ?First(T)=First(F)=(,a,b,AFirst(T')= (,a,b, A,黔First(F)=First(P)=(,a,b,AFirst(F')= *，哥F

22、irst(P)=(,a,b, A(計(jì)算順序)(1)(使用的產(chǎn)生式)(1,2)(3)(3,4)(5)(5,6)Follow(E)= #, ) Follow(E')= Follow(E)=# , ) Follow(T) = First(E') © UFollow(T') =+ U),#=+,),# Follow(T')= Follow(T)=+,# Follow(F)= First(T') 耳 UFollow(T) =(,a,b, A,+ ,),#Follow(F')= Follow(F)=(,a,b, A，+ ,),# Follow(P)

23、= First(F') 耳 UFollow(F)=*,(,a,b, A，+ ,),#證明：.a.文法不含左遞歸；b. 每個(gè)非終結(jié)符的各個(gè)侯選式的First集不相交;c. First(E') n Follow(E')=+,哥 n #,),=中First(T') n Follow(T')=(,a,b, A,號(hào) n +,)=中First(F') n Follow(F')=*,耳 n ,a,( A ,+,#=中改造后的文法滿足 LL(1)文法的三個(gè)條件，是 LL(1)文法。(3) 預(yù)測(cè)分析表如下所示。ab*+A()#EEr TE'ETE&

24、#39;EFE'E'E' r +EE,E'fTA FT'AFT'AFT'AFT'T'T' rTT' rTT' rTT' rTT'七T'七F"PF'"PF'"PF'"PF'F'F' fF'七F' r *F'F' pF'七F' fF'七FP八aPF八A八(E)11. 解答：Sr AbcAr a zBr b ；a. 文法不含左遞歸；b. S

25、,A,B各候選式的First集不相交；c. First(A) n Follow(A)=(a, s n b=中First(B) n Follow(B)=b, s n 中=中.該文法為L(zhǎng)L(1)文法。Sr AbAr a B ；Br b ；a. 文法不含左遞歸；b. S,A,B各候選式的First集不相交；c. First(A) A Follow(A)=a,b, s A b=b 爭(zhēng)該文法不是LL(1)文法。12. 解答：最右推導(dǎo)：E=>T=>F=>(E)=>(E + T)=>(E + F)=>(E + i)=> (T + i)=>(T*F + i)語(yǔ)法

26、樹(shù)：圖4.1句型(T*F + i)的語(yǔ)法樹(shù) 短語(yǔ)：(T*F + i), T*F + i, T*F , i素短語(yǔ)：T*F , i最左素短語(yǔ)：T*F 由于E =>E+T =>E+T*F，故E+T*F為該文法的句型 短語(yǔ)：T*F、E+T*F直接短語(yǔ)：T*F句柄：T*F13.解答：最左推導(dǎo)：S=> =>(T,S)=> (S,S)=> (a,S)=>(a,(T)=> (a,(T,S)=> (a,(S,S)=>(a,(a,S)=> (a,(a,a)最右推導(dǎo):S=> =>(T,S)=> (T,(T)=> (T,(T,S

27、)=>(T,(T,a)=> (T,(T,a)=>(T,(a,a)=> (S,(a,a)=>(a,(a,a)文法中S和T的FirstVT 和LastVT集為: FirstVT(S)=(a,(FirstVT (T)=,a, (lastVT(S)=(a, ) lastVT(T)=,a,)文法GS的算符優(yōu)先關(guān)系表：a()1#a>->>(<<)>>>1，如->0根據(jù)優(yōu)先關(guān)系表，對(duì)每個(gè)終結(jié)符或#建立符號(hào)f與g,把f(和g)分成一組。根據(jù)GS的算 符優(yōu)先關(guān)系表，畫出如下的有向圖。優(yōu)先函數(shù)如下:a()J#f20220g3301

28、0用算符優(yōu)先分析法分析句子 (a,(a,a)棧輸入動(dòng)作#(a. (a. a)fl初始a, (a, a)#r 豌.(a.a)S移進(jìn)#(N歸約0. a)#U (NJa, a)tt移進(jìn)a (N, (a3)#移進(jìn)U IN, (N7a)#歸約fl(N, (N.3)tt移進(jìn)#(N( (N,a)樺StN. (N.N)博歸約# (N, (NI)博歸約a (N, (N)ti (N, N博歸約tt(N)n歸約S(N)#N1u歸約，接受給定的輸入符號(hào)串是文法的一個(gè)句子。14.解答：(1) 該文法的拓廣文法 G為0.S'-S1.S -» aSAB2.S -» BA3.A -» a

29、A4.A -» B5.B -» b其LR(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的DFA如下：|0 = SJ S, S* aSAB, Sr. BA, B* bI 1 = S' T* S 12 = B r b 13 = S r a - SAB, S r aSAB, S - BA, B - b14 = SB - A, A aA, A- B, B - b15 = SaS - AB, A aA, A - B, B - b16 = S aSA B, B . b17 = A r a - A, A r aA, A - B, B - b18 = A B 19 = S BA 110 = S a

30、SAB111 = A r aA , 顯然，上述狀態(tài)中沒(méi)有出現(xiàn)沖突。顯然，該文法是LR(0)的文法，因此也是 SLR(1)的。求各個(gè)非終結(jié)符的Follow集，以便構(gòu)造分析表：Follow(S ')=#Follow(S)=a,b,#Follow(A)=a,b,# Follow(B)=a,b,#構(gòu)造的SLR(1)分析表如下：actiongotoab5AB0S3S2141acc1 2 ：巧Jr5 1r5_3S3S2544S7 JS2I 905S7S2686S2107S7S211B8苗r4r49r2r2r210r1r1r111r3r3r3(2) 該文法的拓廣文法G為0.S'-S1.S -

31、» Sab2.S -» bR3.R -» S4.R -» a其LR(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的DFA如下：10 = SJ S, S r Sab, Sr. bR11 = S' s ，S S - ab12 = S b - R, R S, R a, S Sab, S bR13 = S Sa - b14 = S bR 15 = R " S , , S " S , ab16 = R a - I7= (S Sab 5DFA)如下:顯然,Ii和I5存在移進(jìn)-歸約沖突。求 S'和R的Follow集:Follow(S')=(

32、# Follow(R)=Follow(S)=(a,#在I5中，出現(xiàn)的移進(jìn)一歸約沖突，且 Follow(R) n (a=(a，不能用SLR(1)方法解決。因此，此文法不是 SLR(1)文法。15.解答：(1)構(gòu)造其拓廣文法 G'的產(chǎn)生式為0. S'S1 . SA2. A r BA3. A r e4. B r aB5. B r b構(gòu)造其LR(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的10 = ( S'r S, #, S A, #, ABA, #, AB - aB, a/b/#, B - b, a/b/#11 = (S'S- , #12 = (S " ,

33、#13 = (A B A, #, ABA, #, A，#,B - aB, a/b/#, B b, a/b/#14 = (B 7 - , a/b/#15 = (B a - B, a/b/#, B- aB, a/b/#,B b, a/b/#16 = (A BA，#17 = (B aB , a/b/#該文法的LR(1)項(xiàng)目集規(guī)范族中沒(méi)有沖突，所以該文法是LR(1)文法。構(gòu)造LR(1)分析表如下：狀態(tài)actiongotoab#sAB0S5S4J?ij231acc2r13S5S4r3634r5巧r575S56r27r4r4r4以上分析表無(wú)多的定義入口，所以該文法為L(zhǎng)R(1)文法。(3)對(duì)于輸入串a(chǎn)bab

34、,其分析過(guò)程如下：步驟狀態(tài)棧輸入動(dòng)作(L)0abab#移進(jìn)(2)Oafibab#移進(jìn)(3)0a5b4ab#用B-b歸約(4)0d5B7ab#用行歸約(5)0R3ab#移進(jìn)(6)0B3h5M移進(jìn)0B3a5b4#用B->b歸約C8)0B3&5B7葬用酒進(jìn)行歸約(9)用A- '進(jìn)行歸約(10)0B3B3A6葬用A-BA進(jìn)行歸約(11)0B3A6用A-BA進(jìn)行歸約(12)0A2用S-A進(jìn)行歸約(13)0S1接受16.解答：(1) 對(duì)于產(chǎn)生式Sr AaAb|BbBa來(lái)說(shuō)First(AaAb) n First(BbBa)=a n b=中A , B Vn僅有一條候選式。因此，這個(gè)文法是

35、 LL(1)的。(2) 下面構(gòu)造這個(gè)文法的識(shí)別活前綴的DFA。10 = S' S, S r AaAb, S r - BbBa, A r . , B r . 11 = S' *12 = S a aAb13 = S b bBa14 = S Aa - Ab, A15 = S r Bb , Ba, B r 16 = S AaA b17 = S BbB a18 = (S r AaAb - 19 = (S BbBa - 由于Follow(A)= Follow(B)=(a, b,因此項(xiàng)目集Io中存在歸約-歸約沖突。在Io狀態(tài)下，當(dāng) 輸入符號(hào)是a或是b時(shí)，不知用 Ar 施是Br行歸約。故此文法

36、不是SLR(1)的。但是，此文法時(shí)LR(1)的。17.解答：該文法的拓廣文法 G'為0. S' r S1 . S r (SR2. S r a3. R ,SR4. R r )構(gòu)造其LR(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的 DFA)如下：10 = (S . S, S* (SR, S* a11 = (S' S - 12 = (S ( - SR, S . (SR, S a13 = (S " a 14 = (S r (S - R, R r ,SR, R r )Is = ( Sr (SR - 16 = (R r) 17 = (R, - SR, S . (SR,

37、S a18 = (R,S - R, R r ,SR, R r )19 = (R r ,SR 每個(gè)LR(0)項(xiàng)目集中沒(méi)有沖突。因此，此文法是LR(0)文法。其分析表如下:狀態(tài)actiongotoa()_,sR0工3S211acc2_S3_說(shuō)43r2r2口r24S6S755nr1r1r1r16巧r5r5r557S2S288豆蘭7994r4r4rr418.解答:第5章習(xí)題解答:1,2, 3解答： 略！4.解答：(1)設(shè)S, L, B的值的屬性用val表示：S Sprintf(S. val)1,212L2.length、Sr L .L S.val:= L .Val+ L .val/2 g Sr LS.

38、val:=L.valLL 1BL.val:=L 1.val*2+B.val ,L.length = L 1.length+1 Lr BL.val:=B.val),L.length:=1Br 0B.val:=0Br 1B.val:=1(2)為S, L引入屬性h,用來(lái)記錄配對(duì)的括號(hào)個(gè)數(shù)：S'r S (printf(S.h)Sa S.h:=0Sr (L) S.h:=S.h+1L L S L.h:=L .h+S.hL SL.h:=S.h)(3)為D引入一個(gè)綜合屬性 h,用來(lái)記錄D中含id的個(gè)數(shù)PFprintf(D.h)DD 1;D2D.h:=D 1.h+D2.hA id:TD.h:= 1A p

39、roc id; D 1;S D.h:=D 1.h+15.解答：輸入串為bcccaadadadb時(shí)的語(yǔ)法樹(shù)為：e R/ I、Q h d/c RQ d/c R/ | Q a da采用修剪語(yǔ)法樹(shù)的方法，按句柄方式自下而上歸約該語(yǔ)法樹(shù)，在歸約時(shí)調(diào)用相應(yīng)的語(yǔ)義規(guī)則，由此得到最終的翻譯結(jié)果為：34242421.6. 解答：(a+b)+(c+d/(e-3)*87. 解答：(1) ab-c+*(2) A not C D not or not or(3) abcde/+*+ A B and C not D or or(5) a-bc-d+*+(6) A B or C D not E and or and8. 解

40、答：二兀式四兀式(+,a,b)1.(+,a,b,T i)(-,1,-)2.(-,T,-, T2)(+,c,d)3.(+,c,d,T3)(*,2,3)4.(*, T2,T 3,T4)(+,a,b)5.(+,a,b,T5)(+,c,5)6.(+, T 5,c, T 6)(-,4,6)7.(-, T 4, T6 ,T 7)9. 解答：四元式代碼為：1. (jnz, A , _, x)2. (j, _, _, 3)3. (jnz , B , _, 5)4. (j, _, _, y)5. (jnz , C, _, y)6. (j，_，_, 7)7. (jnz , D, _, y)10.8. (j , _

41、, _, x)解答：11.解答：(1)四元式序列為：1. (j<,A,C,3)2. (j,-,-,14)3. (j<,B,D,5)4. (j,-,-,14)5. (j=,A,1,7)6. (j,-,-,10)7. (+,c,1,Ti)(2)四元式序列為：1. (j >0,2. (j ， _,8. (:=,T,-,C)9. (j,-,-,14)11. (j,-,-,14)12. (+,A,2,T 2)13. (:=, T 2,-,A)14.x, 0, 3)7. (j, _, _,12)_， 8)8. (+, x, 2, T2)3. (j>, y, 0， 5)9. (: = , T2