搜索
第7章LR分析练习P1651、已知文法A-aAd|aAb|ε判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。【解】(1)拓广文法(0)S-A(1)A-aAd(2)A-aAb(3)A-ε(2)构造识别活前缀的DFAFOLLOW(A)={d,b,#}对于状态I0：FOLLOW(A)∩{a}=Ф，对于状态I2：FOLLOW(A)∩{a}=Ф因为，在项目集规范族中无冲突的现象，所以该文法是SLR(1)文法。(3)SLR(1)分析表状态ACTIONGOTOabd#A0S2r3r3r311acc2S2r3r3r333S5S44r1r1r15r2r2r2(4)输入串ab#的分析过程步骤状态栈符号栈当前字符剩余字符串动作10#ab#S2移进202#ab#r3归约A-ε3023#aAb#S5，移进40235#aAb#r2，归约A-aAb501#A#接受3、考虑文法SAS|bASA|a(1)列出这个文法的所有LR(0)项目(3)这个文法是SLR（1）吗？若是，构造这个文法的SLR分析表。【解】[1]令拓广文法G’为[0]S’S[1]SAS[2]Sb[3]ASA[4Aa其LR(0)项目集规范族及识别该文法活前缀的DFA如下图所示：FOLLOW(S)={#,a,b}FOLLOW(A)={a,b}(3)因为I5中：FOLLOW（A）∩{a，b}≠Ф或I7中：FOLLOW（B）∩{a，b}≠Ф所以，该文法不是SLR（1）文法。7、证明下面文法是SLR（1）但不是LR（0）的。S-AA-Ab|bBaB-aAc|a|aAb【解】（一）拓广文法为：0）S’-S1）S-A2）A-Ab3）A-bBa4）B-aAc5)B-a6)B-aAb（二）构造其LR(0)项目集规范族及识别该文法活前缀的DFA如下图：【证明】因为I2、I5中存在移进-归约冲突，所以不是LR（0）I2中FOLLOW（S）={#}，{#}∩{b}=ФI5中FOLLOW（B）={a}{a}∩{b}=Ф因为I2、I5中的移进-归约冲突可以用SLR（1）解决，所以该文法是SLR（1）。11、设文法G[S]为：S→AS|εA→aA|b（1）证明G[S]是LR（1）文法；（2）构造它的LR（1）分析表；(3)给出输入串abab#的分析过程【解】1）对G[S]进行拓广：S’→S[0]S→AS[1]S→ε[2]A→aA[3]A→b[4]再构造其LR(1)项目集规范族DFA如下：FIRST(S)={a,b,#}由DFA可知，在I0-I6中都不存在移进--归约冲突和归约--归约冲突，故该文法是LR（1）文法。2）其LR（1）分析表：状态ACTIONGOTOab#SA0S3S4r2121acc2S3S4r2623S3S454r4r4r45r3r3r3【补充】6．文法G=({U，T，S}{a，b，c，d，e}，P，S)其中P为：S→UTa|TbT→S|Sc|dU→US|e(1)判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。(2)构造相应的分析表。【解】将文法拓广为G′如下：S′→SS→UTa|TbT→S|Sc|dU→US|e该文法的LR(0)项目集规范族为：I0：S′→.SS→.UTaS→.TbU→.USU→.eT→.ST→.ScT→.dI1：S′→S.T→S.T→S.cI2：S→U.TaT→.ST→.ScT→.dS→.UTaS→.TbU→.USU→.eU→U.SI3：S→T.bI4：U→e.I5：T→d.I6：T→Sc.I7：S→UT.aS→T.bI8：T→S.T→S.cU→US.I9：S→Tb.I10：S→UTa.与此相应的识别该文法活前缀的有限自动机如下图：不难看出I1和I8中存在移进-归约和归约-归约冲突,因此该文法不是LR(0)文法。在I1中：S′→S.T→S.T→S.cFOLLOW(S′)={#}FOLLOW(T)={a，b}FOLLOW(S′)∩FOLLOW(T)=ΦFOLLOW(S′)∩{c}=ΦFOLLOW(T)∩{c}=ΦI1中的冲突可以用SLR(1)方法解决。在I8中：T→S.T→S.cU→US.FOLLOW(T)={a，b}FOLLOW(U)={d，e}FOLLOW(T)∩FOLLOW(U)=ΦFOLLOW(T)∩{c}=ΦFOLLOW(U)∩{c}=ΦI8中的归约-归约和移进-归约冲突也可以用SLR(1)方法解决，因此该文法是SLR（1）。(2)由题意可得各非终结符的SELECT集如下：FIRST(S′)=FIRST(S)={e，d}FIRST(S)=FIRST(U)∪FIRST(T)={e}∪FIRST(T)∪{d}={e，d}FIRST(T)=FIRST(S)∪{d}={e，d}FIRST(U)=FIRST(U)∪{e}={e}由题意可得各非终结符的FOLLOW集如下：FOLLOW(S′)={#}FOLLOW(S)=FOLLOW(S′)∪FOLLOW(T)∪FOLLOW(U)∪{c}={#，a，b，c，d，e}FOLLOW(T)={a，b}FOLLOW(U)=FIRST(Ta)∪FIRST(S)=FIRST(T)∪FIRST(S)={e，d}∴根据以上构造的文法的LR(0)项目集规范族和计算出的所有非终结符的FOLLOW集。可以构造该文法的改进的SLR(1)分析表如下：abcde#STU0S5S41321r3r3S6acc2S5S48723S94r7r75r5r56r4r47S10S98r3r3S6r6r69r2r2r2r2r2r210r1r1r1r1r1r1文法是SLR（1），肯定是LALR（1）和LR（1）。