构造LR(0)项目集规范族： 状态 0 项目集 S’→·S S→·AaAb S→·BbBa A→· B→· S’→S· S→A·aAb S→B·bBa S→Aa·Ab A→· S→Bb·Ba B→· S→AaA·b S→BbB·a S→AaAb· S→BbBa· 转换函数 GO[0，S]＝1 GO[0，A]＝2 GO[0，B]＝3 R3 R4 ACCEPT GO[2，a]＝4 GO[3，b]＝5 GO[4，A]＝6 R3 GO[5，B]＝7 R4 GO[6，b]＝8 GO[7，a]＝9 R1 R2 1 2 3 4 5 6 7 8 9 状态0存在“归约－归约”冲突，且FOLLOW(A) ＝｛a,b｝，FOLLOW(B)＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。
构造LR(1)项目集规范族： 状态 0 项目集 S’→·S，# S→·AaAb，# S→·BbBa，# A→·，a B→·，b S’→S·，# S→A·aAb，# S→B·bBa，# S→Aa·Ab，# A→·，b S→Bb·Ba，# B→·，a S→AaA·b，# S→BbB·a，# S→AaAb·，# S→BbBa·，# ACTION a R3 b R4 # S 1 转换函数 GO[0，S]＝1 GO[0，A]＝2 GO[0，B]＝3 R3 R4 ACCEPT GO[2，a]＝4 GO[3，b]＝5 GO[4，A]＝6 R3 GO[5，B]＝7 R4 GO[6，b]＝8 GO[7，a]＝9 R1 R2 GOTO A 2 B 3 1 2 3 4 5 6 7 8 9 LR(1)分析表： 状态 0
1 2 3 4 5 6 7 8 9 S4 R4 S9 S5 R3 S8 ACCEPT R1 R2 6 7 分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。
5.4 考虑以下的文法： E→EE＋ E→EE* E→a
（1）为这个文法构造LR(1)项目集规范族。 （2）构造LR(1)分析表。
（3）为这个文法构造LALR(1)项目集规范族。 （4）构造LALR(1)分析表。
（5）对输入符号串“aa*a+”进行LR(1)和LALR(1)分析。 解：
（1）拓广文法G[S]： 0：S→E 1：E→EE＋ 2：E→EE* 3：E→a
构造LR(1)项目集规范族： 状态 0 项目集 S→·E ，# E→·EE＋ ，a:# E→·EE* ，a:# E→·a ，a:# S→E· ，# E→E·E＋ ，a:# E→E·E* ，a:# E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→a· ，a:# E→EE·＋ ，a:# E→EE·* ，a:# E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ 转换函数 GO[0，E]＝1 GO[0，E]＝1 GO[0，E]＝1 GO[0，a]＝2 ACCEPT GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，a]＝4 R3 GO[3，＋]＝5 GO[3，*]＝6 GO[3，E]＝7 GO[3，E]＝7 GO[3，E]＝7 1 2 3
E→·EE* ，*:+ E→·a ，*:+ 4 5 6 7 E→a· ，*:+ E→EE＋· ，a:# E→EE*· ，a:# E→EE·＋ ，*:+ E→EE·* ，*:+ E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→EE＋· ，*:+ E→EE*· ，*:+ GO[3，E]＝7 GO[3，a]＝4 R3 R1 R2 GO[7，+]＝8 GO[7，*]＝9 GO[7，E]＝7 GO[7，E]＝7 GO[7，E]＝7 GO[7，E]＝7 GO[7，a]＝4 R1 R2 8 9
（2）构造LR(1)分析表 状态 0 1 2 3 4 5 6 7 8 9 ACTION ＋ S5 R3 S8 R1 R2 * S6 R3 S9 R1 R2 a S2 S4 R3 S4 R1 R2 S4 # ACCEPT R3 R1 R2 GOTO E 1 3 7 7
（3）构造LALR(1)项目集规范族: 状态 0 项目集 S→·E ，# E→·EE＋ ，a:# E→·EE* ，a:# E→·a ，a:# S→E· ，# E→E·E＋ ，a:# E→E·E* ，a:# E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→a· ，a:#:*:+ E→EE·＋ ，a:#:*:+ 转换函数 GO[0，E]＝1 GO[0，E]＝1 GO[0，E]＝1 GO[0，a]＝2 ACCEPT GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，a]＝2 R3 GO[3，＋]＝4 1 2 3
E→EE·* ，a:#:*:+ E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ 4 5 E→EE＋· ，a:#:*:+ E→EE*· ，a:#:*:+ GO[3，*]＝5 GO[3，E]＝3 GO[3，E]＝3 GO[3，E]＝3 GO[3，E]＝3 GO[3，a]＝2 R1 R2
（4）构造LALR(1)分析表。 状态 0 1 2 3 4 5 ACTION ＋ R3 S4 R1 R2 * R3 S5 R1 R2 a S2 S2 R3 S2 R1 R2 # ACCEPT R3 R1 R2 GOTO E 1 3 3 （5）对输入符号串“aa*a+”进行LR(1)分析: 步骤 1 2 3 4 5 6 7 8 9 10 11 状态栈 0 02 01 014 013 0136 01 014 013 0135 01 符号栈 # #a #E #Ea #EE #EE* #E #Ea #EE #EE+ #E 输入串 aa*a+# a*a+# a*a+# *a+# *a+# a+# a+# +# +# # # ACTION GOTO S2 R3 S4 R3 S6 R2 S4 R3 S5 R1 1 3 1 3 1 ACCEPT
对输入符号串“aa*a+”进行LALR(1)分析: 步骤 1 2 3 4 5 6 7 8 状态栈 0 02 01 012 013 0135 01 012 符号栈 # #a #E #Ea #EE #EE* #E #Ea 输入串 aa*a+# a*a+# a*a+# *a+# *a+# a+# a+# +# ACTION GOTO S2 R3 S2 R3 S5 R2 S2 R3 1 3 1 3
9 10 11 013 0134 01 #EE #EE+ #E +# # # S4 R1 1 ACCEPT
5.5 说明以下的文法是LR(1)文法，但不是LALR(1)文法。 S→aAd|bBd|aBe|bAe A→c B→c 解：
拓广文法： 0：S’→S 1：S→aAd 2：S→bBd 3：S→aBe 4：S→bAe 5：A→c 6：B→c
构造LR(1)项目集规范族 状态 0 项目集 S’→·S，# S→·aAd，# S→·bBd，# S→·aBe，# S→·bAe，# S’→S· ，# S→a·Ad，# S→a·Be，# A→·c，d B→·c，e S→b·Bd，# S→b·Ae，# A→·c，e B→·c，d S→aA·d，# S→aB·e，# A→c· ，d B→c· ，e S→bB·d，# S→bA·e，# A→c· ，e B→c· ，d S→aAd· ，# S→aBe· ，# 转换函数 GO[0，S]＝1 GO[0，a]＝2 GO[0，b]＝3 GO[0，a]＝2 GO[0，b]＝3 ACCEPT GO[2，A]＝4 GO[2，B]＝5 GO[2，c]＝6 GO[2，c]＝6 GO[3，B]＝7 GO[3，A]＝8 GO[3，c]＝9 GO[3，c]＝9 GO[4，d]＝10 GO[5，e]＝11 R5 R6 GO[7，d]＝12 GO[8，e]＝13 R5 R6 R1 R3 1 2 3 4 5 6 7 8 9 10 11