编译原理:已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法
时间: 2023-06-20 12:04:31 浏览: 41
要判断该文法是否是 SLR(1) 文法,需要进行以下步骤:
1. 构造该文法的 LR(0) 自动机;
2. 对于每个 LR(0) 项集,计算它的闭包和转移;
3. 根据 LR(0) 自动机构造 SLR(1) 分析表。
具体步骤如下:
1. 构造该文法的 LR(0) 自动机:
| 0 | A' → ·A
| 1 | A → ·fAa
| 2 | A → ·fAg
| 3 | A → ·b
| 4 | A → fA·a
| 5 | A → fA·g
初始状态为 {0},通过对状态进行闭包和转移,得到如下 LR(0) 自动机:
状态 | 闭包 | 转移
-----|-------------------|-----
0 | A' → ·A | goto 1
| A → ·fAa |
| A → ·fAg |
| A → ·b |
1 | A' → A· |
| A → f·Aa | goto 2
| A → f·Ag | goto 3
| A → ·fAa |
| A → ·fAg |
| A → ·b |
2 | A → fA·a | goto 4
3 | A → fA·g | goto 5
4 | A → fAa· | reduce by A → fAa
| A → ·fAa |
| A → ·fAg |
| A → ·b |
5 | A → fAg· | reduce by A → fAg
| A → ·fAa |
| A → ·fAg |
| A → ·b |
2. 对于每个 LR(0) 项集,计算它的闭包和转移:
LR(0) 项集 {0} 的闭包为 {A' → ·A, A → ·fAa, A → ·fAg, A → ·b},它的转移符号为 f 和 b。
LR(0) 项集 {1} 的闭包为 {A' → A·, A → f·Aa, A → f·Ag, A → ·fAa, A → ·fAg, A → ·b},它的转移符号为 a 和 g。
LR(0) 项集 {2} 的闭包为 {A → fA·a},它没有可进行的转移。
LR(0) 项集 {3} 的闭包为 {A → fA·g},它没有可进行的转移。
LR(0) 项集 {4} 的闭包为 {A → fAa·, A → ·fAa, A → ·fAg, A → ·b},它的转移符号为 f 和 b。
LR(0) 项集 {5} 的闭包为 {A → fAg·, A → ·fAa, A → ·fAg, A → ·b},它的转移符号为 f 和 b。
3. 根据 LR(0) 自动机构造 SLR(1) 分析表:
对于 LR(0) 项集 {0},有:
| | f | b |
|---|---|---|
| A | 1 | |
对于 LR(0) 项集 {1},有:
| | a | g |
|---|---|---|
| A | 2 | 3 |
对于 LR(0) 项集 {4},有:
| | f | b |
|---|---|---|
| A | | 6 |
对于 LR(0) 项集 {5},有:
| | f | b |
|---|---|---|
| A | | 7 |
其中,状态 6 表示使用产生式 A → fAa 进行规约,状态 7 表示使用产生式 A → fAg 进行规约。由于状态 6 和 7 在输入符号为 a 和 g 时都会进行规约操作,会导致冲突,因此该文法不是 SLR(1) 文法。