语法分析

发表于 2025-09-09 更新于 2025-09-28 Waline：阅读次数：本文字数： 23k 阅读时长 ≈ 1:22

语法分析的角色与任务

在编译器的整体流程中，语法分析（Syntax Analysis 或 Parsing）是继词法分析之后的第二个核心阶段。它扮演着承上启下的关键角色。

语法分析器

语法分析器（Parser）从词法分析器获取词法单元（token）序列作为输入，其核心任务是根据语言的语法规则，将这个线性的序列构造成一个能够反映程序层次结构的树形表示，通常是语法分析树（Parse Tree）或抽象语法树（Abstract Syntax Tree, AST）。

语法分析器的主要功能可以概括为：

结构验证：检查词法单元序列是否符合语言的语法规则。例如， $\mathbf{if}$ 语句是否包含正确的 $\mathbf{then}$ 和 $\mathbf{else}$ 分支，表达式中的括号是否匹配等。
结构构建：为合法的源程序构建一个数据结构（通常是树），清晰地表示出程序的语法结构。这个结构是后续语义分析和代码生成的基础。
错误处理：对于不符合语法的程序，能够检测、报告错误，并尝试从错误中恢复，以便继续分析程序的其余部分，从而一次性报告多个错误。

考虑一个简单的赋值语句：
position = initial + rate * 60

词法分析器将其转换为词法单元流：
<id, 1> <assign, => <id, 2> <plus, +> <id, 3> <mul, *> <number, 60>
语法分析器接收这个流，并根据算术表达式的语法规则（如乘法优先于加法），构建出如下的语法分析树：
1
2
3
4
5
6
7
=
/\
<id, 1> +
/\
<id, 2> *
/\
<id, 3> 60
这棵树明确地表达了运算的层次和优先级，即 rate * 60 是一个子树，其结果再与 initial 相加。

上下文无关文法

为了精确地描述程序设计语言的语法结构，我们需要一种形式化的工具。上下文无关文法（Context-Free Grammar, CFG）就是这样一种强大而简洁的表示方法。它能够自然地描述大多数程序设计语言中存在的嵌套和递归结构，如算术表达式、if-else 语句、循环等。

上下文无关文法

一个上下文无关文法 $G$ 是一个四元组 $(V_T, V_N, P, S)$ ，其中：

$V_T$ ：终结符号（terminal symbol）的集合。它们是构成语言的基本符号，相当于词法分析中的词法单元，如 $\mathbf{id}, \mathbf{number}, +, \mathbf{if}$ 等。
$V_N$ ：非终结符号（non-terminal symbol）的集合。它们是语法变量，代表了由终结符号构成的串的集合，用于表示语言的层次结构，如 $\mathit{expression}, \mathit{statement}$ 等。
$P$ $P$ ：产生式（production）的集合。它定义了非终结符号可以被替换（重写）的方式，因此又可称为重写规则（rewriting rule）。
- 每个产生式形如 $A \to \alpha$ ，其中 $A$ 是一个非终结符号（称为产生式的头）， $\alpha$ 是由终结符号和非终结符号组成的串（称为产生式的体）。
$S$ ：开始符号。它是一个特殊的非终结符号，表示文法所定义的整个语言。

符号表示约定

为了书写方便，我们通常遵循以下约定：

非终结符号：大写字母，如 $A, B, E, T, F$ ，或斜体名称如 $\mathit{stmt}$ 。
终结符号：小写字母、数字、标点符号，或粗体名称如 $\mathbf{id}$ 。
文法符号：大写字母 $X, Y, Z$ 表示一个终结符或非终结符。
文法符号串：小写希腊字母 $\alpha, \beta, \gamma$ 表示任意文法符号串（包括空串 $\varepsilon$ ）。
开始符号：通常是文法中第一个产生式的头，或者显式指定为 $S$ 。
多选产生式：将多个头的产生式 $A \to \alpha_1, A \to \alpha_2, \ldots, A \to \alpha_n$ 合并写为 $A \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n$ 。

算术表达式文法

一个描述加法和乘法表达式的经典文法如下：

非终结符号： $E$ (Expression), $T$ (Term), $F$ (Factor)
终结符号： $\mathbf{id}, +, *, (, )$
开始符号： $E$
产生式：
$\begin{aligned} E &\to E + T \kern{-1em}&&\mid T \\ T &\to T * F \kern{-1em}&&\mid F \\ F &\to ( E ) \kern{-1em}&&\mid \mathbf{id} \end{aligned}$

这个文法不仅定义了合法的表达式，还通过层次结构（ $E \to T \to F$ ）巧妙地蕴含了 $*$ 的优先级高于 $+$ 。

推导

推导（Derivation）是从文法的开始符号出发，通过反复应用产生式进行重写，最终得到一个由终结符号组成的串（即句子）的过程。

一步推导：如果 $A \to \gamma$ 是一个产生式，那么文法符号串 $\alpha A \beta$ 可以被重写为 $\alpha \gamma \beta$ ，记作 $\alpha A \beta \Rightarrow \alpha \gamma \beta$ 。
多步推导：
- $\alpha \xRightarrow{*} \beta$ 表示 $\alpha$ 经过零步或多步推导可以得到 $\beta$ 。
- $\alpha \xRightarrow{+} \beta$ 表示 $\alpha$ 经过一步或多步推导可以得到 $\beta$ 。

推导示例

使用文法 $E \to E + E \mid E * E \mid -E \mid (E) \mid \mathbf{id}$ ，推导出串 $-(\mathbf{id} + \mathbf{id})$ 的过程如下：
$E \Rightarrow -E \Rightarrow -(E) \Rightarrow -(E + E) \Rightarrow -(\mathbf{id} + E) \Rightarrow -(\mathbf{id} + \mathbf{id})$

句型、句子和语言

句型（Sentential Form）：从开始符号 $S$ $S$ 出发，经过零步或多步推导得到的任何文法符号串 $\alpha$ $α$ ，都称为文法的一个句型。
- 句型中可以同时包含终结符和非终结符，也可以是空串 $\varepsilon$ 。
- 即 $S \xRightarrow{*} \alpha$ 。
句子（Sentence）：一个不包含任何非终结符号的句型被称为该文法的一个句子。
语言（Language）：由一个文法 $G$ $G$ 生成的语言，记为 $L(G)$ $L (G)$ ，是该文法所有句子的集合。
- $\omega \in L(G)$ 当且仅当 $S \xRightarrow{*} \omega$ 且 $\omega$ 只包含终结符号。

最左推导与最右推导

在推导的每一步，如果句型中有多个非终结符号，我们可以选择替换其中任意一个。为了使推导过程规范化，通常采用两种策略：

最左推导（Leftmost Derivation）：在每一步推导中，总是选择句型中最左边的非终结符号进行替换。记作 $\xRightarrow[\mathrm{lm}]{*}$ 。
最右推导（Rightmost Derivation）：在每一步推导中，总是选择句型中最右边的非终结符号进行替换。记作 $\xRightarrow[\mathrm{rm}]{*}$ 。

语法分析树

语法分析树（Parse Tree）是推导过程的一种图形化表示，它直观地展示了一个句子是如何由文法的产生式生成的，并清晰地反映了句子的语法结构。

一棵语法分析树具有以下特征：

根节点：标号为文法的开始符号。
内部节点：标号为非终结符号。
叶子节点：标号为终结符号或 $\varepsilon$ （空串）。
父子关系：如果一个内部节点 $A$ 的子节点从左到右依次为 $X_1, X_2, \dots, X_n$ ，那么 $A \to X_1 X_2 \dots X_n$ 必须是文法中的一个产生式。

一棵语法分析树的所有叶子节点从左到右连接起来，就构成了该树的产出（yield），它是一个句型。如果该句型只包含终结符，那么它就是一个句子。

树与推导的对应关系

一棵语法分析树唯一地对应一个最左推导和一个最右推导。反之，一个最左（或最右）推导也唯一地确定一棵语法分析树。

然而，一棵树可能对应多个不同的普通推导序列（因为替换顺序不同）。

假设有推导序列 $A \Rightarrow \alpha_1 \Rightarrow \alpha_2 \Rightarrow \dots \Rightarrow \alpha_n$ 从推导序列构造分析树的过程如下：

初始化， $\alpha_1$ 的分析树是标号为 $A$ 的单节点树。
假设已经构造出了 $\alpha_{i-1} = X_1 X_2 \dots X_{k}$ 的分析树 $T_{i-1}$ ，且 $\alpha_{i-1} \Rightarrow \alpha_i$ 是将 $X_{j}$ 替换为 $\beta$ ，那么在当前分析树中找出第 $j$ 个非 $\varepsilon$ 节点，向这个节点增加构成 $\beta$ 的子节点，得到 $\alpha_i$ 的分析树 $T_i$ 。若 $\beta = \varepsilon$ ，则增加一个标号为 $\varepsilon$ 的叶子节点。
重复上述过程，直到构造出 $\alpha_n$ 的分析树 $T_n$ 。

文法的二义性

一个理想的文法应该为每个合法的句子提供唯一一种语法结构解释。

二义性文法

如果一个文法可以为某个句子生成多于一棵的语法分析树，那么这个文法就是二义性（ambiguous）的。

二义性对于编译器来说是致命的，因为它意味着同一个程序可以有多种不同的解释（即不同的语义）。

表达式的二义性

考虑文法 $E \to E + E \mid E * E \mid \mathbf{id}$ 和句子 $\mathbf{id} + \mathbf{id} * \mathbf{id}$ 。它可以生成两棵不同的分析树：

树 a 对应 $\mathbf{id} + (\mathbf{id} * \mathbf{id})$ ，即先乘后加（符合常见的运算优先级）。
树 b 对应 $(\mathbf{id} + \mathbf{id}) * \mathbf{id}$ ，即先加后乘。

这两种解释显然会导致不同的计算结果。

「悬空 $\mathbf{else}$ 」问题

考虑 $\mathbf{if}$ 语句的常见文法：

$\begin{aligned} \mathit{stmt} \to\ &\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\\ \mid&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\ \mathbf{else}\ \mathit{stmt}\\ \mid &\ \mathit{other} \end{aligned}$

对于句子 $\mathbf{if}\ E_1\ \mathbf{then}\ \mathbf{if}\ E_2\ \mathbf{then}\ S_1\ \mathbf{else}\ S_2$ ，存在两种解析方式：

$\mathbf{else}$ 与最近的未匹配的 $\mathbf{if}$ （即 $\mathbf{if}\ E_2$ ）配对（这是大多数语言的规定）。
$\mathbf{else}$ 与最远的 $\mathbf{if}$ （即 $\mathbf{if}\ E_1$ ）配对。

这会导致 $\mathbf{else}$ 子句的归属不确定，从而产生语义上的歧义。

验证文法生成的语言

验证文法 $G$ 生成语言 $L$ 基本步骤：

首先证明 $L(G) \subseteq L$ $L (G) \subseteq L$ ： $G$ $G$ 生成的每个串都在 $L$ $L$ 中。
- 按照推导序列长度进行数学归纳
然后证明 $L \subseteq L(G)$ $L \subseteq L (G)$ ： $L$ $L$ 中： $L$ $L$ 的每个串都能由 $G$ $G$ 生成。
- 按照符号串的长度来构造推导序列
结合上述两点，得出 $L(G) = L$ 。

例子

定义语言 $L$ 和文法 $G$ ：

语言 $L$ ：所有由 $n$ $n$ 个 $a$ $a$ 后面跟着 $n$ $n$ 个 $b$ $b$ 组成的字符串，其中 $n \ge 0$ $n ⩾ 0$ 。
- 即 $L = \{ a^n b^n \mid n \ge 0 \} = \{ \varepsilon, ab, aabb, aaabbb, \dots \}$
文法 $G$ ：
- 终结符： $\{a, b\}$
- 非终结符： $\{S\}$ （S 是开始符号）
- 产生式：
  1. $S \to aSb$
  2. $S \to \varepsilon$

证明 $L(G) \subseteq L$ ： $G$ 生成的每个串都在 $L$ 中。

证明方法：对推导序列的长度（即产生式应用次数）进行数学归纳。
归纳基础：
- 当推导序列长度为 1 时，唯一的推导是 $S \Rightarrow \varepsilon$ （使用产生式 2）。
- $\varepsilon$ 对应 $a^0 b^0$ ，它在 $L$ 中。所以基础情况成立。
归纳假设：
- 假设任何长度小于 $k$ 的推导 $S \xRightarrow{*} w'$ ，其结果 $w'$ 都属于 $L$ 。
归纳步骤：
- 考虑一个长度为 $k$ 的推导 $S \xRightarrow{k} w$ 。
- 由于 $k > 1$ （因为 $k=1$ 已在基础中处理），第一次应用产生式必然是 $S \to aSb$ （如果第一次是 $S \to \varepsilon$ ，则推导长度为 1）。
- 所以，推导形式为 $S \Rightarrow aSb \xRightarrow{k-1} aw'b$ 。
- 其中， $S \xRightarrow{k-1} w'$ 是一个长度为 $k-1$ 的推导。
- 根据归纳假设， $w'$ 必然属于 $L$ ，即 $w' = a^j b^j$ （对于某个 $j \ge 0$ ）。
- 因此， $w = a(a^j b^j)b = a^{j+1} b^{j+1}$ 。
- 这个字符串形式 $a^{j+1} b^{j+1}$ 也符合 $L$ 的定义（即 $a^n b^n$ 形式，其中 $n=j+1$ ）。
结论：根据数学归纳法，所有由 $G$ 生成的字符串都属于 $L$ 。即 $L(G) \subseteq L$ 成立。

证明 $L \subseteq L(G)$ ： $L$ 中的每个串都能由 $G$ 生成。

证明方法：对字符串的长度进行数学归纳。
归纳基础：
- 当字符串长度为 0 时，唯一的字符串是 $\varepsilon$ 。
- 文法 $G$ 有产生式 $S \to \varepsilon$ ，所以 $\varepsilon$ 可以由 $G$ 生成。基础情况成立。
归纳假设：
- 假设任何长度小于 $m$ 的字符串 $w' \in L$ ，都可以由 $G$ 生成（即 $w' \in L(G)$ ）。
归纳步骤：
- 考虑一个长度为 $m$ 的字符串 $w \in L$ （其中 $m > 0$ ）。
- 由于 $w \in L$ 且 $w \ne \varepsilon$ ，它必然是 $a^n b^n$ 的形式，其中 $n > 0$ 。
- 这意味着 $w$ 必须以 $a$ 开头，以 $b$ 结尾。所以，我们可以将 $w$ 写成 $w = a w' b$ 的形式。
- 那么 $w'$ 必然是 $a^{n-1} b^{n-1}$ 。
- 显然， $w'$ 也属于 $L$ 。
- 而且， $|w'| = m-2$ ，所以 $|w'| < m$ 。
- 根据归纳假设， $w'$ 可以由 $G$ 生成，即存在推导 $S \xRightarrow{*} w'$ 。
- 现在，我们可以构造 $w$ 的推导： $S \to aSb \xRightarrow{*} a w' b = w$ 。
- 因此， $w$ 可以由 $G$ 生成。
结论：根据数学归纳法，所有属于 $L$ 的字符串都可以由 $G$ 生成。即 $L \subseteq L(G)$ 成立。

结合上述两点，得出 $L(G) = L$ 。

由于 $L(G) \subseteq L$ 且 $L \subseteq L(G)$ ，所以文法 $G$ 准确地生成了语言 $L$ 。

为语法分析器设计文法

虽然上下文无关文法很强大，但并非所有文法都适合直接用于构建高效的语法分析器。特别是自顶向下的分析方法，对文法的形式有严格要求。因此，在进行语法分析之前，我们常常需要对文法进行改造。

主要的处理步骤包括：

消除二义性：重写文法以确保每个句子只有唯一的分析树。
消除左递归：改造产生式，以避免自顶向下分析器陷入无限循环。
提取左公因子：改造产生式，以帮助分析器在面临多个选择时做出确定性的决策。

消除二义性

消除二义性没有通用的算法，通常需要根据我们期望的语义（如运算符的优先级和结合性）来重写文法。

处理表达式二义性：通过引入新的非终结符号来强制优先级和结合性。
- 原始二义性文法： $E \to E + E \mid E * E \mid (E) \mid \mathbf{id}$
- 无二义性文法：
  $\begin{aligned} E &\to E + T \kern{-1em}&&\mid T & \quad\text{（加法是左结合的）} \\ T &\to T * F \kern{-1em}&&\mid F & \quad\text{（乘法是左结合的）} \\ F &\to ( E ) \kern{-1em}&&\mid \mathbf{id} & \quad\text{（$F$ 的优先级最高）} \end{aligned}$
  这个新文法通过层次结构 $E \to T \to F$ 确保了乘法的优先级高于加法。同时， $E \to E + T$ 这样的产生式形式强制了加法是左结合的（即 a+b+c 被解析为 (a+b)+c）。
处理「悬空 $\mathbf{else}$ 」：规定 $\mathbf{else}$ 总是与最近的未匹配 $\mathbf{then}$ 结合。
- 原始二义性文法：
  
  $\begin{aligned} \mathit{stmt} \to\ &\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\\ \mid&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\ \mathbf{else}\ \mathit{stmt}\\ \mid &\ \mathit{other} \end{aligned}$
- 无二义性文法：
  
  $\begin{aligned} \mathit{stmt} \to&\ \mathit{matched\_stmt} \mid \mathit{open\_stmt} \\ \mathit{matched\_stmt} \to&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{matched\_stmt}\ \mathbf{else}\ \mathit{matched\_stmt}\\ \mid&\ \mathit{other} \\ \mathit{open\_stmt} \to&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt} \\ \mid&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{matched\_stmt}\ \mathbf{else}\ \mathit{open\_stmt} \end{aligned}$
  
  这里的 $\mathit{matched\_stmt}$ 表示一个完整的、 $\text{\textbf{if}-\textbf{then}-\textbf{else}}$ 配对的语句，而 $\mathit{open\_stmt}$ 表示一个只有 $\text{\textbf{if}-\textbf{then}}$ 、缺少 $\mathbf{else}$ 的语句。文法规则强制 $\mathbf{then}$ 和 $\mathbf{else}$ 之间的语句必须是 $\mathit{matched\_stmt}$ ，从而解决了二义性。

消除左递归

左递归

一个文法是左递归（Left Recursive）的，如果它存在一个非终结符号 $A$ ，使得 $A$ 可以经过一步或多步推导得到一个以 $A$ 自身开头的句型（即 $A \xRightarrow{+} A\alpha$ ）。

立即左递归：存在形如 $A \to A\alpha$ 的产生式。

左递归对于自顶向下的分析器是致命的，因为它会导致分析过程无限循环。

消除立即左递归

立即左递归消除

对于一组具有立即左递归的产生式：

$A \to A\alpha_1 \mid A\alpha_2 \mid \dots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \dots \mid \beta_n$

其中 $\beta_i$ 不以 $A$ 开头。

可以等价地替换为：

$\gdef\nt#1{\rlap{$#1$}\phantom{T_m}} \begin{aligned} \nt A &\to \nt{\beta_1}\nt{A'} \mid \nt{\beta_2} \nt{A'} \mid \dots \mid \nt{\beta_n} \nt{A'} \\ \nt{A'} &\to \nt{\alpha_1}\nt{A'} \mid \nt{\alpha_2} \nt{A'} \mid \dots \mid \nt{\alpha_m} \nt{A'} \mid \nt\varepsilon \end{aligned}$

这个变换的直观理解是：任何由 $A$ 推导出的串，都必须以某个 $\beta_i$ 开头，后面跟着零个或多个由 $\alpha_{j}$ 构成的序列。

例子

原始文法：

$\begin{aligned} \nt{E} &\to \nt{E} \nt{+} \nt{T} \mid \nt T \\ \nt{T} &\to \nt{T} \nt{*} \nt{F} \mid \nt F \end{aligned}$

消除左递归后：

$\begin{aligned} \nt{E} &\to \nt{T} \nt{E'} \\ \nt{E'} &\to \nt{+} \nt{T} \nt{E'} \mid \nt{\varepsilon} \\ \nt{T} &\to \nt{F} \nt{T'} \\ \nt{T'} &\to \nt{*} \nt{F} \nt{T'} \mid \nt{\varepsilon} \end{aligned}$

消除一般左递归

多步左递归

一个文法是多步左递归（Indirect Left Recursive）的，如果它存在一个非终结符号 $A$ ，使得 $A$ 可以经过多步推导得到一个以 $A$ 自身开头的句型（即 $A \xRightarrow{+} A\alpha$ ），但不存在形如 $A \to A\alpha$ 的立即左递归产生式。

例如，文法中存在产生式 $A \to B\alpha$ 和 $B \to A\beta$ ，这将导致 $A \xRightarrow{+} A\beta\alpha$ ，形成多步左递归。

消除立即左递归的方法不足以处理所有左递归情况。对于更一般的左递归（包括多步左递归），我们需要一个更通用的算法。

下面的算法能够消除文法中的所有左递归，无论是立即左递归还是多步左递归。

通用算法

对非终结符号排序：任意选择一个顺序，将文法中的所有非终结符号排序为 $A_1, A_2, \dots, A_n$ 。
迭代处理每个非终结符号：对于 $i = 1, 2, \dots, n$ ：
- 消除对「更早」非终结符号的左递归：对于 $j = 1, 2, \dots, i-1$ $j = 1, 2, \dots, i - 1$ ：
  - 检查所有形如 $A_i \to A_j \gamma$ 的产生式。
  - 对于每一个这样的产生式，用 $A_j$ $A_{j}$ 的所有当前产生式右部来替换 $A_j$ $A_{j}$ 。
    - 如果 $A_j \to \delta_1 \mid \delta_2 \mid \dots \mid \delta_k$ ，则将 $A_i \to A_j \gamma$ 替换为： $A_i \to \delta_1 \gamma \mid \delta_2 \gamma \mid \dots \mid \delta_k \gamma$ 。
  - 重复此步骤，直到 $A_i$ $A_{i}$ 的所有产生式右部都不以 $A_j$ $A_{j}$ （其中 $j < i$ $j < i$ ）开头。
    - 此步骤的目的是将所有形如 $A_i \to A_j \gamma$ 的产生式转换成 $A_i \to \dots$ 的形式，其中右部不再以 $A_j$ 开头，从而将多步左递归转化为立即左递归或非左递归形式。
- 消除立即左递归：此时， $A_i$ 的所有产生式都将是形如 $A_i \to A_i \alpha \mid \beta$ 的形式（其中 $\beta$ 不以 $A_i$ 开头）。应用前面介绍的立即左递归消除方法来处理 $A_i$ 。

例子

原始文法：

$\begin{aligned} S &\to A a \mid b \\ A &\to S c \mid d \end{aligned}$

这个文法存在多步左递归： $A \to S c \to A a c$ 。

消除左递归的步骤：

排序非终结符号：设 $A_1 = S$ ， $A_2 = A$ 。
处理 $A_1 = S$ （ $i = 1$ $i = 1$ ）：
- 消除对「更早」非终结符号的左递归：没有 $j < 1$ ，所以此步骤跳过。
- 消除立即左递归： $S$ 的产生式（ $S \to A a \mid b$ ）没有立即左递归。
- $S$ 的产生式保持不变： $S \to A a \mid b$ 。
处理 $A_2 = A$ （ $i = 2$ $i = 2$ ）：
- 消除对 $A_1$ 的左递归（ $j = 1$ $j = 1$ ）：
  - 我们有产生式 $A \to S c$ 。
  - 将 $S$ 的当前产生式（ $S \to A a \mid b$ ）代入 $A \to S c$ ：
    $A \to (A a) c \mid (b) c \mid d$
  - 整理后得到： $A \to A a c \mid b c \mid d$ 。
  - 现在 $A$ 的产生式右部不再以 $A_1$ （ $S$ ）开头。
- 消除立即左递归：
  - 现在 $A$ 存在立即左递归： $A \to A (a c) \mid (b c \mid d)$ 。
  - 引入新的非终结符号 $A'$ ，将 $A$ 的产生式替换为：
    $\begin{aligned} A &\to b c A' \mid d A' \\ A' &\to a c A' \mid \varepsilon \end{aligned}$

消除左递归后的文法：

$\begin{aligned} S &\to A a \mid b \\ A &\to b c A' \mid d A' \\ A' &\to a c A' \mid \varepsilon \end{aligned}$

这个转换后的文法不再包含任何左递归，适合自顶向下的分析。

提取左公因子

当一个非终结符号的多个产生式体具有相同的公共前缀时，自顶向下的分析器在读入这个前缀后，将无法确定使用哪个产生式。提取左公因子（Left Factoring）就是解决这个问题的技术。

提取方法

对于一组产生式：

$\begin{aligned} A &\to \alpha \beta_1 \mid \alpha \beta_2 \mid \dots \mid \alpha \beta_n \mid \gamma \end{aligned}$

其中 $\alpha$ 是最长公共前缀。

可以等价地替换为：

$\begin{aligned} A &\to \alpha A' \mid \gamma \\ A' &\to \beta_1 \mid \beta_2 \mid \dots \mid \beta_n \end{aligned}$

例子

原始文法：

$\begin{aligned} \mathit{stmt} \to&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\ \mathbf{else}\ \mathit{stmt} \\ \mid&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt} \end{aligned}$

提取左公因子后：

$\begin{aligned} \mathit{stmt} \to&\ \mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}\ \mathit{stmt\_tail} \\ \mathit{stmt\_tail} \to&\ \mathbf{else}\ \mathit{stmt} \mid \varepsilon \end{aligned}$

文法与语言的层级补充

乔姆斯基体系（Chomsky Hierarchy）

语言学家诺姆·乔姆斯基将文法按照产生式形式的限制，划分为四个层级，描述能力从强到弱依次为：

0 型文法（短语结构文法）： $\alpha \to \beta$ ，无限制。对应图灵机。
1 型文法（上下文相关文法）： $\alpha A \beta \to \alpha \gamma \beta$ ， $\gamma$ 非空。 $A$ 的重写依赖于其上下文 $\alpha$ 和 $\beta$ 。对应线性有界自动机。
2 型文法（上下文无关文法）： $A \to \gamma$ 。 $A$ 的重写不依赖于其上下文。对应下推自动机。这是大多数程序设计语言语法描述的基础。
3 型文法（正则文法）： $A \to t$ 或 $A \to tB$ （右线性）或 $A \to Bt$ （左线性）。对应有限自动机（DFA/NFA）。

上下文无关文法 vs. 正则表达式

表达能力：上下文无关文法（CFG）的表达能力强于正则表达式。
- 所有可以用正则表达式描述的语言（正则语言），都可以用 CFG 描述。
- 但存在一些 CFG 能描述而正则表达式无法描述的语言。
经典反例：语言 $L = \{a^n b^n \mid n \ge 1\}$ $L = {a^{n} b^{n} ∣ n ⩾ 1}$ 。
- 这个语言可以用简单的 CFG $S \to aSb \mid ab$ 描述。
- 但它不是正则语言，因为识别它需要一个能够「计数」的机制（ $b$ 的数量必须等于 $a$ 的数量），而有限自动机没有记忆能力，无法完成这种计数。
- 例如说假定 DFA 有 $k$ 个状态，当输入 $a^{k+1}b^{k+1}$ 时，DFA 在读完前 $k+1$ 个 $a$ 后，必然会进入某个状态两次（鸽巢原理）。这意味着 DFA 无法区分 $a$ 的数量，从而无法确保 $b$ 的数量与之匹配。
适用场景：
- 正则表达式：简洁、高效，非常适合描述词法单元（如标识符、数字）这类扁平、非嵌套的结构。
- 上下文无关文法：能够自然地描述具有递归和嵌套特性的语法结构（如表达式、语句块），是语法分析的核心。

为 NFA 构造等价文法

假设我们有一个 NFA $M = (Q, \Sigma, \delta, q_0, F)$ ，其中：

$Q$ 是状态的有限集合。
$\Sigma$ 是输入字母表。
$\delta$ 是转移函数， $\delta\colon Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ 。
$q_0 \in Q$ 是起始状态。
$F \subseteq Q$ 是终结状态的集合。

我们要构造一个等价的 CFG $G = (V, \Sigma, P, S)$ ，其中：

$V$ 是非终结符的有限集合。
$\Sigma$ 是终结符的有限集合（与 NFA 的输入字母表相同）。
$P$ 是产生式的有限集合。
$S$ 是起始非终结符。

步骤：

创建非终结符：
- 对于 NFA 中的每一个状态 $q \in Q$ ，在 CFG 中创建一个对应的非终结符 $A_q$ 。
- 将 CFG 的起始非终结符 $S$ 设定为对应 NFA 起始状态 $q_0$ 的非终结符，即 $S = A_{q_0}$ 。
创建转移产生式：
- 对于 NFA 中的每一个转移 $\delta(q, x) = \{p_1, p_2, \dots, p_k\}$ $δ (q, x) = {p_{1}, p_{2}, \dots, p_{k}}$ ，其中 $q, p_i \in Q$ $q, p_{i} \in Q$ 且 $x \in \Sigma \cup \{\varepsilon\}$ $x \in Σ \cup {ε}$ ：
  - 对于每一个 $p_i \in \{p_1, \dots, p_k\}$ ，在 CFG 中添加一个产生式： $A_q \to x A_{p_i}$
  - 如果 $x = \varepsilon$ ，则产生式为： $A_q \to A_{p_i}$
创建终结状态产生式：
- 对于 NFA 中的每一个终结状态 $q_f \in F$ $q_{f} \in F$ ：
  - 在 CFG 中添加一个产生式： $A_{q_f} \to \varepsilon$

例子

考虑一个接受所有以 a 结尾的字符串的 NFA，例如 (a|b)*a。

状态（ $Q$ ）： $\{q_0, q_1\}$
输入字母表（ $\Sigma$ ）： $\{a, b\}$
起始状态（ $q_0$ ）： $q_0$
终结状态（ $F$ ）： $\{q_1\}$
转移函数（ $\delta$ $δ$ ）：
- $\delta(q_0, a) = \{q_0, q_1\}$ （从 $q_0$ 读 $a$ 可以到 $q_0$ 或 $q_1$ ）
- $\delta(q_0, b) = \{q_0\}$ （从 $q_0$ 读 $b$ 只能到 $q_0$ ）
- $\delta(q_1, a) = \empty$
- $\delta(q_1, b) = \empty$

NFA 图示：

graph LR
start:::hidden -->|start| q0((q0))

q0 -- a, b --> q0
q0 -- a --> q1(((q1)))

q1

classDef hidden display:none
style start fill:#fff,stroke:#fff,stroke-width:0px,color:#333
style q0 fill:#fff,stroke:#333,stroke-width:2px
style q1 fill:#fff,stroke:#333,stroke-width:2px

其中 q0 是起始状态，q1 是终结状态。

构造 CFG 的步骤：

创建非终结符：
- 对于状态 $q_0$ ，创建非终结符 $Q_0$ 。
- 对于状态 $q_1$ ，创建非终结符 $Q_1$ 。
- CFG 的起始非终结符 $S = Q_0$ （对应 NFA 的起始状态 $q_0$ ）。
创建转移产生式：
- 从 $\delta(q_0, a) = \{q_0, q_1\}$ $δ (q_{0}, a) = {q_{0}, q_{1}}$ ：
  - $Q_0 \to a Q_0$
  - $Q_0 \to a Q_1$
- 从 $\delta(q_0, b) = \{q_0\}$ $δ (q_{0}, b) = {q_{0}}$ ：
  - $Q_0 \to b Q_0$
创建终结状态产生式：
- $q_1$ 是终结状态： $Q_1 \to \varepsilon$

最终得到的 CFG $G$ ：

非终结符（V）： $\{Q_0, Q_1\}$
终结符（ $\Sigma$ ）： $\{a, b\}$
起始非终结符（S）： $Q_0$
产生式（P）：
1. $Q_0 \to a Q_0$
2. $Q_0 \to a Q_1$
3. $Q_0 \to b Q_0$
4. $Q_1 \to \varepsilon$

上下文无关文法的局限性

尽管 CFG 功能强大，但它无法描述程序设计语言的所有规则。例如，「变量必须先声明后使用」这类规则。

抽象地看，这类规则类似于语言 $L = \{wcw \mid w \in (a\mid b)*\}$ ，其中 $w$ 的第一次出现可视为「声明」，第二次出现视为「使用」。
这个语言不是上下文无关的，因为它要求两个 $w$ 必须完全相同，这超出了 CFG 的匹配能力。

这类依赖于上下文的规则，通常不在语法分析阶段处理，而是留给语义分析阶段来检查。我们之所以在语法分析阶段坚持使用 CFG，是因为它具有高效的分析算法。

自顶向下分析

自顶向下分析（Top-Down Parsing）是一种重要的语法分析策略。顾名思义，它试图从文法的开始符号（根节点）出发，通过不断应用产生式，自上而下、从左到右地为输入串构建一棵语法分析树。

这个过程可以等价地看作是寻找输入串的最左推导。

核心挑战

在推导的每一步，当面临一个非终结符号 $A$ 时，如果 $A$ 有多个产生式（如 $A \to \alpha_1 \mid \alpha_2 \mid \dots$ ），分析器必须决定选择哪一个产生式来替换 $A$ ，才能最终匹配输入的词法单元序列。

这个选择的正确与否，是自顶向下分析的关键。

上图展示了为输入串 id + id * id 进行自顶向下分析，并逐步构建语法分析树的过程。

递归下降分析

递归下降分析（Recursive Descent Parsing）是自顶向下分析的一种直接实现方式。其核心思想是为文法中的每一个非终结符号编写一个对应的递归函数（或过程）。

程序的执行从与开始符号对应的函数开始。
每个函数的功能是识别并扫描输入中能够由其对应非终结符号推导出的那部分字符串。
在函数内部，它根据产生式的结构来决定下一步操作：
- 如果遇到终结符号，就与当前输入符号进行匹配。匹配成功则消耗输入，继续；失败则报告错误。
- 如果遇到非终结符号，就递归调用该非终结符号对应的函数。

递归下降分析框架

// lookahead 指向下一个输入词法单元
Token lookahead;

// 对应非终结符号 A 的函数
void A() {
    // 1. 选择一个 A 的产生式, 假设为 A -> X1 X2 ... Xk
    //    这是最关键也是最困难的一步

    // 2. 依次处理产生式体中的每个符号
    for (int i = 1; i <= k; i++) {
        if (Xi is a non-terminal) {
            // 递归调用过程
            Xi();
        } else if (Xi is a terminal) {
            // 匹配终结符号
            match(Xi);
        } else {
            // 处理 ε 产生式
        }
    }
}

void match(Terminal t) {
    if (lookahead.type == t) {
        lookahead = getNextToken(); // 消耗输入
    } else {
        error();
    }
}

简单的递归下降分析器在面临选择时，可能会选错产生式。

回溯与左递归问题

回溯（Backtracking）：如果一个选择导致了后续的匹配失败，分析器需要撤销这次选择，将输入指针重置到选择前的位置，然后尝试该非终结符号的下一个产生式。这种反复的尝试和重置称为回溯。回溯会极大地降低分析效率，甚至可能导致对输入的重复扫描。
左递归：如果文法存在左递归（特别是立即左递归，如 $A \to A\alpha$ ），递归下降分析器会陷入无限递归。函数 A() 会无条件地立即再次调用自身，而输入指针没有任何移动，从而导致栈溢出。

由于存在这些严重问题，需要回溯的通用递归下降分析方法在实践中很少使用。我们需要一种更「聪明」的方法，能够在做出选择前就「预知」哪条路是正确的，从而避免回溯。

预测分析

预测分析（Predictive Parsing）是一种特殊的、无回溯的自顶向下分析技术。它通过向前预读一个或多个输入符号（通常是一个，称为向前看符号，lookahead symbol），来唯一地确定当前应该使用哪个产生式。

为了实现预测分析，文法必须满足特定条件，即经过改造，消除了二义性、左递归，提取了左公因子等。这样的文法通常被称为 LL(1) 文法。

LL(1)

第一个 L：表示从左（Left）到右扫描输入。
第二个 L：表示构造最左（Leftmost）推导。
1：表示在做分析决定时，只需要向前看 1 个输入符号。

为了系统地实现预测分析，我们需要两个关键的辅助函数：FIRST 和 FOLLOW。

FIRST 集

$\mathrm{FIRST}(\alpha)$

对于任意文法符号串 $\alpha$ （由终结符和/或非终结符组成）， $\mathrm{FIRST}(\alpha)$ 定义为可以从 $\alpha$ 推导出的所有串的首个终结符号的集合。

如果 $\alpha \xRightarrow{*} \varepsilon$ ，那么 $\varepsilon$ 也在 $\mathrm{FIRST}(\alpha)$ 中。

$\mathrm{FIRST}$ 集告诉我们，一个文法符号串可能以哪些终结符号开头。这正是我们在选择产生式时最需要的信息。

计算 FIRST 集

计算所有文法符号 $X$ 的 $\mathrm{FIRST}(X)$ 集合的算法如下：

初始化：对所有文法符号 $X$ ， $\mathrm{FIRST}(X) = \empty$ 。
迭代计算：不断应用以下规则，直到所有 $\mathrm{FIRST}$ $FIRST$ 集不再增大为止。
- 规则 1（终结符）：如果 $X$ 是一个终结符号，则 $\mathrm{FIRST}(X) = \{X\}$ 。
- 规则 2（产生式）：如果存在产生式 $X \to Y_1 Y_2 \dots Y_k$ $X \to Y_{1} Y_{2} \dots Y_{k}$ ：
  - 将 $\mathrm{FIRST}(Y_1)$ 中所有非 $\varepsilon$ 符号加入到 $\mathrm{FIRST}(X)$ 中。
  - 如果 $\varepsilon \in \mathrm{FIRST}(Y_1)$ ，则再将 $\mathrm{FIRST}(Y_2)$ 中所有非 $\varepsilon$ 符号加入到 $\mathrm{FIRST}(X)$ 中。
  - …以此类推，如果对所有的 $j < i$ ，都有 $\varepsilon \in \mathrm{FIRST}(Y_j)$ ，则将 $\mathrm{FIRST}(Y_i)$ 中所有非 $\varepsilon$ 符号加入到 $\mathrm{FIRST}(X)$ 中。
- 规则 3（ $\varepsilon$ $ε$ 产生式）：
  - 如果存在产生式 $X \to \varepsilon$ ，则将 $\varepsilon$ 加入到 $\mathrm{FIRST}(X)$ 中。
  - 如果存在产生式 $X \to Y_1 Y_2 \dots Y_k$ ，且对于所有的 $i$ ，都有 $\varepsilon \in \mathrm{FIRST}(Y_i)$ ，则将 $\varepsilon$ 加入到 $\mathrm{FIRST}(X)$ 中。

对于一个文法符号串 $\alpha = X_1 X_2 \dots X_n$ ，其 $\mathrm{FIRST}(\alpha)$ 的计算方法与上述规则 2 类似。

计算例子 1

考虑以下文法 G：

$E \to T E'$
$E' \to + T E' \mid \varepsilon$
$T \to F T'$
$T' \to * F T' \mid \varepsilon$
$F \to ( E ) \mid \mathbf{id}$

其中，非终结符是 $\{E, E', T, T', F\}$ ，终结符是 $\{+, *, (, ), \mathbf{id}\}$ 。

计算各符号的 FIRST 集。

过程

初始化
- 首先，为所有非终结符创建一个空的 FIRST 集：
  - $\mathrm{FIRST}(E) = \empty$
  - $\mathrm{FIRST}(E') = \empty$
  - $\mathrm{FIRST}(T) = \empty$
  - $\mathrm{FIRST}(T') = \empty$
  - $\mathrm{FIRST}(F) = \empty$
- 根据规则 1，知道所有终结符的 FIRST 集就是它们自身：
  - $\mathrm{FIRST}(+) = \{+\}$
  - $\mathrm{FIRST}(*) = \{*\}$
  - $\mathrm{FIRST}(() = \{(\}$
  - $\mathrm{FIRST}()) = \{)\}$
  - $\mathrm{FIRST}(\mathbf{id}) = \{\mathbf{id}\}$
第 1 轮迭代：
- 对于 $F$ ：
  - 产生式 $F \to ( E )$ ：右侧第一个符号是终结符 $($ 。根据规则 2，将 $($ 加入 $\mathrm{FIRST}(F)$ 。
  - 产生式 $F \to \mathbf{id}$ ：右侧第一个符号是终结符 $\mathbf{id}$ 。将 $\mathbf{id}$ 加入 $\mathrm{FIRST}(F)$ 。
  - 更新后： $\mathrm{FIRST}(F) = \{ (, \mathbf{id} \}$
- 对于 $T'$ ：
  - 产生式 $T' \to * F T'$ ：右侧第一个符号是终结符 $*$ 。将 $*$ 加入 $\mathrm{FIRST}(T')$ 。
  - 产生式 $T' \to \varepsilon$ ：根据规则 3，将 $\varepsilon$ 加入 $\mathrm{FIRST}(T')$ 。
  - 更新后： $\mathrm{FIRST}(T') = \{ *, \varepsilon \}$
- 对于 $T$ ：
  - 产生式 $T \to F T'$ ：右侧第一个符号是非终结符 $F$ 。根据规则 2，将 $\mathrm{FIRST}(F)$ 中所有非 $\varepsilon$ 符号加入 $\mathrm{FIRST}(T)$ 。
  - $\mathrm{FIRST}(F)$ 是 $\{ (, \mathbf{id} \}$ ，其中没有 $\varepsilon$ 。所以将 $\{ (, \mathbf{id} \}$ 加入 $\mathrm{FIRST}(T)$ 。
  - 更新后： $\mathrm{FIRST}(T) = \{ (, \mathbf{id} \}$
- 对于 $E'$ ：
  - 产生式 $E' \to + T E'$ ：右侧第一个符号是终结符 $+$ 。将 $+$ 加入 $\mathrm{FIRST}(E')$ 。
  - 产生式 $E' \to \varepsilon$ ：根据规则 3，将 $\varepsilon$ 加入 $\mathrm{FIRST}(E')$ 。
  - 更新后： $\mathrm{FIRST}(E') = \{ +, \varepsilon \}$
- 对于 $E$ ：
  - 产生式 $E \to T E'$ ：右侧第一个符号是非终结符 $T$ 。将 $\mathrm{FIRST}(T)$ 中所有非 $\varepsilon$ 符号加入 $\mathrm{FIRST}(E)$ 。
  - $\mathrm{FIRST}(T)$ 是 $\{ (, \mathbf{id} \}$ ，其中没有 $\varepsilon$ 。所以将 $\{ (, \mathbf{id} \}$ 加入 $\mathrm{FIRST}(E)$ 。
  - 更新后： $\mathrm{FIRST}(E) = \{ (, \mathbf{id} \}$
- 第 1 轮迭代结束，各集合状态如下：
  - $\mathrm{FIRST}(E) = \{ (, \mathbf{id} \}$
  - $\mathrm{FIRST}(E') = \{ +, \varepsilon \}$
  - $\mathrm{FIRST}(T) = \{ (, \mathbf{id} \}$
  - $\mathrm{FIRST}(T') = \{ *, \varepsilon \}$
  - $\mathrm{FIRST}(F) = \{ (, \mathbf{id} \}$
第 2 轮迭代：
- 对于 $F$ ：其产生式右侧都以终结符开始， $\mathrm{FIRST}(F)$ 不会再改变。
- 对于 $T'$ ：其产生式右侧以终结符或 $\varepsilon$ 开始， $\mathrm{FIRST}(T')$ 不会再改变。
- 对于 $T$ ：
  - 产生式 $T \to F T'$ ：需要考察 $\mathrm{FIRST}(F)$ 。 $\mathrm{FIRST}(F)$ 仍然是 $\{ (, \mathbf{id} \}$ ，将其加入 $\mathrm{FIRST}(T)$ 不会带来任何变化。因为 $\varepsilon \notin \mathrm{FIRST}(F)$ ，不需要继续考察 $T'$ 。所以 $\mathrm{FIRST}(T)$ 不变。
- 对于 $E'$ ：其产生式右侧以终结符或 $\varepsilon$ 开始， $\mathrm{FIRST}(E')$ 不会再改变。
- 对于 $E$ ：
  - 产生式 $E \to T E'$ ：需要考察 $\mathrm{FIRST}(T)$ 。 $\mathrm{FIRST}(T)$ 仍然是 $\{ (, \mathbf{id} \}$ ，将其加入 $\mathrm{FIRST}(E)$ 不会带来任何变化。因为 $\varepsilon \notin \mathrm{FIRST}(T)$ ，不需要继续考察 $E'$ 。所以 $\mathrm{FIRST}(E)$ 不变。
- 在第 2 轮迭代中，所有 FIRST 集都没有增大。因此，算法终止。

最终所有非终结符的 FIRST 集计算完毕：

$\mathrm{FIRST}(E) = \{ (, \mathbf{id} \}$
$\mathrm{FIRST}(E') = \{ +, \varepsilon \}$
$\mathrm{FIRST}(T) = \{ (, \mathbf{id} \}$
$\mathrm{FIRST}(T') = \{ *, \varepsilon \}$
$\mathrm{FIRST}(F) = \{ (, \mathbf{id} \}$

计算例子 2

在上面的文法中，计算一个符号串 $\alpha = T' F$ 的 $\mathrm{FIRST}$ 集，即 $\mathrm{FIRST}(T' F)$ 。

过程

考察第一个符号 $T'$ ：
- $\mathrm{FIRST}(T') = \{ *, \varepsilon \}$ 。
- 将其中所有非 $\varepsilon$ 符号加入 $\mathrm{FIRST}(T' F)$ 。
- 当前 $\mathrm{FIRST}(T' F) = \{ * \}$ 。
检查 $T'$ 是否能推导出 $\varepsilon$ ：
- $\varepsilon \in \mathrm{FIRST}(T')$ 。
- 因此，需要继续考察下一个符号 $F$ 。
考察第二个符号 $F$ ：
- $\mathrm{FIRST}(F) = \{ (, \mathbf{id} \}$ 。
- 将 $\mathrm{FIRST}(F)$ 中所有非 $\varepsilon$ 符号加入 $\mathrm{FIRST}(T' F)$ 。
- 当前 $\mathrm{FIRST}(T' F) = \{ *, (, \mathbf{id} \}$ 。
检查 $F$ 是否能推导出 $\varepsilon$ ：
- $\varepsilon \notin \mathrm{FIRST}(F)$ 。
- 计算过程停止。

所以， $\mathrm{FIRST}(T' F) = \{ * , (, \mathbf{id} \}$ 。

FOLLOW 集

当一个产生式可能推导出 $\varepsilon$ 时（例如 $A \to \varepsilon$ ），我们无法仅凭 $\mathrm{FIRST}$ 集做出判断。此时，我们需要知道在当前句型中，什么终结符号可以紧跟在 $A$ 的后面。如果当前的向前看符号 $a$ 就是这样一个符号，那么选择 $A \to \varepsilon$ 就是一个合理的决策。这就是 $\mathrm{FOLLOW}$ 集的作用。

FOLLOW(A)

对于任意非终结符号 $A$ ， $\mathrm{FOLLOW}(A)$ 定义为在某些句型中，能够紧跟在 $A$ 右边的终结符号的集合。

如果 $A$ 可以是某个句型的最右符号，那么输入结束标记 $\$$ 也在 $\mathrm{FOLLOW}(A)$ 中。 $\$$ 是一个特殊的终结符号。

计算 FOLLOW 集

计算所有非终结符号 $A$ 的 $\mathrm{FOLLOW}(A)$ 集合的算法如下：

初始化：对所有非终结符号 $A$ ， $\mathrm{FOLLOW}(A) = \empty$ 。
规则 1（开始符号）：将 $\$$ 放入 $\mathrm{FOLLOW}(S)$ 中，其中 $S$ 是开始符号。
迭代计算：不断应用以下规则，直到所有 $\mathrm{FOLLOW}$ $FOLLOW$ 集不再增大为止。
- 规则 2：如果存在产生式 $A \to \alpha B \beta$ $A \to α Bβ$ ：
  - 将 $\mathrm{FIRST}(\beta)$ 中除 $\varepsilon$ 之外的所有符号加入到 $\mathrm{FOLLOW}(B)$ 中。
- 规则 3：如果存在产生式 $A \to \alpha B$ $A \to α B$ ，或者存在产生式 $A \to \alpha B \beta$ $A \to α Bβ$ 且 $\varepsilon \in \mathrm{FIRST}(\beta)$ $ε \in FIRST (β)$ ：
  - 将 $\mathrm{FOLLOW}(A)$ 中的所有符号加入到 $\mathrm{FOLLOW}(B)$ 中。

表达式文法的 FIRST 与 FOLLOW 集

考虑熟悉的表达式文法（已消除左递归）：

$\begin{aligned} E &\to T E' \\ E' &\to + T E' \mid \varepsilon \\ T &\to F T' \\ T' &\to * F T' \mid \varepsilon \\ F &\to ( E ) \mid \mathbf{id} \end{aligned}$

计算该文法的 FOLLOW 集。

过程

FIRST 集计算结果：

$\mathrm{FIRST}(F) = \{ (, \mathbf{id} \}$
$\mathrm{FIRST}(T) = \{ (, \mathbf{id} \}$
$\mathrm{FIRST}(E) = \{ (, \mathbf{id} \}$
$\mathrm{FIRST}(E') = \{ +, \varepsilon \}$
$\mathrm{FIRST}(T') = \{ *, \varepsilon \}$

FOLLOW 集计算结果：

将 $\$$ 放入 $\mathrm{FOLLOW}(E)$ （为了视觉区分，下面用 $\mathbf{F}(E)$ 表示）。
从 $F \to (E)$ ，将 $)$ 放入 $\mathbf{F}(E)$ 。所以 $\mathbf{F}(E) = \{ ), \$ \}$ 。
从 $E \to TE'$ ，将 $\mathbf{F}(E)$ 加入 $\mathbf{F}(E')$ 。所以 $\mathbf{F}(E') = \{ ), \$ \}$ 。
从 $E' \to +TE'$ ，将 $\mathbf{F}(E')$ 加入 $\mathbf{F}(E')$ 。
从 $E \to TE'$ 和 $E' \to +TE'$ ， $\mathrm{FIRST}(E')$ 包含 $+$ ，所以将 $+$ 加入 $\mathbf{F}(T)$ 。
从 $E \to TE'$ ， $\varepsilon \in \mathrm{FIRST}(E')$ ，所以将 $\mathbf{F}(E)$ 加入 $\mathbf{F}(T)$ 。
从 $E' \to +TE'$ $E^{'} \to + T E^{'}$ ， $\varepsilon \in \mathrm{FIRST}(E')$ $ε \in FIRST (E^{'})$ ，所以将 $\mathbf{F}(E')$ $F (E^{'})$ 加入 $\mathbf{F}(T)$ $F (T)$ 。
- 综合 5, 6, 7， $\mathbf{F}(T) = \{ +, ), \$ \}$ 。
从 $T \to FT'$ ，将 $\mathbf{F}(T)$ 加入 $\mathbf{F}(T')$ 。所以 $\mathbf{F}(T') = \{ +, ), \$ \}$ 。
从 $T' \to *FT'$ ，将 $\mathbf{F}(T')$ 加入 $\mathbf{F}(T')$ 。
从 $T \to FT'$ 和 $T' \to *FT'$ ， $\mathrm{FIRST}(T')$ 包含 $*$ ，所以将 $*$ 加入 $\mathbf{F}(F)$ 。
从 $T \to FT'$ ， $\varepsilon \in \mathrm{FIRST}(T')$ ，所以将 $\mathbf{F}(T)$ 加入 $\mathbf{F}(F)$ 。
从 $T' \to *FT'$ $T^{'} \to * F T^{'}$ ， $\varepsilon \in \mathrm{FIRST}(T')$ $ε \in FIRST (T^{'})$ ，所以将 $\mathbf{F}(T')$ $F (T^{'})$ 加入 $\mathbf{F}(F)$ $F (F)$ 。
- 综合 10, 11, 12， $\mathbf{F}(F) = \{ *, +, ), \$ \}$ 。

最终结果：

$\mathrm{FOLLOW}(E) = \{ ), \$ \}$
$\mathrm{FOLLOW}(E') = \{ ), \$ \}$
$\mathrm{FOLLOW}(T) = \{ +, ), \$ \}$
$\mathrm{FOLLOW}(T') = \{ +, ), \$ \}$
$\mathrm{FOLLOW}(F) = \{ *, +, ), \$ \}$

LL(1) 文法的判定

一个文法是 LL(1) 文法，当且仅当对于该文法的任意一个非终结符号 $A$ 的两个不同产生式 $A \to \alpha$ 和 $A \to \beta$ ，满足以下两个条件：

$\mathrm{FIRST}(\alpha)$ $FIRST (α)$ 和 $\mathrm{FIRST}(\beta)$ $FIRST (β)$ 的交集为空。即 $\mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \empty$ $FIRST (α) \cap FIRST (β) = \emptyset$ 。
- 这个条件保证了当向前看符号 $a$ 属于某个产生式右部的 $\mathrm{FIRST}$ 集时，它不会同时属于另一个的，因此选择是唯一的。
如果 $\beta \xRightarrow{*} \varepsilon$ $β * ε$ （即 $\varepsilon \in \mathrm{FIRST}(\beta)$ $ε \in FIRST (β)$ ），那么 $\mathrm{FIRST}(\alpha)$ $FIRST (α)$ 和 $\mathrm{FOLLOW}(A)$ $FOLLOW (A)$ 的交集必须为空。即 $\mathrm{FIRST}(\alpha) \cap \mathrm{FOLLOW}(A) = \empty$ $FIRST (α) \cap FOLLOW (A) = \emptyset$ 。
- 这个条件处理了 $\varepsilon$ 产生式的情况。如果向前看符号 $a$ 属于 $\mathrm{FOLLOW}(A)$ ，我们可能会选择 $A \to \varepsilon$ 。为了保证选择唯一， $a$ 就不能出现在任何其他产生式 $A \to \alpha$ 的 $\mathrm{FIRST}$ 集中。

FIRST/FOLLOW 冲突

考虑文法 $G$ ：

$\begin{aligned} S &\to A a\\ A &\to a \mid \varepsilon \end{aligned}$

这个文法定义了语言 $a$ 与 $aa$ ，没有二义性、左递归和左公因子。然而，它不是 LL(1) 文法。

非终结符 $A$ 有两个产生式： $A \to a$ 和 $A \to \varepsilon$ 。

计算 FIRST 和 FOLLOW 集：

$\mathrm{FIRST}(A) = \{ a, \varepsilon \}$
$\mathrm{FOLLOW}(A) = \{ a \}$ （因为 $S \to A a$ ， $a$ 紧跟在 $A$ 之后）

$\mathrm{FIRST}(a) \cap \mathrm{FOLLOW}(A) = \{ a \} \ne \empty$ ，违反了 LL(1) 条件 2。

当分析器要推导 $A$ 时，向前看符号 $a$ 既属于 $\mathrm{FIRST}(A \to a)$ （即 $\mathrm{FIRST}(a)$ ），也属于 $\mathrm{FOLLOW}(A)$ ，导致无法唯一选择产生式。

表驱动的预测分析

有了 FIRST 和 FOLLOW 集，我们就可以构建一个预测分析表（Predictive Parsing Table），从而实现一个高效的、非递归的预测分析器。

预测分析表的构造

预测分析表是一个二维数组 $M[A, a]$ ，其中：

$A$ 是非终结符号（行）。
$a$ 是终结符号或结束标记 $\$$ （列）。
表项 $M[A, a]$ 的内容是当面临非终结符 $A$ 和输入符号 $a$ 时，应该使用的 $A$ 的产生式。

构造算法：
对于文法中的每一个产生式 $A \to \alpha$ ，执行以下步骤：

对于 $\mathrm{FIRST}(\alpha)$ 中的每一个终结符号 $a$ ，将产生式 $A \to \alpha$ 加入到 $M[A, a]$ 中。
如果 $\varepsilon \in \mathrm{FIRST}(\alpha)$ ，那么对于 $\mathrm{FOLLOW}(A)$ 中的每一个终结符号 $b$ （包括 $\$$ ），将产生式 $A \to \alpha$ 加入到 $M[A, b]$ 中。
所有未被填充的表项都标记为错误（Error）。

如果在这个过程中，任何一个表项 $M[A, a]$ 被填入了多于一个产生式，那么该文法就不是 LL(1) 文法。这种在同一个表项中的多个产生式称为冲突（conflict）。

非递归预测分析器模型

一个表驱动的预测分析器由以下几个部分组成：

输入缓冲区：存放待分析的词法单元串，以 $\$$ 结尾。
分析栈：存放文法符号。初始时，栈底是 $\$$ ，其上是开始符号 $S$ 。
预测分析表 M：指导分析过程的决策。
驱动程序：读取输入，查询分析表，并操作分析栈。

graph TD
    %% 定义子图
    subgraph "预测分析器"
        direction LR

        %% 节点定义与样式
        Input[输入缓冲区：<br>id+id*id$]:::input-node --> Driver{驱动程序}:::driver-node
        Stack[分析栈]:::stack-node -- 读栈顶 --> Driver
        Driver -- 查询 M[栈顶，输入] --> M[预测分析表]:::table-node
        M -- 返回产生式 --> Driver
        Driver -- 操作 --> Stack
        Driver --> Output[输出：<br>产生式序列]:::output-node
    end

    %% 样式定义
    classDef input-node fill:#f0f8ff, stroke:#3498db, stroke-width:2px, font-size:14px, text-align:left
    classDef stack-node fill:#e8f8f5, stroke:#1abc9c, stroke-width:2px, font-size:14px
    classDef driver-node fill:#fef9e7, stroke:#f39c12, stroke-width:2px, font-size:14px
    classDef table-node fill:#f9e7f7, stroke:#e74c3c, stroke-width:2px, font-size:14px
    classDef output-node fill:#f6ddcc, stroke:#d35400, stroke-width:2px, font-size:14px, text-align:left

    %% 边的样式
    style Input stroke:#3498db, stroke-width:1.5px
    style Stack stroke:#1abc9c, stroke-width:1.5px
    style M stroke:#e74c3c, stroke-width:1.5px
    style Output stroke:#d35400, stroke-width:1.5px

分析算法

初始化：输入指针 ip 指向输入串的第一个符号，栈中放入 $\$$ 和开始符号 $S$ （ $S$ 在栈顶）。
循环执行，令 $X$ $X$ 为栈顶符号， $a$ $a$ 为 ip 指向的输入符号：
- 如果 $X$ $X$ 是终结符或 $\$$ $$$ ：
  - 若 $X = a$ ，则匹配成功。从栈中弹出 $X$ ，ip 前进。
  - 若 $X \neq a$ ，则语法错误。
- 如果 $X$ $X$ 是非终结符：
  - 查询分析表 $M[X, a]$ 。
  - 若 $M[X, a]$ 是一个产生式 $X \to Y_1 Y_2 \dots Y_k$ ，则预测。从栈中弹出 $X$ ，然后将 $Y_k, Y_{k-1}, \dots, Y_1$ 逆序压入栈中（保证 $Y_1$ 在栈顶）。
  - 若 $M[X, a]$ 是错误项，则语法错误。
结束条件：
- 当栈顶为 $\$$ 且输入也为 $\$$ 时（即栈中只剩 $\$$ 且输入已耗尽），分析成功。
- 在任何其他情况下遇到错误，则分析失败。

分析过程

分析 id + id * id 的过程。

预测分析表 M：

非终结符号\输入符号	$\mathbf{id}$	$+$	$*$	$($	$)$	$\$$
$E$	$E \to T E'$	-	-	$E \to T E'$	-	-
$E'$	-	$E' \to + T E'$	-	-	$E' \to \varepsilon$	$E' \to \varepsilon$
$T$	$T \to F T'$	-	-	$T \to F T'$	-	-
$T'$	-	$T' \to \varepsilon$	$T' \to * F T'$	-	$T' \to \varepsilon$	$T' \to \varepsilon$
$F$	$F \to \mathbf{id}$	-	-	$F \to (E)$	-	-

分析过程追踪：

匹配	栈	输入	动作
-	`$E`	`id+id*id$`	预测 $E\to TE'$
-	`$E'T`	`id+id*id$`	预测 $T\to FT'$
-	`$E'T'F`	`id+id*id$`	预测 $F\to \mathbf{id}$
-	`$E'T'id`	`id+id*id$`	匹配 $\mathbf{id}$
`id`	`$E'T'`	`+id*id$`	预测 $T'\to \varepsilon$
`id`	`$E'`	`+id*id$`	预测 $E'\to +TE'$
`id`	`$E'T+`	`+id*id$`	匹配 $+$
`id+`	`$E'T`	`id*id$`	预测 $T\to FT'$
`id+`	`$E'T'F`	`id*id$`	预测 $F\to \mathbf{id}$
`id+`	`$E'T'id`	`id*id$`	匹配 $\mathbf{id}$
`id+id`	`$E'T'`	`*id$`	预测 $T'\to *FT'$
`id+id`	`$E'T'F*`	`*id$`	匹配 $*$
`id+id*`	`$E'T'F`	`id$`	预测 $F\to \mathbf{id}$
`id+id*`	`$E'T'id`	`id$`	匹配 $\mathbf{id}$
`id+id*id`	`$E'T'`	`$`	预测 $T'\to \varepsilon$
`id+id*id`	`$E'`	`$`	预测 $E'\to \varepsilon$
`id+id*id`	`$`	`$`	接受

自底向上分析

与从开始符号出发推导输入串的自顶向下分析相反，自底向上分析（Bottom-Up Parsing）采用一种「逆向」的策略。它从输入的词法单元串（即语法树的叶子节点）开始，通过一系列的归约（Reduction）操作，逐步将子串替换为非终结符号，层层向上构建，最终目标是归约到文法的开始符号（即语法树的根节点）。

这个过程可以看作是寻找输入串的最右推导的逆过程。因此，自底向上分析又被称为移进-归约分析（Shift-Reduce Parsing），这是实现该策略的最通用、最强大的技术框架。

上图直观地展示了为 id * id 进行自底向上分析的过程，从叶子节点 id 开始，逐步归约为 F、T，最终到达根节点 E。

归约与句柄

自底向上分析的核心操作是归约。

归约

归约（Reduction）是推导的逆向操作。在分析的某一步，如果当前句型中的某个子串 $\beta$ 与某个产生式 $A \to \beta$ 的产生式体匹配，那么就可以将该子串 $\beta$ 替换为产生式的头 $A$ 。

自底向上分析的关键挑战在于，在每一步中，如何正确地选择要归约的子串。一个错误的归约选择可能会导致无法最终归约到开始符号。

为了确保分析的正确性，我们必须在每一步都选择一个特定的、正确的子串进行归约，这个子串被称为句柄。

句柄

句柄（Handle）是当前最右句型中与某个产生式体匹配的子串，并且对它的归约代表了相应最右推导的一个逆向步骤。

更形式化地说，如果 $S \xRightarrow[\mathrm{rm}]{*} \alpha A w \xRightarrow[\mathrm{rm}]{} \alpha \beta w$ ，那么产生式 $A \to \beta$ 在最右句型 $\alpha \beta w$ 中的位置就是一个句柄。

在一个无二义性的文法中，每个最右句型有且仅有一个句柄。
自底向上分析的本质，就是一个不断寻找并归约句柄的「句柄剪枝」过程。

句柄识别

考虑文法

$\begin{aligned} E &\to E + T \mid T\\ T &\to T * F \mid F\\ F &\to \mathbf{id} \end{aligned}$

对输入串 id + id * id 的最右推导的逆过程如下：

最右句型	句柄	归约用的产生式
`id + id * id`	`id`	$F \to \mathbf{id}$
`F + id * id`	`F`	$T \to F$
`T + id * id`	`id`	$F \to \mathbf{id}$
`T + F * id`	`id`	$F \to \mathbf{id}$
`T + F * F`	`F`	$T \to F$
`T + T * F`	`T * F`	$T \to T * F$
`T + T`	`T`	$E \to T$
`E + T`	`E + T`	$E \to E + T$
`E`（开始符号）	-	-

第三步选择归约 id 为 F，而非将 T 归约为 E，是因为后者操作后 E * id 不再是个句型。

移进-归约分析

移进-归约分析（Shift-Reduce Parsing）是实现自底向上分析的标准算法模型。它使用一个分析栈来暂存文法符号，并通过四种基本动作来驱动分析过程。

分析栈：用于存放已处理的文法符号。
输入缓冲区：存放剩余的输入词法单元。

分析器在栈顶和当前输入符号的基础上，做出以下四种决策之一：

移入（Shift）：将下一个输入符号压入分析栈顶。
归约（Reduce）：当栈顶形成一个句柄 $\beta$ $β$ 时，分析器用对应的产生式 $A \to \beta$ $A \to β$ 进行归约。
- 具体操作是：从栈顶弹出 $\beta$ （长度为 $|\beta|$ 的符号），然后将非终结符 $A$ 压入栈中。
接受（Accept）：当栈中只剩下开始符号且输入缓冲区为空时，宣布分析成功。
报错（Error）：在无法执行任何有效动作时，报告语法错误。

一个关键的性质是：对于任何正确的移进-归约分析过程，句柄总是出现在栈的顶端。这使得我们无需在整个已处理的符号串中搜索句柄，只需关注栈顶即可。

移进-归约过程

对输入串 id * id 的分析过程：

栈	输入	动作
`$`	`id * id $`	移入
`$ id`	`* id $`	归约（ $F \to \mathbf{id}$ ）
`$ F`	`* id $`	归约（ $T \to F$ ）
`$ T`	`* id $`	移入
`$ T *`	`id $`	移入
`$ T * id`	`$`	归约（ $F \to \mathbf{id}$ ）
`$ T * F`	`$`	归约（ $T \to T * F$ ）
`$ T`	`$`	归约（ $E \to T$ ）
`$ E`	`$`	接受

移进-归约冲突

移进-归约分析器的核心挑战在于决策：在某个状态下，是应该继续移入，还是应该进行归约？对于某些文法，分析器可能会面临无法唯一决策的困境，这称为冲突。

冲突类型

移进/归约冲突（Shift/Reduce Conflict）：分析器无法确定是应该将下一个输入符号移入栈中，还是应该对栈顶的句柄进行归约。
- 经典的「悬空 $\mathbf{else}$ 」问题就是典型的移进/归约冲突。当栈顶为 $\dots \ \mathbf{if} \ \mathit{expr} \ \mathbf{then}\ \mathit{stmt}$ ，下一个输入是 $\mathbf{else}$ 时，分析器不知道是应该移入 $\mathbf{else}$ （与当前的 $\mathbf{if}$ 匹配），还是应该将 $\mathbf{if} \ \mathit{expr} \ \mathbf{then}\ \mathit{stmt}$ 归约为一个 $\mathit{stmt}$ 。
归约/归约冲突（Reduce/Reduce Conflict）：栈顶的符号串可以匹配多个不同的产生式体，分析器不知道应该使用哪个产生式进行归约。
- 这种冲突通常源于文法设计不佳或语言本身的模糊性。例如，如果文法中有 $\mathit{expr} \to \mathbf{id}$ 和 $\mathit{param} \to \mathbf{id}$ ，当栈顶是 $\mathbf{id}$ 时，无法确定是归约为 $\mathit{expr}$ 还是 $\mathit{param}$ 。

LR 语法分析

LR 语法分析是目前最强大、最通用的移进-归约分析技术。它能够处理比 LL 分析方法更广泛的文法类别，并且可以被高效地实现。

LR(k)

L：表示从左（Left）到右扫描输入。
R：表示构造最右（Rightmost）推导的逆过程。
k：表示在做分析决定时，需要向前看 k 个输入符号。

在实践中，我们主要关注 $k=0$ 或 $k=1$ 的情况，如 LR(0)、SLR(1)、LALR(1) 和 LR(1)，因为它们在表达能力和分析器规模之间取得了很好的平衡。

LR 分析器的主要优点：

强大的文法处理能力：能够处理几乎所有用于描述程序设计语言的上下文无关文法。
自动生成：LR 分析器（特别是其核心的分析表）可以由工具根据文法自动生成。
高效性：分析过程无回溯，效率高。
精确的错误定位：能够尽早地（在扫描到第一个不匹配的符号时）检测到错误。

LL(k) 与 LR(k) 的对比：

LR(k) 的宽松：
- LR 分析器在做归约决策时，它已经完全看到了产生式的右部 $\alpha$ 。这意味着它已经有了 $\alpha$ 提供的所有上下文信息。
- 在此基础上，它再向前看 $k$ 个符号，这些 $k$ 个符号是紧跟在 $\alpha$ 之后的。
- 所以，LR 分析器在做决策时，拥有更丰富的上下文信息：它知道要归约的子串是什么，以及这个子串后面跟着什么。
LL(k) 的严格：
- LL 分析器在做预测决策时，它还没有看到产生式的右部 $\alpha$ 的任何部分。它只是在一个非终结符 $A$ 处，需要选择一个 $\alpha_i$ 来展开。
- 它向前看的 $k$ 个符号，是 $\alpha_i$ 最终推导出的字符串的开头。
- 这意味着 LL 分析器必须仅仅根据这 $k$ 个符号，就预测整个 $\alpha_i$ 的结构，而不能依赖 $\alpha_i$ 本身的内容（因为它还没被识别出来）。

LR 分析的核心思想是利用一个确定有限自动机（DFA）来识别句柄。这个自动机的每个状态（state）都代表了我们已经识别出的、可能构成句柄前缀的文法符号串的信息。

LR 分析器本质上是一个由分析表驱动的、精确的移进-归约分析器。其核心结构由以下几个部分组成：

LR 分析器结构

graph TD
subgraph LR Parser
    Driver(分析驱动程序)
    Stack(分析栈)
    Table(分析表)
end

Input[输入缓冲区: a₁a₂...aₙ$] --> Driver
Driver -- 查看栈顶状态 s --> Stack
Driver -- 查看当前输入 a --> Input
Driver -- (s, a) --> Table
Table -- 动作 --> Driver
Driver -- 操作 --> Stack
Driver -- 推进 --> Input
Driver --> Output(输出分析结果或错误)

style Stack fill:#f9f,stroke:#333,stroke-width:2px
style Table fill:#ccf,stroke:#333,stroke-width:2px
style Driver fill:#cfc,stroke:#333,stroke-width:2px
style Input fill:#ffc,stroke:#333,stroke-width:2px
style Output fill:#fcc,stroke:#333,stroke-width:2px

输入缓冲区：存放待分析的整个输入串，以结束符 $\$$ 结尾。
分析栈：存储状态序列 $s_0s_1\dots s_m$ ，其中 $s_m$ 是栈顶状态。每个状态都概括了它下面的符号串所代表的语法信息。
分析表：这是 LR 分析器的核心，它是一个二维表，指导分析驱动程序的所有决策。它包含两部分：
- ACTION 表：根据当前栈顶状态 $s_m$ 和下一个输入符号 $a_i$ ，决定执行移入、归约、接受还是报错。
- GOTO 表：在执行归约操作 $A \to \beta$ 后，假设栈顶状态变为 $s_k$ ，GOTO 表根据 $s_k$ 和非终结符 $A$ 决定下一个要压入栈的状态。
分析驱动程序：执行一个简单的循环，根据栈顶状态和当前输入符号，查询分析表来决定下一步动作，并更新分析栈和输入。

这个模型是所有 LR 类分析器（包括 SLR、LALR、LR(1)）的通用工作框架。它们之间的区别仅在于分析表的构造方法不同。

LR(0) 项

为了构建这个自动机，我们首先需要一个能够表示「识别进度」的工具，这就是 LR(0) 项。

LR(0) 项

一个 LR(0) 项（item）是在一个产生式的产生式体中，某个位置插入一个点「 ${\tiny\bullet}$ 」形成的。

例如，对于产生式 $A \to XYZ$ ，存在四个 LR(0) 项：

$A \to {\tiny\bullet} XYZ$ ：表示我们期望看到一个能从 $XYZ$ 推导出的串。
$A \to X{\tiny\bullet} YZ$ ：表示我们已经识别出一个 $X$ ，期望后续能看到 $YZ$ 。
$A \to XY{\tiny\bullet} Z$ ：表示我们已经识别出 $XY$ ，期望后续能看到 $Z$ 。
$A \to XYZ{\tiny\bullet}$ ：表示我们已经完整地识别出了产生式体 $XYZ$ ，此时可以进行归约。

规范 LR(0) 项集族的构造

LR 分析器的自动机中的每个状态，都对应一个 LR(0) 项的集合（即项集）。构造这个自动机的过程，就是构造所有可能的项集（状态）以及它们之间的转换关系。

这个过程依赖于三个核心概念：

增广文法（Augmented Grammar）：
- 在原始文法 $G$ 的基础上，增加一个新的开始符号 $S'$ 和一个产生式 $S' \to S$ 。
- 目的：为分析器提供一个唯一的接受状态。当分析器准备按照 $S' \to S$ 进行归约时，就意味着整个输入串已经被成功识别。
闭包操作 $\mathrm{CLOSURE}(I)$ ：
- 目的：扩展一个项集，使其包含所有可能需要立即开始识别的产生式。
- 直观含义：如果项集 $I$ 中有一个项 $A \to \alpha {\tiny\bullet} B \beta$ ，这意味着我们接下来期望识别非终结符 $B$ 。为了识别 $B$ ，我们必须从 $B$ 的某个产生式的开头开始。因此，我们需要将所有形如 $B \to {\tiny\bullet} \gamma$ 的项都加入到闭包中。这个过程需要递归进行，直到没有新的项可以加入为止。
- 这与 NFA 到 DFA 转换中的 $\varepsilon$ -closure 思想非常相似。
$\mathrm{GOTO}(I, X)$ 函数：
- 目的：计算自动机的状态转换。
- 直观含义：如果当前状态是项集 $I$ ，并且我们从输入中识别出了文法符号 $X$ （无论是通过移入终结符还是归约得到非终结符），那么分析器将转移到哪个新状态？
- 计算方法： $\mathrm{GOTO}(I, X)$ 的结果是项集 $I$ 中所有形如 $A \to \alpha {\tiny\bullet} X \beta$ 的项，将点 ${\tiny\bullet}$ 向右移动一位得到 $A \to \alpha X {\tiny\bullet} \beta$ ，然后对这个新项集求闭包。

通过反复应用 $\mathrm{CLOSURE}$ 和 $\mathrm{GOTO}$ ，我们可以从初始项集 $\mathrm{CLOSURE}({S' \to {\tiny\bullet} S})$ 出发，系统地构造出所有可达的项集，这个集合被称为规范 LR(0) 项集族。

示例

下面使用一个简单的算术表达式文法作为例子，原始文法 $G$ ：

$E \to E + T \mid T$
$T \to T * F \mid F$
$F \to (E) \mid \mathbf{id}$

增广文法 $G'$ ：

$S' \to E$
$E \to E + T \mid T$
$T \to T * F \mid F$
$F \to (E) \mid \mathbf{id}$

CLOSURE

假设我们从增广文法的初始项集开始，即只包含 $S' \to {\tiny\bullet} E$ 这一个项。

计算 $\mathrm{CLOSURE}(\{S' \to {\tiny\bullet} E\})$ ：

初始化：结果集 $I = \{S' \to {\tiny\bullet} E\}$ 。
处理 $S' \to {\tiny\bullet} E$ ：
- 点 ${\tiny\bullet}$ 后面是非终结符 $E$ 。
- 将所有 $E$ 的产生式，并在其右部开头加上点 ${\tiny\bullet}$ ，加入到 $I$ 中。
- $I$ 变为 $\{S' \to {\tiny\bullet} E, E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T\}$ 。
处理 $E \to {\tiny\bullet} E + T$ ：
- 点 ${\tiny\bullet}$ 后面是非终结符 $E$ 。但 $E$ 的产生式（ $E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T$ ）已经存在于 $I$ 中，无需重复添加。
处理 $E \to {\tiny\bullet} T$ ：
- 点 ${\tiny\bullet}$ 后面是非终结符 $T$ 。
- 将所有 $T$ 的产生式，并在其右部开头加上点 ${\tiny\bullet}$ ，加入到 $I$ 中。
- $I$ 变为 $\{S' \to {\tiny\bullet} E, E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T, T \to {\tiny\bullet} T * F, T \to {\tiny\bullet} F\}$ 。
处理 $T \to {\tiny\bullet} T * F$ ：
- 点 ${\tiny\bullet}$ 后面是非终结符 $T$ 。但 $T$ 的产生式（ $T \to {\tiny\bullet} T * F, T \to {\tiny\bullet} F$ ）已经存在于 $I$ 中，无需重复添加。
处理 $T \to {\tiny\bullet} F$ ：
- 点 ${\tiny\bullet}$ 后面是非终结符 $F$ 。
- 将所有 $F$ 的产生式，并在其右部开头加上点 ${\tiny\bullet}$ ，加入到 $I$ 中。
- $I$ 变为 $\{S' \to {\tiny\bullet} E, E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T, T \to {\tiny\bullet} T * F, T \to {\tiny\bullet} F, F \to {\tiny\bullet} (E), F \to {\tiny\bullet} \mathbf{id}\}$ 。
处理 $F \to {\tiny\bullet} (E)$ 和 $F \to {\tiny\bullet} \mathbf{id}$ ：
- $F \to {\tiny\bullet} (E)$ ：点 ${\tiny\bullet}$ 后面是终结符 $($ ，不引发新的非终结符产生式添加。
- $F \to {\tiny\bullet} \mathbf{id}$ ：点 ${\tiny\bullet}$ 后面是终结符 $\mathbf{id}$ ，不引发新的非终结符产生式添加。
循环结束：没有新的项可以加入。

最终结果： $\mathrm{CLOSURE}(\{S' \to {\tiny\bullet} E\}) = \{S' \to {\tiny\bullet} E, E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T, T \to {\tiny\bullet} T * F, T \to {\tiny\bullet} F, F \to {\tiny\bullet} (E), F \to {\tiny\bullet} \mathbf{id}\}$

这个闭包操作告诉我们，如果分析器期望看到一个 $E$ ，那么它可能从 $E$ 本身开始（递归），或者从 $T$ 开始。如果从 $T$ 开始，它又可能从 $T$ 本身开始（递归），或者从 $F$ 开始。如果从 $F$ 开始，它可能从 $($ 开始，或者从 $\mathbf{id}$ 开始。 $\mathrm{CLOSURE}$ 确保我们考虑了所有这些「立即可能」的识别路径。

GOTO

计算出了上面的项集 $I_0 = \mathrm{CLOSURE}(\{S' \to {\tiny\bullet} E\})$ 后，现在想知道，如果在状态 $I_0$ 下识别出了一个非终结符 $E$ ，分析器会转移到哪个新状态。

计算 $\mathrm{GOTO}(I_0, E)$ ：

识别点后为 $E$ 的项：从 $I_0$ $I_{0}$ 中找出所有形如 $A \to \alpha {\tiny\bullet} E \beta$ $A \to α ∙ Eβ$ 的项：
- $S' \to {\tiny\bullet} E$
- $E \to {\tiny\bullet} E + T$
移动点：将这些项中的点 ${\tiny\bullet}$ $∙$ 向右移动一位，越过 $E$ $E$ ：
- $S' \to E{\tiny\bullet}$
- $E \to E{\tiny\bullet} +T$
  得到一个临时的项集 $J' = \{S' \to E{\tiny\bullet} , E \to E{\tiny\bullet} +T\}$ 。
对 $J'$ 求闭包：现在，我们计算 $\mathrm{CLOSURE}(J')$ $CLOSURE (J^{'})$ ：
- 初始化：结果集 $J = \{S' \to E{\tiny\bullet} , E \to E{\tiny\bullet} +T\}$ 。
- 处理 $S' \to E{\tiny\bullet}$ ：点 ${\tiny\bullet}$ 后面没有文法符号，不引发新的项添加。
- 处理 $E \to E{\tiny\bullet} +T$ ：点 ${\tiny\bullet}$ 后面是终结符 $+$ ，不引发新的非终结符产生式添加。
- 循环结束：没有新的项可以加入。

最终结果： $\mathrm{GOTO}(I_0, E) = \{S' \to E{\tiny\bullet} , E \to E{\tiny\bullet} +T\}$

当我们处于状态 $I_0$ （期望识别一个完整的表达式 $E$ ）并成功识别了 $E$ 后，我们进入了一个新状态。在这个新状态中，我们可能已经完成了整个输入串的识别（对应 $S' \to E{\tiny\bullet}$ ，可以归约），或者我们可能识别了一个 $E$ 之后，接下来期望看到一个 $+$ 符号（对应 $E \to E{\tiny\bullet} +T$ ）。 $\mathrm{GOTO}$ 函数就是描述这种状态转移的。

通过反复应用这两个函数，就可以构建出完整的 LR(0) 项集族，也就是 LR(0) 自动机的状态和状态转换图。

内核项与非内核项

在 LR(0) 项集中，我们根据项的来源和形式，将其分为两类：

内核项（Kernel Items）
- 定义：所有形如 $A \to \alpha {\tiny\bullet} X \beta$ 的项，其中 $\alpha$ 不为空（即点 ${\tiny\bullet}$ 不在产生式体的最左边）。
- 特例：增广文法的起始项 $S' \to {\tiny\bullet} S$ 也是一个内核项。这是因为它是整个自动机构造的起点，是唯一的「点在最左边但不是由闭包操作添加」的项。
- 直观含义：内核项代表了分析器已经识别出了一些文法符号（点左边的 $\alpha$ ），并且现在期望识别 $X \beta$ 。它们是项集的核心，决定了状态的唯一性。
非内核项（Non-Kernel Items）
- 定义：所有形如 $A \to {\tiny\bullet} \beta$ 的项，其中 $A \ne S'$ （即点 ${\tiny\bullet}$ 在产生式体的最左边，且不是增广文法的起始项）。
- 直观含义：非内核项总是通过 $\mathrm{CLOSURE}$ 操作被添加到项集中的。它们表示分析器期望识别某个非终结符（点右边的第一个符号），因此需要考虑该非终结符的所有可能产生式。

非内核项是完全由内核项通过 $\mathrm{CLOSURE}$ 操作派生出来的。这意味着，只要我们知道一个项集中的所有内核项，我们就可以通过重新计算 $\mathrm{CLOSURE}$ 来恢复出所有的非内核项。

在构造 LR 自动机时，每个状态（项集）在内存中只存储其内核项。
当需要某个状态的完整信息（包括非内核项）时，例如在计算 $\mathrm{GOTO}$ 函数时，或者在构建 ACTION 表需要判断归约动作时，就对该状态的内核项集合调用 $\mathrm{CLOSURE}$ 函数，临时计算出完整的项集。

示例

承袭上面的文法，有 $I_0 = \mathrm{CLOSURE}(\{S' \to {\tiny\bullet} E\}) = \{S' \to {\tiny\bullet} E, E \to {\tiny\bullet} E + T, E \to {\tiny\bullet} T, T \to {\tiny\bullet} T * F, T \to {\tiny\bullet} F, F \to {\tiny\bullet} (E), F \to {\tiny\bullet} \mathbf{id}\}$

内核项：
- $S' \to {\tiny\bullet} E$ （增广文法的起始项）
非内核项：
- $E \to {\tiny\bullet} E + T$
- $E \to {\tiny\bullet} T$
- $T \to {\tiny\bullet} T * F$
- $T \to {\tiny\bullet} F$
- $F \to {\tiny\bullet} (E)$
- $F \to {\tiny\bullet} \mathbf{id}$

再看另一个项集， $I_1 = \mathrm{GOTO}(I_0, E) = \{S' \to E{\tiny\bullet} , E \to E{\tiny\bullet} +T\}$ ：

内核项：
- $S' \to E{\tiny\bullet}$ （点不在最左边）
- $E \to E{\tiny\bullet} +T$ （点不在最左边）
非内核项：
- $I_1$ 中没有非内核项，因为这两个项的点后面都是终结符或已经到达末尾，不会触发 $\mathrm{CLOSURE}$ 操作添加新的点在最左边的项。

LR(0) 自动机

LR(0) 自动机是一个 DFA，其状态和转换定义如下：

状态：规范 LR(0) 项集族中的每一个项集。
- 初始状态： $\mathrm{CLOSURE}(\{S' \to {\tiny\bullet} S\})$ 对应的项集。
- 接受状态：包含形如 $A \to \alpha {\tiny\bullet}$ 的项集对应的状态。
转换：如果 $\mathrm{GOTO}(I, X) = J$ ，则存在一条从状态 $I$ 到状态 $J$ 的、标号为 $X$ 的转换。

这个自动机能够识别文法的所有「可行前缀」，即可出现在移进-归约分析器栈中的最右句型的前缀。

这个自动机的核心作用是识别文法的可行前缀。

可行前缀

可行前缀（Viable Prefix）是指一个最右句型的前缀，该前缀不会超过该句柄的右端。换句话说，一个字符串是可行前缀，如果它能作为某个正确的移进-归约分析过程中的栈内容出现。

例如 $E \xRightarrow[\mathrm{rm}]{*} F * \mathbf{id} \xRightarrow[\mathrm{rm}]{} (E) * \mathbf{id}$ 可能的前缀有：

$($
$(E$
$(E)$
$(E) *$

LR(0) 自动机中的每一个状态都对应一个项集，这个项集精确地描述了在识别了某个可行前缀之后，我们期望看到的后续符号。

当自动机从初始状态出发，沿着一条路径 $\gamma$ 到达状态 $j$ 时，意味着 $\gamma$ 是一个可行前缀。
状态 $j$ $j$ 中的项集则告诉我们，在看到 $\gamma$ $γ$ 之后的所有可能性：
- 如果存在项 $A \to \alpha {\tiny\bullet} a \beta$ （ $a$ 是终结符），表示如果下一个输入是 $a$ ，我们可以通过移入 $a$ 继续扩展当前的可行前缀。这对应一个移入动作。
- 如果存在项 $A \to \alpha {\tiny\bullet}$ ，表示栈顶的 $\alpha$ 已经构成了一个完整的产生式体，它可能是一个句柄。这对应一个归约动作。

LR 分析器的执行

在实际的 LR 分析过程中，我们并不需要每次都用整个栈中的符号串去驱动 LR(0) 自动机。分析器采用了一种更高效的方式：

栈中存储状态：分析栈中直接存储自动机的状态编号，而不是文法符号。初始时，栈中只有初始状态 $s_0$ 。
移入操作：当分析器处于状态 $s_m$ ，决定对输入符号 $X$ 进行移入时，它会查询 $\mathrm{GOTO}(s_m, X)$ 得到新状态 $s_j$ ，然后将 $s_j$ 压入栈顶。这等同于在自动机上从状态 $s_m$ 沿着边 $X$ 走到状态 $s_j$ 。
归约操作：当决定使用产生式 $A \to \beta$ （长度为 $r=|\beta|$ ）进行归约时，分析器从栈顶弹出 $r$ 个状态。此时暴露出的新栈顶状态 $s_{m-r}$ ，就是归约发生前、识别 $\beta$ 之前的状态。然后查询 $\mathrm{GOTO}(s_{m-r}, A)$ 得到新状态 $s_k$ ，并将 $s_k$ 压入栈中。

通过这种方式，分析栈中的状态序列始终对应于 LR(0) 自动机上的一条从初始状态开始的路径，而这条路径的标号序列就是当前栈内隐式表示的文法符号串。

SLR 分析

单纯的 LR(0) 自动机在决策时有一个缺陷：只要一个状态中包含形如 $A \to \alpha{\tiny\bullet}$ 的归约项，它就会无条件地选择归约。这在很多情况下会导致冲突。

SLR（Simple LR）分析是对 LR(0) 的一个简单改进。它在决定是否归约时，会额外考虑下一个输入符号。

SLR 决策规则

对于一个包含归约项 $A \to \alpha{\tiny\bullet}$ 的状态 $I_i$ ，SLR 分析器只有在下一个输入符号 $a$ 属于 $\mathrm{FOLLOW}(A)$ 集合时，才会选择使用该产生式进行归约。

理由：如果我们将 $\alpha$ 归约为 $A$ ，那么在语法树中， $A$ 的父节点必然期望看到一个可以跟在 $A$ 后面的符号。 $\mathrm{FOLLOW}(A)$ 正是所有这些可能符号的集合。

SLR 通过引入向前看符号（具体来说是 FOLLOW 集）来解决 LR(0) 分析中的冲突，其理论基础是有效项（Valid Item）的概念。

有效项

我们称 LR(0) 项 $A \to \beta_1 {\tiny\bullet} \beta_2$ 对可行前缀 $\alpha\beta_1$ 是有效的，如果存在一个最右推导 $S' \xRightarrow[\mathrm{rm}]{*} \alpha A w \xRightarrow[\mathrm{rm}]{} \alpha \beta_1 \beta_2 w$ 。

直观含义：一个项是有效的，意味着在当前的分析进度下（已经识别了 $\alpha\beta_1$ ），这个项所代表的语法结构仍然是可能出现的。

LR(0) 自动机的一个重要性质是：从初始状态沿着路径 $\gamma$ 到达的状态 $I$ ，其包含的项集正是对可行前缀 $\gamma$ 的所有有效项的集合。

SLR 正是利用这个性质来解决冲突：

当分析器处于状态 $I$ ，栈内容对应可行前缀 $\gamma$ ，并且 $I$ 中包含一个归约项 $A \to \alpha{\tiny\bullet}$ 时，这意味着 $A \to \alpha{\tiny\bullet}$ 对 $\gamma$ 是有效的。
根据有效项的定义，这意味着存在一个推导 $S' \xRightarrow[\mathrm{rm}]{*} \gamma A w \xRightarrow[\mathrm{rm}]{} \gamma \alpha w$ 。
在这个推导中，归约完成后，下一个输入符号必然是 $w$ 的第一个符号，而这个符号必须属于 $\mathrm{FOLLOW}(A)$ 。
因此，只有当下一个输入符号 $a \in \mathrm{FOLLOW}(A)$ 时，执行归约 $A \to \alpha$ 才是合理的。否则，即使 $A \to \alpha{\tiny\bullet}$ 是一个有效项，这次归约在当前上下文中也是不成立的。

SLR 分析表的构造

SLR 分析器由一个分析表驱动，该表分为两部分：ACTION 表和 GOTO 表。

$\mathrm{ACTION}[i, a]$ ：当分析器处于状态 $i$ ，面临输入终结符 $a$ 时，应该采取的动作。
$\mathrm{GOTO}[i, A]$ ：当分析器处于状态 $i$ ，归约得到非终结符 $A$ 后，应该转移到的新状态。

构造算法：

构造文法的规范 LR(0) 项集族 $C = \{I_0, I_1, \dots, I_n\}$ 。
对于每个状态 $i$ $i$ （对应项集 $I_i$ $I_{i}$ ）：
- 移入：如果项 $[A \to \alpha {\tiny\bullet} a \beta]$ 在 $I_i$ 中，且 $\mathrm{GOTO}(I_i, a) = I_j$ （ $a$ 是终结符），则置 $\mathrm{ACTION}[i, a] = \text{移入}\ j$ （shift $j$ ）。
- 归约：如果项 $[A \to \alpha {\tiny\bullet} ]$ 在 $I_i$ 中（ $A \ne S'$ ），则对于 $\mathrm{FOLLOW}(A)$ 中的所有终结符 $b$ ，置 $\mathrm{ACTION}[i, b] = \text{归约}\ A \to \alpha$ （reduce $A \to \alpha$ ）。
- 接受：如果项 $[S' \to S {\tiny\bullet} ]$ 在 $I_i$ 中，则置 $\mathrm{ACTION}[i, \$] = \text{接受}$ （accept）。
- GOTO：如果 $\mathrm{GOTO}(I_i, A) = I_j$ （ $A$ 是非终结符），则置 $\mathrm{GOTO}[i, A] = j$ 。
所有未被填充的表项均为错误。

如果构造过程中，任何一个 ACTION 表项被填入了多个动作，则说明该文法不是 SLR(1) 文法。

表达式文法的 SLR 分析表

下表中， $\mathbf{id}, +, *, (, )$ 是 ACTION 表的列（终结符）， $E, T, F$ 是 GOTO 表的列（非终结符）。行表示状态编号。

状态	$\mathbf{id}$	$+$	$*$	$($	$)$	$\$$	$E$	$T$	$F$
0	$s_5$	-	-	$s_4$	-	-	1	2	3
1	-	$s_6$	-	-	-	$\text{ACC}$	-	-	-
2	-	$r_2$	$s_7$	-	$r_2$	$r_2$	-	-	-
3	-	$r_4$	$r_4$	-	$r_4$	$r_4$	-	-	-
4	$s_5$	-	-	$s_4$	-	-	8	2	3
5	-	$r_6$	$r_6$	-	$r_6$	$r_6$	-	-	-
6	$s_5$	-	-	$s_4$	-	-	-	9	3
7	$s_5$	-	-	$s_4$	-	-	-	-	10
8	-	$s_6$	-	-	$s_{11}$	-	-	-	-
9	-	$r_1$	$s_7$	-	$r_1$	$r_1$	-	-	-
10	-	$r_3$	$r_3$	-	$r_3$	$r_3$	-	-	-
11	-	$r_5$	$r_5$	-	$r_5$	$r_5$	-	-	-

$s_j$ 表示移入并进入状态 $j$ ， $r_k$ 表示按第 $k$ 条产生式归约， $\text{ACC}$ 表示接受。

SLR 的局限性

SLR 方法虽然简单有效，但其能力仍然有限。它使用 FOLLOW 集来决定归约动作，但 $\mathrm{FOLLOW}(A)$ 是一个对非终结符 $A$ 的全局信息，它包含了 $A$ 在所有可能上下文中后面可能跟随的符号。

SLR 冲突示例

考虑下面这个文法，它区别 L-value（左值，可出现在赋值号左边）和 R-value（右值）：

$\begin{aligned} S &\to L = R \mid R \\ L &\to *R \mid \mathbf{id} \\ R &\to L \end{aligned}$

增广后，我们构造其 LR(0) 项集族，会得到一个包含以下项的状态，我们称之为 $I_2$ ：

$I_2 = \{ S \to L{\tiny\bullet} =R, R \to L{\tiny\bullet} \}$

现在，假设分析器处于状态 $I_2$ ，下一个输入符号是 $=$ ：

根据项 $S \to L{\tiny\bullet} =R$ ，分析器应该移入 $=$ 。
根据项 $R \to L{\tiny\bullet}$ ，分析器需要判断是否可以归约。SLR 的规则是查看下一个输入符号是否在 $\mathrm{FOLLOW}(R)$ 中。

我们来计算 $\mathrm{FOLLOW}(R)$ ：

从产生式 $S \to L=R$ 看， $\$$ 可能跟在 $R$ 后面（如果 $S \to L=R$ 是整个句子的结构），所以 $\$ \in \mathrm{FOLLOW}(R)$ 。
从产生式 $L \to *R$ 看， $R$ 后面没有符号，所以 $\mathrm{FOLLOW}(L)$ 的成员也在 $\mathrm{FOLLOW}(R)$ 中。
$\mathrm{FOLLOW}(L)$ 呢？从 $S \to L=R$ 看， $=$ 在 $L$ 后面，所以 $= \in \mathrm{FOLLOW}(L)$ 。
因此， $= \in \mathrm{FOLLOW}(R)$ 。

冲突产生：因为 $= \in \mathrm{FOLLOW}(R)$ ，SLR 规则会在 $\mathrm{ACTION}[2, =]$ 中填入「归约 $R \to L$ 」。但同时，根据项 $S \to L{\tiny\bullet} =R$ ， $\mathrm{ACTION}[2, =]$ 中也需要填入「移入」。这就产生了一个移进/归约冲突。

问题根源：SLR 的判断过于粗糙。虽然 $=$ 在某种情况下可以跟在 $R$ 后面（例如 $*\mathbf{id} = \dots$ ，其中 $*\mathbf{id}$ 归约为 $L$ ，再归约为 $R$ ），但在状态 $I_2$ 这个「特定的上下文」中，我们已经识别了一个可以作为左值的 $L$ 。此时如果后面跟的是 $=$ ，那么它必须是赋值语句的一部分，唯一的合法动作是移入 $=$ 。将 $L$ 归约为 $R$ 会导致后续无法匹配 $R=R$ 这样的非法结构。

SLR 无法区分这种上下文，因为它只看全局的 FOLLOW 集。更强大的 LR(1) 和 LALR(1) 分析方法通过在项中携带更精确的展望符信息，能够解决这类冲突。

更强大的 LR 分析器

SLR 分析方法通过引入 FOLLOW 集来解决 LR(0) 分析中的冲突，但这是一种相对「粗糙」的解决方案。 $\mathrm{FOLLOW}(A)$ 包含了非终结符 $A$ 在任何可能上下文中后面可以跟随的终结符，它没有考虑分析器在某个特定状态下的具体上下文信息。这可能导致在某些情况下，即使 FOLLOW 集允许归约，但该归约在当前上下文中实际上是非法的，从而引发无法解决的冲突。

为了解决这一问题，我们需要更强大的分析方法，它们能够在分析决策中包含更精确的向前看信息。主要有两种：

规范 LR(1) 分析（Canonical LR(1) Parsing）：在项中直接携带精确的展望符，理论上最强大，但生成的分析器状态数最多。
向前看 LR 分析（Lookahead LR, LALR(1)）：作为 LR(1) 的一种优化，它在保持强大分析能力的同时，显著减少了状态数量，使其在规模上与 SLR 分析器相当，是 YACC 等大多数语法分析器生成工具的理论基础。

规范 LR(1) 分析

规范 LR(1) 分析的核心思想是将 SLR 中用于判断归约的「向前看」信息，直接集成到自动机的状态（即项集）中。这样，每个状态不仅知道已经识别了什么，还精确地知道在何种后续输入下可以进行归约。

LR(1) 项

为了携带这种精确的展望信息，我们引入了 LR(1) 项（LR(1) item）。

LR(1) 项

一个 LR(1) 项由两部分组成，形式为 $[A \to \alpha {\tiny\bullet} \beta, a]$ 。

核心（Core）：即我们熟悉的 LR(0) 项 $A \to \alpha {\tiny\bullet} \beta$ 。
展望符（Lookahead）：一个终结符 $a$ 。

这个项的直观含义是：我们当前期望识别一个能由 $\beta$ 推导出的串，并且如果识别成功（即 $\beta$ 推导出 $\varepsilon$ ），那么只有当下一个输入符号是 $a$ 时，我们才能将 $\alpha\beta$ 归约为 $A$ 。

当 $\beta$ 不为空时，展望符 $a$ 在当前步骤中不起作用。
当 $\beta$ 为空时，即对于归约项 $[A \to \alpha{\tiny\bullet} , a]$ ，展望符 $a$ 提供了进行归约的精确条件：只有当下一个输入符号是 $a$ 时，才能执行此归约。
对于任何有效的 LR(1) 项 $[A \to \alpha {\tiny\bullet} \beta, a]$ ，其展望符 $a$ 必然是 $\mathrm{FOLLOW}(A)$ 的一个成员。LR(1) 的优势在于它将 $\mathrm{FOLLOW}(A)$ 这个全局集合，细化到了每个具体项的特定展望符上。

规范 LR(1) 项集族的构造

与 LR(0) 类似，我们通过 CLOSURE 和 GOTO 两个操作来构造 LR(1) 自动机的状态（项集）。

增广文法：与之前相同，引入新的开始符号 $S'$ 和产生式 $S' \to S$ 。初始项为 $[S' \to {\tiny\bullet} S, \$]$ ，展望符为文件结束符 $\$$ 。
闭包操作 $\mathrm{CLOSURE}(I)$ ：
- 目的：扩展项集，以包含所有因当前项而需要立即开始识别的产生式，并传播展望符。
- 规则：对于项集 $I$ 中的每一个项 $[A \to \alpha {\tiny\bullet} B \beta, a]$ ，我们需要将非终结符 $B$ 的所有产生式也加入到闭包中。对于 $B$ 的每一个产生式 $B \to \gamma$ ，我们添加的新项是 $[B \to {\tiny\bullet} \gamma, b]$ ，其中展望符 $b$ 是所有可能跟在 $B$ 后面的符号，即 $b \in \mathrm{FIRST}(\beta a)$ 。
- 展望符的计算： $\mathrm{FIRST}(\beta a)$ 表示，能跟在 $B$ 后面的符号，要么是 $\beta$ 的首终结符集，要么当 $\beta$ 能推导出 $\varepsilon$ 时，是原项的展望符 $a$ 。这个过程递归进行，直到没有新项可以加入。
$\mathrm{GOTO}(I, X)$ 函数：
- 目的：计算状态转换。
- 规则： $\mathrm{GOTO}(I, X)$ 的结果是，将 $I$ 中所有形如 $[A \to \alpha {\tiny\bullet} X \beta, a]$ 的项，把点向右移动一位得到 $[A \to \alpha X {\tiny\bullet} \beta, a]$ ，然后对这个新项集求闭包。
- 注意：在 GOTO 操作中，展望符保持不变。

通过这两个函数，从初始项集 $\mathrm{CLOSURE}(\{[S' \to {\tiny\bullet} S, \$]\})$ 出发，我们就可以构造出完整的规范 LR(1) 项集族。

LR(1) 分析表的构造

LR(1) 分析表的构造算法与 SLR 类似，但决策依据更加精确：

构造文法的规范 LR(1) 项集族 $C = \{I_0, I_1, \dots, I_n\}$ 。
对于每个状态 $i$ $i$ （对应项集 $I_i$ $I_{i}$ ）：
- 移入：如果项 $[A \to \alpha {\tiny\bullet} a \beta, b]$ 在 $I_i$ 中，且 $\mathrm{GOTO}(I_i, a) = I_j$ （ $a$ 是终结符），则置 $\mathrm{ACTION}[i, a] = \text{移入}\ j$ 。
- 归约：如果项 $[A \to \alpha {\tiny\bullet} , a]$ $[A \to α ∙, a]$ 在 $I_i$ $I_{i}$ 中（ $A \ne S'$ $A \neq = S^{'}$ ），则置 $\mathrm{ACTION}[i, a] = \text{归约}\ A \to \alpha$ $ACTION [i, a] = 归约 A \to α$ 。
  - 注意：只对展望符 $a$ 设置归约动作
- 接受：如果项 $[S' \to S {\tiny\bullet} , \$]$ 在 $I_i$ 中，则置 $\mathrm{ACTION}[i, \$] = \text{接受}$ 。
- GOTO：如果 $\mathrm{GOTO}(I_i, A) = I_j$ （ $A$ 是非终结符），则置 $\mathrm{GOTO}[i, A] = j$ 。
所有未被填充的表项均为错误。

如果构造过程中，任何一个 ACTION 表项被填入了多个动作，则说明该文法不是 LR(1) 文法。

解决 SLR 冲突

回到之前 SLR 无法解决的文法：

$\begin{aligned} S &\to L = R \mid R \\ L &\to *R \mid \mathbf{id} \\ R &\to L \end{aligned}$

在 LR(1) 分析中，我们会得到两个不同的状态，它们的核心都是 LR(0) 状态 $I_2 = \{ S \to L{\tiny\bullet} =R, R \to L{\tiny\bullet} \}$ ，但展望符不同：

一个状态可能包含项 $[S \to L{\tiny\bullet} =R, \$]$ ，它来自识别了一个完整的 $S \to L=R$ 的前缀。
另一个状态可能包含项 $[R \to L{\tiny\bullet} , =]$ ，它来自识别了 $R \to L$ 之后，期望后面跟 $=$ 的情况（例如在 $*\mathbf{id} = \dots$ 中， $*\mathbf{id}$ 先归约为 $L$ ）。

具体的分析表决策如下：

当分析器处于包含 $[S \to L{\tiny\bullet} =R, \$]$ $[S \to L ∙ = R, $]$ 的状态，且下一个输入是 $=$ $=$ 时：
- 根据项 $[S \to L{\tiny\bullet} =R, \$]$ ，动作是移入。
- 这个状态中不包含展望符为 $=$ 的归约项。
当分析器处于包含 $[R \to L{\tiny\bullet} , =]$ $[R \to L ∙, =]$ 的状态，且下一个输入是 $=$ $=$ 时：
- 根据项 $[R \to L{\tiny\bullet} , =]$ ，动作是归约 $R \to L$ 。
- 这个状态中不包含点在 $=$ 前面的移入项。

LR(1) 通过不同的展望符将原本在 SLR 中混合在一起的冲突情况，分离到了不同的状态中，从而消除了冲突。

LALR(1) 分析

LR(1) 分析虽然强大，但其实用性受到一个严重问题的制约：对于一个典型的程序设计语言文法，LR(1) 分析器可能会产生数千个状态，而 SLR 或 LALR(1) 分析器可能只有几百个。

观察 LR(1) 项集族可以发现，其中存在大量核心相同（即 LR(0) 部分完全一样）而仅展望符不同的项集。

如上面的项集族中，状态 3, 6、状态 4, 7 与状态 8, 9 都是核心相同的项集，实质上它们来自相同的 LR(0) 状态。

LALR(1) 的核心思想

LALR(1)（Lookahead LR）分析通过合并所有核心相同的 LR(1) 项集来减少状态数量。合并后的新项集是原始项集的并集。

例如，如果存在两个 LR(1) 项集：

$I_i = \{ [C \to c{\tiny\bullet} C, c/d], [C \to {\tiny\bullet} cC, c/d], \dots \}$
$I_j = \{ [C \to c{\tiny\bullet} C, \$], [C \to {\tiny\bullet} cC, \$], \dots \}$

它们的核心（ $\{ C \to c{\tiny\bullet} C, C \to {\tiny\bullet} cC, \dots \}$ ）是相同的。LALR(1) 会将它们合并成一个新状态：

$I_{ij} = \{ [C \to c{\tiny\bullet} C, c/d/\$], [C \to {\tiny\bullet} cC, c/d/\$], \dots \}$
这里的 $c/d/\$$ 表示展望符集合

LALR(1) 的构造与冲突

构造方法（朴素版）：

首先，完整地构造出文法的规范 LR(1) 项集族。
然后，找出所有核心相同的项集，并将它们合并成一个新的项集。
根据合并后的项集族来构造 LALR(1) 分析表。动作的确定方式与 LR(1) 相同。

合并可能产生的冲突：

合并过程不会产生新的移进/归约冲突。因为移入动作只依赖于项的核心，如果合并前没有 S/R 冲突，合并后也不会有。
但是，合并过程可能会引入新的归约/归约冲突。
- 假设状态 $I_i$ 包含归约项 $[A \to \alpha{\tiny\bullet} , a]$ ，状态 $I_j$ 包含归约项 $[B \to \beta{\tiny\bullet} , b]$ 。
- 如果 $I_i$ 和 $I_j$ 的核心相同，它们会被合并。
- 如果在合并后的新状态中，恰好 $a=b$ ，那么当下一个输入是 $a$ 时，分析器就面临着是按 $A \to \alpha$ 归约还是按 $B \to \beta$ 归约的选择，从而产生了 R/R 冲突。而在 LR(1) 中，由于它们处于不同状态，这个冲突并不存在。

因此，LALR(1) 的分析能力介于 SLR(1) 和 LR(1) 之间。它能处理比 SLR(1) 更多的文法，但比 LR(1) 少。不过，对于绝大多数程序设计语言的文法，LALR(1) 的能力已经足够，并且其分析器规模远小于 LR(1)，使其成为实践中的首选。

文法分析能力的比较

不同类型的语法分析方法能够处理的文法范围不同，它们之间存在一种层次关系。

LR(k) 是最强大的分析方法，能够处理所有无二义性的上下文无关文法。
在 $k=1$ 的情况下，分析能力从强到弱依次是**：LR(1) > LALR(1) > SLR**(1)。
LL(1) 文法是 LR(1) 文法的一个真子集，但与 LALR(1) 和 SLR(1) 的关系是相交，而非包含。也就是说，存在 LL(1) 文法不是 LALR(1) 或 SLR(1) 的，反之亦然。
任何二义性文法都不是 LR 文法，因为二义性必然导致分析表中的冲突。

二义性文法的处理

虽然理论上二义性文法无法被 LR 分析器处理，但在实践中，我们有时会故意使用简洁的二义性文法，并通过「额外规则」来解决冲突，而不是重写文法。最典型的例子就是表达式文法。

考虑一个简单的二义性表达式文法：

$E \to E + E \mid E * E \mid (E) \mid \mathbf{id}$

这个文法没有定义 $+$ 和 $*$ 的优先级（precedence）和结合性（associativity），因此对于 $\mathbf{id} + \mathbf{id} * \mathbf{id}$ 这样的输入存在两种解析方式。这在 LR 分析表中会体现为移进/归约冲突。

例如，当分析栈内容为 $E + E$ ，下一个输入为 $*$ 时，分析器面临选择：

归约：将 $E + E$ 归约为 $E$ （对应 $+$ 优先）。
移入：将 $*$ 移入栈中（对应 $*$ 优先）。

我们可以通过为运算符指定优先级和结合性规则来指导分析器解决这类冲突：

优先级：
- 如果下一个输入符号的优先级高于栈顶句柄中运算符的优先级，则选择移入。
- 如果下一个输入符号的优先级低于栈顶句柄中运算符的优先级，则选择归约。
结合性（当优先级相同时）：
- 对于左结合运算符（如 $+$ , $-$ , $*$ , $/$ ），选择归约。
- 对于右结合运算符（如赋值 $=$ , 幂 $\text{\textasciicircum}$ ），选择移入。

悬空 else 问题

悬空 $\mathbf{else}$ （dangling else）问题是另一个经典的移进/归约冲突。

当分析器看到 $\mathbf{if}\ \mathit{expr}\ \mathbf{then}\ \mathit{stmt}$ ，下一个输入是 $\mathbf{else}$ 时，它不知道是应该将 $\mathbf{else}$ 移入（与最近的 $\mathbf{if}$ 匹配），还是应该将 $\mathbf{if}\ \mathit{expr} \ \mathbf{then}\ \mathit{stmt}$ 归约为一个 $\mathit{stmt}$ 。

几乎所有的编程语言都采用移入策略，即 $\mathbf{else}$ 与最近的未匹配的 $\mathbf{if}$ 结合。YACC 等工具默认就采用这种方式解决该冲突。

语法错误处理

一个健壮的编译器必须能够处理源代码中的错误。语法分析器在错误处理中扮演着关键角色。

错误处理的目标：

清晰、准确地报告错误及其位置。
能够从错误中恢复（recover），继续分析程序的剩余部分，以便一次性报告多个错误。
不应显著降低处理正确程序时的效率。

错误恢复策略

恐慌模式恢复（Panic Mode）

这是最简单也最常用的一种恢复策略。

思想：当分析器检测到错误时，它会丢弃后续的输入符号，直到找到一个预定义的同步词法单元（synchronizing token）为止。
同步词法单元：通常是能够明确标记一个语法单元开始或结束的符号，例如：
- 语句结束符（如 ;）
- 块结束符（如 }）
- 高级结构起始的关键字（如 if, while, for）
LR 分析器中的实现：
1. 检测到错误（查表发现 error 条目）。
2. 从分析栈中弹出状态，直到找到一个状态 $s$ ，它对于某个非终结符 $A$ 有一个合法的 GOTO 转换。这个 $A$ 通常是表示一个主要语法结构（如表达式、语句、块）的非终结符。
3. 在输入流中，丢弃词法单元，直到找到一个属于 $\mathrm{FOLLOW}(A)$ 的符号 $a$ 。
4. 将 $\mathrm{GOTO}(s, A)$ 压入栈中，并从符号 $a$ 开始继续分析。

短语层次恢复（Phrase-Level）

这是一种更复杂的策略，它试图在错误点进行局部修正。

思想：分析器在发现错误时，不会立即进入恐慌模式，而是尝试用少量修改（如插入、删除或替换一个符号）来修正错误，使分析可以继续。
实现：通常需要为分析表中的每个 error 条目预先编写特定的错误处理例程。例如，如果在一个表达式中 $)$ 后面紧跟着一个 $\mathbf{id}$ ，处理例程可能会猜测程序员漏掉了一个运算符，并插入一个 $+$ 。

语法分析器生成工具：YACC

YACC（Yet Another Compiler-Compiler）是一个经典的语法分析器生成工具，它根据用户提供的 LALR(1) 文法规则，自动生成一个 C 语言的语法分析器。

YACC 工作流程

graph LR
A[源文件.y] -- YACC --> B{y.tab.c};
B -- C 编译器 --> C[a.out/a.exe];
D[输入流] -- 通过词法分析器 yylex() --> C;
C -- 执行分析 --> E[输出];

subgraph "编译时"
    A
    B
end
subgraph "运行时"
    D
    C
    E
end

style A fill:#f9f,stroke:#333,stroke-width:2px
style B fill:#bbf,stroke:#333,stroke-width:2px
style C fill:#bfb,stroke:#333,stroke-width:2px
style D fill:#ffb,stroke:#333,stroke-width:2px
style E fill:#fbb,stroke:#333,stroke-width:2px

YACC 源程序结构

一个 YACC 源文件（通常以 .y 结尾）分为三个部分，由 %% 分隔：

声明部分：
- C 语言的 #include、宏定义等，写在 %{ ... %} 中。
- 使用 %token 声明终结符（词法单元）。
- 使用 %left, %right, %nonassoc 定义运算符的结合性和优先级。
翻译规则部分：
- 定义文法的产生式以及与每个产生式相关联的语义动作（semantic action）。
- 格式：head: body1 { action1 } | body2 { action2 };
- 语义动作是嵌入的 C 代码，在归约发生时执行。
- $$ 代表产生式头部的属性值，$1, $2, … 代表产生式体中从左到右第 1、2、… 个符号的属性值。
辅助 C 代码部分：
- 用户定义的 C 函数。
- 必须包含一个名为 yylex() 的词法分析器函数，它负责从输入中读取并返回下一个词法单元。这个函数通常由 Lex/Flex 工具生成。
- 还需包含一个 yyerror(char *s) 函数，用于报告错误。

YACC 中的错误恢复

YACC 提供了一种基于错误产生式的机制来实现恐慌模式恢复。

可以在文法规则中定义一个特殊的终结符 error。
例如，规则 stmt: error ';' 的含义是：
1. 当分析器在解析一个 stmt 时遇到错误，它会进入错误模式。
2. 它会从栈中弹出状态，直到进入一个可以移入 error 符号的状态。
3. 然后，它会丢弃输入流中的词法单元，直到找到一个分号 ;。
4. 找到分号后，它会执行归约 stmt -> error ';'，并执行相应的语义动作，然后恢复正常分析。

这种方式允许程序员为语言中的主要语法结构（如语句、声明、函数定义）定义恢复点，从而实现相对健壮的错误恢复。

简单计算器

这个计算器可以处理整数的加、减、乘、除运算，支持括号，并能处理一元负号。

/* ------------------ 1. 声明部分 ------------------ */
%{
#include <stdio.h>
#include <ctype.h>

int yylex(void);
void yyerror(char const *s);
%}

/* 
 - %union 定义了所有符号（终结符和非终结符）
 - 可能的属性值类型。这里我们只需要整数值。
 */
%union {
    int iVal; 
}

/* 
 - %token 声明终结符。
 - <iVal> 表示 NUMBER 这个终结符的属性值是 iVal 类型（即 int）。
 - 像 '+' '-' 这样的单字符终结符不需要声明。
 */
%token <iVal> NUMBER

/* 
 - %type 声明非终结符的属性值类型。
 - 这里 expr 非终结符的计算结果是整数。
 */
%type <iVal> expr

/* 
 - 定义运算符的结合性和优先级。
 - 在同一行的符号优先级相同。
 - 后声明的行比先声明的行优先级更高。
 - %left: 左结合, %right: 右结合, %nonassoc: 不结合。
 */
%left '+' '-'        /* 最低优先级 */
%left '*' '/'        /* 中等优先级 */
%right UMINUS        /* 一元负号，最高优先级 */

%%
/* ------------------ 2. 翻译规则部分 ------------------ */

/* 
 - program 是起始符号。
 - 一个 program 可以是空的，也可以是一系列由换行符分隔的表达式。
 - 每当计算完一个表达式（归约到 program），就打印结果。
 */
program:
    /* 空规则，允许空输入 */
    | program expr '\n' { printf("= %d\n", $2); }
    | program error '\n' { yyerrok; } /* 错误恢复规则 */
    ;

/*
 - expr 定义了表达式的构成。
 - $$ 代表左侧非终结符（expr）的属性值。
 - $1, $2, $3 代表右侧从左到右第 1, 2, 3 个符号的属性值。
 */
expr:
      NUMBER          { $$ = $1; }
    | expr '+' expr   { $$ = $1 + $3; }
    | expr '-' expr   { $$ = $1 - $3; }
    | expr '*' expr   { $$ = $1 * $3; }
    | expr '/' expr   { 
                        if ($3 == 0) {
                            yyerror("divide by zero");
                            $$ = 0;
                        } else {
                            $$ = $1/$3;
                        }
                      }
    | '-' expr %prec UMINUS { $$ = -$2; } /* 处理一元负号 */
    | '(' expr ')'    { $$ = $2; }
    ;

%%
/* ------------------ 3. 辅助 C 代码部分 ------------------ */

/* 
 - main 函数：程序的入口。
 - 它调用 yyparse() 来启动语法分析。
 */
int main(void) {
    printf("Enter expressions, one per line.\n");
    return yyparse();
}

/*
 - 词法分析器 yylex()。
 - 在实际项目中，这通常由 Lex/Flex 生成。这里手写一个简化的版本。
 - 它从输入中读取字符，识别出 NUMBER 或单字符运算符，并返回对应的 token。
 - 识别出 NUMBER 时，需要将其值存入 yylval.iVal。
 */
int yylex(void) {
    int c;
    while ((c = getchar()) == ' ' || c == '\t'); // 跳过空白字符

    if (isdigit(c)) {
        int num = c - '0';
        while (isdigit(c = getchar())) {
            num = num * 10 + (c - '0');
        }
        ungetc(c, stdin); // 把多读的字符退回去
        yylval.iVal = num; // 设置 NUMBER 的属性值
        return NUMBER;
    }

    if (c == EOF) {
        return 0; // 文件结束
    }

    // 对于其他字符（如 + - */( ) \n），直接返回其 ASCII 码作为 token
    return c;
}

/*
 - 错误报告函数 yyerror()。
 - 当 yyparse() 遇到语法错误时，会调用此函数。
 */
void yyerror(char const *s) {
    fprintf(stderr, "Error: %s\n", s);
}

编译和运行：

保存文件：将上述代码保存为 calc.y。
生成分析器：使用 YACC（或其现代替代品 Bison）处理 .y 文件。-d 选项会额外生成一个头文件 y.tab.h，其中包含了 token 的定义。
$ bison -d calc.y # 或者 yacc -d calc.y
这会生成 y.tab.c 和 y.tab.h。
编译 C 代码：使用 C 编译器（如 GCC）编译生成的 C 文件。
$ gcc y.tab.c -o calc
运行计算器：
$ ./calc