编译原理 笔记 2

自底向上语法分析

自底向上的思想是从要分析的终结符串开始，每一步规约都是将一个子串用一个产生式替换，直到达到开始符号或报错

基本改进方法

与自顶向下相似，直接分析的版本不确定性太高，因此需要进行限制

选择可规约串

对于一个句型，可规约串定义为该句型的短语

对于文法 $G = (V_{N}, V_{T}, P, S)$，设 $\alpha, \beta, \delta\in(V_{N}\cup V_{T})^{*}, w\in V_{T}^{*}$：

• 若 $S\mathop{\Rightarrow}\limits^{*}\alpha A\delta$ 且 $A\mathop{\Rightarrow}\limits^{+}\beta$，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对非终结符 $A$ 的短语
• 若 $S\mathop{\Rightarrow}\limits^{*}\alpha A\delta$ 且 $A\Rightarrow\beta$，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对非终结符 $A$ 的直接短语
• 若 $S\mathop{\Rightarrow}\limits_{rm}^{*}\alpha Aw$ 且 $A\Rightarrow\beta$，则称 $\beta$ 是右句型 $\alpha\beta w$ 相对非终结符 $A$ 的句柄

短语可以理解为可以被规约的子串，直接短语就是可以通过一步就能规约到的子串，而句柄是所有直接短语中最靠左的一个（因为在句柄的定义中要求了最右推导，因此右边的直接短语已经被推导完了）

例如对于文法：

$$\begin{align*} S &\to AB \\ A &\to aA \\ A &\to \varepsilon \\ B &\to b \\ B &\to bB \end{align*}$$

则：

• 句子 $aaab$ 的短语包括 $\varepsilon, a, aa, aaa, aaab, b$，直接短语包括 $\varepsilon, b$，句柄为 $\varepsilon$
• 句型 $aaAb$ 的短语包括 $aA, aaA, aaAb, b$，直接短语包括 $aA, b$，句柄为 $aA$

如果文法是二义的，则右句型的最右推导可能有多个，则句柄也可能会有多个

最右推导与最左规约

通常采用移进-规约分析

与自顶向下分析比较

• 功能较强：规约的时候可以获取完整的串信息，而推导只能获得局部信息
• 利于出错处理
• 有成熟的自动化技术

移进-规约分析

有一个分析引擎和下推栈，分析引擎能完成的动作包括：

• Reduce：按照确定的方式对栈顶短语进行规约
• Shift：从输入序列移进一个单词到栈顶
• Error：发现错误，进行处理或恢复
• Accept：分析成功

移进-规约分析例子

上图中的步骤逆向过来就是一种最右推导，称之为规范推导

移进-规约冲突

到达一个既可移进又可规约的状态，例如文法：

$$\begin{align*} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text { else } S \end{align*}$$

则对于待分析串 $\text{if } E \text{ then if } E \text{ then } S \text { else } S$，当栈内是 $\text{if } E \text{ then if } E \text{ then } S$ 时，既可移进又可规约

规约-规约冲突

到达了一个状态，可能有多种短语可以用于规约，例如产生式：

$$A \to aA \,|\, aaA \,|\, b$$

则对于 $aaab$ 时，对于栈中的 $aaA$，无法确定该用哪一个短语

表驱动方法

解决上面两个冲突的方法，即通过一张分析表来决定状态机的下一步行为，常见的表有 LR 分析中的 LR 分析表、算符优先分析中的算法优先分析表

LR 分析

代表从左（L）到右扫描输入序列，产生最右（R）推导，是一种表驱动的移进-规约分析

LR 分析表构造

主要是构造两张表 ACTION 表和 GOTO 表：

• ACTION 表：根据栈顶状态和当前输入符号来确定下一步动作
• GOTO 表：根据栈顶状态和规约用的非终结符决定下一个状态

每一个状态为一个 set<pair>，每一个 pair 代表了在当前状态下，消耗的栈顶符号与去掉这个符号后下一步允许什么串进入，本质上是一个大型状态转移图

LR 分析表对应的状态转移图实例

这张表具体的构造方法按照分析方法不同分别讨论

LR 分析算法

1
2
3
4
5
6
7
8
9
10
11
12
13

if (ACTION[i, a] == sj) { // shift
    PUSH j; // push state j to stack
    READ w; // read one symbol in the input
}
else if (ACTION[i, a] == rj) { // reduce 
    // the j-th formula is A -> beta
    POP len(beta); // pop |beta| states from the top of stack
    PUSH GOTO[k, A]; // k is the current stack top
}
else if (ACTION[i, a] == acc) { // accept
    return;
}
else exit(1); // error

带符号栈的 LR 分析算法

除了状态栈之外，还有一个符号栈，存储的读入但是没有规约的符号，算法修改为：

1
2
3
4
5
6
7
8
9
10
11
12
13

if (ACTION[i, a] == sj) { // shift
    PUSH (j, a); // push state j and symbol a to stack
    READ w; // read one symbol in the input
}
else if (ACTION[i, a] == rj) { // reduce 
    // the j-th formula is A -> beta
    POP len(beta); // pop |beta| states from the top of both stack individually
    PUSH (GOTO[k, A], A); // k is the current stack top
}
else if (ACTION[i, a] == acc) { // accept
    return;
}
else exit(1); // error

LR(0) 分析

首先引入一些概念

LR(0) FSM

LR(0) 分析的主要工具，是一个以 $V_{N}\cup V_{T}$ 为字母表的 DFA，可以通过增广后的文法直接构造

可以证明，$G$ 的 LR(0) FSM 对应的语言是 $G'$ 所有活前缀的集合

FSM 的状态

LR(0) FSM 的状态是一个特殊的 LR(0) 项集，一个 LR(0) 项是指在右端某一位置有圆点的产生式，圆点代表着已分析过的串与该产生式匹配的位置

项有如下分类：

• 移进项：$A\to \alpha .a\beta$
• 待约项：$A\to \alpha .B\beta$
• 规约项：$A\to \alpha .$
• 接收项：$S'\to S .$

我们将 LR(0) FSM 的每一项定义为一个项集的闭包 (CLOSURE)

1
2
3
4
5
6
7
8
9

def CLOSURE(I):
    J = I
    while (1):
        for (j, p) in zip(J, P): # P is all the generation formula
            if j.hasform("A -> α.Bβ") and p.hasform("B -> γ"):
                J.append("B -> .γ")
        if J.hasNotChanged():
            break
    return J

则其状态转移函数定义为：

$$\begin{align*} \text{GO}(I, X) &= \text{CLOSURE}(J) \\ J &= \{A\to \alpha X.\beta \,|\, A\to \alpha.X\beta \in I \} \end{align*}$$

则构造状态集合的方法就是从 $\{\text{CLOSURE}(\{S'\to .S\})\}$ 开始，利用上述的状态转移函数逐步扩展状态集合

LR(0) FSM 的构造举例

增广文法的每个活前缀都有唯一与之相对应的状态

LR(0) 分析表的构造

令状态集合为 $C = \{I_{0} ,\dots,I_{n}\}$，则构造 ACTION 与 GOTO 表的方法为：

• $\mathrm{GOTO}(k, A) = j \Leftrightarrow \mathrm{GO}(I_{k}, A) = I_{j}$
• $\mathrm{ACTION}(k, a) = sj \Leftrightarrow A\to\alpha.a\beta \in I_{k} \,\&\, \mathrm{GO}(I_{k}, a) = I_{j}$
• $\mathrm{ACTION}(k, a) = rj \Leftrightarrow A\to\alpha.\in I_{k}$
• $\mathrm{ACTION}(k, \#) = acc \Leftrightarrow S'\to S. \in I_{k}$

LR(0) 文法

按照上述定义构造的分析表，如果各表项均没有多重定义，则称为 LR(0) 文法，等价于要求每个状态满足：

• 不同时含有移进和规约项（不能有移进-规约冲突）
• 不含有两个以上规约项（不能有规约-规约冲突）

一个非 LR(0) 文法的例子为：

$$\begin{align*} E &\to E + T \,|\, T \\ T &\to T * F \,|\, F \\ F &\to (E) \,|\, v \,|\, d \end{align*}$$

短语 $T$ 即存在移进-规约冲突

SLR(1) 分析

由于 LR(0) 限制非常严格（要求看到栈顶状态就能决定动作），因此做一些条件的放松，常见的是允许向前查看一个符号成为 LR(1)，首先来研究其简化版本 SLR(1)

SLR(1) 通过判断下一个输入符号是否属于要规约的非终结符的 Follow 集合，来解决移进-规约冲突和规约-规约冲突

• 如果一个状态中规约项的非终结符的 Follow 集两两无交，则可以解决规约-规约冲突
• 如果一个状态中所有规约项中要规约的非终结符的 Follow 集与所有要移进的符号集互不相交，则可以解决移进-规约冲突

SLR(1) 分析表

其分析表的构造相对于 LR(0) 来说只用做简单的修改，也即在填充 $\mathrm{ACTION}(k, a) = rj$ 时，需要保证 $a\in \mathrm{Follow}(A)$

按照上述定义构造的分析表，如果各表项均没有多重定义，则称为 SLR(1) 文法，等价于要求每个状态满足：

• 对于任意两项 $A\to \alpha.$ 与 $B\to \beta.$，有 $\mathrm{Follow}(A) \cap \mathrm{Follow}(B) = \emptyset$
• 对于任意两项 $A\to \alpha.a\beta$ 与 $B\to \gamma.$，均有 $a\notin \mathrm{Follow}(B)$

一个非 SLR(1) 文法的例子为：

$$\begin{align*} E &\to (L,E) \,|\, F \\ L &\to L,E \,|\, E \\ F &\to (F) \,|\, d \end{align*}$$

短语 $(F)$ 会被错误的规约为 $(E)$

LR(1) 分析

在 SLR(1) 的基础上进一步改进，将传统的项增加一个终结符，表示产生式右端完整匹配后所允许留在符号串中的下一个终结符，即项会形如：

$$A\to \alpha.\beta\,,\,a$$

其中 $a\in V_{T}\cup\{\#\}$

对于形如 $A\to \alpha.\,,\,a$ 的项，只有当下一个输入为 $a$ 的时候才能进行规约

LR(1) FSM

LR(1) FSM 的状态是 LR(1) 项集的闭包，闭包算法为：

1
2
3
4
5
6
7
8
9

def CLOSURE(I):
    J = I
    while (1):
        for (j, p) in zip(J, P):
            if j.hasform("[A -> α.Bβ, a]") and p.hasform("B -> γ"):
                J.append("[B -> .γ, b]") for b in First(βa)
        if J.hasNotChanged():
            break
    return J

初态定义为 $I_{0} = \mathrm{CLOSURE}(\{[S'\to .S, \#]\})$

状态转移函数定义为：

$$\begin{align*} GO(I, X) &= \text{CLOSURE}(J) \\ J &= \{[A\to \alpha X.\beta\,,\, a] \,|\, [A\to \alpha.X\beta \,,\, a] \in I \} \end{align*}$$

从初态开始利用上述转移函数扩展，可以得到项集规范族

在上述非 SLR(1) 的例子中，$E\to F.$ 所期待的下一个输入符号没有 $)$，因此 $(F)$ 中的 $F$ 不会被规约为 $E$，而是会选择移进

LR(1) 分析表构造

• $\mathrm{GOTO}(k, A) = j \Leftrightarrow \mathrm{GO}(I_{k}, A) = I_{j}$
• $\mathrm{ACTION}(k, a) = sj \Leftrightarrow [A\to\alpha.a\beta\,,\,b] \in I_{k} \,\&\, \mathrm{GO}(I_{k}, a) = I_{j}$
• $\mathrm{ACTION}(k, b) = rj \Leftrightarrow [A\to\alpha.\,,\, b]\in I_{k}$
• $\mathrm{ACTION}(k, \#) = acc \Leftrightarrow [S'\to S.\,,\, \#] \in I_{k}$

LR(1) 文法

按上述算法构造的分析表若每项都无重复定义，则称为 LR(1) 文法，其 FSM 每一个状态都满足：

• 对于任意两个项目 $[A\to \alpha.a\beta\,,\, b]$ 与 $[B\to \gamma., c]$，一定有 $a\neq c$
• 对于任意两个项目 $[A\to \alpha.\,,\, a]$ 与 $[B\to \beta.\,,\, b]$，一定有 $a\neq b$

LR(k) 文法

可以扩展到 LR(k) 文法，但是状态机的复杂度过高，无实际意义，并且可以证明 $\mathrm{LR}(\mathbb{N}^{+})$ 都是等价的

LALR(1) 分析

是一个 LR(1) 与 SLR(1) 的折中版本

将 LR(1) 的项的第一部分称为芯，如果 LR(1) FSM 的两个状态的芯构成的集合完全相同，那么我们称其为同芯的状态

将 LR(1) FSM 中的同芯状态合并，如果得到的新状态没有规约-规约冲突，则得到的新文法是 LALR(1) 文法

LALR(1) FSM

构造方法为 brute-force 方法：

• 构造增广文法的 LR(1) FSM 状态集
• 合并同芯状态
• LALR(1) FSM 状态的后继状态是其合并前所有同芯状态的后继状态的并

LALR(1) FSM 状态数与 LR(0) 状态数相同，但是其能力强于 SLR(1)