第章LR分析.docVIP

第7章 LR分析 练习 P165 1、已知文法 A-aAd| aAb|ε 判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。 【解】 (1)拓广文法 (0)S-A (1) A-aAd (2)A- aAb (3)A-ε (2)构造识别活前缀的DFA FOLLOW(A)={d,b,#} 对于状态I0：FOLLOW(A)∩{a}=Ф ，对于状态I2：FOLLOW(A)∩{a}=Ф 因为，在项目集规范族中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表 状态 ACTION GOTO a b d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)输入串ab#的分析过程 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 1 0 # a b# S2移进 2 02 #a b # r3归约A-ε 3 023 #aA b # S5，移进 4 0235 #aAb # r2，归约A- aAb 5 01 #A # 接受 3、考虑文法S?A S | b A ? S A | a (1)列出这个文法的所有LR(0)项目 (3)这个文法是SLR（1）吗？若是，构造这个文法的SLR分析表。 【解】 [1]令拓广文法G’为 [0]S’ ? S [1]S ? A S [2]S ? b [3]A ? S A [4A ? a 其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-A A-Ab|bBa B-aAc|a|aAb 【解】 （一）拓广文法为： 0）S’-S 1） S-A 2） A-Ab 3）A-bBa 4） B-aAc 5) B-a 6) 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）分析表： 状 态 ACTION GOTO a b # S A 0 S3 S4 r2 1 2 1 acc 2 S3 S4 r2 6 2 3 S3 S4 5 4 r4 r4 r4 5 r3 r3 r3 【补充】 6．文法G= ({U，T，S}{a，b，c，d，e}，P，S) 其中P为： S→UTa|Tb T→S|Sc|d U→US|e (1)判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。 (2)构造相应的分析表。 【解】将文法拓广为G′如下： S′→S S→UTa|Tb T→S|Sc|d U→US|e 该文法的LR(0)项目集规范族为： I0：S′→.S S→ .UTa S→.Tb U→.US U→.e T→.S T→.Sc T→.d I1：S′→S. T→S. T→S.c I2：S→ U.Ta T→.S T→.Sc T→.d S→ .UTa S→.Tb U→.US U→.e U→U.S I3： S→T.b I4：U→e. I5：T→d. I6：T→Sc. I7：S→ UT.a S→T.b I8：T→S. T→S.c U→US. I9：S→Tb. I10：S→ UTa. 与此相应的识别该文法活前缀的有限自动机如下图： 不难看出I1