编译原理及实现课后答案.docVIP

5.1 考虑以下的文法： S→S;T|T T→a 为这个文法构造LR(0)的项目集规范族。 这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。 对输入串“a;a”进行分析。 解： （1）拓广文法G[S’]： 0：S’→S 1：S→S;T 2：S→T 3：T→a 构造LR(0)项目集规范族 状态 项目集 转换函数 0 S’→·S S→·S;T S→·T T→·a GO[0，S]＝1 GO[0，S]＝1 GO[0，T]＝2 GO[0，a]＝3 1 S’→S· S→S·;T ACCEPT GO[1，;]＝4 2 S→T· R2 3 T→a· R3 4 S→S;·T T→·a GO[4，T]＝5 GO[4，a]＝3 5 S→S;T· R1 （2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。LR(0)分析表如下： 状态 ACTION GOTO ； a # S T 0 S3 1 2 1 S4 ACCEPT 2 R2 R2 R2 3 R3 R3 R3 4 S3 5 5 R1 R1 R1 （3）对输入串“a;a”进行分析如下： 步骤 状态栈 符号栈 输入符号栈 ACTION GOTO 0 0 # a;a# S3 1 03 #a ;a# R3 2 3 02 #T ;a# R2 1 4 01 #S ;a# S4 5 014 #S; a# S3 6 0143 #S;a # R3 5 7 0145 #S;T # R1 1 8 01 #S # ACCEPT 5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。 S→A A→Ab|bBa B→aAc|a|aAb 解：文法G[S]： 0：S→A 1：A→Ab 2：A→bBa 3：B→aAc 4：B→a 5：B→aAb 构造LR(0)项目集规范族： 状态 项目集 转换函数 0 S→·A A→·Ab A→·bBa GO[0，A]＝1 GO[0，A]＝1 GO[0，b]＝2 1 S→A· A→A·b ACCEPT GO[1，b]＝3 2 A→b·Ba B→·aAc B→·a B→·aAb GO[2，B]＝4 GO[2，a]＝5 GO[2，a]＝5 GO[2，a]＝5 3 A→Ab· R1 4 A→bB·a GO[4，a]＝6 5 B→a·Ac B→a· B→a·Ab A→·Ab A→·bBa GO[5，A]＝7 R4 GO[5，A]＝7 GO[5，A]＝7 GO[5，b]＝2 6 A→bBa· R2 7 B→aA·c B→aA·b A→A·b GO[7，c]＝8 GO[7，b]＝9 GO[7，b]＝9 8 B→aAc· R3 9 B→aAb· A→Ab· R5 R1 状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。 状态5： FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ 状态9： FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ 状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下： 状态 ACTION GOTO a b c # A B 0 S2 1 1 S3 ACCEPT 2 S5 4 3 R1 R1 R1 4 S6 5 R4 S2 7 6 R2 R2 R2 7 S9 S8 8 R3 9 R5 R1 R1 R1 该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。 5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。 S→AaAb|BbBa A→ε B→ε 解：拓广文法G[S’]： 0：S’→S 1：S→AaAb 2：S→BbBa 3：A→ε 4：B→ε 构造LR(0)项目集规范族： 状态 项目集 转换函数 0 S’→·S S→·AaAb S→·BbBa A→· B→· GO[0，S]＝1 GO[0，A]＝2 GO[0，B]＝3 R3 R4 1 S’→S· ACCEPT 2 S→A·aAb GO[2，a]＝4 3 S→B·bBa GO[3，b]＝5 4 S→Aa·Ab A→· GO[4，A]＝6 R3 5 S→Bb·Ba B→· GO[5，B]＝7 R4 6 S→AaA·b GO[6，b]＝8 7 S→BbB·a GO[7，a]＝9 8 S→AaAb· R1 9 S→BbBa· R2 状态0存在“归约－归约”冲突，且FOLLOW(A) ＝｛a,b｝，FOLLOW(B)＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。 构造LR(1)项目集规范族： 状态 项目集 转换函数 0 S’→·S，# S→·Aa