3A.3.6 自底向上 - LR(1)、LALR

3.3.6.1 LR(1)项集定义

有的文法构建出来的 LR(0) 项集可能会存在移入、规约冲突,例如:

S -> L = R | R L -> * R | id R -> L

我们为该文法的增广文法构建两个项集闭包:

I0: S’ -> ·S S -> ·L = R S -> ·R L -> ·*R L -> ·id R -> ·L

I1: S -> L· = R R -> L·

可见在 I1 中,我们既可以通过项 R -> L· 进行规约,也可以根据项 S -> L· = R 进行移入操作。想要解决这种冲突,解析器就必须读取更多的上下文信息来辅助自己做决策:即向前查看(Look ahead)符号。如果输入的下一个符号是 =, 那么就继续移入,否则就进行规约。

为了让 Look ahead 的符号能够与项集中的项进行匹配,我们必须让项保存更多信息,也就是说我们必须让项更加“精细化”,Look ahead 将要查看多少个符号,就必须向项里面引入等量的额外分量,来形成新的映射关系。我们在这里仅讨论 LR(1), 所以还需要往项里面引入一个变量,用来表示终结符号。修改之后,之前的项 A -> α·β 变成了 [A -> α·β, a], 终结符号 a 表示该项合法的后继符号,即 Look ahead 符号为 a 时,该项才可能是一个可以应用的项。该类项称为 LR(1) 项,其集合称为 LR(1) 项集。

进一步思考可以发现在项 [A -> α·β, a] 中,如果 β 不为空,则符号 a 其实没有作用,因为此时只可能进行移入操作;只有对于形如 [A -> α·, a] 的项,如果下一个输入符号是 a 时,才能进行规约。由此可见引入 Look ahead 符号其实本质上是在协助判断是否可以进行规约,例如上面例子中,我们需要通过下一个符号来判断是否可以通过 R -> L· 进行规约。

3.3.6.2 规范LR(1)语法分析表

为了正确地构建文法的 LR(1) 项集族,我们需要先对用到的两个算法稍作修改:

  • Closure(I), 使用下述三重循环为项集 I 构建闭包项集:

    for (I 中每个项 [A -> α·Bβ, a]) for (文法中的每个产生式 B -> γ) for (First(βa) 中的每个终结符号 b) 将 [B -> ·γ, b] 加入到 I 中

    重复该循环直到没有新的项加入到 I 中为止

  • Goto(I, X) 所表示的项集闭包的构建算法如下:

    1. 初始化集合 K

    2. 对于 I 中每个项 [A -> α·Xβ, a], 将 [A -> αX·β, a] 加入到集合 K

    3. Closure(K) 即为 Goto(I, X) 的项集闭包

有了 Closure 与 Goto 算法,我们就可以为文法构建 LR(1) 项集族了:

  1. 给定文法 G, 创建其增广文法 G’, 令 C 为 G’ 的项集族,初始化为空集

  2. 令 I0 = {[S’ -> ·S, $]},将 Closure(I0) 加入 C 中

  3. 对于 C 中的每个项集 I, 对于 G’ 中的每个文法符号 X, 如果 GOTO(I, X) 不在 C 中,则将其加入其中

  4. 循环第 3 步,直到没有新的项集加入到 C 中为止

对比 LR(0) 的项集族算法,其实只有 I0 不一样。现在我们可以为给定文法 G 构造其 LR(1) 的语法分析表了,其算法如下:

  1. 求出增广文法 G’ 的项集族 C = {I0, I1, I2, … ,In},i 代表 Ii 所对应的状态

  2. 对于任意项集 Ii, 执行如下操作构造 Action 部分:

    1. 如果 [A -> α·aβ, b] 在 Ii 中,并且 Goto(Ii, a) = Ij, 则将 Action[i, a] 的动作设置为移入

    2. 如果 [A -> α·, a] 在 Ii 中,则将 Action[i, a] 的动作设置为规约

    3. 如果 [S’ -> S·, $] 在 Ii 中,则将 Action[i, $] 设置为“接受”

    如果上述步骤产生了冲突,则该文法就不是 LR(1) 文法,我们无法为其构建一个 LR(1) 分析表

  3. 对于任意项集 Ii, 执行如下操作构造 Goto 部分: 对于所有的非终结符号 A, 如果 GOTO(Ii, A) = Ij, 那么将 Goto[i, A] 设置为“状态转换到 j”

  4. 将语法分析表中第 2 步与第 3 步没有设置的条目设置为报错

通过该算法得到的语法分析表成为规范 LR(1) 语法分析表。整个算法的思路与 LR(0) 语法分析表的思想是一样的,区别在于为了匹配 Look ahead 符号,在项中引入了额外的分量使项集更加精细化,从而导致产生了更多的项集,这也正是使用 Look ahead 的目的:通过更多的上下文信息将 LR(0) 中有冲突的项集划分开来。

3.3.6.3 LALR语法分析表

规范LR(1) 语法分析表已经将如何利用 Look ahead 符号来辅助解析过程的思路表达得很充分了,但额外增加的状态数量导致了对空间的需求量显著增加,为了使其具备实践价值,我们必须想办法减少状态数量。

我们在构建规范LR(1) 语法分析表时,每一个状态都是有用的,所以我们不可能直接扔掉一些状态来减少分析表的状态数量,那么剩下的策略就只能是合并:在不产生冲突的情况下,将多个状态合并为一个。

如何确定可以合并哪些状态呢?

我们知道对于同一个文法,LR(1) 项集比 LR(0) 项集多的原因是前者引入了额外的分量:Look ahead 符号。再回顾一下 LR(1) 项的形式:[A -> α·β, a], 其中第一个分量是 LR(0) 项:A -> α·β,第二个分量是 LA 符号:a. 我们将 LR(1) 项集中仅由第一个分量组成的集合叫着 LR(1) 项集的核心(Core)。容易得出:任何一个 LR(1) 项集的核心,都有一个 LR(0) 项集与之对应。根据鸽巢原理:必定存在多个 LR(1) 项集的核心,与同一个 LR(0) 项集对应。

为什么 LR(1) 项集核心必定与一个 LR(0) 对应呢?

我们知道 LR(0) 项集所代表的意义是:当前情况下,所有可能的合法产生式集合,以及每个产生式当前所处的位置!这个意义不会因为我们向前查看了输入符号而发生改变,也就是说,在自底向上解析的过程中,在任意时刻,解析器当前状态所对应的那个项集,不管 LR(k) 中的 k 是多少,其项集核心都是一样的;LR(1) 多出来的项集是 LR(0) 项集中各个项与 Look ahead 符号组合形成的新状态,所以将 Look ahead 符号剔除之后,其必定与一个 LR(0) 项集对应。

唯一合理的假设是我们将核心相同的 LR(1) 项集合并成一个状态,但要注意一个问题是:合并之后的状态不能存在冲突。由此可以得到如下合并思路:对于任意 n 个核心相同的 LR(1) 项集,只要他们的移入、规约操作没有冲突,那么就可以将他们合并为一个 LR(1) 项集。通过该方式构建的语法分析表叫着 LALR 语法分析表,由于 LALR 分析表即利用了 LA 技术,又显著减少了状态数量,所以具备很好的实践价值。

最后更新于