編譯原理習(xí)題答案某課本貌似是清華出版那本ch

1、編譯原理課后習(xí)題第七章第 7 章 LR 分析第1題 已知文法 AaAd|aAb|判斷該文法是否是 SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab#給出分析過程。：文法：AaAd|aAb|文法為 G，增加產(chǎn)生式 SA若產(chǎn)生式排序?yàn)椋?123S AA AAaAdaAb由產(chǎn)生式知：(S ) = ,a(A ) = ,aFollow(S ) = #Follow(A ) = d,b,#G的 LR(0)項(xiàng)目集族及識別活前綴的 DFA 如下圖所示：在 I0 中：A .aAd 和A .aAb 為移進(jìn)項(xiàng)目，A .為歸約項(xiàng)目，存在移進(jìn)-歸約不是 LR(0)文法。在 I0、I2 中：Follow(A) a=

2、d，b，# a=，因此所給文法1盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章所以在 I0、I2 中的移進(jìn)-歸約構(gòu)造的 SLR(1)分析表如下：題目 1 的 SLR(1)分析表可以由 Follow 集解決，所以 G 是 SLR(1)文法。題目 1 對輸入串 ab#的分析過程分析成功，說明輸入串 ab 是文法的句子。2盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)棧（se stack）文法符號棧剩余輸入串（input left）動作（action）0#ab#.Shift0 2#ab#.Reduce by :A 0 2 3#aAb#.Shift0 2 3 5#aAb#.Reduce by :A aAb0 1#A#.

3、狀態(tài)（Se）ActionGotoadb#A0S2r3r3r311acc2S2r3r3r333S4S54r1r1r15r2r2r2編譯原理課后習(xí)題第七章第2題 若有定義二進(jìn)制數(shù)的文法如下： SLL|LLLB|B B0|1試為該文法構(gòu)造 LR 分析表，并說明屬哪類 LR 分析表。給出輸入串 101.110 的分析過程。：文法：SL.L|LLLB|B B0|1文法為 G，增加產(chǎn)生式 SS若產(chǎn)生式排序?yàn)椋?123456S SS S L L BBL.LLLBB01由產(chǎn)生式知：(S ) = 0,1(S(L(B)=0,10,10,1Follow(S ) = #Follow(S Follow(LFollow(

4、B)=#.,0,1,#.,0,1,#G的 LR(0)項(xiàng)目集族及識別活前綴的 DFA 如下圖所示：3盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章在 I2 中：B .0 和 B .1 為移進(jìn)項(xiàng)目，S L.為歸約項(xiàng)目，存在移進(jìn)-歸約是 LR(0)文法。在 I2、I8 中：Follow(s) 0，1= # 0，1=，因此所給文法不所以在 I2 、I8 中的移進(jìn)-歸約構(gòu)造的 SLR(1)分析表如下：題目 2 的 SLR(1)分析表可以由 Follow 集解決，所以 G 是 SLR(1)文法。4盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)（Se）ActionGoto01#S L B012345678S4S5acc S6

5、S4S5r2r4r4r4r4 r5r5r5r5 r6r6r6r6 S4S5r3r3r3r3 S4S5r11 2 3.7.8 3.7編譯原理課后習(xí)題第七章題目 2 對輸入串 101.110#的分析過程分析成功，說明輸入串 101.110 是題目 2 文法的句子。5盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)棧（se stack）文法符號棧剩余輸入串（input left）動作（action）00 50 30 20 2 40 2 70 20 2 50 2 70 20 2 60 2 6 50 2 6 30 2 6 80 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 1# #1

6、 #B #L #L0 #LB #L #L1 #LB #L #L.#L.1 #L.B #L.L #L.L1 #L.LB #L.L #L.L0 #L.LB #S101.110#.01.110#.01.110#.01.110#.1.110#.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1 Reduce by :S LB ShiftReduce by :B 0 Reduce by :S LB ShiftReduce by :B 1 Reduce by :S LB ShiftShiftRed

7、uce by :B 1 Reduce by :S B ShiftReduce by :B 1 Reduce by :S LB ShiftReduce by :B 0 Reduce by :S L.L編譯原理課后習(xí)題第七章第3題 考慮文法 S A S | bA S A | a構(gòu)造文法的 LR(0)項(xiàng)目集規(guī)范族及相應(yīng)的 DFA。如果把每一個 LR(0)項(xiàng)目看成一個狀態(tài)，并從每一個形如 B X的狀態(tài)出發(fā)畫一條標(biāo)記為 X 的箭弧刀狀態(tài) B X，而且從每一個形如 B A的狀態(tài)出發(fā)畫標(biāo)記為的箭弧到所有形如 A 的狀態(tài)。這樣就得到了一個 NFA。說明這個 NFA 與(a)中的 DFA 是等價的。構(gòu)造文法的

8、SLR 分析表。對于輸入串 bab，給出 SLR 分析器所作出的動作。 (5)構(gòu)造文法的 LR(1)分析表和 LALR 分析表。：(1)令文法 G為(0) S SSSAAA SbS Aa其 LR(0)項(xiàng)目集規(guī)范族及識別該文法活前綴的 DFA 如下圖所示：FOLLOW(S)=#,a,bFOLLOW(A)=a,bLR(0)項(xiàng)目：6盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章(2)顯然，對所得的 NFA 求閉包，即得上面的 LR(0)項(xiàng)目集，即 DFA 中的狀態(tài)。故此 NFA與(a)中 DFA 是等價的。(3)文法的 SLR 分析表如下：因?yàn)?I5 中：FOLLOW（A）a，b I7 中：FOLL

9、OW（S）a，b所以，該文法不是 SLR（1）文法。7盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)actiongotoab#SA0S4S3121S4S3acc652S4S3723r2r2r24r4r45S4/ r3S3/r3726S4S3657S4 / r1S3 / r1r165編譯原理課后習(xí)題第七章或者：從分析表中可看出存在歧義，所以不是該文法 SLR（1）文法。注意：不是 SLR(1)文法就不能構(gòu)造 SLR(1)分析表，也不能作分析過程。(4)對于輸入串 bab，SLR 分析器所作出的動作如下：（在第 5 個動作產(chǎn)生歧義）(5)LR(1)項(xiàng)目集族為： I0 :S S, #S S SAAS, #b, #SA

10、, a / ba, a / bI1 : S S,#A A A SS SA,a, a SA,a/ a/ b b/ bAS, a / bb, a / bI2 : S AS, #S b, # S AS, #A SA, a / b8盛威網(wǎng)（）專業(yè)的計算機(jī)站步驟狀態(tài)棧符號棧當(dāng)前字符剩余字符串動作(1)0#bab#移進(jìn)(2)03#bab#歸約 Sb(3)01#Sab#移進(jìn)(4)014#Sab#歸約 Aa(5)015#SAb#歸約 ASA(6)02#Ab#移進(jìn)(7)023#Ab#歸約 Sb(8)027#AS#歸約 SAS(9)01#S#接受編譯原理課后習(xí)題第七章Aa, a/ bS I3:b,#A I4:a,

11、a / bI5:S S S A AA SA, a / b AS, a / b AS, a / bb, a/ bSA, a / ba, a / bI6: A SA,a/bA SA, a / b A a, a / b S AS, a / bS b, a / bI7: S b, a / bI8 : S AS, # SA, a / bSA, a / ba, a / bAS, a / bA A A SSb, a /bI9 :S S S SAAS, #AS, #b, #SA, a / ba, a / bI10 :S A A A SSAS, a/bSA, a/bS A, a/ba, a / bb, a/bA

12、S, a / bI11 :9盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章S S S AAAS, a/bb, a/bAS, a / bS A, a/ba, a / bI12 :SA, a/bAS, a/bb, a/bAS, a / bS A, a/ba, a / bS S S S AAI5 狀態(tài)集中存在“歸約移進(jìn)”法構(gòu)造 LALR 分析表。，故無法構(gòu)造 LR(1)分析表，因而也就無注意：其實(shí)是可以構(gòu)造的，這個題目出得不太嚴(yán)格。因?yàn)闀系亩x是：根據(jù)這種文法構(gòu)造的 LR（1）分析表不含多重定義時，稱 這樣的分析表為 LR（1）分析表，能用 LR（1）分析表的分析器稱為 LR（1）分析器（規(guī)范的

13、LR 分析器），能構(gòu)造的 LR（1）分析表的文法稱為 LR（1）文法。習(xí)題：（1）列出這個文法的所有 LR(0)項(xiàng)目（2）按（1）列出的項(xiàng)目構(gòu)造識別這個文法活前綴的 NFA，把這個 NFA 確定化為 DFA，說明這個 DFA 的所有狀態(tài)全體這個文法的 LR(0)規(guī)范族（3）這個文法是 SLR 的嗎？若是，構(gòu)造出它的 SLR 分析表（4）這個文法是 LALR 或LR(1)的嗎？答：（1）令文法 G為012S SS A SS b10盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章A S AA a其 LR(0)項(xiàng)目：(2) 識別這個文法活前綴的 NFA 如上圖所示：確定化為 DFA 如下圖所示：11盛

14、威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章（3）因?yàn)?I5 中：FOLLOW（A）a，b I7 中：FOLLOW（S）a，b所以，該文法不是 SLR（1）文法。（4）LR(1)項(xiàng)目集族為：I0 :S S, #S S SAAS, #b, #SA, a / ba, a / bI1 : S S,#A A A SS SA,a, a SA,a/ a/ b b/ bAS, a / bb, a / b12盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章I2: S AS,#b, #AS, #SA, a / bS S AAa, a/ bS I3:b,#I4:A a,a / bI5:S S S A AA SA,

15、a / b AS, AS,a / ba / bb, a/ bSA, a / ba, a/ bI6: A SA,a/bA SA, a / b A a, a / b S AS, a / bS b, a / bI7: S b, a / bI8 : S AS, # SA,A A A SSa / bSA, a / ba, a/ bAS, a / bb, a/ bI9 :S S S SAAS, #AS, #b, #SA, a / ba, a / bI10 :S AS, a/bA SA, a/b A S A, a/b13盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章A a, a / b S b, a/bS

16、AS, a / bI11 :AS, a/bb, a/bAS, a / bS A, a/ba, a / bS S S AAI12 :SA, a/bAS, a/bb, a/bAS, a / bS A, a/ba, a / bS S S S AA因?yàn)?I5 狀態(tài)集中存在“歸約移進(jìn)”文法。，所以不是 LR(1)文法，也不是 LALR14盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章第6題 文法 G=(U,T,S,a,b,c,d,e,P,S)其中 P 為：SUbTS|Sc|d UUS|e判斷 G 是 LR(0)，SLR(1)，LALR(1)還是 LR(1)，說明理由。構(gòu)造相應(yīng)的分析表。：文法：SUbTS

17、|Sc|d UUS|e文法為 G，增加產(chǎn)生式 SS若產(chǎn)生式排序?yàn)椋?1234567S SS S T T T UUUTaTbSScdUSe由產(chǎn)生式知：(S ) = d,e(S(U(T)=d,eed,eFollow(S ) = #Follow(SFollow(U Follow(T)=a,b,c,d,e,#d,ea,b15盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章G的 LR(0)項(xiàng)目集族及識別活前綴的 DFA 如下圖所示：在 I1 中：S S.為接受項(xiàng)目，T S. 為歸約項(xiàng)目，T S.c 為移進(jìn)項(xiàng)目，存在接受-歸約和移進(jìn)-歸約，因此所給文法不是 LR(0)文法。在 I1 中：Follow(S)

18、Follow(T)= Follow(T) c= a ，b在 I8 中：Follow(U) Follow(T) # a ，b=c=c=d,e a ，b c=所以在 I1 中的接受-歸約和移進(jìn)-歸約與 I8 中的移進(jìn)-歸約和歸約-歸約Follow 集解決，所以 G 是 SLR(1)文法?？梢杂?6盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章構(gòu)造的 SLR(1)分析表如下：第8題 證明文法： SA$ ABaBb|DbDa BD是 LR(1)但不是 SLR(1)。(其中$相當(dāng)于#)：文法：ABaBb|DbDa BD文法為 G，增加產(chǎn)生式 SA若產(chǎn)生式排序?yàn)椋?1234SAA A BDBaBbDbDa

19、由產(chǎn)生式知：(S ) = a,b17盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)（Se）ActionGotoabcde#SUT0S5S41231r3r3S6Acc2S5S48273S94r7r75r5r56r4r47S10S98r3r3S6r6r69r2r2r2r2r2r210r1r1r1r1r1r1編譯原理課后習(xí)題第七章(A(B(D)=a,bFollow(S ) = #Follow(AFollow(B Follow(D)=#a,ba,bG的 LR(1)項(xiàng)目集族及識別活前綴的 DFA 如下圖所示：在 I0 中：B .,a 和 T .，b 為歸約項(xiàng)目，但它們的搜索符不同，若當(dāng)前輸入符為 a 時用產(chǎn)生式 B 歸約

20、，為 b 時用產(chǎn)生式 D 歸約，所以該文法是 LR(1)文法。若不看搜索符，在 I0 中項(xiàng)目 B .和 T .為歸約-歸約，而Follow(B ) Follow(D ) = a,b a,b不是 SLR(1)文法。構(gòu)造的 LR(1)分析表如下：題目 4 的LR(1)分析表，不能用 Follow 集解決，所以該文法18盛威網(wǎng)（）專業(yè)的計算機(jī)站SeActionGotoa . b . #ABD0123456789r3r4.Acc S4.S5r3 r4.S8 S9.r1 r2123. 67編譯原理課后習(xí)題第七章第 16題 給定文法：Sdo S or S|do S|S; (1)(2)(3)構(gòu)造識別該文法活

21、前綴的 DFA。該文法是 LR(0)嗎?是 SLR(1)嗎?說明理由。若對一些終結(jié)符的優(yōu)先級以及算符的結(jié)合規(guī)則規(guī)定如下：or 優(yōu)先性大于 do;服從左結(jié)合；;優(yōu)先性大于 do ；;優(yōu)先性大于 or ；a)b)c)d)請構(gòu)造該文法的 LR 分析表,并說明 LR(0)項(xiàng)目集中是否存在和如何解決的。：首先化簡文法,用d 代替do;用o 代替 or;用a 代替 SdSoS|dS|S;S|a文法為 G，增加產(chǎn)生式 SS若產(chǎn)生式排序?yàn)椋篴ct;文法可寫成：01234S SS S SSdSoSdSS;Sa由產(chǎn)生式知：(S ) = d,a(S ) = d,aFollow(S ) = #Follow(S ) =

22、 o,;,#(1)識別該文法活前綴的 DFA 如下圖。19盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章(2) 該文法不是 LR(0)也不是 SLR(1)因?yàn)椋涸?I5、I6、和 I8 中存在移進(jìn)-歸約又由于 Follow(S ) = o, ; ,#在 I6、和I8 中：，因此所給文法不是 LR(0)文法。Follow(S ) ; =o, ; ,# ; =;在 I5 中：Follow(S ) ; , o =o , ; ,# ; , o =; , o 所以該文法也不是 SLR(1) 文法。此外很容易證明所給文法是二義性的，SSdSoSddSoSSSdSddSoS因此該文法不可能滿足 LR 文法。

23、(3) 若對一些終結(jié)符的優(yōu)先級以及算符的結(jié)合規(guī)則規(guī)定如下：a)b)c)d)or 優(yōu)先性大于 do;服從左結(jié)合；;優(yōu)先性大于 do ；;優(yōu)先性大于 or ；20盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章則：在 I5 中：“or 和;優(yōu)先性都大于 do”，所以遇輸入符 o 和; 移進(jìn)；遇#號歸約。在 I6 中：“; 號服從左結(jié)合”，所以遇輸入符屬于 Follow(S )的都應(yīng)歸約。在 I8 中：“; 號優(yōu)先性大于 do ”， 所以遇輸入符為;號 移進(jìn)；遇 o 和#號歸約。此外，在 I1 中：接受和移進(jìn)可以不看成，因?yàn)榻邮苤挥杏?號。由以上分析，所有存在的移進(jìn)-歸約可用規(guī)定的終結(jié)符優(yōu)先級以及算符

24、的結(jié)合規(guī)則解決，所構(gòu)造的 LR 分析表如下：21盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)（Se）ActionGotodo;a#S0S2S311S4Acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1r4r1編譯原理課后習(xí)題第七章附加題問題 1：試判別如下文法是否 LR(0)或 SLR(1)文法:a) 文法 GE:E E + T TT (E) id id E其中 E,T 為非終結(jié)符,其余符號為終結(jié)符b) 文法 GS:S Ab ABcaA ab其中 S,A,B 為非終結(jié)符,其余符號為終結(jié)符：a) 增加產(chǎn)生式 SE，得增廣文法 GS構(gòu)造識別活前綴的有限狀態(tài)機(jī)如下：22盛威網(wǎng)

25、（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章可驗(yàn)證：狀態(tài) I3 有移進(jìn)-歸約，所以 GE不是 LR(0)文法；進(jìn)一步，因Follow(T)=+,#，不含，所以 GE是SLR(1)文法。b) 增加產(chǎn)生式 SS，得增廣文法 GS構(gòu)造識別活前綴的有限狀態(tài)機(jī)如下：I4 存在歸約/歸約， I3存在歸約/移進(jìn).因此不是LR(0)文法。能否使用SLR(1)方法解決：I4 中，因?yàn)?Follow(S) = # 而 Follow(B) = c.所以可以解決。 I3中，因Follow(A) = b，不含 a，因此該移進(jìn)/歸約是SLR(1)文法也可解決.文法參考解答：為下列文法構(gòu)造 LR（1）分析表，并給出串 baab

26、# 的分析過程:增廣文法文法 GS:S S(0)(1)(2)(3)S X X XXaX b其中 S,S,X 為非終結(jié)符,其余符號為終結(jié)符參考解答：參見P146 的例子, 自行補(bǔ)充對輸入串 baab#的分析過程23盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章問題 2：（1）構(gòu)造下列文法 G（P）的 LR（1）FSM，驗(yàn)證它是 LR（1）文法:P P P P (0)(1)(2)(3)P P(P)Aa(4) A 其中 P,P,A 為非終結(jié)符（2）通過合并同芯集（狀態(tài)）的方法構(gòu)造相應(yīng)于上述 LR（1）FSM并判斷 G（P）是否 LALR（1）文法？的LALR（1）FSM，：（1） 構(gòu)造文法 G（P）

27、的 LR（1）項(xiàng)目集族和轉(zhuǎn)換函數(shù)如下：P(aAAAaP(I5:P P(P.)P P.(P), (/#, (/)(P)，所以 G（P）是 LR（1）文法。其中的每個狀態(tài)均無宏（2） 可以看出：I2 和 I6，I3 和 I8，I4 和 I9，I5 和 I10，I7 和 I11 是同芯狀態(tài). 通過合并同芯狀態(tài)的方法構(gòu)造相應(yīng)于上述 LR（1）轉(zhuǎn)換圖的 LALR（1）轉(zhuǎn)換圖 如下：24盛威網(wǎng)（）專業(yè)的計算機(jī)站I11:P P(P). , (/)I7:P P(P). , (/#I10:P P(P.) , (/)P P.(P) , (/)I4:P Aa. , (/#I8:P P(.P) , (/)P .P(P

28、) , (/)P .Aa, (/)P ., (/)A ., aI2:P A.a , (/#I6:P A.a , (/)I3:P P(.P) , (/#P .P(P) , (/)P .Aa, (/)P ., (/)A ., aI9:P Aa. , (/)I1:SP., # P P.(P) , (/#I0:S.P, # P .P(P) , (/#P .Aa, (/#P ., (/#A ., a編譯原理課后習(xí)題第七章P(AAaP()可以看出: 所有狀態(tài)都不存在移進(jìn)-歸約和歸約-歸約法。.所以,G（P）是LALR（1）文問題 3：設(shè)文法 G 為：S ABA | aB | b(1)證明它是 LR(1)文

29、法； (2)構(gòu)造它的 LR(1)分析表；(3)給出輸入符號串 abab 的分析過程。：(1)(0)(3)文法G:S S(1) S B aBA(2) A BA(5) B bA (A) =(4), a, b25盛威網(wǎng)（）專業(yè)的計算機(jī)站I7-11:P P(P). , (/)/#I5-10:P P(P.) , (/)/#P P.(P) , (/)I4-9:P Aa. , (/)/#I2-6:P A.a , (/)/#I3-8:P P(.P) , (/)/#P .P(P) , (/)P .Aa, (/)P ., (/)A ., aI1:SP., # P P.(P) , (/#I0:S.P, # P .P

30、(P) , (/#P .Aa, (/#P ., (/#A ., a編譯原理課后習(xí)題第七章(B) = a, b構(gòu)造的 DFA 如下:SABBAabbaBba由項(xiàng)目集規(guī)范族看出，不存在該文法是 LR(1)文法。動作。(2)LR(1)分析表如下：26盛威網(wǎng)（）專業(yè)的計算機(jī)站狀態(tài)ActionGotoaB#SAB0S4S5r31231acc2r13S4S5r3634S4S575r5r5r5I4:BaB, a|b|# BaB, a|b|# Bb, a|b|#I5:Bb, a|b|#I7:BaB,a|b|#I6: ABA, #I3: ABA, #ABA, #A, #BaB, a|b|# Bb, a|b|#I

31、0: SS, #SA, #ABA, #A, #BaB,a|b|# Bb, a|b|#I2: SA, #I1: SS, #編譯原理課后習(xí)題第七章(3)輸入串 abab 的分析過程為：問題4：給定文法G(S):S SS L （L） aL , S S試為該文法配上屬性計算的語義規(guī)則（或動作）集合（即設(shè)計一個屬性文法），它輸出配對括號的個數(shù)。如對于句子(a,(a)，輸出是2。：產(chǎn)生式語義規(guī)則SSpr(S.num)S(L)Sa LL1,SLSS.num:=L.num+1S.num:=0L.num:=L1.num+S.numL.num:=S.num27盛威網(wǎng)（）專業(yè)的計算機(jī)站步驟狀態(tài)棧符號棧當(dāng)前字符剩余字

32、符串動作(1)0#abab#移進(jìn)(2)04#abab#移進(jìn)(3)045#abab#歸約 Bb(4)047#aBab#歸約 BaB(5)03#Bab#移進(jìn)(6)034#Bab#移進(jìn)(7)0345#Bab#歸約 Bb(8)0347#BaB#歸約 BaB(9)033#BB#歸約 A(10)0336#BBA#歸約 ABA(11)036#BA#歸約 ABA(12)02# A#歸約 SA(13)01#S#acc6r27r4r4r4編譯原理課后習(xí)題第七章問題5：給定文法GS:S L （L） aL , S S如下是相應(yīng)于GS的一個屬性文法：SSLL(1)(2)(3)(4)（L）aL1 , S S.num :=

33、 L.num +1; S.num := 0; L.num := L1.num + S.num; L.num := S.num; S下圖分別是輸入串 ( a，( a) ) 的語法分析樹和對應(yīng)的帶標(biāo)注語法樹，但其屬性值沒有標(biāo)出，試將其標(biāo)出（即填寫右下圖中符號“=”右邊的值）。：28盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章問題 6：對上題中所給的GS的屬性文法是一個S-屬性文法，故可以在自下而上分析的過程中，增加一個語義棧來計算屬性值。下圖（a）是 GS的一個 LR 分析表, 圖(b) 描述了輸入串( a，( a ) ) 的分析和計值過程（語義棧中的值對應(yīng)15）行沒有給出，試補(bǔ)齊之。S.num

34、或L.num），其中，第 14），題 3 圖（a）29盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章題 3 圖（b）：# ( L)# S#14）15）024601- - 1 - 2問題 7：下面的屬性文法 GN可以將一個二進(jìn)制小數(shù)轉(zhuǎn)換為十進(jìn)制小數(shù)，令 N.val 為 GN生成的二進(jìn)制數(shù)的值，例如對輸入串 101.101, N.val=5.625.2 S .len2N S S B S1S1 BS2 N.val := S1.val +*S2 .val ; S.val := 2 * S1.val + B.val; S.len := S1.len + 1 BS.val = B.val;B.val :=

35、0S.len:= 1 030盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章B 1B.val:= 1（1） 試消除該屬性文法（翻譯模式）中的左遞歸，以便可以得到一個可以進(jìn)行自上而下進(jìn)行語義處理（翻譯）的翻譯模式；（2） 對變換后的翻譯模式，構(gòu)造一個自上而下翻譯程序。：（1）消去原文法中的左遞歸：N S R R B B S S BRBR01可驗(yàn)證該文法是 LL（1）文法。再考慮語義規(guī)則，得到如下翻譯模式：2 S .len2N S1S2 N.val := S1.val +*S2 .val ;S.len := R.slen R.sval:=R1.sval;S B R.ival := B.val; R.

36、ilen := 1 R S.val := R.sval;R B R1.ival:=2*R.ival+B.val; R1.ilen:=R.ilen+1R.slen:=R1.slenR1R B B R.sval:=R.ival; R.slen:=R.ilen01B.val :=0B.val :=1(2) 對變換后的翻譯模式，可構(gòu)造一個如下的自上而下翻譯程序：real ParseN()(S1val,S1len) := ParseS();/變量 S1val,S1len 分別對應(yīng)屬性 S1.val,S1.lenMatchToken();/匹配, 函數(shù) MatchToken 參見第 4 講，本例省略/變量

37、 S2val,S2len 分別對應(yīng)屬性 S2.val,(S2val,S2len) := ParseS();S2.lenNval := S1val + 2 (-S2len)return Nval;* S2val ;/變量 Nval 對應(yīng)屬性 N.val(,) ParseS()/（,）代表一個/結(jié)構(gòu)類型31盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章Bval := ParseB(); Rival := Bval;Rilen := 1;(Rsval, Sval := Slen :=returnRslen) := ParseR(Rival, Rilen); Rsval;Rslen ;(Sval,Sl

38、en);(,)ParseR(Rival,Rilen)switch(lookahead) / lookahead 為下一個輸入符號case 0, 1: Bval := ParseB();R1ival := 2*Rival+Bval;R1ilen := Rilen+1；(R1sval, Rsval := Rslen :=break;R1slen) := R1sval;R1slen ;ParseR(R1ival,R1ilen);case , #: Rsval:=Rival; Rslen:=Rilen; break;default:prf(syntax errorn)exit(0);return (R

39、sval,Rslen);ParseB()switch (lookahead) case 0:MatchToken(0); Bval := 0;break; case 1:MatchToken(1); Bval := 1;break;default:prf(syntax errorn)exit(0);32盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章return Bval;問題 8：對于上題（1）所得到的翻譯模式（結(jié)果應(yīng)滿足 L-屬性的條件），在進(jìn)行自下而上的語義處理時，語義棧中的值有兩個分量，分別對應(yīng)文法符號的綜合屬性 val 和 len。若該翻譯模式中，嵌在產(chǎn)生式中間的語義規(guī)則集中含有除復(fù)寫

40、規(guī)則之外的語義規(guī)則，則變換該翻譯模式，使嵌在產(chǎn)生式中間的語義規(guī)則集中僅含復(fù)寫規(guī)則；根據(jù)（1）所得到的新翻譯模式，文法符號的所有繼承屬性均可以通過歸約前已出現(xiàn)在分析棧中的綜合屬性進(jìn)行。試寫出在按每個產(chǎn)生式歸約時語義處理的代碼片斷（設(shè)語義棧由向量 v 表示，歸約前棧頂位置為 top，語義值 vi的兩個分量分別用 vi.val 和 vi.len 表示）。：(1) 將如下翻譯模式2 S .len2N S1S2 N.val := S1.val +*S2 .val ; S B R.ival := B.val; R.ilen := 1 R S.val := R.sval; S.len := R.slen R

41、 B R1.ival:=2*R.ival+B.val; R1.ilen:=R.ilen+1R.slen:=R1.slenR1R.sval:=R1.sval;R B B R.sval:=R.ival; R.slen:=R.ilen01B.valB.val:=0:=1變換為：2 S .len2N S1S2 N.val := S1.val +*S2 .val ; S B M.bval := B.val M R.ival := M.sval; R.ilen := M.val R S.val := R.sval; S.len := R.slen R B P.rival:= R.ival; P.rilen

42、:= R.ilen; P.bval:=B.val; P R1.ival:= P.sval;R1.ilen:= P.slen R.sval:=R1.sval; R.slen:=R1.slen R.sval:=R.ival; R.slen:=R.ilenR1R B B M P 01B.val :=0B.val :=1 M.sval := M.bval; M.val := 1 P.sval = 2*P.rival + P.bval; P.sleP:= P.rilen +1(2)按每個產(chǎn)生式歸約時語義處理的代碼片斷:N S1 S2vtop-2.val := vtop-2.val + 2(-vtop.len) * vtop.val; S R R B BMPRR1vtop-2.val := vtop.val; vtop-2.len := vtop.len vtop-2.val := vtop.val; vtop-2.len := vtop.len vtop+1.val := vtop.val; vtop+1.len := vtop.len 33盛威網(wǎng)（）專業(yè)的計算機(jī)站編譯原理課后習(xí)題第七章B B M 01