第 5 章 自底向上的语法分析-LR(0)

5.4. LR 分析技术

5.4.1. LR 分析技术概述

前面讨论的算符优先分析法对文法有一定的要求，必须是算符文法，不能包含 $A\to \varepsilon$ 的空规则的性质，而 LR 系列分析技术，对文法几乎没有限制，如果他允许左递归，允许回溯，允许两个非终结符相邻，允许有空规则 $A\to \varepsilon$ 等。LR 系列分析技术是当前最通用的分析方法。

LR(k) 分析技术，L 代表从左向右分析，R 代表最右推导，$\displaystyle{ k }$ 代表向前查看 $\displaystyle{ k }$ 个字符。LR 分析法实际上是最右推导的逆过程——规范归约。

LR(k) 分析技术利用已经移进栈中的和归约后进入栈中的一切文法符号，并向前查看最多 k 个符号，就能确定句柄（自底向上语法分析中的“可归约子串”）是否已经在栈顶形成，一旦句柄出现在栈顶，立即进行归约。因此 LR(k) 是一种严格的从左向右分析法。

算符优先分析法并不是严格从左向右的，因为当栈顶形成最左素短语的尾部，要向栈底（即从右向左）去寻找素短语的头部。

通常，我们考虑 $\displaystyle{ k = 0 , 1 }$ 的情形。LR 系列分析技术有 LR(0), SLR(1), LR(1), LALR(1)。所有这些分析法，只是 LR 分析表中填写的内容不同，分析表的结构和程序相同。

LR 分析器的 4 个组成部分：

• 一个输入串
• 一个分析栈
• 一张 LR 分析表
• LR 分析总控程序

5.4.2. LR(0) 分析法

问题分析

在 LR(0) 中，0 表示不用向前查看任何字符，不需要利用即将读入的下一个字符的信息。

LR 分析法如何回答自底向上分析法面临的两个问题呢？

• 如何确定或找出“可归约子串”？
• 可归约子串归约到哪一个非终结符？

设文法 $\displaystyle{ G \left[ S \right] }$

在推导过程中将序号也带入句型中

给定输入串 #caaaad#，先分析推导过程

现在对末尾的句子进行规范归约

仔细观察每一次归约时栈中的内容可以发现，当发生归约时，栈中总为如下形式：$\beta\omega \bigcirc \!\!\!\!\!\! p \,\,$，其中 $\omega$ 一定是第 $\displaystyle{ p }$ 条规则的右部：$A\to \omega$。如第一次归约时，$\beta=c, \omega=a, \bigcirc \!\!\!\! p\,=②$

此时，上面的两个问题就得到了答案

• $\omega$ 为可归约子串
• 归约到第 $\displaystyle{ p }$ 条规则的非终结符

$\beta\omega \bigcirc \!\!\!\!\!\! p \,\,$ 的形式较为重要，因此引入 活前缀 的概念

活前缀

定义 5.10 把句型中 $\beta\omega \bigcirc \!\!\!\!\!\! p \,$ 这种形式的前部称为活前缀，有时也称为可归约前缀或 $\bigcirc \!\!\!\! p$ 可归前缀

任何前部都是从左开始的，如 $\displaystyle{ ab cd ② }$ 的活前缀有 $\displaystyle{ a , ab , ab c , ab cd }$

如果求出了文法 G 的所有活前缀，就可以很方便的进行语法分析。假设文法 G 的所有活前缀为 $x_1 \bigcirc \!\!\!\!\!\! {\scriptsize p_1}\,, x_2 \bigcirc \!\!\!\!\!\! {\scriptsize p_2}\,,\cdots ,x_n \bigcirc \!\!\!\!\!\! {\scriptsize p_n}\,$ 则移进归约的语法分析过程大致为：每当移进一个符号，就查看栈中内容是否与某一个活前缀 $x_i \bigcirc \!\!\!\!\!\! {\scriptsize p_i}\,$ 相同，若相同，则按照第 $\displaystyle{ p _{ i } }$ 条规则进行归约，否则移进下一个符号（具体的还是看上面的流程图方便理解）

于是问题的核心变成了：如何求文法 G 的所有活前缀？

我们发现，如果 $\beta A\xi \bigcirc \!\!\!\!\!\! p \,\,$ 是活前缀，且有 $A\to \omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,$，则 $\beta\omega \bigcirc \!\!\!\!\!\! {\scriptsize m} \,$ 一定是活前缀。这个基本性质是求所有活前缀的基础（我好像发现不了）。

当 $U\to \beta \bullet A\xi \bigcirc \!\!\!\!\!\! p \,$ 分析到非终结符 $\displaystyle{ A }$ 时（$\beta$ 已经分析完成，进入栈中，下一步将分析 $\displaystyle{ A }$），对于 $\displaystyle{ A }$ 的任何产生式规则 $A\to \omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,$，都会产生新的活前缀 $\beta \bullet \omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,$，这个新活前缀表示，$\beta$ 已经在栈中，分析将从 $\omega$ 继续。由于两个活前缀 $\beta \bullet A\xi \bigcirc \!\!\!\!\!\! p \,,\beta \bullet \omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,$ 中的 $\beta$ 是相同的部分，因此将它们组成一个集合

上述思想经过进一步提炼，产生了 LR(0) 项目和 LR(0) 项目集及其闭包的概念。

项目 项目集 项目集闭包

定义 5.11 文法 G 中每一条产生式规则的右部添加一个圆点，称为一个 LR(0) 项目集。

对规则 $A\to cAd$，有 4 个 LR(0) 项目：

对于空规则 $A\to \varepsilon$，只有一个项目 $A\to \bullet$

定义 5.12

• $S\to \bullet \alpha$，$\displaystyle{ S }$ 为文法的开始符号，称该项目为初始项目
• $A\to \alpha \bullet a\beta$，其中 $a\in V_\mathrm{T}$，称该项目为移进项目
• $A\to \alpha \bullet B\beta$，其中 $B\in V_\mathrm{N}$，称该项目为待约项目
• $A\to \alpha \bullet$，其中 $A\in V_\mathrm{N}$，若 $\displaystyle{ A }$ 不是文法 G 的开始符号，则称为归约项目，否则称为接收项目
• 设有两个项目 $A\to \alpha \bullet a\beta, A\to \alpha a \bullet \beta$，两者同属于一条规则，只是圆点位置相差一个终结符，则称后者为前者的后继项目

为保证文法 G 中只有一个接收项目，且一旦到达接收项目，就完成整个语法分析。为此，需要对不满足要求的文法进行拓广。若一个文法 G 的开始符号 $\displaystyle{ S }$ 不是只出现在一条规则的左边，则这个文法 G 需要拓广。

定义 5.13 设文法 G 的开始符号为 $\displaystyle{ S }$，引入一个新的开始符号 $S^\prime$，并加入一条新规则 $S^\prime\to S$。于是形成了新的文法 $G^\prime[S^\prime]$，$G^\prime$ 是 $\displaystyle{ G }$ 的拓广。

文法拓广的目的就是保证开始符号只出现在第一条规则左边。

定义 5.14 由 LR(0) 项目组成的集合，称为 LR(0) 项目集。

在活前缀部分，若 $U\to \beta \bullet A\xi \bigcirc \!\!\!\!\!\! p \,$ 是活前缀，则对任何 $A\to B\omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,$，都会产生新的活前缀 $\beta \bullet B\xi \bigcirc \!\!\!\!\!\! p \,$，组成集合 $\{U\to \beta \bullet A\xi \bigcirc \!\!\!\!\!\! p \,,A\to \bullet B\omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,\}$

若 $\displaystyle{ B }$ 为非终结符，则关于 $\displaystyle{ B }$ 的任何规则 $B\to \xi \bigcirc \!\!\!\!\!\! k\,$，又都会产生新活前缀 $\beta \xi \bigcirc \!\!\!\!\!\! k\,$，于是这个集合就扩大为 $\{U\to \beta \bullet A\xi \bigcirc \!\!\!\!\!\! p \,,A\to \bullet B\omega \bigcirc \!\!\!\!\!\! {\scriptsize m}\,,B\to \bullet \xi \bigcirc \!\!\!\!\!\! k\,\}$

这一过程将一直进行下去，直到该集合不再扩大为止。由此产生了求 LR(0) 项目集闭包的算法。

例 5.10 已知文法 G

已知项目集 $I:\{S\to \bullet A\}$，求 $\text{CLOSURE}(I)$

警告！下面的内容没有人能看得懂！

状态变迁

有了项目集的闭包，现在考虑项目集之间的状态变迁。

设有文法 $\displaystyle{ G \left[ S \right] }$

另有项目集 $I:\{S\to \bullet cAd\}$，当终结符号 $\displaystyle{ c }$ 移进栈后，项目集应变迁到它的后继项目集的闭包 $\text{CLOSURE}(\{S\to c \bullet Ad\})=\{S\to c \bullet Ad,A\to \bullet a, A\to \bullet Aa\}$

为此，可定义 GO 函数表达状态之间的这种转换。

定义 5.15 项目集 $\displaystyle{ I }$ 经过符号 $\displaystyle{ X }$ 的状态转换函数 $\text{GO}(I,X)=\text{CLOSURE}(I$ 的后继项目集$\displaystyle{ ) }$.

例如，若 $\displaystyle{ I }$ 是 $\{S\to \bullet cAd\}$，$\displaystyle{ X = c }$，则 $\displaystyle{ I }$ 的后继项目集是 $\{S\to c \bullet Ad\}$，该后继项目集的闭包为 $\{S\to c \bullet Ad,A\to \bullet a, A\to \bullet Aa\}$。因此，$\text{GO}(\{S\to c \bullet Ad\}, c)=\{S\to c \bullet Ad,A\to \bullet a, A\to \bullet Aa\}$

构造 DFA 项目集规范族

有了 CLOSURE 和 GO，可以很方便的构造一个 DFA，它正好能够识别一个文法 G 中的所有活前缀。这个 DFA，它正好能够识别一个文法DFA 中的每一个状态，都是一个 LR(0) 的项目集的闭包。

设拓广文法 G’ 的开始符号规则是 $S^\prime\to S$，DFA 构造步骤如下：

state_set = CLOSURE(['S_1 -> S'])
// state_set 是一个由各个 LR(0) 项目集闭包所组成的集合
let flag = false
do {
  flag = false
  // state_set 中每个项目集 I 及文法 G' 中每个符号 X
  for (const { I, X } of THETA(state_set, G_1.symbols)) {
    // 如果 GO(I, X) 不空且不在 state_set 中，则添加进去
    if (GO(I, X) !== null && !state_set.has(GO(I, X))) {
      state_set.push(GO(I, X))
      flag = true
    }
  }
} while (flag)

state_set = CLOSURE(['S_1 -> S'])
// state_set 是一个由各个 LR(0) 项目集闭包所组成的集合
let flag = false
do {
  flag = false
  // state_set 中每个项目集 I 及文法 G' 中每个符号 X
  for (const { I, X } of THETA(state_set, G_1.symbols)) {
    // 如果 GO(I, X) 不空且不在 state_set 中，则添加进去
    if (GO(I, X) !== null && !state_set.has(GO(I, X))) {
      state_set.push(GO(I, X))
      flag = true
    }
  }
} while (flag)

这个 DFA 的初始状态是文法 G 的初始项目所在的 LR(0) 项目集闭包。终止状态是含有归约项目或接收项目的 LR(0) 项目集闭包。这个 DFA 识别的正好是文法 G 的所有活前缀。有时把识别文法 G 的所有活前缀的 LR(0) 项目集闭包组成的 DFA 称为 LR(0) 项目集规范族。

没错，我写到这里早就已经看不懂了，感觉没有任何目标和头绪。

例 5.11 设有文法 $\displaystyle{ G \left[ S \right] }$

试给出该文法 G 的 LR(0) 项目集规范族

例 5.12 已知文法 $G: A\to aA\mid \varepsilon$

试给出该文法的 LR(0) 项目集规范族。

LR(0) 分析表

LR(0) 项目集规范族中包含了丰富的信息，从中可以形成一张 LR(0) 分析表。分析表由 ACTION 子表和 GOTO 子表组成，其中，ACTION 下的 $\displaystyle{ a _{ i } }$ 是终结符，GOTO 下的 $\displaystyle{ S }$ 等是非终结符。

ACTION 子表有如下动作

1. 移进。如果状态 0 所在行与 $\displaystyle{ a _{ 1 } }$ 所在列的单元格内为 s2，即有 $\displaystyle{ a _{ 1 } }$ 移进栈，并将状态转为 2
   • 
2. 归约。如果状态 $\displaystyle{ n }$ 所在行与 $\displaystyle{ a _{ 1 } }$ 所在列的单元格内为 r3，即有“按照第 3 条产生式规则归约”
   • 
3. 接收。如果状态 1 所在行与 # 所在列交叉处为 acc，则成功接收，正确识别出句子。
4. 报错。ACTION 子表的空白处为报错。

GOTO 子表的列均为非终结符，表示状态转移，终结符的状态由 ACTION 完成。例如，状态 0 所在行与 GOTO 的 $\displaystyle{ A }$ 所在列交叉处为 2，则当前状态 0 若识别出非终结符 $\displaystyle{ A }$，状态将变迁为 2.

LR(0) 分析表的构造步骤：

1. 若移进项目 $A\to \alpha \bullet a\beta$ 属于 $\displaystyle{ I _{ k } }$ 且 $\text{GO}(I_k, a)=I_j$，则令 $\text{ACTION}[k][a]=s_j$，即

   • 

2. 若归约项目 $A\to \beta \bullet$ 属于 $\displaystyle{ I _{ k } }$，设 $A\to \beta \bigcirc \!\!\!\!\!\! p\,$，则令 $\text{ACTION}[k][:]=r_p$，表示不论下一个字符是什么，只要当前状态为 $\displaystyle{ k }$，则一定按照第 $\displaystyle{ p }$ 条产生式规则归约。

3. 若接收项目 $S^\prime \to S \bullet$ 属于 $\displaystyle{ I _{ k } }$，则令 $\text{ACTION}[k][\#]=acc$，表示成功接收

4. 若 $\text{GO}(I_k,A)=I_p$，则令 $\text{GOTO}[k][A]=p$，表示状态 $\displaystyle{ k }$ 下若识别出非终结符 $\displaystyle{ A }$，则状态变为 $\displaystyle{ p }$

5. 分析表中不能用以上规则填写的交叉处，全部填上“报错标记”

定义 5.16 若一个文法 G 的 LR(0) 项目集规范族中所有的 LR(0) 项目集均不含有冲突项目，则称该文法为 LR(0) 文法。

冲突分析

1. “移进-归约”冲突 在例 5.12 中，分析表一个单元格内同时出现了 s2 和 r3，即在这一步有两种选择：按照 $A\to \bullet aA$ 移进，或者按照 $A\to \bullet \text{③}$ 归约。 广义地，有项目集 $I_k=\{A\to \alpha \bullet a \beta, B\to \gamma \bullet\}$，有两种选择此时，发生了冲突
   • $I_k \underset{\text{shift} }{\overset{a}{\longrightarrow} } I_m$
   • reduce by $B\to \gamma \bigcirc\!\!\!\!\!\! p\,$
2. “归约-归约”冲突 有项目集 $I_k=\{A\to \beta \bullet, B\to \gamma \bullet\}$，由于两个都是归约项目，因此可以按照 $A\to \beta\bigcirc\!\!\!\!\!\! p\,$ 或 $B\to \gamma \bigcirc\!\!\!\!\!\! {\scriptsize m}\,$ 归约，此时发生了冲突
3. “移进-移进”冲突不会发生

例 5.14 对例 5.11 中的文法 $\displaystyle{ G \left[ S \right] }$，给出 LR(0) 分析器识别串 #caad# 的过程

总结

LR 分析器的总控程序工作步骤：

type MySymbol = string;
let stack: Array<[number, MySymbol]> = [];

stack.push([0, '#'])   // 状态 0 和 # 入栈
let a: MySymbol = getSymbol()  // 读入符号
while (true) {
    let [state, s] = stack[stack.length - 1]           // 根据栈顶当前状态和 a
    let t: Shift | Reduce | Acc | never = ACTION[state][a] // 查表
    if (t instanceof Shift) {
        stack.push([t.state, a])  // 对移进动作，将二元组 (I_j, a) 入栈
        a = getSymbol()
    } else if (t instanceof Reduce) {  // 对归约动作，按照第 j 条规则归约
        let tobeReduced: MySymbol[] = []
        for (let i = 0; i < t.symbol_num; i++) {
            tobeReduced.push(stack.pop()[1])
        }
        let newSymbol: MySymbol = reduce(tobeReduced, t.rule)
        let currentState: number = stack[stack.length - 1][0]
        let nextState: number = GOTO[currentState][newSymbol];
        stack.push([nextState, newSymbol])
    } else if (t instanceof Acc) {
        return true
    } else {
        throw new Error("error!")
    }
}

type MySymbol = string;
let stack: Array<[number, MySymbol]> = [];

stack.push([0, '#'])   // 状态 0 和 # 入栈
let a: MySymbol = getSymbol()  // 读入符号
while (true) {
    let [state, s] = stack[stack.length - 1]           // 根据栈顶当前状态和 a
    let t: Shift | Reduce | Acc | never = ACTION[state][a] // 查表
    if (t instanceof Shift) {
        stack.push([t.state, a])  // 对移进动作，将二元组 (I_j, a) 入栈
        a = getSymbol()
    } else if (t instanceof Reduce) {  // 对归约动作，按照第 j 条规则归约
        let tobeReduced: MySymbol[] = []
        for (let i = 0; i < t.symbol_num; i++) {
            tobeReduced.push(stack.pop()[1])
        }
        let newSymbol: MySymbol = reduce(tobeReduced, t.rule)
        let currentState: number = stack[stack.length - 1][0]
        let nextState: number = GOTO[currentState][newSymbol];
        stack.push([nextState, newSymbol])
    } else if (t instanceof Acc) {
        return true
    } else {
        throw new Error("error!")
    }
}