编译原理:已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法
时间: 2023-06-20 13:04:32 浏览: 50
为了判断一个文法是否是 SLR(1) 文法,需要进行以下步骤:
1. 求出该文法的 FIRST 集合和 FOLLOW 集合;
2. 构造出该文法的 LR(0) 自动机;
3. 求出该文法的 ACTION 表和 GOTO 表;
4. 检查 ACTION 表和 GOTO 表是否满足 SLR(1) 文法的要求。
首先,我们求该文法的 FIRST 集合和 FOLLOW 集合:
FIRST(A) = {f, b}
FIRST(a) = {a}
FIRST(g) = {f, b}
FIRST(b) = {b}
FOLLOW(A) = {$, a}
FOLLOW(a) = {a}
FOLLOW(g) = {a}
FOLLOW(b) = {a}
接下来,我们构造该文法的 LR(0) 自动机:
状态 0:
A → .fAa
A → .fAg
A → .b
状态 1:
A → f.Aa
A → f.Ag
状态 2:
A → fA.a
A → fAg.
状态 3:
A → b.
状态 4:
S' → A.
根据 LR(0) 自动机,我们可以得到该文法的 ACTION 表和 GOTO 表:
ACTION | f | b | a | $
-------------------------------------
0 | s1 | | |
1 | s2 | | |
2 | r2 | r2 | s3 | r2
3 | r3 | r3 | r3 | r3
GOTO | A |
--------------
0 | 4 |
1 | |
2 | |
3 | |
根据 SLR(1) 文法的要求,对于 ACTION 表,对于任意一个状态 i 和任意一个终结符 a,如果 ACTION[i,a] 中既有移进项目,又有归约项目,那么就不是 SLR(1) 文法。但是,对于该文法的 ACTION 表,我们可以发现,只有状态 0 中有移进项目,其他状态都只有归约项目,不会出现移进-归约冲突,因此该文法是 SLR(1) 文法。