第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
编译原理课后第五章答案.doc
5.1 考虑以下的文法：
S→S;T|T
T→a
（1） 为这个文法构造 LR(0)的项目集规范族。
（2） 这个文法是不是 LR(0)文法？如果是，则构造 LR(0)分析表。
（3） 对输入串“a;a”进行分析。
解：
（1）拓广文法 G[S’]：
0：S’→S
1：S→S;T
2：S→T
3：T→a
构造 LR(0)项目集规范族
状态
0
1
2
3
4
5
项目集
S’→·S
S→·S;T
S→·T
T→·a
S’→S·
S→S·;T
S→T·
T→a·
S→S;·T
T→·a
S→S;T·
转换函数
GO[0，S]＝1
GO[0，S]＝1
GO[0，T]＝2
GO[0，a]＝3
ACCEPT
GO[1，;]＝4
R2
R3
GO[4，T]＝5
GO[4，a]＝3
R1
（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是 LR(0)文法。LR(0)分析
表如下：
状态
0
1
2
3
4
5
；
S4
R2
R3
R1
ACTION
GOTO
a
S3
R2
R3
S3
R1
#
ACCEPT
S
1
R2
R3
R1
T
2
5
（3）对输入串“a;a”进行分析如下：
步骤
状态栈
符号栈
输入符号栈 ACTION
GOTO
0
1
3
0
03
02
#
#a
#T
a;a#
;a#
;a#
S3
R3
R2
2
1
4
5
6
7
8
01
014
0143
0145
01
#S
#S;
#S;a
#S;T
#S
;a#
a#
#
#
#
S4
S3
R3
R1
ACCEPT
5
1
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
1
2
3
4
5
6
7
8
9
项目集
S→·A
A→·Ab
A→·bBa
S→A·
A→A·b
A→b·Ba
B→·aAc
B→·a
B→·aAb
A→Ab·
A→bB·a
B→a·Ac
B→a·
B→a·Ab
A→·Ab
A→·bBa
A→bBa·
B→aA·c
B→aA·b
A→A·b
B→aAc·
B→aAb·
A→Ab·
转换函数
GO[0，A]＝1
GO[0，A]＝1
GO[0，b]＝2
ACCEPT
GO[1，b]＝3
GO[2，B]＝4
GO[2，a]＝5
GO[2，a]＝5
GO[2，a]＝5
R1
GO[4，a]＝6
GO[5，A]＝7
R4
GO[5，A]＝7
GO[5，A]＝7
GO[5，b]＝2
R2
GO[7，c]＝8
GO[7，b]＝9
GO[7，b]＝9
R3
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)分析表如下：
状态
0
1
2
3
4
5
6
7
8
9
ACTION
GOTO
B
4
A
1
7
a
S5
S6
R4
R3
R5
b
S2
S3
R1
S2
R2
S9
c
#
ACCEPT
R1
R1
R2
R2
S8
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
1
2
3
4
项目集
S’→·S
S→·AaAb
S→·BbBa
A→·
B→·
S’→S·
S→A·aAb
S→B·bBa
S→Aa·Ab
转换函数
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
5
6
7
8
9
A→·
S→Bb·Ba
B→·
S→AaA·b
S→BbB·a
S→AaAb·
S→BbBa·
R3
GO[5，B]＝7
R4
GO[6，b]＝8
GO[7，a]＝9
R1
R2
状态 0 存在“归约－归约”冲突，且 FOLLOW(A) ＝｛a,b｝，FOLLOW(B)＝｛a,b｝，即 FOLLOW(A)
∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是 SLR(1)文法。
构造 LR(1)项目集规范族：
状态
0
1
2
3
4
5
6
7
8
9
项目集
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·，#
LR(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
状态
0
1
2
3
4
5
6
7
8
9
ACTION
GOTO
b
R4
S5
R3
S8
a
R3
S4
R4
S9
#
ACCEPT
S
1
A
2
6
B
3
7
R1
R2
分析表无重定义，说明该文法是 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
1
2
3
4
5
6
7
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＋ ，*:+
E→·EE* ，*:+
E→·a ，*:+
E→a· ，*:+
E→EE＋· ，a:#
E→EE*· ，a:#
E→EE·＋ ，*:+
E→EE·* ，*:+
E→E·E＋ ，*:+
E→E·E* ，*:+
E→·EE＋ ，*:+
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
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
E→·a ，*:+
E→EE＋· ，*:+
E→EE*· ，*:+
8
9
GO[7，a]＝4
R1
R2
（2）构造 LR(1)分析表
ACTION
GOTO
#
ACCEPT
R3
R1
R2
a
S2
S4
R3
S4
R1
R2
S4
E
1
3
7
7
状态
＋
*
0
1
2
3
4
5
6
7
8
9
S5
R3
S8
R1
R2
S6
R3
S9
R1
R2
（3）构造 LALR(1)项目集规范族:
状态
项目集
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 ，*:+
转换函数
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
0
1
2
3
4
5
E→a· ，a:#:*:+
R3
E→EE·＋ ，a:#:*:+
E→EE·* ，a:#:*:+
E→E·E＋ ，*:+
E→E·E* ，*:+
E→·EE＋ ，*:+
E→·EE* ，*:+
E→·a ，*:+
E→EE＋· ，a:#:*:+
E→EE*· ，a:#:*:+
GO[3，＋]＝4
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)分析表。
状态
ACTION
GOTO
＋
*
R3
S4
R1
R2
R3
S5
R1
R2
a
S2
S2
R3
S2
R1
R2
#
ACCEPT
R3
R1
R2
E
1
3
3
0
1
2
3
4
5
（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+”进行 LALR(1)分析:
步骤
状态栈
符号栈
1
2
3
4
5
6
7
8
9
10
11
0
02
01
012
013
0135
01
012
013
0134
01
#
#a
#E
#Ea
#EE
#EE*
#E
#Ea
#EE
#EE+
#E
输入串
aa*a+#
a*a+#
a*a+#
*a+#
*a+#
a+#
a+#
+#
+#
#
#
输入串
aa*a+#
a*a+#
a*a+#
*a+#
*a+#
a+#
a+#
+#
+#
#
#
5.5 说明以下的文法是 LR(1)文法，但不是 LALR(1)文法。
S→aAd|bBd|aBe|bAe
A→c
B→c
解：
拓广文法：
0：S’→S
ACTION
GOTO
S2
R3
S4
R3
S6
R2
S4
R3
S5
R1
1
3
1
3
1
ACCEPT
ACTION
GOTO
S2
R3
S2
R3
S5
R2
S2
R3
S4
R1
ACCEPT
1
3
1
3
1
1：S→aAd
2：S→bBd
3：S→aBe
4：S→bAe
5：A→c
6：B→c
构造 LR(1)项目集规范族
状态
0
1
2
3
4
5
6
7
8
9
10
11
12
13
项目集
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· ，#
S→bBd· ，#
S→bAe· ，#
转换函数
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
R2
R4
构造 LR(1)分析表：
状态
0
1
2
3
ACTION
c
d
e
#
a
S2
b
S3
ACCEPT
S6
S9
S
1
GOTO
A
4
8
B
5
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
