已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法
时间: 2023-06-18 12:05:43 浏览: 110
SLR(1).rar_SLR_SLR文法_slr(1)
5星 · 资源好评率100%
为了判断该文法是否是 SLR(1) 文法,需要构造 SLR(1) 分析表并检查是否存在冲突。
首先,构造该文法的 LR(0) 项目集规范族:
$I_0$:
A→•fAa
A→•fAg
A→•b
$I_1$:
A→f•Aa
A→f•Ag
$I_2$:
A→b•
$I_3$:
A→fA•a
A→fA•g
$I_4$:
A→f•a
A→f•g
$I_5$:
A→fAa•
A→fAg•
可以看到,该文法的 LR(0) 项目集规范族中不存在冲突的状态,因此该文法是 LR(0) 文法。
接下来,对每个 LR(0) 项目集 $I_i$,以及该项目集中每个项目所能看到的向前符号集合,构造对应的 SLR(1) 分析表中的项。
对于该文法,终结符号集合为 {a, b, f, g},非终结符号集合为 {A}。
构造 SLR(1) 分析表的过程如下:
- 对于每个 $I_i$,以及该项目集中每个项目所能看到的向前符号集合,构造对应的 ACTION 行和 GOTO 行。
- 如果存在一个项目 $A→α•aβ$,其中 $a$ 是一个终结符号,且 $A→α$ 在项目集 $I_i$ 中,则将 ACTION[i,a] 设置为 “移进 $I_j$” 的信息,其中 $I_j$ 是 $A→α•aβ$ 所在的项目集。如果 $A→α•aβ$ 在 $I_i$ 中是唯一的 $a$-项目,则 $I_j$ 也是唯一的。
- 如果存在一个项目 $A→α•$,且 $A→α$ 在项目集 $I_i$ 中,则对于 $I_i$ 中每个 $a$,将 ACTION[i,a] 设置为 “规约 $A→α$” 的信息。特别地,如果 $α$ 是空串,则对于 $I_i$ 中每个 $a$,将 ACTION[i,a] 设置为 “接受” 的信息。
- 如果存在一个非终结符号 $A$ 和一个终结符号 $a$,使得 $A→α•$ 在 $I_i$ 中,且 $A→α$ 后跟着一个项目 $B→β$,则将 GOTO[i,A] 设置为 $I_j$,其中 $I_j$ 是项目集 $I_k$,满足 $B→•β$ 在 $I_k$ 中,且 $A$ 是 $B→β•$ 中的符号。
按照上述方法构造 SLR(1) 分析表,得到的结果如下:
| | a | b | f | g |
|------|---------------|---------------|---------------|---------------|
| 0 | S5 | | S1 | S2 |
| 1 | | | S3 | S4 |
| 2 | R3 | R3 | R3 | R3 |
| 3 | S6 | | | |
| 4 | R1 / R2 | R1 / R2 | R1 / R2 | R1 / R2 |
| 5 | | | | |
| 6 | | | | |
其中,“S” 表示移进操作,“R” 表示规约操作。例如,ACTION[0,a] = S5 表示当状态为 0 且下一个输入符号为终结符号 a 时,应该执行移进操作并转移到状态 5。
可以发现,在状态 4 中存在 ACTION 表和 GOTO 表的冲突。具体来说,当下一个输入符号为 a 或 g 时,ACTION[4,a] 和 ACTION[4,g] 均为 R1/R2。因此,该文法不是 SLR(1) 文法。
阅读全文