Flex与Bison实现Cminus词法语法分析：从AST构建到避坑指南-开发者社区

简介：编译原理大作业中，词法分析与语法分析是常见难点，一套基于Flex和Bison的Cminus完整工程能帮助计算机相关专业学生快速掌握编译器前端实现，也可作为课程设计、期末作业或毕设的可靠参考。压缩包共14个文件，包含6个C源码、2个头文件、Flex词法定义文件、Bison语法定义文件，以及可执行解析器、运行脚本、README说明与实验报告文档，整体约328KB，目录组织清晰，便于对照源码逐模块理解词法规则、语法规则与树形中间表示的构建。项目代码已充分测试并成功运行，作者在答辩评审中平均分达96分，可在现有词法语法分析基础上继续扩展语义分析、中间代码生成等后续环节。目前已有106人学习下载，配套文档说明详细，若运行环境不熟还可私聊作者获取远程教学，对初学者友好。

1. 编译原理大作业从哪下手：用Flex和Bison把Cminus的词法语法分析跑通

编译原理大作业里，“用Flex和Bison对Cminus进行词法分析与语法分析”基本是标配：Cminus是简化掉指针和结构体的C语言子集，你要让它跑完词法、语法两个阶段，交出源代码和文档说明。这门课作业真正花时间的不是背文法，而是把两个生成器接起来，让token流转起来、语法树立起来。

很多同学卡在同一个地方：flex文件能生成，bison文件也能生成，但两个文件一链接就各种undefined，或者语法分析器一堆shift/reduce冲突，跑起来结果全看运气。这一类问题不是文法没写对，而是对生成器的工作方式缺一个直观认识。

接下来的顺序按“先搭词法、再搭语法、最后联调”走，把最小可用的.l/.y骨架、AST构建方法、5个高频踩坑和交作业用的测试文档写法都列出来。照着搭一遍，你就能回答“这作业到底在做什么、能不能跑、坑在哪”。

2. Flex词法分析：把Cminus源码切成token，同时传出行号与字面量

2.1 先弄清Flex和Bison的分工：你写的正则最终要去喂给谁

Bison生成的解析器yyparse运行到需要下一个符号时，会调用Flex生成的yylex()。yylex()每被调用一次，读入一部分源码，返回一个token编号；如果这个token需要携带值（标识符名、常量值），就把值放进全局变量yylval。之后Bison在自己的栈里消费这个token，按文法做移进或者归约。

token编号从哪来？Bison的.y文件里所有%token都会生成统一的编号，写进它用-d选项生成的cminus.tab.h。Flex的.l文件必须include这个头文件，规则里的return IF、return NUM才能和Bison侧对上。如果两边编号不一致，跑了半天语法全错，多半是这里出了问题。

这里有个新手常误解的点：Flex和Bison不是运行时库，而是生成器。你写的.l文件经flex命令变成lex.yy.c，.y文件经bison命令变成cminus.tab.c。真正编译进可执行文件的是这两份生成的C代码，加上你自己写的main.c和ast.c。所以Makefile里要安排生成顺序，第5章我会给完整写法。

还有一个基本约定：flex默认的yylex签名是int yylex(void)，Bison在C模式下调用的也是它，不需要自己声明函数指针。但一旦你在Bison侧开启%locations或传参模式，就要对应改用yylex(YYSTYPE *yylval, YYLTYPE *yylloc)这类带参数的协议。大作业通常用不到，知道有这回事就行。

2.2 写第一版cminus.l：关键字、标识符、数字和运算符怎么排规则顺序

一个能跑的最小词法文件，骨架是三段式：%{和%}之间放C的头文件和外部声明，%%和%%之间放规则，第二个%%之后放辅助函数。下面这份对应Cminus常见的token集合，注释里标了每条规则的作用：

%{ /* cminus.l —— 词法分析部分 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "cminus.tab.h" /* 如果需要额外的全局状态，放在这里 */ int comment_depth = 0; %} DIGIT [0-9] ID [a-zA-Z_][a-zA-Z0-9_]* %option noyywrap yylineno %% "int" { yylval.sval = strdup(yytext); return INT; } "void" { yylval.sval = strdup(yytext); return VOID; } "if" { return IF; } "else" { return ELSE; } "while" { return WHILE; } "return" { return RETURN; } {DIGIT}+ { yylval.ival = atoi(yytext); return NUM; } {ID} { yylval.sval = strdup(yytext); return ID; } "<=" { return LE; } ">=" { return GE; } "==" { return EQ; } "!=" { return NE; } "<" { return LT; } ">" { return GT; } "+" { return PLUS; } "-" { return MINUS; } "*" { return TIMES; } "/" { return DIV; } "=" { return ASSIGN; } ";" { return SEMI; } "," { return COMMA; } "(" { return LPAREN; } ")" { return RPAREN; } "{" { return LBRACE; } "}" { return RBRACE; } "[" { return LBRACKET; } "]" { return RBRACKET; } [ \t]+ ; \n ; "//".* ; /* 单行注释：吃掉到行尾为止 */ . { fprintf(stderr, "line %d: 非法字符 '%s'\n", yylineno, yytext); } %%

规则顺序为什么要这样排？Flex的匹配原则是“最长匹配优先，相同长度先出现的规则优先”。“if”这两个字符如果放在{ID}后面，输入if时最长匹配结果仍是ID规则，返回的token就是ID，语法分析器会把它当成变量名而不是关键字。所以关键字规则必须写在标识符规则前面，这是词法作业最常见的第一个坑。运算符同理，双字符的<=、>=、==、!=要放在单字符<、>、=前面，否则读到= =会被拆成两个ASSIGN。

yylval的字段由Bison的%union决定，flex侧用sval还是ival要看cminus.tab.h里的定义。atoi对超大数字不会检查溢出，测试时如果故意填一个超过int范围的字面量，这里得到的是未定义行为，严谨实现应该用strtol并检查errno。token设计时，我是按下面这张表来对齐flex规则和bison声明的：

| 类别 | 示例 | flex规则 | Bison侧token | | 关键字 | int void if else while return | 写在ID之前 | INT VOID IF ELSE WHILE RETURN | | 标识符 | foo _tmp | {ID} | ID | | 常量 | 0 42 | {DIGIT}+ | NUM | | 单字符运算符 | + - * / = ; , ( ) { } [ ] | 原样匹配 | PLUS MINUS TIMES DIV ASSIGN SEMI COMMA LPAREN RPAREN ... | | 双字符运算符 | <= >= == != | 放在单字符之前 | LE GE EQ NE |

2.3 状态、跨行注释与yytext的“有效期”问题

Flex的yytext是指向内部缓冲区的指针，不是每次匹配单独分配的内存。每次yylex()返回后，缓冲区并不会立刻失效；但一旦Bison为了决定走哪条产生式而继续读下一个token，上一个yytext指向的内容就可能被新内容覆盖。所以凡是需要在语法分析阶段保留的字符串，必须在规则动作里马上strdup，否则会出现所有变量名都一样、打印出来乱码这类灵异现象。

对注释，Cminus标准文法要求/*/，而且不嵌套。跨行注释如果不用状态，一条规则很难写干净，因为注释里可能含、/、换行这些字符。常见的做法是用flex的%x exclusive状态：

%x COMMENT %% "/*" { BEGIN(COMMENT); } <COMMENT>"*/" { BEGIN(INITIAL); } <COMMENT>\n ; <COMMENT>. ;

%x声明一个只能显式进入的状态，BEGIN(COMMENT)切换过去之后，普通初始状态的规则不再参与匹配。带前缀的规则只在COMMENT状态下生效。如果不小心把" <em> /"写成无前缀规则，注释外的 </em> /也会被吞掉。状态必须在%%之前声明，规则里写错状态名，flex会直接报错。

参数说明：yylineno是flex内建的行号计数器，在%option里开启后自动维护，不要自己写line_no++，否则和flex内部逻辑冲突会导致行号翻倍。noyywrap是为了去掉对库函数yywrap的依赖，如果编译环境报undefined reference to yywrap，就是少了这个选项，或者要自己补一个返回1的yywrap函数。另外测试文件请保持LF换行，Windows记事本产生的\r会落到.兜底规则里，报一个看着像乱码的非法字符。

3. Bison语法分析：用Cminus文法生成语法树，处理冲突和优先级

3.1 从Cminus文法到bison规则：声明、语句和表达式怎么组织

Cminus文法分成三层：程序由若干声明组成，声明分变量声明和函数声明；函数体是复合语句，里面是局部声明加语句列表；语句分表达式语句、if、while、return和复合语句；表达式由赋值、算术、比较和函数调用组成。你不需要把整本文法背下来，但要把bison文件里的%token、%union和规则结构跟文法对应起来。

Bison的每条规则写成非终结符: 候选1 \| 候选2 ;，动作代码放在每个候选末尾，用$1、$2、$3引用各符号的语义值，用$$给当前非终结符赋值。例如下面这段：

statement: expression-stmt | compound-stmt | if-stmt | while-stmt | return-stmt ; if-stmt: IF LPAREN expression RPAREN statement { $$ = new_node(NODE_IF, $3, $5, NULL); } | IF LPAREN expression RPAREN statement ELSE statement { $$ = new_node(NODE_IF, $3, $5, $7); } ;

IF、LPAREN这些token没有值，但expression和statement的语义值都是AST节点指针，所以$3、$5传进new_node后，if节点会挂上条件子树和then子树，有else时再挂else子树。这棵AST是后面遍历、生成中间表示的地基。

Bison默认的起始符号是第一条规则左边的非终结符。如果想显式指定，在文件开头写%start program。Cminus的入口放在哪条规则上、$1是不是整棵树的根，决定了你的main函数拿到的root是谁。我最初直接把declaration-list当入口，结果AST根上少了program这一层，遍历函数判断节点类型时写得很别扭，建议保留program层。

3.2 用%union和$1/$2把token拼成AST节点

token的语义值类型不统一：NUM是整数，ID是字符串，非终结符又要携带AST节点，所以Bison用%union声明一个C联合体，再用%token 、%token 、%type 把每个符号绑定到对应字段。完整写法：

%union { int ival; char *sval; struct ASTNode *node; } %token <sval> INT VOID ID %token <ival> NUM %token IF ELSE WHILE RETURN %token ASSIGN SEMI COMMA %token LPAREN RPAREN LBRACE RBRACE LBRACKET RBRACKET %token PLUS MINUS TIMES DIV %token LT LE GT GE EQ NE %type <node> program declaration-list declaration %type <node> var-declaration fun-declaration params param-list param %type <node> compound-stmt local-declarations statement-list statement %type <node> expression-stmt if-stmt while-stmt return-stmt %type <node> expression additive-expression term factor var call

加了绑定之后，flex侧写yylval.sval、yylval.ival才有对应字段。假如某个非终结符忘了写%type，bison会把它默认当成未声明类型处理，这时写$$ = $1会报警告，更麻烦的是动作里用->访问字段编译直接报错。

表达式规则是构建AST最典型的例子。下面只写出算术部分：

additive-expression: term { $$ = $1; } | additive-expression PLUS term { $$ = new_node(NODE_OP, $1, $3, NULL); ((ASTNode *)$$)->ival = '+'; } | additive-expression MINUS term { $$ = new_node(NODE_OP, $1, $3, NULL); ((ASTNode *)$$)->ival = '-'; } ;

这里$$先赋值成new_node的结果，再把运算符记在ival字段里，后面遍历输出表达式树时按ival判断是+还是-。new_node内部要做malloc和字段清零，防止ival、sval是随机值。动作代码里$$原本持有旧指针时直接覆盖即可，旧节点仍由子节点持有，不会被误删。

AST节点本身的结构，我一般按这样设计，文件不大但够用：

/* ast.h */ #ifndef AST_H #define AST_H typedef enum { NODE_PROGRAM, NODE_VAR_DECL, NODE_FUN_DECL, NODE_IF, NODE_WHILE, NODE_RETURN, NODE_ASSIGN, NODE_OP, NODE_VAR, NODE_CONST, NODE_CALL, NODE_LIST } NodeKind; typedef struct ASTNode { NodeKind kind; int ival; char *sval; struct ASTNode *kids[3]; } ASTNode; ASTNode *new_node(NodeKind kind, ASTNode *k0, ASTNode *k1, ASTNode *k2); void print_ast(ASTNode *root, int depth); void free_ast(ASTNode *root); #endif

3.3 优先级与二义性：if-else悬空怎么默认解决，负数要不要加

Cminus的表达式优先级从低到高是关系运算、加减、乘除、括号和调用。Bison用%left/%right声明token优先级和结合性，声明在规则之前：

%left LT LE GT GE EQ NE %left PLUS MINUS %left TIMES DIV

声明的顺序越靠后优先级越高。有了这些声明，shift/reduce冲突自动消掉，a+b*c会按乘除先归约，a-b-c按左结合归约。如果不声明，bison会对每个没有优先级的token对报shift/reduce conflict，能编但行为不可控。

对if-else悬空，Bison默认策略是shift，所以else会尽量绑定最近的if，这与C语言语义一致。但bison会对每个冲突都打警告，交大作业时看到一堆“conflicts: 6 shift/reduce”很难看，所以要跑一遍bison -v生成cminus.output，逐一确认冲突位置，把警告清干净。

这里有一个容易踩的扩展点：负数。教材的Cminus没有一元负号，-5在词法上是MINUS和NUM两个token，语法上只能作为表达式a - b出现。如果作业要求支持负数常量，一般做法是给factor加一条规则，再声明一个假token来提高它的优先级：

%left LT LE GT GE EQ NE %left PLUS MINUS %left TIMES DIV %left UMINUS factor: LPAREN expression RPAREN { $$ = $2; } | MINUS factor %prec UMINUS { $$ = new_node(NODE_NEG, $2, NULL, NULL); } ;

%prec UMINUS让这条规则采用UMINUS的优先级，而UMINUS声明在乘除之后，优先级高于乘除，于是-23归约成(-2)3而不是-(23)。不写这个优先级的话，-和的shift/reduce冲突会让结果随bison默认选择变化，行为看起来“随缘”，属于典型的玄学现场。大作业如果按原书文法，不需要支持负数，你可以在文档里写明“不支持一元负号”，并给一个报错测试用例。

4. 避坑：Flex+Bison大作业里最常翻车的5个问题

4.1 编译期与链接期的三个坑

坑1：undefined reference to yylex 或者 yylex 未声明。

现象：lex.yy.c编译正常，链接时报undefined reference to `yylex'，或者在bison生成的解析器里报隐式声明警告。

原因：通常是flex生成的lex.yy.o没有进入链接命令；或者.l文件%{ %}块里声明了extern int yylex()，而bison侧要求的是int yylex(void)，两边函数签名不一致。另一个隐藏触发点是环境里libfl没链接，flex默认依赖yywrap。

解决：Makefile的OBJS里写上lex.yy.o；.l文件加%option noyywrap去掉对yywrap的依赖；在.y文件的%{ %}块声明extern int yylex(void); extern int yylineno;。代码层面保证flex和bison以相同签名编译。

坑2：make 报 missing separator，直接死在 Makefile。

现象：执行make，输出Makefile:12: *** missing separator. Stop.，第12行恰好是某条编译规则。

原因：Makefile的规则行前面必须是一个Tab字符，编辑器或复制粘贴时被替换成了空格。make对空格和Tab的处理不同，只认Tab开头的行才是规则。

解决：用cat -A Makefile检查行首是不是显示的^I；在vim里:set noexpandtab后重新敲一遍Tab。顺手把clean目标的rm命令也检查一遍，同样的错误会在那里再出现一次。

坑3：bison -d生成的cminus.tab.h在flex扫描时还不存在。

现象：第一次make报fatal error: cminus.tab.h: No such file or directory，但手动执行bison -d之后又一切正常。

原因：Makefile没有声明依赖，flex命令执行时，cminus.tab.h还没有被bison生成。

解决：Makefile里把lex.yy.c的依赖写上cminus.tab.h，让bison -d先执行；首次生成时也可以先手动跑一次bison -d cminus.y再看flex。这个顺序问题在IDE固化配置时很隐蔽，因为IDE不会告诉你前一次生成的.h去哪了。

4.2 运行期的两个坑

坑4：所有标识符打印出来都一样，或者字符串内容随机乱码。

现象：输入a=1; b=2;，AST里两个变量的名字都是b；输入超长标识符时程序崩溃。

原因：yylval.sval保存的是yytext指针，yytext生命周期只到下一次匹配。Bison在归约时才读语义值，那时缓冲区内容已经被后续输入覆盖。

解决：flex规则里对带sval的token一律做strdup。建立一条原则：凡是进yylval的字符串字段，必须拷贝出缓冲区；凡是进ival的整数字段，立即用strtol解析并检查溢出，别用裸atoi。

坑5：bison警告很多conflicts，程序还能跑但结果随输入漂移。

现象：编译通过，但是输入while(a<b)a=a+1;时，有的测试用例正确，有的把比较和赋值归约错位；不仔细看警告根本发现不了。

原因：运算符优先级没声明，bison为表达式嵌套场景生成shift/reduce冲突后，默认行为可能不符合文法语义。

解决：用bison -v生成cminus.output，查看每个冲突出现在哪个状态；为加减乘除、关系运算分别声明%left。逐条消除告警再继续写动作代码。调试本身用第5章的yydebug方法打开黑匣子看移进归约轨迹，比对着文法猜快得多。

5. 联调、测试与交作业用的文档说明：从Makefile到测试报告

5.1 Makefile：把flex、bison和手写代码串起来的三步

到这一步，你已经有了cminus.l、cminus.y、ast.c、ast.h、main.c五个文件。剩下的事情是让构建工具按正确顺序生成C代码再编译。我一般用这样一套Makefile：

CC = gcc CFLAGS = -Wall -g -std=gnu11 OBJS = lex.yy.o cminus.tab.o ast.o main.o cminus: $(OBJS) $(CC) $(CFLAGS) -o $@ $(OBJS) lex.yy.o: lex.yy.c cminus.tab.h $(CC) $(CFLAGS) -c lex.yy.c cminus.tab.o: cminus.tab.c cminus.tab.h $(CC) $(CFLAGS) -c cminus.tab.c lex.yy.c: cminus.l cminus.tab.h flex cminus.l cminus.tab.c cminus.tab.h: cminus.y bison -d cminus.y ast.o: ast.c ast.h $(CC) $(CFLAGS) -c ast.c main.o: main.c ast.h cminus.tab.h $(CC) $(CFLAGS) -c main.c clean: rm -f cminus $(OBJS) lex.yy.c cminus.tab.c cminus.tab.h

逻辑说明：bison -d同时输出cminus.tab.c和cminus.tab.h，flex的.l包含这个头文件，所以lex.yy.c的生成依赖cminus.tab.h，编译lex.yy.o时头文件也必须可见。-std=gnu11是为了让strdup这类POSIX函数有声明，换成-std=c11会报隐式声明警告，这是gcc环境下的一个典型差异。

参数说明：-Wall在flex生成的代码里会刷出大量unused function警告，先不用慌，必要时加-Wno-unused-function针对性关闭；-g保留调试符号，配合gdb能追踪AST构建过程。flex和bison的版本不同，生成代码风格略有差异，但Makefile这套依赖关系是通用的。

5.2 打开yydebug：用调试输出确认每个token和归约步骤

Bison生成的解析器内置调试开关。你想看每次读到什么token、进入什么状态、归约到哪个非终结符，只要在main里这样写：

/* main.c */ #include <stdio.h> #include "cminus.tab.h" extern int yyparse(void); extern int yydebug; extern FILE *yyin; int main(int argc, char **argv) { if (argc > 1) { yyin = fopen(argv[1], "r"); if (!yyin) { perror("fopen"); return 1; } } yydebug = 1; if (yyparse() == 0) printf("parse ok\n"); else printf("parse failed\n"); return 0; }

注意三个细节：bison默认生成的解析器里保留调试分支，运行时把yydebug置1即可；但如果编译时用-DYYDEBUG=0强制关闭了，需要重新生成解析器。flex侧想看每个token匹配到了哪条规则，用flex -d重新生成lex.yy.c，运行时会输出--accepting rule at line N。yydebug输出很长，一个10行的.cminus可能打印几百行状态迁移，建议配合小测试文件使用。

输出长什么样？大致是Starting parse、Entering state 3、Reading a token: Next token is token IF、Reducing stack by rule 12这类。这些打印能直接回答两个问题：你的token有没有被错误识别；某条产生式究竟走了哪个候选。我第一次打开yydebug时，发现自己if语句的else分支压根没归约到if-stmt的第二个候选，就是因为flex没返回ELSE，打印结果一目了然。

5.3 测试用例与文档说明：覆盖每条文法，别只测“能编译过”

交作业不只要交代码，文档说明里得证明你的词法分析和语法分析覆盖了Cminus的每一条文法规则。我习惯建一个tests目录，每个用例只测一类特性，并配上期望输出：

每跑一个用例，把AST打印和报错信息存进result/目录。文档说明按这个结构写：设计概述（flex和bison分工、token表、文法产生式列表）、冲突消除措施（if-else悬空、优先级声明）、AST节点类型设计、测试环境与运行命令、逐用例测试结果。运行命令写到让助教能直接复制粘贴执行的程度，README第一行就是make && ./cminus tests/t01_decl.cminus。

文档里不要光贴代码，要把“为什么这么设计”写明白。助教最想看的是你认识到冲突存在、列出消除策略，而不是一份只有结果没有过程的文件。打印AST的函数值得一提：每层缩进两个空格，先打印节点kind再递归子节点，输出能肉眼对上文法结构，比单测还直观。

6. 再往前一步：符号表、语义检查和中间代码生成的方向

到这里，词法分析和语法分析已经跑通。如果目标是尽快交作业，做到第5章就够；但如果想把编译课吃透，最自然的下一步不是堆更多文法，而是信息收集。flex和bison在分析过程中其实丢掉了很多信息，比如每个标识符在哪一行声明、作用域嵌套关系，符号表就是把这些信息捡回来的数据结构。

一个可行的架构：建一个作用域栈，进入函数或块时push，退出时pop；遍历AST时遇到var-declaration就把名字和类型登记进当前作用域；遇到表达式里的var引用，沿作用域链向上查找，未找到就报“未声明变量”。语义检查接着做类型匹配，比如Cminus里赋值操作左右类型是否一致、函数实参个数是否等于形参个数、return语句在void函数里是否合法。这一阶段不需要新的生成器，纯粹写C遍历AST即可。

如果想把作业做成完整编译器前端，可以再接一个中间代码生成。常见做法是把AST转成三地址码，输出像t1 = a + b这样的指令，再交给一个简单解释器执行。这比直接生成汇编简单，又能让测试用例真正“跑出结果”。我当年就是卡在这：AST建得很好，打印也正常，真正要计算表达式时才意识到，得先给AST节点加一个eval函数，按后序遍历带入符号表求值，否则所有输出都只是语法形状，没有语义结果。

有一个血泪教训：无论你后续做多少扩展，AST节点设计时一定预留统一的内存释放接口。我大作业早期图省事，节点全部堆分配从不free，后面加符号表想复用结构时才发现整个树需要深拷贝，改了两天。建议从一开始就在ast.c里写free_ast，递归释放子节点和sval，valgrind跑得干干净净再交。这套Flex+Bison的前端做完，你对词法分析、语法分析、AST、错误定位就有一条完整的闭环经验了，之后看LLVM IR、写解释器都建立在同样的心智模型上。希望帮到你。

本文还有配套的精品资源，点击获取