Yacc与Bison语法工具实战指南

可视化演示

展示LR移进归约解析栈过程、BNF文法规则与语义动作$$/$1/$2值传递、Flex/Bison工具链从源码到AST pipeline。

工具全景

开餐厅的第一步不是买锅买菜，而是找到一个能听懂菜谱的帮厨。1975年，贝尔实验室的 Stephen Johnson 写出了 Yacc（全称 Yet Another Compiler-Compiler），它正是这样一位帮厨：把写作文法的规则文件翻译成一份可以执行的 C 语言程序。几十年后，GNU 项目推出了它的开源升级版 Bison，语法兼容 Yacc，功能更强、维护更活跃，就像同一套手艺带出来的两代弟子。

从编译原理的角度看，Yacc/Bison 是 LALR(1) 语法分析器生成器。它本身不直接做语法分析，而是负责“生成做语法分析的程序”——帮厨不亲自炒菜，却能把菜谱变成贴在灶台边的标准流程卡。完整的流水线是：Flex（切菜工）把源码字符切成 token 流，Yacc/Bison（主厨）按文法规则把 token 归约成语法树，并在归约时执行语义动作，最终输出计算结果。

这套协作的数学基础是文法的四元组表示。所谓文法，就是一门语言的“总菜谱”，它由四个部分拼成：

有了这位帮厨，接下来要做的就是安排他正式上岗：安装工具、准备砧板和锅具。

安装编译

帮厨上岗前要办好入职手续。好在 Yacc/Bison 的安装非常轻松：在 Ubuntu/Debian 上执行 sudo apt install bison flex，macOS 上执行 brew install bison，Windows 用户则可以用 WSL 或 MSYS2 环境一键装好。装完后，在终端敲 bison --version 看到版本号，就说明这位帮厨已经站在后厨门口了。

上岗后的日常工作分四步。第一步，写词法文件 calc.l，告诉切菜工怎么把字符切成 token；第二步，写文法文件 calc.y，告诉主厨菜谱内容；第三步，用工具生成 C 源码；第四步，用 C 编译器把它们链接成可执行程序。整个流程可以用一条流水线描述：

实际敲命令时，bison -d calc.y 的 -d 参数尤其关键：它会额外生成头文件，让词法文件里的 return NUMBER 和文法文件里的 %token NUMBER 用上同一套编号。正如切菜工和主厨必须对同一份食材清单，否则“鸡丁”和“鸡块”就会对不上号。

文件结构

帮厨把菜谱装订成册，翻开来看，里面正好三大段落，段与段之间用 %% 这条粗横线隔开。第一段是声明区，写在第一个 %% 之前：这里用 %{...%} 包进 C 语言的宏和头文件，用 %token 声明食材清单（终结符），用 %union 定义语义值的类型，用 %left/%right 定下“先乘除后加减”的规矩。这些都像菜谱扉页的用料说明和厨房守则。

第二段是规则区，夹在两个 %% 之间，是全册的核心：每一条产生式就是一道菜的做法，比如 expr : expr '+' term { $$ = $1 + $3; }，冒号左边是菜名，右边是原料组合，花括号里是出锅前的调味动作。第三段是用户代码区，写在第二个 %% 之后，放着 main() 主函数、yyerror() 错误处理函数等辅助工具，相当于后厨的杂役和总管。整本册子的结构可以概括为： 记住这个三段结构，你写任何 .y 文件都能像填表格一样按部就班，不会漏掉任何一段。

文法规则

菜谱里有两类名字：一类是“鸡丁”“花生”这种直接由切菜工提供的终结符，它们在文法中不再展开；另一类是“宫保鸡丁”“鱼香肉丝”这种需要由多个部分组装出来的非终结符，它们出现在产生式的左边。终结符必须和词法文件里 return 的 token 名完全一致，正如菜谱写了“鸡丁”，切菜工就必须切出“鸡丁”而不是“鸡块”。

写产生式时，Bison 用冒号代替箭头，用分号收尾，用竖线 | 合并同一种菜的多款做法。一个经典的表达式文法长这样：

注意这里用的是左递归：E → E + T 中 E 出现在加号左边。LR 分析器天生偏爱左递归，因为归约可以边读边做，栈不会堆得太高；如果写成右递归 E → T + E，就像把食材全堆在台面上最后才统一装盘，输入一长就会堆到天花板。这也是菜谱书写最重要的一条隐藏规矩。

冲突处理

后厨最怕什么？同一堆食材，两本菜谱都说自己做得成。比如文法写成 expr : expr '+' expr | expr '*' expr，解析 1 + 2 * 3 时，分析器读完 1 + 2 正要归约成表达式，却看见后面跟来一个 *——是按菜谱先把 1+2 做成菜，还是把 * 和后面的 3 也请进锅里？这个两难就是移进-归约冲突：栈顶已经可以归约，而新来的符号又请求移进。

Bison 处理冲突的默认策略是“移进优先”，但这不一定符合小学数学。于是老板定了规矩：在声明区用 %left 和 %right 给运算符贴上优先级和结合性标签。声明靠后的优先级更高，所以 %left '*' 写在 %left '+' 之后，乘号就比加号“更急”，冲突发生时先移进 *，从而算出了正确的 1 + (2 * 3)。这条裁决规则可以写成：

悬空 else（dangling else）是另一道经典选择题：if (a) if (b) x; else y; 里这个 else 到底配哪个 if？Bison 默认移进，也就是就近匹配，这正是大多数语言想要的语义。如果你不喜欢靠默认值碰运气，更稳妥的办法是从文法上把优先级“焊死”——像上一节那样把表达式拆成 expr/term/factor 三层，冲突从根上就不存在了。

语义动作

语法树形状对了，味道还得对。解析器不仅要判断“1+2*3“合不合语法，还得算出它等于 7。这份”调味”工作由语义动作承担：每一条产生式后面跟的花括号代码，就是这道菜出锅前的调味步骤。动作里的 $$ 表示装盘后的菜（产生式左边非终结符的值），$1、$3 分别表示第一、第三个原料的值。 默认情况下语义值只有一种类型（int），就像所有菜都用同一种盘子。但真实程序还需要字符串、浮点数、结构体，于是 Bison 提供 %union 来定制一套“多格餐盘”： 为了让 $$ 能装下不同类型，声明区要用 %union { int num; double dval; } 定义联合类型，再用 %token <num> NUMBER 和 %type <num> expr 给食材和菜品绑定格子。这样词法分析器把 yylval 写进对应的 .num 字段，语义动作就能安全取用——正如切菜工把鸡丁放进标了名的料盒，主厨才不会拿错。

位置与错误恢复

客人投诉“这道菜咸了”，后厨得能回答“是哪一锅、哪一批”。位置追踪就是干这个的：Bison 维护一个全局变量 yylloc，类型是 YYLTYPE，里面装着 first_line、first_column、last_line、last_column 四个字段。词法分析器每读一个 token 就更新它，语义动作里则用 @$ 指代归约结果的位置，@1、@3 指代各个原料的位置。父节点的位置由所有子节点合并而来：

有了位置，还得有“救场”的本事。语法错误就像炒糊了一道菜——优秀的主厨不会关店，而是倒掉糊菜继续做后面的菜。做法是在文法里插入 error 终结符，例如 lines : lines expr '\n' | error '\n'：一旦语法出错，Bison 会把出错的 token 以及之后的部分输入“吞掉”，直到遇见换行符，然后从那里重新同步继续解析。配合 yyerror() 打印错误信息、yyerrok 复位错误状态、yyclearin 清除前瞻符号，整个解析器就能在错误面前“永不言败”。

实战案例

所有知识最终要落到一盘真菜上：实现一个完整的计算器。先写词法文件 calc.l，切菜工的活很轻——识别数字、跳过空白、返回运算符：

文法文件 calc.y 则用 %left 处理优先级，配上语义动作，主函数和错误处理也一并写在用户代码区：

编译后输入 2 + 3 * 4，回车就是 14。计算过程完全遵守优先级：

如果哪里不对，Bison 还准备了调试工具：bison -v calc.y 生成 y.output 查看状态表，bison --debug -t 加上运行时 yydebug=1，就能让解析器每移进、每归约都“现场直播”。亲眼看着语法树从叶子长到根，你就真正读懂了主厨的每一步操作。

%{#include "calc.tab.h"%}%%[0-9]+   { yylval.num = atoi(yytext); return NUMBER; }[ \t\n]+ ;"+"      { return '+'; }"*"      { return '*'; }"("      { return '('; }")"      { return ')'; }%%

%union { int num; }%token <num> NUMBER%left '+'%left '*'%%expr : expr '+' expr { $$ = $1 + $3; }     | expr '*' expr { $$ = $1 * $3; }     | '(' expr ')'  { $$ = $2; }     | NUMBER        { $$ = $1; }     ;%%int main() { while (yyparse()); return 0; }int yyerror(char *s) { fprintf(stderr, "%s\n", s); return 0; }

AI 应用场景

Python 演示

import ply.lex as leximport ply.yacc as yacc # 词法规则: 切菜工把源码切成食材丁tokens = ('NUMBER', 'PLUS', 'TIMES', 'LPAREN', 'RPAREN')t_PLUS = r'\+'t_TIMES = r'\*'t_LPAREN = r'\('t_RPAREN = r'\)'t_ignore = ' \t\n'  def t_NUMBER(t):    r'\d+'    t.value = int(t.value)    return t  def t_error(t):    # 遇到不认识字符时报告    print('非法字符:', t.value[0])    t.lexer.skip(1)  # 文法规则: 主厨的菜谱, 与 Bison 的 .y 文件一一对应def p_expression_plus(p):    'expression : expression PLUS term'    p[0] = p[1] + p[3]  # 语义动作: $$ = $1 + $3  def p_expression_term(p):    'expression : term'    p[0] = p[1]  def p_term_times(p):    'term : term TIMES factor'    p[0] = p[1] * p[3]  def p_term_factor(p):    'term : factor'    p[0] = p[1]  def p_factor_num(p):    'factor : NUMBER'    p[0] = p[1]  def p_factor_paren(p):    'factor : LPAREN expression RPAREN'    p[0] = p[2]  def p_error(p):    # 对应 Bison 的 yyerror    if p:        print('语法错误: 意外符号', p.value)    else:        print('语法错误: 输入不完整')  lexer = lex.lex()parser = yacc.yacc()  def main():    print('迷你计算器 (输入 q 退出)')    while True:        try:            line = input('calc > ')        except EOFError:            break        line = line.strip()        if not line:            continue        if line == 'q':            break        result = parser.parse(line)        if result is not None:            print('结果:', result)  if __name__ == '__main__':    main()

1. tokens = ('NUMBER', 'PLUS', 'TIMES', 'LPAREN', 'RPAREN')声明终结符清单，等价于 Bison 里的 %token，定了有哪些食材。
2. t_NUMBER用正则 \d+ 识别数字并转成 int，相当于 calc.l 里 [0-9]+ 那条规则。
3. 'expression : expression PLUS term'产生式写法与 Bison 完全一致，冒号、竖线、分号语法都保留了下来。
4. p[0] = p[1] + p[3]这就是 $$ = $1 + $3，归约时执行调味动作。
5. def p_error(p)对应 yyerror，负责报告语法错误并继续等待输入。
6. yacc.yacc()PLY 内部完成 LALR(1) 分析表构建，类似 bison -d 生成解析器的瞬间。
7. parser.parse(line)对一行输入做语法分析并返回结果，是 yyparse() 的 Python 表亲。

常见误区

面试题