有关编译原理给定文法G[S]:S→SaA|aA→AbS|b（1）请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的（2）请构造该文法的LR(0)分析表（3）什么是LR(0)文法?该文法是LR(0)文法吗?为

Question

有关编译原理
给定文法G[S]:
S→SaA|a
A→AbS|b
（1）请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的
（2）请构造该文法的LR(0)分析表
（3）什么是LR(0)文法?该文法是LR(0)文法吗?为什么?
（4）什么是SLR(1)文法?该文法是SLR(1)文法吗?为什么?

Answer 1

⑴拓广文法 1 分
G[S ′ ]:S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ：
⑵ 该文法的 LR(0) 分析表：
状态 \x05ACTION \x05GOTO
\x05a \x05b \x05# \x05S \x05A
0 \x05S 2 \x05 \x05 \x051 \x05
1 \x05S 3 \x05 \x05acc \x05 \x05
2 \x05r 3 \x05r 3 \x05r 3 \x05 \x05
3 \x05 \x05S 5 \x05 \x05 \x054
4 \x05r 2 \x05r 2 /S 6 \x05r 2 \x05 \x05
5 \x05r 5 \x05r 5 \x05r 5 \x05 \x05
6 \x05S 2 \x05 \x05 \x057 \x05
7 \x05r 4 /S 3 \x05r 4 \x05r 4 \x05 \x05
⑶ LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态.
该文法不是 LR(0) 文法
因为存在冲突状态：I 4 和 I 7
⑷ SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态,冲突可用 FOLLOW 集解决.
该文法不是 SLR(1) 文法.
因为 FOLLOW(S)={a,b,#} ,所以无法解决冲突