第4章 语法分析

导读

语法分析（Parsing）是编译过程中最核心、最复杂的阶段之一。它将词法分析产生的记号流转换为结构化的语法表示（通常是语法树），同时检查源程序是否满足语言的语法规则。语法分析器的质量直接影响编译器的错误检测能力和编译效率。

本章将全面介绍语法分析的理论和实践方法。我们将从上下文无关文法（CFG）开始，学习如何用形式化的方法描述编程语言的语法结构；然后深入探讨自顶向下和自底向上两大类语法分析方法，包括递归下降、LL分析、LR分析、SLR分析、LALR分析等；最后讨论语法错误处理策略和Yacc/Bison等语法分析器生成工具。

语法分析是编译原理中最有"理论深度"的部分，涉及大量的形式语言理论。但请不要被理论吓倒——我们的最终目标是构建能够正确、高效、容错地分析程序语法结构的工具。理论是手段，实践是目的。

核心概念详解

4.1 上下文无关文法

上下文无关文法（Context-Free Grammar, CFG）是描述编程语言语法结构的标准工具。一个CFG是一个四元组 (V, T, P, S)，其中：

• V 是变量（非终结符）的有限集合
• T 是终结符的有限集合，V ∩ T = ∅
• P 是产生式的有限集合
• S ∈ V 是开始符号

产生式的形式：A → α，其中 A ∈ V，α ∈ (V ∪ T)*

推导（Derivation）：如果 A → α 是一个产生式，那么对于任意 βAγ，有 βAγ ⇒ βαγ。这表示将 βAγ 中的 A 替换为 α。

语言（Language）：文法G生成的语言 L(G) = {w ∈ T | S ⇒ w}，即从开始符号出发，经过若干步推导能得到的所有终结符串的集合。

示例：算术表达式文法

E → E + T | T
T → T * F | F
F → ( E ) | id

这个文法生成的语言包括：id、id + id、id * id、(id + id) * id 等所有合法的算术表达式。

4.2 推导与语法树

最左推导：每步推导都替换最左边的非终结符。

最右推导（规范推导）：每步推导都替换最右边的非终结符。

对于文法 E → E + T | T，T → T * F | F，F → ( E ) | id，表达式 id + id * id 的最左推导：

E ⇒ E + T
  ⇒ T + T
  ⇒ F + T
  ⇒ id + T
  ⇒ id + T * F
  ⇒ id + F * F
  ⇒ id + id * F
  ⇒ id + id * id

语法树（Parse Tree）是推导的图形化表示：

• 根节点是开始符号
• 每个内部节点是一个产生式的左部
• 每个叶子节点是一个终结符或 ε
• 每个内部节点的子节点是该产生式的右部

二义性（Ambiguity）：如果一个文法对同一个句子存在两棵不同的语法树（或两个不同的最左推导），则该文法是二义的。

经典例子：

E → E + E | E * E | ( E ) | id

对于 id + id * id，这个文法可以产生两棵不同的语法树：

• 一棵表示 (id + id) * id
• 另一棵表示 id + (id * id)

这就是为什么我们需要 E → E + T | T，T → T * F | F 这样的文法来强制运算符优先级。

4.3 消除二义性

消除文法二义性的常用方法：

方法1：强制优先级和结合性

通过引入额外的非终结符来强制优先级：

原始二义文法:
E → E + E | E * E | -E | ( E ) | id

消除二义后的文法:
E → E + T | T
T → T * F | -F | F
F → ( E ) | id

这里 * 的优先级高于 +（因为 T 在 E 的更深层），且都是左结合的。

方法2：使用优先级声明

在Yacc/Bison中，可以用 %left、%right、%nonassoc 声明运算符的优先级和结合性：

%left '+'
%left '*'
%right UMINUS

4.4 自顶向下分析

自顶向下分析从开始符号出发，尝试为输入串构造一棵语法树。分析过程中，每次遇到非终结符时，选择一个产生式来展开它。

递归下降分析是最直观的自顶向下方法：

def E():
    T()
    while lookahead == '+':
        match('+')
        T()

def T():
    F()
    while lookahead == '*':
        match('*')
        F()

def F():
    if lookahead == '(':
        match('(')
        E()
        match(')')
    elif lookahead == 'id':
        match('id')
    else:
        error()

LL(1)分析使用预测分析表来驱动分析过程：

分析栈: $E
输入:   id + id * id$

步骤1: 栈顶E，输入id，查表M[E,id] = E → TG
       弹出E，压入GT（G是E的剩余部分）
步骤2: 栈顶G，输入id，M[G,id] = ε
       弹出G
步骤3: 栈顶T，输入id，M[T,id] = FS
       弹出T，压入SF
...

4.5 FIRST和FOLLOW集合

构造LL(1)预测分析表需要计算FIRST和FOLLOW集合：

FIRST(α)：从α出发能推导出的所有串的第一个终结符的集合。

FIRST(aα) = {a}，其中a是终结符
FIRST(Aα) = FIRST(A)，其中A是非终结符
FIRST(ε) = {ε}
FIRST(αβ) = FIRST(α) - {ε} ∪ (如果 ε ∈ FIRST(α) 则 FIRST(β))
FIRST(A → α₁ | α₂ | ...) = FIRST(α₁) ∪ FIRST(α₂) ∪ ...

FOLLOW(A)：在某个推导中，A的右边可能出现的终结符的集合。

如果 S ⇒* αAaβ，则 a ∈ FOLLOW(A)
如果 S ⇒* αA，则 $ ∈ FOLLOW(A)

LL(1)文法的条件：

对于文法的每个产生式 A → α | β，以下条件必须满足：

α 和 β 不能同时推导出以同一个终结符开头的串

α 和 β 不能同时推导出 ε

如果 β ⇒* ε，则 α 不能推导出以 FOLLOW(A) 中终结符开头的串

等价地：FIRST(α) ∩ FIRST(β) = ∅，且如果 α ⇒ ε 或 β ⇒ ε，则 FIRST(α) ∩ FOLLOW(A) = ∅ 且 FIRST(β) ∩ FOLLOW(A) = ∅。

4.6 自底向上分析

自底向上分析从输入串出发，尝试通过归约（reduce）来构造语法树。它是自顶向下分析的逆过程。

移入-归约分析（Shift-Reduce Parsing）使用一个栈和一个输入缓冲区：

• 移入（Shift）：将输入符号压入栈顶
• 归约（Reduce）：将栈顶的符号串（句柄）替换为产生式左部的非终结符
• 接受（Accept）：输入全部处理完毕，栈中只剩开始符号
• 报错（Error）：检测到语法错误

句柄（Handle）：与某个产生式右部匹配的子串，归约它将产生最右推导的逆步骤。

4.7 LR分析法

LR分析法是最强大的自底向上分析方法。"LR"表示从左到右扫描输入（L），产生最右推导的逆（R）。

LR(k)分析器使用k个前瞻符号来决定分析动作。实际中最常用的是LR(0)、SLR(1)、LALR(1)和LR(1)。

LR分析器的结构：

栈          输入          动作
$           id+id*$       移入
$id         +id*$         归约 F → id
$F          +id*$         归约 T → F
$T          +id*$         归约 E → T
$E          +id*$         移入
$E+         id*$          移入
$E+id       *$            归约 F → id
$E+F        *$            归约 T → F
$E+T        *$            移入
$E+T*       $             移入
$E+T*$      $             ...

LR分析表由两部分组成：

• ACTION表：决定移入、归约、接受或报错
• GOTO表：决定归约后栈的状态转移

4.8 SLR分析

SLR（Simple LR）分析是最简单的LR分析方法。它基于LR(0)项目集族，但使用FOLLOW集合来解决冲突。

LR(0)项目：在产生式右部的某个位置加一个点（·）。例如，对于产生式 A → XYZ，有以下项目：

• A → ·XYZ
• A → X·YZ
• A → XY·Z
• A → XYZ·

LR(0)项目集族的构造：

增广文法：添加 S' → S

初始项目集：I₀ = closure({S' → ·S})

对每个项目集I和每个文法符号X，计算 goto(I, X)

closure操作：

closure(I):
    J = I
    repeat
        for J 中的每个项目 A → α·Bβ:
            for 每个产生式 B → γ:
                if B → ·γ 不在 J 中:
                    将 B → ·γ 加入 J
    until J 不再变化
    return J

SLR分析表的构造：

构造LR(0)项目集族

对于状态i：

- 如果 A → α·aβ 在Ii中且 goto(Ii, a) = Ij，则 ACTION[i, a] = shift j

- 如果 A → α· 在Ii中，则对于所有 a ∈ FOLLOW(A)，ACTION[i, a] = reduce A → α

- 如果 S' → S· 在Ii中，则 ACTION[i, $] = accept

如果 goto(Ii, A) = Ij，则 GOTO[i, A] = j

所有未定义的条目为 error

4.9 LALR分析

LALR（Lookahead LR）分析是SLR分析的增强版本，它比SLR更强大，比LR(1)更节省空间。

LR(1)项目：在LR(0)项目的基础上增加一个前瞻符号。形式为 [A → α·β, a]，表示当项目 A → α·β 在栈顶且下一个输入符号是a时，可以进行相应操作。

LALR的核心思想：将具有相同核心（LR(0)部分）的LR(1)项目集合并。合并后的项目集包含所有原始项目的前瞻符号。

LALR(1)分析表与LR(1)分析表有相同的状态数，但每个状态可能有更多的归约动作（因为合并了前瞻符号）。LALR(1)能够处理所有SLR(1)文法，且大多数实际编程语言的语法都可以用LALR(1)描述。

Yacc/Bison默认使用LALR(1)分析。

重要知识点

4.10 错误恢复策略

语法分析器必须能够检测并报告语法错误，同时尽可能从错误中恢复以继续分析后续代码。

恐慌模式恢复（Panic Mode Recovery）：

• 发现错误后，丢弃栈顶和/或输入中的符号，直到遇到同步记号（synchronizing token）
• 同步记号通常是分号 ; 或结束符 }
• 优点：简单，不会死循环
• 缺点：可能跳过大量代码，遗漏后续错误

短语层次恢复（Phrase-Level Recovery）：

• 在局部进行修改：替换栈顶符号、插入符号、删除输入符号
• 为每个状态预定义可能的错误恢复动作
• 优点：可以跳过较少的代码
• 缺点：可能导致死循环，需要仔细设计

错误产生式（Error Productions）：

• 在文法中添加专门的错误产生式来捕获常见错误
• 例如：stmt → ID = error ; 捕获赋值语句中表达式缺失的错误
• 优点：可以精确定位常见错误
• 缺点：需要预判常见错误类型

4.11 Yacc/Bison语法分析器生成器

Yacc（Yet Another Compiler Compiler）和Bison是经典的语法分析器生成工具。用户用BNF风格的规则描述文法，工具自动生成LALR(1)分析器代码。

Yacc程序的结构：

%{
    /* C代码声明 */
    #include <stdio.h>
    extern int yylex();
    void yyerror(char *s) { fprintf(stderr, "%s\n", s); }
%}

%token NUM ID
%left '+' '-'
%left '*' '/'

%%

expr:
    expr '+' term   { printf("ADD\n"); $$ = $1 + $3; }
  | expr '-' term   { printf("SUB\n"); $$ = $1 - $3; }
  | term            { $$ = $1; }
  ;

term:
    term '*' factor { printf("MUL\n"); $$ = $1 * $3; }
  | term '/' factor { printf("DIV\n"); $$ = $1 / $3; }
  | factor          { $$ = $1; }
  ;

factor:
    NUM             { $$ = $1; }
  | ID              { $$ = lookup($1); }
  | '(' expr ')'    { $$ = $2; }
  ;

%%

Yacc的工作流程：

解析规则部分，提取文法

构造LALR(1)分析表

生成C代码实现分析器

用户提供的动作代码嵌入到分析过程中

4.12 二义文法的处理

某些有用的文法是二义的，但我们仍然可以使用它们。方法是通过额外的规则来消除二义性：

优先级和结合性声明：在Yacc中，用 %left、%right、%prec 声明运算符的优先级和结合性。

dangling-else问题：

stmt → if expr then stmt
     | if expr then stmt else stmt
     | other

对于 if E1 then if E2 then S1 else S2，二义性在于 else 属于哪个 if。通常的规则是 else 属于最近的未匹配的 if。在Yacc中，这可以通过优先级声明来解决：

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

stmt: IF expr THEN stmt %prec LOWER_THAN_ELSE
    | IF expr THEN stmt ELSE stmt
    ;

常见误区

误区一：LR分析比LL分析"更好"

LR分析确实更强大（能处理更多的文法），但并不意味着它总是更好的选择：

• LL分析更容易理解和实现
• LL分析的错误信息通常更友好
• LL分析更适合手工实现的编译器
• 许多实际语言（如Java、Python）的语法是LL(1)或可以方便地转换为LL(1)

误区二：所有文法都可以转换为LR(1)

不是所有文法都是LR的。LR文法必须是无二义的，且不能包含"可归约前缀"冲突。但幸运的是，大多数实际编程语言的语法都可以用LR或LALR描述。

误区三：语法分析器能检测所有错误

语法分析器只能检测语法错误（违反文法规则的错误）。它不能检测：

• 语义错误（如类型不匹配）
• 上下文敏感错误（如变量未声明）
• 逻辑错误（如死循环）

误区四：LR分析表一定很大

LR分析表的大小取决于文法的复杂度，而非语言的复杂度。通过LALR合并，分析表可以相当紧凑。Yacc/Bison生成的分析表通常只有几百到几千个条目。

实践应用

4.13 语法分析在现实世界的应用

编程语言编译器：

• GCC使用手工编码的递归下降分析器（C/C++前端）
• Clang/LLVM使用递归下降分析器
• Java编译器（javac）使用递归下降分析器
• Rust编译器使用LALR分析器（早期）→ 手工编码的LL分析器

解析器生成工具：

• Yacc/Bison：C/C++的LALR(1)分析器生成器
• ANTLR：Java的LL(*)分析器生成器
• PEG.js：JavaScript的PEG分析器生成器

数据格式解析：

• JSON解析器
• XML解析器（SAX、DOM）
• YAML解析器

自然语言处理：

• 句法分析器
• 依存句法分析

4.14 语法分析器的性能优化

语法分析器的性能优化技术：

避免不必要的归约：使用"归约-归约"和"移入-归约"冲突的解决策略

内联小函数：减少函数调用开销

使用查找表：将复杂的条件判断转换为查表操作

预读优化：减少回溯和重新分析

增量分析：只重新分析发生变化的部分

本章小结

本章全面介绍了语法分析的理论和实践。核心内容包括：

上下文无关文法（CFG）：描述编程语言语法的形式化工具，由非终结符、终结符、产生式和开始符号组成。

推导与语法树：最左推导和最右推导，语法树是推导的图形化表示，二义性是一个重要的问题。

自顶向下分析：递归下降、LL(1)分析，需要计算FIRST和FOLLOW集合来构造预测分析表。

自底向上分析：移入-归约分析，LR分析法（LR(0)、SLR(1)、LALR(1)、LR(1)），是最强大的语法分析方法。

错误恢复：恐慌模式、短语层次恢复、错误产生式等策略。

Yacc/Bison工具：自动化的语法分析器生成工具，使用LALR(1)分析。

语法分析是编译的核心环节，选择合适的分析方法对编译器的性能和可维护性有重要影响。