【正文】 I1S’ →SI3S→aSSSS→aSSSS→SbS→aSaSSbS→cScaI5I2I3I5S→aSSSS→aSSSS→I7S→aSSSSS→AbA→I2S→AbbI4I3A→a 解： 狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0S’ →(SRS→I2S→((SRS→I4S→(S(SRS→,SRR→I6R→, (SRS→I8R→,S,SRR→LR(0)分析表如下：ACTIONGOTOa(),SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可見是LR(0)文法。 解： （1）狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0S’ →SabS→S→SRR→aS→bRRSabI4I5I6I2I3S→Sar2I5R→SabaI3I6R→a項(xiàng)目I1,I5同時具有移進(jìn)和歸約項(xiàng)目，對于I5={ R→Sab },follow(R)={a},follow(R) ∩{a}={a},所以SLR(1)規(guī)則不能解決沖突，從而該文法不是SLR(1)文法。SS→BAB→I2S→aaSABS→bSaBbI5I2I3I4I3S→BaAA→bAaBbI6I7I8I4I4B→bABA→BB→r2I7A→aBA→bABabI10I8I7I4I8A→BBB→r3I11S→aSABSLR(1)分析表如下：ACTIONGOTOabSAB0S2S4131ACC2S2S4533S7S4684R5R5R55S7S4986R2R2R27S7S41088R4R4R49S41110R3R3R311R1R1R1（3）先求識別全部活前綴的DFA：狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0S’ →aSbS→abSabI1I2I3I1S’ →SSBS→aaSbS→abSbaI4I5I2I3S→baSbS→abSabI6I2I3I4S→aSr3I6S→bSr1I8S→bSaSLR(1)分析表如下：ACTIONGOTOabS0S2S311ACC2S2S543S2S364S75R3R3R36S87R1R1R18R2R2R2（4）先求識別全部活前綴的DFA：狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0S’ →aAS→accI2(沖突)S→acAdA→BB→BcI6I7r6I4S→aAAdA→AcI8I5r4I6S→bBBddB→cBcI9I7r6I8A→cAdddI11I10A→cAdddI12I12B→cBdd其SLR(1)分析表如下：ACTIONGOTOabcdSAB0S2S311Acc2S5R4R443S7R6R664R15S5R4R486R27S7R6R698S109S1110R3R311S1212R5R5（5）解：原文法等價化為q1→q2, q1→q3, q2→q4。D, q5→S end, q5→S。q1q1→q3q2→q5q3→begin Dq4→Dq1q2q3q4beginI1I2I3I4I5I1q1’ →q1R1I3q1→q3q5q4→q4DI6I5q3→beginDq5→S。 Sendq5→q5q5DSI10I11I9I7q3→beginq5R4I9q5→Sq5end。q5DR6I13q5→s。q5q5→S。q5SLR(1)分析表如下：ACTIONGOTO。, q2→ε,q3→q3。q1q1→ACCI2q1→beginq2d。q2q2I3R3I3(沖突項(xiàng)目)Q1→beginq2d。q3。q4q4→q3Ddq4SI4I10I5I6R7I4q1→beginq2q3q4end。R5I6q4→SR1I8(沖突項(xiàng)目)q3→q3。q4q4→q4SI9I6R7I9q3→q3。R4I10q2→q2dI11I11q2→q2d。R2因?yàn)閒ollow(q4)={end,}，故沖突項(xiàng)目可以通過SLR(1)規(guī)則來解決，從而文法為SLR(1)文法。Sq1q2q3q40S2112R3R3R3R333R7S10R7S6454S7S85R5R56R6R67R18R7R7S699R4R41011R2R2R2R2SS→cAdS→AScA→cdA→A→SI3S→cdA→SbA→aS→cAdS→I5A→aAdA→AAScA→cdA→AAdS→bSAabcI11I10I5I4I3I7A→cdbbI2I9S→cAScS→AAAdS→bA→SbA→aSAabcdI11I10I5I4I3I14I10S→AAScS→AAAdS→bA→SbA→aSAabcdI11I10I5I4I3I13I11A→ASbbcI2I12I12A→AScI14S→cAd不同之處在于SLR(1)增加了在歸約的時候考慮向前符號a以解釋可能出現(xiàn)的“移進(jìn)——?dú)w約”沖突；SLR（1）的分析較稀疏些，原因是填寫歸約項(xiàng)時，并不是在一狀態(tài)對應(yīng)行上全部填寫歸約動作，而是考慮了相應(yīng)非終結(jié)符的FOLLOW集因素。SS→BAA→aB,a,bB→I2S→AAA→BAB→b,a,bABabI6I3I4I5I4B→aaB,a,bB→,a,bI6A→BA,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOabSAB0S4S5R31231ACC2R23S4S5R3634S4S575R5R5R56R27R4R4R4用 LR(1)分析表對輸入符號串a(chǎn)bab的分析過程：步驟狀態(tài)棧中符號余留符號分析動作下一狀態(tài)10ababS44204ababS553045ababR574047aBabR43503BabS446034BabS5570345BabR4780347BaBR439033BBR36100336BBAR2611036BAR211201AaccSS→AB,a,bA→I2S→AB,a,bB→b,a,bBabI3I5I4I3A→AB,a,bI5B→aaB,a,bB→,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOabSAB0R3R3R3121Acc2S5S4R13R2R2R24R5R5R55S5S466R4R4R4表中沒有多從定義的元素，所以文法是LR(1)文法。EE→T/+T→a/+ET(aI1I1I5I4I1E’ →E+T/++I2I2E→E+(E)/+T→/TI4T→aE)/+E→T)/+T→a+/)ECTaI7I8I9I12I6E→T)/+E→EE))/+E→T)/+T→a+/)(aETI8I12I14I9I9E→T/+I11E→E+(E)+/)T→+/)I13E→E+T)+/)E→E+/)LALR(1)分析：（合并同心集）狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0E’ →E+T/+E→(E)/+T→E→ET/+/）T→a/+/）T(aI3/I13I5/I8I4/I12I3/I13E→E+T+/)/I5/I8T→(E+T+/)E→(E)+/)T→+/)/I7/I14T→(E+T+/)+)I2/I11I10/I15I10/I15T→(E) 解： （1）求LR(1)項(xiàng)目集和狀態(tài)轉(zhuǎn)換圖：狀態(tài)項(xiàng)目集經(jīng)過的符號到達(dá)的狀態(tài)I0E’ →E+E,+,*E→i,+,*EiI1I2I1E’ →E+E,+,*E→E,+,*I3E→E+E+E,+,*E→i,+,*EiI5I2I4E→E*E+E,+,*E→i,+,*EiI6I2I5E→E+E+E,+,*E→E,+,*E→E*E,+,*+*I3I4依據(jù)以上圖求出該文法的LR(1)分析表知道由于項(xiàng)目I5,I6導(dǎo)致了有多重定義的元素，所以不是LR(1)文法。等價的LR(1)文法為：E→E+T|TF→T*F|FF→i。例如，假設(shè)表達(dá)式運(yùn)算滿足左結(jié)合律（即a+b+c=(a+b)+c而不是右結(jié)合律：