语法分析——基础内容

本文将讲述语法分析的基础内容，包括引论和各种定义。 在之后的文章中，我们将详细讲述各种语法分析的技巧。

引论

我们知道，编译器是由两个大部分，即前端和后端组成的。 前端负责进行词法和语法分析，并生成中间代码，后端负责把中间代码变成目标语言。 概念上说，语法分析器从词法分析器读取词法单元（可能还有符号表），然后生成语法分析树，然后交给前端的其他部分进一步处理。 但是实际上，使用语法制导翻译的技巧，我们可以一边进行语法分析，一边产生结果，因此语法分析通常也包括了进行处理的部分。

语法分析器主要使用三种方法：通用方法、自顶向下方法和自底向上方法。 通用方法可以处理任意文法，但是速度过慢而难以用于编译器中，其中最主要的是CYK算法和Earley算法； 剩下的两种方法存在特殊的优化以处理特别的文法，其中最重要的是LL文法和LR文法。 其中LL文法通常应用自顶向下方法，LR文法通常应用自底向上方法。 我们将重点介绍自顶向下方法中的（基于回溯的）递归下降法和（不使用回溯的）预测分析法，以及自底向上方法中的移入规约法。 递归下降法较为易于实现，因此通常用于手工编写的编译器中，可以使用回溯确定产生式，但是回溯效率较低； 预测分析法更易于实现，但是能够处理的文法较少； 移入规约法适用的文法更多，但是编写较为复杂，因此通常使用某些方法自动生成。

在语法分析这一大块内容中，我们只考虑如何用语法分析器输出语法分析树，而其他内容，如类型检查、生成中间代码等在以后再仔细分析。

代表性的文法

要使用文法来识别一个固定的关键字以及以它们开头的文法相当容易，因此我们主要聚焦表达式的文法。 在各种表达式中，存在各种优先级和结合性的问题，因此更加困难也更加普遍。

我们主要聚焦下面这个文法及其衍生： \(E \quad \to \quad E + E \; | \; E * E \; | \; ( E ) \; | \; \mathbf{id}\) 其中id是一个终结符。 这个文法显然是具有二义性的，因此可以用来说明各种解决二义性的技巧。

我们此前提到过，解决二义性的重要方法就是分配优先级和结合性，因此我们有下面这个文法： \(\newcommand\qatoq{\quad &\to \quad} \newcommand\qtoq{\quad \to \quad} \newcommand\gor{\; | \;} \begin{aligned} E \qatoq E + T \; | \; T \\ T \qatoq T * F \gor F \\ F \qatoq (E) \gor \mathbf{id} \end{aligned}\) 这个文法指明了各个运算符的优先级。 我们不加证明地说这个文法是LR的，但不是LL的，因此适用于自底向上的分析，而不适用自顶向下的分析。 其不适用于自顶向下分析的原因就是其是左递归的。 我们在自顶向下地构造语法分析树的根时使用第一个产生式，因为它是起始式，然后尝试把它展开成$E+T$。 此时根的左子节点又出现了$E$这一符号，因此这个过程会不断重复，却并不读入任何一个符号。 我们在之后的内容中会介绍左递归的消除，消除后的文法如下所述： \(\begin{aligned} E \qatoq T E^\prime \\ E^\prime \qatoq + T E^\prime \gor \epsilon \\ T \qatoq F T^\prime \\ T^\prime \qatoq * F T^\prime \gor \epsilon \\ F \qatoq ( E ) \gor \mathbf{id} \end{aligned}\) 这个文法即可用于自顶向下的分析，但是其中又引入了空串。

语法错误的处理

虽然在语法分析中，只要出现错误，就不能再生成正确的程序，但从错误中恢复的能力依然是非常重要的。 如果编译器不能从错误中恢复并继续执行，那么每次编译程序都只能输出一个错误，这无疑是令人沮丧的。

我们可以把错误分为词法错误、语法错误、语义错误和逻辑错误。 词法错误和语法错误容易在词法和语法分析中检测到，而诸如类型不匹配之类的语义错误则不在本文的考虑范围之类。 LL和LR分析方法可以非常容易地检测出语法错误——只要语法分析器发现输入的某个前缀不能通过添加某些符号而产生正确的串，就能报告这个错误。

我们介绍几种常见的错误恢复方法：

1. 恐慌模式：一旦发现错误，就不断地从输入中丢弃符号，直到发现同步词法单元为止。 同步词法单元是人为规定的一组词法单元，通常表示为分号或后括号等分隔符。 这种恢复方式非常简单且不会陷入死循环，但是会丢弃大量的内容。
2. 短语层次恢复： 发生错误时，将剩下输入的一个前缀替换为指定的符号使语法分析可以继续进行。 通常将逗号替换成分号或是删除或插入分号。 当然，我们必须仔细选择这种方法，以免陷入死循环。
3. 错误产生式：通过预测一些程序员容易犯下的错误，手动编写一些可以用于识别错误的产生式。
4. 全局纠正：发生错误时，通过某些算法找出编辑距离最小的良构（即满足文法的）程序。 这种算法通常耗时过长且实现复杂，而且编辑距离最短的程序不一定就是期望中的程序。

上下文无关文法

本节中我们将回顾并介绍一些关于文法的定义。

形式定义与约定

形式地说，上下文无关文法满足以下定义：

上下文无关文法是一个四元组$(V, \Sigma, R, S)$。 其中$V$是非终结符号的有限集合，表示句子中的不同成分； $\Sigma$是终结符号的有限集合，构成句子的实际内容； $R$是产生式的有限集合，产生式是一个从$V$到$(V \cup \Sigma)^*$的二元关系，指明了如何产生一个非终结符号； $S \in V$称为开始符号。 由开始符号产生的串的集合就是这个文法的语言。

数学上可将产生式表示为有序的对$(\alpha, \beta),\; \alpha \in V ,\; \beta \in (V \cup \Sigma)^*$。 实际上通常将它写为$\alpha \to \beta$的形式，其中$\alpha$称为其头部或左部，$\beta$称为产生式体或右部。 有些时候也用::=代替箭头。

通常终结符号和非终结符号不会产生歧义，我们约定黑粗体如$\mathbf{id}$或是引号包括的串如"if"总是表示终结符号。 特别需要注意的是几个其他的约定： 我们约定靠前的大写字母如$A,B,C$表示非终结符号； 靠后的大写字母（通常用来表示未知数）如$X,Y,Z$表示任意文法符号，包括终结和非终结符号； 靠后的小写字母如$u,v,w$表示终结符号串（可以为空）； 小写的希腊字母如$\alpha, \beta$表示任意的文法符号串（可以为空）。

推导与语法分析树

利用产生式将非终结符号重写为其产生式体的行为就叫做推导（derivation）。 推导的过程通常用双层右箭头$\Rightarrow$表示。

形式化地说，设存在一产生式$A \to \gamma$，那么由$\alpha A \beta$通过产生式得出$\alpha \gamma \beta$的过程称为推导，记为$\alpha A \beta \Rightarrow \alpha \gamma \beta$，其中$\alpha, \beta, \gamma$为任意文法符号串。 如果存在一个推导序列$\alpha \Rightarrow \beta \Rightarrow \cdots \Rightarrow \gamma$，那么称$\alpha$推导出$\gamma$。

我们记一次这样的替换为一次推导。 这样我们可以定义一个关系：经零次或多次推导出，记为$\Rightarrow^*$。 显然，我们有$\alpha \Rightarrow^* \alpha$且$\alpha \Rightarrow^* \beta , \beta \Rightarrow^* \gamma \implies \alpha \Rightarrow^* \gamma$。

如果文法$G$的开始符号$S$可经零次或多次推导出$\alpha$，那么称$\alpha$是$G$的一个句型。 句型可以包含终结符号和非终结符号，也可以是空串。 如果一个句型不包含非终结符号，那么称它为一个句子。 从这里可以看出自然语言是如何影响程序设计语言的，以中文为例，我们可以写出以下生成式：

句子 ::= 主语 谓语 。
谓语 ::= 谓语动词 | 谓语动词 宾语
主语 ::= ...
谓语动词 ::= ...
宾语 ::= ...

那么有以下推导：

句子 => 主语 谓语 。 => 主语 谓语动词 宾语 。 => ... => 我 吃 饭 。

我们把具体的词语看作终结符号，而用来描述句法的词语看作非终结符号，那么就可以看出句型和句子的区别。

在进行推导时，我们总是需要做出两个选择： 首先，我们要选择替换哪个非终结符号； 其次，我们要选择用哪个生成式进行替换。

如果选择替换哪个符号时总是选择最左边的非终结符号，那么就称这个推导是最左（leftmost）推导，记作$\alpha \Rightarrow_{lm} \beta$。 如果总是选择最右边的，那么就称这个推导为最右推导，记作$\alpha \Rightarrow_{rm} \beta$。 由于在自底向上分析中大量使用最右推导，因此这个推导也叫规范（canonical）推导。 如果一个句型可以只用最左推导就得到，那么称其为最左句型。

---

最左和最右推导如此重要的原因将在介绍语法分析树时得到解答。

语法分析树是这样一颗多叉树： 其每个非叶子结点表示一个产生式的应用，内部结点的标号是产生式的头部，而其所有子节点从左到右对应产生式体中的一个符号。

其叶子节点的标号可以是终结符号，也可以是非终结符号，而从左至右排列所有叶子节点就可以得到一个句型，称为这棵树的结果。 当然，实际语法分析中生成的语法分析树的叶子节点总是非终结符号。

虽然语法分析树中没有给出推导的顺序，但是如果限制推导是最左或是最右的，那么推导和分析树是一一对应的。 具体来说，每一棵语法分析树对应唯一的最左推导和唯一的最右推导； 而最左推导或最右推导对应唯一一棵语法分析树。

我们可以使用归纳方法为每一个推导序列构造一棵分析树：

• 归纳基础：表示推导$\alpha \Rightarrow A$的分析树就是标号为$A$的单个结点；
• 归纳步骤：假设以及构造好了$X_1 X_2 \dots X_k$的语法分析树， 然后我们利用产生式$X_i \to \beta$推导出$X_1 \dots X_{i-1} \beta X_{i+1} \dots X_k$， 其中$\beta = Y_1 Y_2 \dots Y_m$。 现在在原语法分析树中找出从左至右第$i$个非空（$\epsilon$）叶子结点，然后向其添加$m$个子结点，标号从左至右为$Y_1 Y_2 \dots Y_m$。 特别地，如果$m=0$，那么就向这个叶子节点添加一个空子结点即可。

二义性

如果一个文法可以为某个句子生成多棵语法分析树，也就是说有多种最左（或最右）推导可以推出同一句子，那么这个文法是二义性的。

考虑本文开头介绍的那个二义性文法，我们有多种方式可以产生id + id * id：

E => E + E => id + E => id + E * E => id + id * E => id + id * id
E => E * E => E + E * E => id + E * E => id + id * E => id + id * id

这两种推导都是最左推导，因此对应两棵不同的语法分析树。 第一个推导的根节点的叶子节点为E + E，而第二个的为E * E。 通常我们希望采用第一个分析树，因为在求值时在底部的先计算，从而第一个分析树的求值顺序和通常意义的乘法和加法对应。

有些时候，我们可以在语法分析器中使用二义性文法，但是最终我们必须使用一些规则来抛弃生成的语法分析树，直到只剩一个为止。

正则表达式

在乔姆斯基层级中，上下文无关文法比正则表达式更加高级，这就意味着所有正则表达式均可以用这个文法表示。 我们已经知道正则表达式和NFA等价，接下来我们给出用NFA构造文法的算法：

1. 为NFA的每个状态$i$构造一个非终结符号$A_i$；
2. 如果存在从状态$i$到状态$j$标号为$a$的边，那么构造产生式$A_i \to a A_j$，如果标号为空，则构造$A_i \to A_j$；
3. 如果状态$i$是一个接受状态，则构造产生式$A_i \to \epsilon$；
4. 如果状态$i$是开始状态，则令$A_i$为其开始符号。

另一方面，正则表达式不能识别文法$E \to a E b | ab$描述的语言，这个语言表示两两配对的$ab$。 我们说“有穷自动机不能计数”，因为有穷自动机不能在看到b之前确定a的个数； 另一方面，上下文无关文法只能对两个符号计数（如成对的花括号、括号等），而无法对更多的符号计数。

那么，为什么不直接使用文法处理所有内容，而要分割词法分析和语法分析呢？ 其一，分离词法和语法分析可以缩小编译器前端的模块大小； 其二，词法规则通常远比文法规则简单，而且更易于理解； 第三，使用自动机识别词法的正则表达式比构造的语法分析器更快。

并不存在一个严格的规则来分割词法和语法，但是由于其特性，词法通常用来识别各种关键字和标识符等，而语法通常用来描述嵌套的结构，如各种语句等。

设计文法

本节中将介绍几个简化文法的方法，其中消除二义性和左递归可以使得一个文法可用自顶向下方式分析。

消除无用符号

如果一个文法中存在某些文法符号$X$，这些符号不能出现在任何推导过程中，即不存在$S \Rightarrow^* w X y \Rightarrow^* wxy$的推导，那么就称这个符号是无用的。

显然，文法中的无用符号是多余的，因此我们希望设计一个算法来消除文法中的所有无用符号。

如果一个符号不是无用的，那么它必然满足两个条件： $X$是有结果的，即存在推导$X \Rightarrow^* w$，其中$w$是一个终结符号串； $X$是可达的，即存在推导$S \Rightarrow^* \alpha X \beta$。

现在我们分别针对这两点设计算法。

首先我们利用类似宽度优先搜索的方式找出逐步替换所有产生式中的非终结符号，并找出有结果的非终结符。

q = empty_queue();
s = empty_set();
// 首先寻找经过一次推导就能得出终结符号串的头部
for(const auto & prod : productions)
{
    const auto & head = prod.head;
    if(s.find(head))
        continue;
    bool isTerminalString = true;
    for(const auto & symb : prod.body)
        if(!symb.isTerminal)
        {
            isTerminalString = false;
            break;
        }
    if(!isTerminalString)
        continue;
    s.insert(head);
    q.push(head);
}

// 逐步替代所有非终结符
while(!q.empty())
{
    const auto & front = q.front();
    for(const auto & prod : productions)
    {
        const auto & head = prod.head;
        if(s.find(head)) continue;
        if(!prod.body.find(front)) continue;
        
        bool isTerminalString = true;
        for(const auto & symb : prod.body)
            if(!s.find(symb))
            {
                isTerminalString = false;
                break;
            }
        if(!isTerminalString) continue;
        s.insert(head);
        q.push(head);
    }
    q.pop();
}
return s;

我们现在我们已经找到了所有有结果的非终结符号，可以安全地在文法中消去所有头部为无结果符号或产生式体含有无结果符号的产生式。 如果上一个过程连开始符号都消去了，那么这个文法的语言就是空集，此时就可以结束了。

接下来我们要找到所有不可达的符号，这相对而言比较简单。 我们构造一张有向图，然后为所有符号构造一个结点。 如果产生式中一个符号$A$的式体含有符号$B$，就在$A$、$B$之间连接一条边。 然后从开始符号起，用任意方法遍历整张图即可。

考虑文法

S ::= 0 | A
A ::= AB
B ::= 1

首先寻找有结果的符号，显然S和B是有结果的，而A ::= AB是无结果的。 现在删去A，得到新的文法：

S ::= 0
B ::= 1

B是不可达的，因此这个文法只剩下S ::= 0了。 这看起来似乎有些违反直觉，因为原来的文法似乎可以识别1111...这样的串。 但是需要注意的是，我们规定所有串都是有限长的，因此这个文法的语言中并不含无限个1组成的串。

消除二义性

我们以悬空-else语句为例讨论文法的二义性。 考虑这个经典的识别if else的文法：

stmt ::= "if" expr "then" stmt | "if" expr "then" stmt "else" stmt | ...

这个文法在识别如下句子时会出现问题：

if E_1 then if E_2 then S_1 else S_2

换成熟悉的C语言就是下面这个歧义：

if(true)
    if(false)
        puts("1");
    else
        puts("2");

最后面这个else语句到底会不会执行呢？ 如果把它看作和紧邻的if一组，那么就会执行，而如果把它看作和最上面的if一组，那么就不会执行。 任何一个成熟的C/C++编译器遇到这种情况时都会发出警告，而默认把else和最近的if匹配。

我们可以修改文法而避免这种歧义，其基本思想是任何一个then和else之间的语句，如果出现其他的else，则必须是已经和最近的if匹配的。

stmt ::= matched_stmt | open_stmt
matched_stmt ::= "if" expr "then" matched_stmt "else" matched_stmt 
| ...
open_stmt ::= "if" expr "then" stmt 
| "if" expr "then" matched_stmt "else" open_stmt

这样书写文法有些过于麻烦，因此我们通常选择稍微修改一下语法分析器而非使用这种文法。

消除左递归

左递归的文法是指存在一个推导满足$A \Rightarrow^+ A \alpha$的文法，即存在一个至少推导一次的推导链满足推导后的串的一个前缀含有原符号。

首先我们讨论立即左递归的消除，即存在形如$A \to A \alpha$的产生式的左递归的消除。

对任何立即左递归产生式$A \to A \alpha | \beta$，其可以用两条产生式取代： \(\begin{aligned} A \qatoq \beta A^\prime \\ A^\prime \qatoq \alpha A^\prime \gor \epsilon \end{aligned}\) 回忆一下本章开头所提到的两个文法，可以发现左递归的消除正是利用这个方法实现的。

现在我们提出一个对所有不含环（即不存在$A \Rightarrow^+ A$的推导）和空产生式的左递归消除方法：

// 首先遍历所有非终结符号
for(int i = 1; i <= n; i++)
{
    for(int j = 1; j < i; j++)
    {
        /*
            设A_j的产生式体为 δ_1 | δ_2 | ... | δ_k，
            则将形如 A_i ::= A_j α 的所有产生式替换为
            A_i ::= δ_1 α | δ_2 α | ... | δ_k α 
        */
        replace_production(non_terminals[i], non_terminals[j]);
    }
    // 消除A_i的所有立即左递归
    eliminate_lrecursion(non_terminals[i]);
}

这个算法的原理非常简单，也容易理解。

提取左公因子

提取左公因子虽然并不能改变文法的二义性，但是可以把自顶向下语法分析器做决定的时间延后。 比如对于文法：

stmt ::= "if" expr "then" stmt "else" stmt
| "if" expr "then" stmt

自顶向下的语法分析器必须在读取到if词素时就选择使用哪个产生式来产生语法分析树的子结点。 然而如果我们把文法改写成：

stmt ::= if-stmt else-stmt
if-stmt ::= "if" expr "then" stmt
else-stmt ::= ε | "else" stmt

那么就可以让语法分析器在读到else之后再做出决定。 通常此时已知的信息足以帮助语法分析器选择正确的语法分析树，即使文法还是二义性的。

这个提取左公因子的算法非常简单，只要不断应用上述过程找出产生式体的最长公共前缀，然后用新的非终结符号替换即可。

消除空产生式和单位产生式

形如$A \to \epsilon$（且$A$不为开始符号）的产生式称为空产生式，而形如$A \to B$的产生式称为单位产生式。

要消除空产生式，首先要找到它们。 我们定义一个非终结符$A$为可为空的（nullable），若： 存在产生式$A \to \epsilon$； 或存在产生式$A \to X_1 X_2 \cdots X_k$，其中$X_1, X_2 \cdots X_k$都是可为空的。

我们首先计算所有可为空的非终结符的集合，然后对每一条产生式，若其式体中存在可为空的非终结符，则生成对应的省略非终结符的产生式。 注意还要保留原有的产生式 最后，删去所有空产生式（除非头部为开始符号）即可。

比如，考虑以下文法：

S ::= A b B | C
B ::= AA | AC
C ::= b | c
A ::= a | ε

首先计算可为空的非终结符：A和B。 然后把产生式体中的它们删去：

S ::= A b B | C
| b B   //删去A
| A b   //删去B
| b     //删去AB
B ::= AA | A | AC | C
C ::= b | c
A ::= a | ε

最后删去空产生式即可：

S ::= A b B | b B | A b | b | C
B ::= AA | A | AC | C
C ::= b | c
A ::= a

单位产生式的处理更加简单，对每个单位产生式$A \to B$，把$B$的所有产生式头替换成$A$，然后用新的产生式替换$A \to B$即可。 如果存在这样的单位产生式，那么消除单位产生式后$B$的产生式可以省略，因为其已经含在$A$的产生式中了。

消除环

我们知道，如果一个文法有环，就是指存在推导$A \Rightarrow^+ A$。 如果我们已经在文法中消除了所有空产生式，那么环只能由单位产生式产生。 因为如果非单位产生式生成了环，那么一定会附加其他的符号（注意我们已经消除了空产生式，因此其他符号一定不能生成空串），而这与定义矛盾。 因此依次消除空产生式和单位产生式就可以消除环了。

乔姆斯基范式

如果一个语言中所有的产生式都是形如以下三种形式的： \(\begin{aligned} A \qatoq BC \\ A \qatoq a \\ S \qatoq \epsilon \end{aligned}\) 其中$A,B,C$都是非终结符且$B,C$不是开始符号，$a$是终结符，$S$是开始符号，那么称这个语言是满足乔姆斯基范式的。 特别地，如果这个语言不生成空串，那么还可以把它的所有产生式写为以下形式： \(\begin{aligned} A \qatoq BC \\ A \qatoq a \\ \end{aligned}\) 此时不再要求$B,C$不是开始符号，这种语言称作乔姆斯基规约范式（Chomsky reduced form）。 这个范式在用数学方法研究语法分析时和通用语法分析算法（如CYK算法）中经常使用，但在一般的语法分析中并不常见。

要将语言变成乔姆斯基范式，需要按一定顺序进行以下操作：

1. 移除右手的开始符号： 添加产生式$S_0 \to S$，然后把$S_0$指定为新的开始符号。
2. 移除非单独存在的终结符号： 对所有形如$A \to X_1 \dots a \dots X_n$的产生式，其中$a$为终结符，构造非终结符$N \to a$并用$N$替换$a$。
3. 移除非两个非终结符的产生式： 对所有形如$A \to X_1 X_2 \dots X_n, \; n>2$，构造一组产生式 \(\begin{aligned} A \qatoq X_1 A_1 \\ A_1 \qatoq X_2 A_2 \\ \dots \\ A_{n-2} \qatoq X_{n-1} X_n \end{aligned}\) 并用新的产生式替换旧的。
4. 移除空产生式。
5. 移除单位产生式。

要小心选择这几个步骤的顺序，因为一些步骤可能会摧毁上几步中产生的性质，而一些步骤会导致产生式数量大量上升。 按照上文给出的顺序就是一个不错的选择。

非上下文无关的文法