【正文】 E (56)E (28)E*()E (28) 2E (28)854E (4)*E (5)E (20)E (8)+解： P194 2. 給出下面表達(dá)式的后綴式表示：解： (3) a+b*(c+d/e) : abcde/+*+(4) (a∧b)∨(┐c∨d) : ab∧c┐d∨∨(5) –a+b*(c+d) : abcd+*+(6) (a∨b) ∧(c∨┐d∧e) : ab∨cd┐e∧∨∧P195 4. 將下列中綴式改寫為后綴式表示：解： (2) ((a*d+c)*d+e)*f+g : adc+*d*e+f*g+ (4) x5∨x5 : x5x5∨P195 5. 將下列后綴式改寫為中綴式表示：解： (1) abc*cd+e/ : a*(bc)(c+d)/e(3) abc+a0∧ab+0a0∧∨ : (ab+c∧a0) ∨(a+b0∧a0)P195 6. 利用所給的語(yǔ)義子程序給出下列算術(shù)表達(dá)式語(yǔ)法制導(dǎo)翻譯過程：以（1）(a+b)為例進(jìn)行分析，（2）（3）兩題與（1）類似；解：，該表存在錯(cuò)位，應(yīng)糾正：步驟狀態(tài)棧符號(hào)棧輸入串規(guī)約規(guī)則調(diào)用子程序后綴表示10(a+b)204(a+b)3045(a+b)F∷＝iSUB6a4043(F+b)T∷＝FSUB4a5042(T+b)E∷＝TSUB2a6041(E+b)a70416(E+b)a804165(E+b)F∷＝iSUB6ab904163(E+F)T∷＝FSUB4ab1004169(E+T)E∷＝E(1)+TSUB1ab+11048(E)ab+120481(E)F∷＝(E)SUB5ab+1303FT∷＝FSUB4ab+1402TE∷＝TSUB2ab+1501EaccP195 8. 寫出下列賦值語(yǔ)句的自下而上語(yǔ)法制導(dǎo)翻譯過程，并給出產(chǎn)生四元式序列：a:=b*(c+d)步驟狀態(tài)棧符號(hào)棧PLACE輸入串規(guī)約規(guī)則調(diào)用子程序四元式10a:=b*(c+d)202aVa:=b*(c+d)V∷＝iSUB8303VVa:=b*(c+d)4034V:=Vab*(c+d)50349V:=bVaFb*(c+d)F∷＝iSUB760347V:=FVaTb*(c+d)T∷＝FSUB570346V:=TVaTb*(c+d)803461V:=T*VaTb(c+d)9034618V:=T*(VaTbc+d)100346189V:=T*(cVaTbFc+d)F∷＝iSUB7110346187V:=T*(FVaTbTc+d)T∷＝FSUB5120346186V:=T*(TVaTbEc+d)E∷＝TSUB3130346182V:=T*(EVaTbEc+d)1403461820V:=T*(E+VaTbEcd)15034618209V:=T*(E+dVaTbEcFd)。(4) 證明：構(gòu)造其LR(1)項(xiàng)目規(guī)范集：I0: S’?S, S?aAa, S?aBb, S?bAb, S?bBa, I1: S’S?, I2: Sa?Aa, Sa?Bb, A?x, a B?x, bI3: S b?Ab, Sb?Ba, A?x, b B?x, aI4: SaA?a, I5: SaB?b, I6: Ax?, a Bx?, bI7: SbA?b, I8: SbB?a, I9: Ax?, b Bx?, aI10: SaAa?, I11: SaBb?, I12: SbAb?, I13: SbBa?, 對(duì)于I6與I9并不存在“歸約歸約”沖突，于LR(1)文法相符；然合并同心集I6和I9，得：Ax, a/b Bx, a/b出現(xiàn)了“歸約歸約”沖突，故該文法并非LALR文法。(1) 證明：構(gòu)造其LR(0)項(xiàng)目集：I0: S’?S S?aSbS S?aS S?cI1: Sa?SbS Sa?S S?c S?aSbS S?aSI2: SaS?bS SaS?因?yàn)镮2中出現(xiàn)了“移進(jìn)歸約”沖突，因此不是LR(0)文法；(2) 證明：構(gòu)造其LR(0)項(xiàng)目集：I0: S’?S S?aAa S?aBbI1: S’S?I2: Sa?Aa Sa?Bb A?x B?xI3: SaA?aI4: SaB?bI5: Ax? Bx?I6: SaAa?I7: SaBb?由于I5中出現(xiàn)了“移進(jìn)規(guī)約”沖突，因此G2[S]不是LR(0)文法；∵FOLLOW(A)={a}∩FOLLOW(B)==Φ∴ACTION[i, a]=“用產(chǎn)生式Ax進(jìn)行歸約”； ACTION[i, b]=“用產(chǎn)生式Bx進(jìn)行歸約”；因而該文法為SLR(1)文法。則拓廣文法：S’S，SS(S)，Sε。(2)構(gòu)造LR（0）分析表狀態(tài) ACTIONGOTOa b c d Z A B0S4S5S61 2 3 7 8 1acc2r1r1r1r1r13r2r2r2r2r24S4S5S65r4r4r4r4r46r6r6r6r6r67S98S109r3r3r3r3r310r5r5r5r5r5規(guī)則順序：r1：Z→A r2：Z→B r3: A→aAb r4: A→C r5: B→aBb r6: B→d(3)分析符號(hào)串a(chǎn)acbb是否為該文法的句子步驟狀態(tài)棧符號(hào)棧輸入串分析動(dòng)作下一狀態(tài)10＃aaacbb＃S44204＃aacbb＃S443044＃aacbb＃S5540445＃aacbb＃r4GOTO[4,A]=750447＃aaAbb＃S99604479＃aaAbb＃r3GOTO[4,A]=77047＃aAb＃S9980479＃aAb＃r3GOTO[0,A]=2902＃A＃r1GOTO[0,Z]=11001＃Z＃acc成功P147 24. 給定文法： E∷＝EE+ | EE* | a（1） 構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族；（2） 它是SLR(1)文法嗎？若是，構(gòu)造它的SLR(1)分析表；解：(1) 在上述文法中引入新的開始符號(hào)E’,并將E’作為第0個(gè)規(guī)則r1:E∷=EE+ r2: E∷=EE* r3: E∷=a則基本LR(0)項(xiàng)目集為：⑴E’∷=?E ⑵E’∷=E? ⑶E∷=?EE+ ⑷E∷=E?E+⑸E∷=EE?+ ⑹E∷=EE+? ⑺E∷=?EE* ⑻E∷=E?E*⑼E∷=EE?* ⑽E∷=EE*? ⑾E∷=?a ⑿E∷=a?E*+aEEaI5: E∷=EE*?I4: E∷=EE+?I2: E∷=a?I3: E∷=?a E∷=EE?+ E∷=E?E+ E∷=?EE+ E∷=EE?* E∷=E?E* E∷=?EE*I1: E’∷=E? E∷=E?E+ E∷=?EE+ E∷=E?E* E∷=?EE* E∷=?aI0: E’∷=?E E∷=?EE+ E∷=?EE* E∷=?aa(2) 在I1中存在“移進(jìn)E?a”和“歸約：E’E?”沖突，因此該文法不是LR(0)文法，但有FOLLOW(E’)={}∩{a}=Ф，而該動(dòng)作沖突可用SLR(1)方法解決，該文法是SLR(1)文法，其分析表如下：狀態(tài)ACTIONGOTO+*aE0S211S2acc32r3r3r33S4S5S234r1r1r15r2r2r2P147 26. 對(duì)如下文法G： S∷＝S(S) S∷＝ε構(gòu)造LR(1)項(xiàng)目規(guī)范集以及LR(1)分析表，并用分析器給出(())的分析過程。bI10:B::= aBbI7:A::= aAI2: Z::= AaBb B::= cB ::= aAb A ::= I5: A::= caBbB::= aAbA::=A Z ::= bBbAdcadcaBAZ(1)I0: Z’ ::= A::= B::= Bb B ::=aB B ::= Ab A::= aA A ::= Z ::= Z::= 解：在上述文法中引入新的開始符號(hào)Z’，并將Z’::=Z作為第0個(gè)規(guī)則，從而得到所謂的拓廣文法G’，則其LR（0）項(xiàng)目有：Z’ ::= ∨+∨?！舏＃∨*∨+∨+i?！?∨+i+i?！?i*i+ii＃∨]矛盾，所以該文法非算符優(yōu)先文法P146 21. [E]優(yōu)先關(guān)系矩陣分析下列句子: i, i+i, i*i+i, i*(i*i)以及i*(i+i*i)+((i+i)*i解：以i*i+i為例，其余類似：符號(hào)棧關(guān)系輸入串最左素短語(yǔ)＃]a[ ∵A →AaA→B] ∴a的優(yōu)先關(guān)系＋*↑()if111111g222212根據(jù)S則f(R）g(S)若R=(↑*(1)步驟符號(hào)棧關(guān)系輸入串規(guī)則1b(((aa)a)a)b2b(((aa)a)a)b3b(((aa)a)a)b4b(((aa)a)a)b5b(((aa)a)a)b6b(((aa)a)a)b7b(((M=a)a)a)bM∷=a8b(((Ma=)a)a)b9b(((Ma)a)a)b10b(((La)a)bL∷=Ma)11b((M=a)a)bM∷=(L12b((Ma=)a)b13b((Ma)a)b14b((La)bL∷=Ma)15b(M=a)bM∷=(L16b(Ma=)b17b(Ma)b18b(LbL∷=Ma)19bM=bM∷=(L20bMb21ZZ∷=bMb(2)步驟符號(hào)棧關(guān)系輸入串規(guī)則1((aa)a)2( (aa)a)3((aa)a)4((aa)a)5((M=a)a)M∷=a6((Ma=)a)7((