什么是 LALR (1) 解析器?

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

回到顶部