检查使用示例中构建的 SLR 分析表，字符串 id * id + id 是否被接受。

解决方案

最初，LR 分析器处于状态 0。

在字符串末尾添加 $，即 id * id + id $。

栈输入字符串原因
0id ∗ id + id $Action [0, id] = s5 ∴ 移入 id 和状态 5
0 id 5∗ id + id $Action [5,∗] = r6. ∴ 根据 F → id 进行归约。goto(0, F) = 3
0 F 3∗ id + id $Action [3,∗] = r4, 根据 T → F 进行归约。goto(0, T) = 2
0 T 2∗ id + id $Action [2,∗] = s7, 移入 ∗，7
0T2*7id + id $Action [7, id] = s5, 移入 id，5
0T2*7 id 5+id $Action [5, +] = r6, 根据 F → id 进行归约。goto(7, F) = 10
0T2*7 F 10+id $Action [10, +] = r3S, 根据 T → T ∗ F 进行归约，goto(0, T) = 2
0 T 2+id $Action [2, +] = r2, 根据 E → T 进行归约。goto(0, E) = 1
0 E 1+id $Action [1, +] = s6, 移入 +，6
0 E 1 + 6id $Action [6, id] = s5, 移入 id，5。
0 E 1 + 6 id 5$Action [5, $] = s6, 根据 F → id 进行归约，goto(6, F) = 3
0 E 1 + 6 F 3$Action [3, $] = r4, 根据 T → F 进行归约，goto(6, F) = 9
0 E 1 + 6 T 9$Action [9, $] = r1, 根据 E → E + T 进行归约，goto(0, E) = 1
0 E 1$Action [1, $] = accept

在第一行，栈顶为 0，要处理的符号为 id。因此，检查第 0 行和 id 列，即 Action [0, id] = s5，即从字符串中移入 id 和状态 5 到栈中。

在第二行，Action [5, *] = r3 表示根据产生式编号 6（即 F → id）进行归约。从栈中弹出 id 并压入 F。然后查看 goto (0, F) = 3，所以将 3 压入栈中。在第七行，Action [10, +] = r3，即根据产生式编号 3（即 T → T ∗ F）进行归约。

从栈中弹出T2 * 7F10，将 T 压入栈中。然后查看 goto [0, T] = 2。所以，将 2 压入栈中。在最后一行，Action [1, $] = accept。这意味着分析器将接受该字符串。

SLR 分析表的算法

SLR 分析表有两个部分

  • Action（动作）
  • goto（转移）

可以使用以下算法填充 Action 和 goto 表：

算法

输入 - 增广文法 G′

输出 - SLR 分析表

方法

  • 最初构造一组项目

             C = {I0, I1, I2 … … In}，其中 C 是文法的 LR (0) 项目集。

  • 解析动作基于每个项目或状态 I1。

各种动作如下：

  • 如果 A → α ∙ a β 存在于 Ii 中，并且 goto (Ii, a) = Ij，则设置 Action [i, a] = shift j”。
  • 如果 A → α ∙ 存在于 Ii 中，则对所有符号 a 设置 Action [i, a] 为“reduce A → α”，其中 a ∈ FOLLOW (A)。
  • 如果 S′ → S ∙ 存在于 Ii 中，则动作表 Action [i, $] 中的条目为“accept”。
  • SLR 表的 goto 部分可以填充如下：状态 i 的 goto 转移仅考虑非终结符。如果 goto (Ii, A) = Ij，则 goto [i, A] = j
  • 所有未由规则 2 和 3 定义的条目都被视为“错误”。

更新于：2021 年 11 月 8 日

2K+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告