什么是 LALR(1) 解析器？

LALR 解析器是前瞻 LR 解析器。它的功能介于 SLR 和 CLR 解析器之间。它是 CLR 解析器的压缩版本，因此由此获得的表格将比 CLR 解析表更小。

在这里，首先，我们将构建 LR(1) 项目。接下来，我们将查找具有相同第一个组成部分的项目，并将它们合并以形成单个项目集。这意味着状态具有相同的第一个组成部分，但不同的第二个组成部分可以集成到单个状态或项目中。

例如。

假设如果

I4: C → d ∙ , c | d

I7: C → d ∙ , $

这两个项目或状态 (I4 和 I7) 具有相同的第一个组成部分，即 d ∙ ，但第二个组成部分不同，即 I4 中的 c | d 和 I7 中的 $。

∴ 这些状态可以合并为

I47: C → d ∙ , c |d | $

LALR 解析表的构造

算法

输入 - 增广文法 G′

输出 - LALR 解析表

方法

  • 构造 LR(1) 项目集，即构造

    C = {I0, I1, I2 … . . In}

  • 选择具有相同核心或第一个组成部分的相似状态，并将它们合并为一个。

    令 C′ = {J0, J1, J2 … . . Jm} 为结果集。

  • 为状态 J1 构造解析动作，类似于 CLR 构造。如果解析表中存在冲突，则可以认为该算法无法生成 LALR 解析器。

  • 构造 goto 动作如下。

令 goto [J,∗] = K，其中 J 是 C 的一个或多个状态的并集。

即，J = I1 ∪ I2 … .∪ Im，则

则 K = goto (I1,∗) ∪ goto (I2,∗) … .∪ goto (Im,∗)

LALR 解析器的运作


LALR 文法 - 如果 LALR 解析表中没有多个表示的条目，则该文法被称为 LALR(1) 或 LALR 文法。

更新于: 2021 年 11 月 2 日

4K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告