什么是 LALR (1) 解析器？

  • Z时代
  • 2024-01-10
  • 分类：综合

LALR Parser 是 Look Ahead LR Parser。它介于 SLR 和 CLR 解析器之间。它是 CLR Parser 的压缩，因此在此获得的表将小于 CLR Parsing Table。

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

例如。

假设如果

I 4 : C → d ∙ , c | d

我7 : C → d ∙ , $

两个项目或状态（I 4和 I 7）具有相同的第一个分量，即 d ∙ ，但具有不同的第二个分量，即 c | d 在 I 4和 $在 I 7。

∴ 这些状态可以合并得到

I 47 : C → d ∙ , c |d | $

LALR解析表的构建

算法

输入- 增强语法 G'

输出- LALR 解析表

方法

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

    C = {我0 , 我1 , 我2 .... . } _ _

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

    令 C′ = {J 0 , J 1 , J 2 .... . J m } 是结果集。

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

  • 如下构造 goto 动作。

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

即，J = I 1 ∪ I 2 … .∪ I m，则

那么 K = goto (I 1 ,∗) ∪ goto (I 2 ,∗) ... .∪ goto (I m ,∗)

LALR解析器的工作


LALR Grammar - LALR 解析表没有多重表示的条目的语法被称为 LALR (1) 或 LALR 语法。

以上是 什么是 LALR (1) 解析器？ 的全部内容， 来源链接： utcz.com/z/363389.html

回到顶部