跳到主要内容

语法分析

语法分析​

词法分析把源代码切成一串 token 后,下一步就是判断这串 token 是否符合语言的语法结构,并把它们组织成一棵语法分析树(parse tree)。这个阶段叫语法分析(Parsing),它是编译器前端最核心的部分。

通俗理解:如果说词法分析是把一句话拆成"名词、动词、形容词",那语法分析就是判断这些词能不能组成一句合法的话,并画出主谓宾结构图。"我 吃 苹果"合法,"苹果 吃 我"虽然词法合法但语法不对——这时就要报错。

上下文无关文法(CFG)​

上下文无关文法是描述编程语言语法的标准工具,形式上是一个四元组 G = (V, T, P, S):

  • V:非终结符集合(大写字母,如 E、T),代表语法结构。
  • T:终结符集合(小写字母或具体符号,如 +、id),也就是 token。
  • P:产生式集合,形如 A -> α,其中 α 是终结符和非终结符的串。
  • S:开始符号。

比如算术表达式的经典文法:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

推导是从开始符号出发,反复用产生式的右侧替换左侧,最终得到一个终结符串。每一步选择替换哪个非终结符,有两种规范策略:

  • 最左推导:每次替换最左侧的非终结符。
  • 最右推导:每次替换最右侧的非终结符。

推导过程可以画成一棵语法分析树:根是开始符号,内部节点是非终结符,叶子是终结符。同一棵语法树可能对应多种推导顺序,但树本身是唯一的。

二义性文法指同一个字符串能画出两棵不同的语法树。比如:

E -> E + E | E * E | id

对 id + id * id,可以先归约乘法也可以先归约加法,两棵树语义完全不同。消除二义性的常用手段是引入优先级和结合性——像上面 E -> E + T; T -> T * F 就通过分层强制乘法优先。

自顶向下分析​

自顶向下分析从开始符号出发,尝试推导出目标串。最直观的实现是递归下降:每个非终结符对应一个函数,函数内部按产生式右侧顺序调用其他函数或匹配 token。

递归下降有两个必须解决的问题:

左递归会让函数无限递归。像 E -> E + T 一进入 E() 就先调用 E(),栈爆。消除方法是引入新的非终结符:

E  -> E + T | T           消除左递归后:
E -> T E'
E' -> + T E' | ε

左公因子会让预测失效。S -> if E then S else S | if E then S,看到 if 不知道选哪条。提取左公因子:

S  -> if E then S S'
S' -> else S | ε

FIRST 集合:FIRST(α) 是所有能从 α 推导出的串的第一个终结符。FOLLOW 集合:FOLLOW(A) 是所有能紧跟 A 出现的终结符。

有了这两个集合就能构造 LL(1) 预测分析表:查看当前非终结符和下一个 token,唯一确定用哪条产生式。LL(1) 里的 "L" 分别表示从左向右扫描、最左推导,"1" 表示只需看一个 token 的先行符号。

递归下降解析器示例​

以 E -> E + T | T、T -> id 为例,先消除左递归得到:

E  -> T E'
E' -> + T E' | ε
T -> id

对应的 C 语言递归下降代码:

#include <stdio.h>
#include <string.h>

const char *tokens[] = {"id", "+", "id", "+", "id", "$"};
int pos = 0;

const char *peek() { return tokens[pos]; }
void advance() { pos++; }

int match(const char *s) {
if (strcmp(peek(), s) == 0) { advance(); return 1; }
return 0;
}

void T() {
if (!match("id")) {
printf("语法错误: 期望 id, 得到 %s\n", peek());
}
}

void E_prime() {
if (strcmp(peek(), "+") == 0) {
match("+");
T();
E_prime(); // 尾递归对应原来的左递归
}
// else: ε 产生式,直接返回
}

void E() {
T();
E_prime();
}

int main() {
E();
if (strcmp(peek(), "$") == 0) printf("解析成功\n");
else printf("解析失败: 剩余 %s\n", peek());
}

每个非终结符是一个函数,函数体按产生式右侧顺序调用。E' 里的递归调用替代了原文法的左递归,栈不会炸。

自底向上分析​

自底向上分析反过来:从输入串出发,一步步归约(reduce)回开始符号。它的核心思想是移入-归约(shift-reduce):

  • 移入:把下一个 token 压到栈上。
  • 归约:如果栈顶匹配某条产生式的右侧,就把它替换成左侧非终结符。

被归约的那部分栈顶叫句柄(handle),也就是"当前这一步最应该归约的位置"。找到句柄是自底向上分析的关键。

LR 分析器是自底向上分析的主流实现,架构由三部分组成:

  • 栈:交替存放符号(或状态)和输入历史。
  • 状态机:由文法离线构造出的 DFA,栈顶状态决定下一步做什么。
  • 分析表:ACTION 表告诉当前状态遇到某个 token 是移入还是归约;GOTO 表告诉归约后跳到哪个新状态。

LR 分析器族​

LR 分析器按能力从弱到强排列:

类型前瞻状态数能力
LR(0)0少最弱,几乎无实用文法能过
SLR(1)用 FOLLOW 集近似与 LR(0) 相同中等,能过大部分简单文法
LR(1)精确前瞻极多最强,能覆盖几乎所有确定性上下文无关文法
LALR(1)合并 LR(1) 中同心状态与 SLR 相同略弱于 LR(1),但状态数少一个数量级

LR(1) 表达力最强,但表大得惊人——一个中等规模的语言可能生成上万个状态。LALR(1) 把 LR(1) 里"内核项相同、只有前瞻集不同"的状态合并,得到和 SLR 差不多大的表,同时保留绝大部分 LR(1) 的能力。这正是 yacc/bison 选择 LALR(1) 的原因:表小、速度快、覆盖度足够。

冲突​

LR 分析器构造时可能遇到两种冲突:

shift-reduce 冲突:当前状态既能移入也能归约。最经典的例子是 if-else 悬挂:

S -> if E then S
| if E then S else S

遇到 if E1 then if E2 then S1 else S2,else 该归约给外层还是内层?bison 的默认策略是"移入优先",也就是绑到最近的 if,这符合大多数语言的语义。

reduce-reduce 冲突:栈顶同时匹配多条产生式的右侧,不知道该归约成哪个非终结符。这通常意味着文法设计有问题,需要重写。

工具:yacc/bison 与 ANTLR​

yacc/bison 是 LALR(1) 分析器生成器,配 flex 使用是 Unix 传统组合。一个最小 bison 语法示例:

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

%%
expr: expr '+' expr { yylval = $1 + $3; }
| expr '*' expr { yylval = $1 * $3; }
| NUM { yylval = $1; }
;
%%

%left 声明左结合。真实 bison 里当前产生式的返回值写作两个连续美元符(常记作 dollar-dollar),$1、$3 分别代表右侧第 1、3 个符号的值;上面示例为避免与 Markdown 数学公式分隔符冲突,改写成了 yylval。bison 会自动把这种带二义性的文法结合优先级信息编译成无冲突的分析表。

ANTLR 走的是另一条路线:LL(*) 分析,也就是自顶向下但允许任意前瞻。它生成可读性极好的递归下降代码,能报出更友好的错误信息,也天然支持左递归改写(用户可以直接写 E -> E + T,工具帮你消)。现代语言前端(比如 Kotlin、Groovy 的部分工具链)更多选 ANTLR。

错误恢复​

发现语法错误后,编译器不能直接退出——用户希望一次编译能报出多个错误。常见策略:

  • panic mode:跳过输入 token 直到遇到"同步符号"(比如 ;、}),从熟悉的边界处继续。实现简单,但可能吞掉后续错误。
  • 短语级恢复:在错误点尝试插入、删除或替换一个 token,让分析器能继续。效果好但实现复杂,编译器要维护一份"错误修复规则表"。

工业级编译器(比如 clang)通常混合使用两种策略,并结合大量启发式规则来给出诸如"是不是少了个分号?"这样的贴心提示。