5 LR 分析

LR 分析概述

  前面讲述的是自顶向下的语法分析，而 LR 分析则是一类自底向上的语法分析。LR 分析是一个比较广泛的概念，包括 LR（0），SLR（1），LR（1），LALR（1）等分析法。

根据分析表进行移进-归约处理

  所有的这些 LR 分析都是首先构造一个分析表，然后根据分析表对某一句子进行移进-规约的。分析表的一个示例可以参见表3。

表3 LR 分析构造的分析表示例

	ACTION						GOTO
	$a$	$c$	$e$	$b$	$d$	$\#$	$S$	$A$	$B$
$0$	$S2$								$1$
$1$					$\mathit{acc}$
$2$				$S4$				$3$
$3$	$S5$			$S6$
$4$	$r2$	$r2$	$r2$	$r2$	$r2$	$r2$
$5$					$S8$				$7$
$6$	$r3$	$r3$	$r3$	$r3$	$r3$	$r3$
$7$				$S9$
$8$	$r4$	$r4$	$r4$	$r4$	$r4$	$r4$
$9$	$r1$	$r1$	$r1$	$r1$	$r1$	$r1$

移进-规约算法的流程也比较机械。维护一个二元组栈 $S$，初始有元素 $(0,\#)$。记 $(q,a)$ 为栈顶元素，接下来反复从词法分析部分中获取一个 token $a$，执行下面的操作：

• 如果 $\operatorname{ACTION}[q,a]=S _ j$，说明应该移进状态 $j$ 了。此时 $(j,a)$ 压栈 $S$。
• 如果 $\operatorname{ACTION}[q,a]=r _ i$，说明应该使用产生式 $i$ 进行归约了，此时分两步：
  1. 记产生式 $i$ 是 $A\to\alpha$，那么将 $|\alpha|$ 个状态和符号弹出分析栈 $S$。
  2. 如果 $\operatorname{GOTO}[q,A]$ 为空，报错；否则 $(\operatorname{GOTO}[q,A],A)$ 压入分析栈 $S$。
• 如果 $\operatorname{ACTION}[q,a]$ 为空，报语法错误。
• 如果 $\operatorname{ACTION}[q,a]=\mathit{acc}$，接受该符号串，结束算法。

反复执行上面操作，最终要么接受，要么报错。

如何构造分析表

  这个主要是通过构造识别活前缀的 DFA 来实现的。先介绍一下一些概念：

• 前缀：任意符号串 $\alpha$ 的含有头符号的子串称为 $\alpha$ 的前缀。这个定义还是非常直观易理解的。注意空串 $\varepsilon$ 为任意串的前缀。
• 可归前缀：文法 $G[S]$ 中，如果 $S\stackrel{*}{\Rightarrow}\alpha A\omega\Rightarrow \alpha\beta\omega$ 是句型 $\alpha\beta\omega$ 的规范推导（也即最右推导），则 $\alpha\beta$ 称为可归前缀，$\alpha\beta$ 的前缀称为活前缀。

有了上面的概念，接下来是如何构造这种识别活前缀的 DFA。假设文法为 $G=(V _ N,V _ T,P,S)$，主要步骤分为以下 $4$ 步：

1. 等价改写文法 $G$ 为 $G^\prime$，其中 $G^\prime=(V _ N\cup\lbrace S^\prime\rbrace,V _ T,P\cup\lbrace S^\prime\to S\rbrace,S^\prime)$，且有 $V _ N\cap\lbrace S^\prime\rbrace=\varnothing$。用人话说，就是找一个原来文法的非终结符集中没有的新非终结符 $S^\prime$，这个非终结符可以推导出 $S$，并把这一产生式加入原文法。文法的起始符号也变成了这个 $S^\prime$。

   

2. 为每个规则 $A\to\alpha$ 构造一个 NFA $M:A\to\alpha$。大可以回顾之前NFA↔正规文法中的内容，只不过我们这里 NFA 的边上也可以是非终结符了。用形式化的语言来说，令 $\alpha=x _ 1x _ 2\cdots x _ n$，则增加 $n + 1$ 个状态 $q _ 1,\cdots,q _ {n+1}$，其中 $f(q _ i,x _ i)=\lbrace q _ {i+1}\rbrace(1\leq i\leq n)$，且 $q _ 1,q _ {n+1}$ 分别是开始状态、结束状态。

   

3. 把所有的 NFA 合并为一个 NFA。具体地，在某一条规则 $A\to\alpha$ 的 NFA 中，有一个 $f(q,B)=\lbrace p\rbrace(B\in V _ N)$ 的转换，那么找到所有以 $B$ 为左部的产生式对应的 NFA 的开始状态集合 $\lbrace q _ 1,q _ 2,\cdots,q _ k\rbrace$，增加转换边 $f(q,\varepsilon)=q _ i(i=1,2,\cdots,k)$。最后仅保留 $S^\prime\to S$ 这一产生式的 NFA 的开始状态作为整个 NFA 的开始状态。

   

4. 使用子集构造法将其转换为 DFA，然后再使用分隔法把这个 DFA 最小化，就可以得到最终的识别活前缀的 DFA。

可识别活前缀的 DFA 所存在的问题

  实际上，对于上文中这个文法 $G^\prime[S^\prime]$ 的例子，我们先是构造了一个含有 $6$ 个 NFA 的状态图。其中每一个 NFA 的终态都对应一个产生式。比如状态 $1$ 代表产生式 $0$，状态 $10$ 代表产生式 $3$。这两个状态，在 NFA 确定化、最小化的过程中，可能变成同一个状态，那么此时识别活前缀的 DFA 就出现问题：走到这一个状态，应该使用哪个产生式进行归约呢？
  虽然所有的上下文无关文法都可以构造一个识别活前缀的 DFA，但是这个 DFA 未必是有用的，可能存在归约-归约冲突（或者移进-归约冲突等），存在冲突时，这个 DFA 就对我们帮助不大。因此，我们需要定义几种优良的文法，以有效使用构造活前缀的 DFA。LR 分析的每一种分析法，就对应一种这样的优秀文法。

注意所对应的这些 LR 文法都是无二义性的。

不同的 LR 文法及其分析

LR（0）文法及其分析

  在 LR（0）分析中，识别活前缀的 NFA 的状态不用数字来表示，而是用 LR（0）项目集规范族。比如上面的那个文法例子中，状态 $2$ 用 $\cdot aAcBe$ 表示，状态 $5$ 用 $aAc\cdot Be$ 表示。这样我们最后得到的识别活前缀的 DFA，其中的状态就不会是一些不明所以的数字，而是一些 LR（0）项目的集合。
  使用这个 LR（0）项目集还有一个好处，就是可以直接徒手搓识别活前缀的 DFA，而不需要上述一系列繁琐的步骤。具体来说，步骤是这样的：

1. 初始状态 $I _ 0$ 包含一个 $S^\prime\to\cdot S$。

2. Closure 操作：对于未完全确定的 $I _ i$，确定之（实际上就是求 $I _ i$ 的闭包）。具体来说是这样，找到 $I _ i$ 里面的“$\cdot$”之后的所有非终结符 $\lbrace A _ j\rbrace$，那么把左部在 $\lbrace A _ j\rbrace$ 中的所有产生式都加进来。一直到 $I _ i$ 中的项目不再新增了，$I _ i$ 就算是完全确定了。(1)

   1. Closure 操作用数学化的语言描述如下。
      1. 一开始 $\operatorname{Closure}(I _ i)= I _ i$。
      2. 将 $\lbrace[B\to\cdot\gamma] | [A\to\alpha\cdot B\beta]\in\operatorname{Closure}(I _ i)\rbrace$ 并入 $\operatorname{Closure}(I _ i)$。
      3. 重复上一步，直到 $\operatorname{Closure}(I _ i)$ 不再变化，计算完成。

3. Move 操作：对于完全确定的状态 $I$，考虑这个状态有哪些出边。很显然 $I$ 的项目集中，所有“$\cdot$”之后的终结符、非终结符都可以作为出边。至于边指向的状态中应该有哪些项目，其实就是把 $I$ 中的项目往后移一个这样的符号。(1)

   1. Move 操作也可以用数学化的语言描述，有 $$\operatorname{Move}(I,X)=\lbrace[A\to\alpha X\cdot\beta]|[A\to\alpha\cdot X\beta]\in I\rbrace$$

      其中这个 $X$ 可以是终结符，也可以是非终结符。

   比如边上是 $a$，那么出边指向的状态中，应包含 $I$ 中那些“$\cdot$”后为 $a$ 的项目，这个点移到 $a$ 后面的结果。

一直重复上面的步骤，直到状态不再新增、所有状态均已完全确定，这个识别活前缀的 DFA 就算构造好了。比如上面的那个文法例子，对应的结果如下图。

  接下来就是用这个 NFA 去构造 LR（0）分析表。其实方法很简单：

• 考虑有出边的状态 $i$。对于这种状态，如果 $i$ 通过符号 $\alpha$ 到达状态 $j$：
  • $\beta=a$ 是一个非终结符。置 $\operatorname{ACTION}[i,a] = S _ j$。
  • $\beta=A$ 是一个终结符。置 $\operatorname{GOTO}[i,A]=j$。

• 考虑所有含有归约项目的状态 $i$。对于这里面所有的归约项目：

  • 如果不是接受项目，且该项目对应的产生式序号为 $j$，那么置 $\operatorname{ACTION}[i,\cdot]=r _ j$（意思是 ACTION 中关于 $i$ 的这一整行都填上 $r _ j$）。(1)

    1. 注意这一条规则，后面 SLR（1）和 LR（1）都会对此进行修改，以优化我们的 LR 分析表。

  • 如果是接受项目 $S^\prime\to S\cdot$，直接置 $\operatorname{ACTION}[i,\#]=\mathit{acc}$ 即可。

实际上在上面构造 LR（0）分析表的过程中，我们可能会遇到一系列问题（同一个单元格要填两个东西的问题）。比如移进-归约冲突(1)，亦或者归约-归约冲突(2)。因此，我们直接定义不会产生这两种冲突的文法为 LR（0）文法，也是很简单粗暴实用了。

1. 比如一个状态 $i$ 中同时含有 $A\to\alpha\cdot a\beta$ 和 $B\to\gamma\cdot$，会发现 $\operatorname{ACTION}[i,a]$ 既要填 $S _ j$ 又要填 $r _ k$。这就导致了冲突。
2. 比如一个状态 $i$ 中同时含有 $A\to\alpha\cdot$ 和 $B\to\beta\cdot$，会发现 $\operatorname{ACTION}[i]$ 这一行既要都填 $r _ j$ 又要都填 $r _ k$。这是不可能的，因此就导致了冲突。

SLR（1）文法及其分析

  当文法不是 LR（0）文法时，可以采用简单向后看 $1$ 个输入符号的方法，解决移进-规约冲突或归约-归约冲突。这也是 SLR（1）文法的由来，其中 S 代表的是 Simple。
  原理也是十分简单。比如一个项目集 $I _ k=\lbrace A\to\alpha\cdot\red{a}\beta,A\to\gamma\red{\cdot},B\to\delta\red{\cdot}\rbrace$。这个项目集明显存在上述两种冲突。但是，如果 $A,B$ 后面都不跟 $a$，那么若下一个 token 是 $a$ ，则到这一个状态显然就不能使用产生式 $A\to\gamma$ 或者 $B\to\beta$ 进行归约，只能选择移进。
  具体地，可以描述一下这种冲突可解决的情况。若 $I _ k$ 所含的移进符号集（即“$\cdot$”后面紧跟的终结符所构成的集合），以及所有归约项目对应产生式左部的非终结符的 Follow 集，两两相交为空，则冲突可解决：

• 若下一符号 $a _ i$ 在移进符号集中，则选择移入。
• 若下一符号 $a _ i\in\operatorname{FOLLOW}(A _ i)$，则使用相应的产生式（归约项目中以 $A _ i$ 为左部的）进行归约。

  SLR（1）文法由 NFA 构造分析表的过程，与 LR（0）的唯一区别就是，当某个状态 $i$ 含有编号为 $j$ 的产生式 $A\to\alpha$ 的归约项目时，并不是置 $\operatorname{ACTION}[i]$ 一整行为 $r _ j$，而是对于 $\forall a\in\operatorname{FOLLOW}(A)$，置 $\operatorname{ACTION}[i,a]= r _ j$。直观地理解起来，SLR（1）的进步就是能够提前排除语法错误，因为如果下一个符号不是 $\operatorname{FOLLOW}(A)$ 中的终结符，那么即使这里过了，使用 $j$ 号产生式 $A\to\alpha$ 进行了归约，到后面还是会发现语法错误的。因此不如直接在这里就报错，SLR（1）文法很好地实现了这一点。

思考：一个项目集中是否会有多个左部相同的归约项目？

  上面说道，“若下一符号 $a _ i\in\operatorname{FOLLOW}(A _ i)$，则使用相应的产生式（归约项目中以 $A _ i$ 为左部的）进行归约”。那如果 $I _ k$ 中有一个 $A\to\alpha _ 1$，还有一个 $A\to\alpha _ 2$，$\alpha _ 1\neq\alpha _ 2$，到底要用谁进行归约？

首先明确 $3$ 个要点：

• 正经的识别活前缀的 NFA 都是一棵以 $I _ 0$ 为根的树。
• 若 $I _ k$ 里面同时有多个 $A\to\alpha _ i$，那么一定是可以以 $I _ k$ 这个结点按照路径 $\alpha _ i$ 向上的，换句话说，如果记 $\alpha _ i$ 里面最长的那个为 $\hat\alpha$，那么所有的 $\alpha _ i$ 都是 $\hat\alpha$ 的后缀。
• 一个 $I _ k$ 里面的 $A\to\cdot\alpha$ 是怎么来的？除了 $I _ 0$ 里面的 $S^\prime\to\cdot S$ 这一个项目是开局自带的，其它的 $A\to\cdot\alpha$ 的出现必然是因为 $I _ k$ 里面有一个 $B\to\beta\cdot A\gamma$，由这一项目所引入的。

  因此就以两个归约项目 $A\to\alpha _ 1\cdot$，还有一个 $A\to\alpha _ 2\cdot$ 为例。由于之前所说的第 2 点，其中 $\alpha _ 1$ 和 $\alpha _ 2$ 是“一个为另一个的后缀”的关系。因此我们不妨将这两个归约项目分别写为 $A\to\alpha$ 和 $A\to\beta\alpha$，其中 $\beta\neq\varepsilon$。沿着 $\alpha$ 从状态 $I _ k$ 向前回溯，你会发现一个状态 $I _ k^\prime$，它里面有 $A\to\cdot\alpha$ 和 $A\to\beta\cdot\alpha$ 两个项目。根据前面的第 3 点，$I _ k^\prime$ 里面必然还有一个 $B\to\gamma\cdot A\delta$。

  先说结论：我不知道。

即便一个文法是 LR（0）文法，它依然可以使用 SLR（1）分析法，使得分析表更加精致、能够尽早发现语法错误。

  看到这里，SLR（1）文法的定义也就不言自明了。

LR（1）文法及其分析

  SLR（1）文法用 Follow 集来看能否使用某产生式进行归约，实际上还是太粗糙了（太 Simple 了，符合 SLR 中的 S）。下一个 token $a$ 即使是属于 $\operatorname{FOLLOW}(A)$，也不一定能使用 $A\to\alpha$ 进行归约，也就是说这只是一个必要条件，归约了有可能后续会发现语法错误。LR（1）正是对此进行了相应改进，将使用 $A\to\alpha$ 归约的条件从 $a\in \operatorname{FOLLOW}(A)$ 进一步缩小到 Follow 集合的某一个子集 $a\in\operatorname{subset}(\operatorname{FOLLOW}(A))$。
  LR（1）分析法在构造项目时，将特定位置的后继符信息一并纳入考量范围。具体来说，LR（1）项目的构成为[LR（0）项目，搜索符]，同时，形如 $[A\to\alpha\cdot,a]$ 的项表示仅在下一个输入符号等于 $a$ 时才可以按照 $A\to\alpha$ 进行归约，这样的 $a$ 的集合总是 $\operatorname{FOLLOW}(A)$ 的子集，因此比 SLR（1）更精细。
  LR（1）手搓识别活前缀的 NFA，其操作大体上与 LR（0）是相同的，主要区别是：

• 初始状态：$I _ 0$ 里面现在包括的是一个 $[S^\prime\to\cdot S,\#]$。

• Closure 操作：操作的第 $2$ 步，并入 $\operatorname{Closure}(I _ i)$ 的为： $$\lbrace[B\to\cdot\gamma,\red{b}]|[A\to\alpha\cdot B\red{\beta},\red{a}]\in\operatorname{Closure}(I _ i),b\in\operatorname{FIRST}(\beta a)\rbrace$$

  这个说起来也很有道理。只有下一个 token 为 $b$ 的时候才能使用 $B\to\gamma$ 归约，相当于从当前的状态按照 $\gamma$ 进行回退，然后再按照 $B$ 进行推进。归约后变成了 $A\to\alpha B\cdot\beta$。如果所以这个 $b$ 自然就需要与 $\beta$ 去匹配；特别地，如果 $\beta$ 是空或者可以推出空，则 $b$ 还可以是 $a$。

• Move 操作：仅仅是项目的形式变动一下而已： $$\operatorname{MOVE}(I,X)=\lbrace [A\to\alpha X\cdot\beta,\red{a}]|[A\to\alpha\cdot X\beta,\red{a}]\in I\rbrace$$

  注意在进行 Move 的过程中，前瞻符号 $\red{a}$ 是不会变的。

  现在说说构造 LR（1）分析表。其实就是一个不同，状态 $i$ 如果含有一个普通的归约项目 $[A\to\alpha\cdot,a]$，那么置 $\operatorname{ACTION}[i,a]=r _ j$。
  LR（1）文法的定义已经不言自明了，在此不再展开。

LALR（1）文法及其分析

  在 LR（1）分析的过程中，很多时候会发现状态数量太多了。并且我们发现如果不看后面的前瞻符号，有很多状态都是一模一样的。LALR（1）正是出于这一种思想，把 LR（1）分析构造的 NFA 中相应的状态进行合并，同时同心项目的前瞻符也进行一个合并，最终得到一个状态数量更少的 NFA。
  但是在上面的合并过程中，可能会产生冲突（主要指的是归约-归约）冲突，这个时候就不能采取合并。所以 LALR（1）文法仅仅是 LR（1）文法的一个子集。
  LALR（1）文法的杰出贡献是减少了 NFA 的状态数，但是相应的代价就是延缓了潜在的语法错误发现的时机。在实际分析过程中，LALR（1）的优化往往比它的短板更显著，是可以接收的，比如 Bison 就是采用 LALR（1）分析。

LL 文法和 LR 文法之间的关系

  关系如下图所示。