原创力文档- 1、本文档共7页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
第７章LR分析
1．文法A→aAd|aAb|ε
判断该文法是否是SLR(1)文法，假设是构造相应分析表，并对输入串ab#给出分析过程。
答案：文法：A→aAd|aAb|ε
拓广文法为G′，增加产生式S′→A
假设产生式排序为：
0S→A
1A→aAd
2A→aAb
3A→ε
由产生式知：
First(S)={ε,a}
First(A)={ε,a}
Follow(A)={d,b,#}
G′的LR(0)工程集标准族及识别活前缀的DFA如以下图所示：
在I0中：A→.aAd和A→.aAb为移进工程，A→.为归约工程，存在移进-归约冲突，因此所给文法不是LR(0)文法。
在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=φ
所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。
构造的SLR(1)分析表如下：题目1的SLR(1)分析表
对输入串ab#的分析过程
10.判断以下各题所示文法是否为ＬＲ类方法，假设是请说明是LR(0),SLR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，假设不是请说明理由．
〔３〕S-aAd|eBd|aBr|eAr
A-a
B-a
答案：
１〕列出扩展文法Ｇ＇的产生式列表：
(0)S＇-S
(1)S-aAd
(2)S-eBd
(3)S-aBr
(4)S-eAr
(5)A-a
(6)B-a
2〕Ｇ＇的LR(0)工程集族及识别活前缀的DFA如以下图所示：
B
B
I0:
S＇-.S
S-.aAd
S-.eBd
S-.aBr
S-.eAr
I1:
S＇-S.
I2:
S-a.Ad
S-a.Br
A-.a
B-.a
I3:
S-e.Bd
S-e.Ar
B-.a
A-.a
S
a
e
I4:
S-aA.d
I5:
S-aB.r
I6:
A-a.
B-a.
A
B
a
I7:
S-eB.d
I8:
S-eA.r
A
a
I9:
S-aAd.
d
I10:
S-aBrd.
r
I11:
S-eBd.
d
I12:
S-eAr.
r
从上图中看出工程集I6中存在归约-归约冲突，所以该文法不是LR(0)文法。
下面判断是否为SLR(1)文法：
Follow(S)={#}
Follow(A)={d,r}
Follow(B)={d,r}
对于I6，Follow(A)∩Follow(B)={d,r}不为φ，所以工程集I6中的归约-归约冲突不能消除，该文法不是SLR(1)文法。
下面判断是否为LR(1)文法，在上面的工程集标准族中参加搜索符：B
B
I0:
S＇-.S,#
S-.aAd,#
S-.eBd,#
S-.aBr,#
S-.eAr,#
I1:
S＇-S.,#
I2:
S-a.Ad,#
S-a.Br,#
A-.a,d
B-.a,r
I3:
S-e.Bd,#
S-e.Ar,#
B-.a,d
A-.a,r
S
a
e
I4:
S-aA.d,#
I5:
S-aB.r,#
I6:
A-a.,d
B-a.,r
A
B
a
I7:
S-eB.d,#
I8:
S-eA.r,#
A
a
I9:
S-aAd.,#
d
I10:
S-aBr.,#
r
I11:
S-eBd.,#
d
I12:
S-eAr.,#
r
I13:
B-a.,d
A-a.,r
从上图可以看出原来存的的归约-归约冲突已经消除，所以该文法为LR(1)文法。
但假设合并同心工程集I6和I13，那么归约-归约冲突又会重现，因此该文法不是LALR(1)文法。
3)LR(1)分析表
Action
Goto
State
aedr#
SAB
0
S2S3
1
1
acc
2
S6
45
3
S13
87
4
S9
5
S10
6
R5R6
7
S11
8
S12
9
R1
10
R3
11
R2
12
R4
13
R6R5
11.设文法G[S]为：
S-AS|ε
A-aA|b
证明G[S]是LR[1]文法;
扩展文法G’为：
S’-S
S-A
文档评论（0）