Flex与Bison实战：构建Cminus编译器前端从词法到AST

简介：基于Flex和Bison的Cminus词法分析与语法分析工程，是一个完整的编译原理课程大作业源码与文档包，面向计算机相关专业在校生、课程设计者及需要完成类似毕设项目的开发者。压缩包共14个文件，以6个C源文件和2个头文件为主体，配合词法规则文件、语法规则文件、可执行程序及实验报告和说明文档，完整呈现从正则表达式与文法规则到词法/语法分析器的构建流程，整体仅328KB，结构清晰便于按模块查阅。已有106人学习下载，代码经实际测试运行成功，可靠性较高。通过阅读源码与配套文档，读者可快速理解词法分析与语法分析这两个编译前端核心阶段的工作原理，结合实验报告梳理实现思路；参考其架构可进行二次扩展，用于课程汇报、答辩材料准备，也可作为编译器前端教学演示项目，适合入门学习与进阶修改。

1. 这个作业题，其实是让你徒手造一个“能跑”的编译器前端

编译原理课的大作业大多长一个样：给你一门小语言，让你用工具链把词法分析、语法分析跑通，最后产出一个看得见结果的程序。Cminus就是那门被裁剪到只剩骨头的小语言，Flex负责把源码切成token，Bison负责把token流拼成语法树。很多人卡在这一步不是因为理论没学会，而是不知道这两件工具到底怎么配合、文件怎么组织、冲突怎么排掉。这篇就把整条路走一遍：从语言规格到token定义，从flex规则到bison文法，从AST节点到调试手法，照着做，你能拿到一份能编译、能跑、能交作业的完整工程，而不是停留在“我好像懂原理，但不知道从哪下手”的状态。

2. 动手前先定边界：Cminus语言规格、token约定与工程目录

写编译器第一步不是写代码，是把语言规格钉死。Cminus的版本不少，老师给的往往只是一段话：“C语言的子集，去掉结构体、指针、浮点，保留int、void、数组和函数”。听起来简单，但一旦开始写flex规则，你就会发现“注释怎么处理”“数组声明怎么写”“函数参数允许不允许空”都是必须提前拍板的事。我一般建议按下面这套最常见的Cminus规格来，它覆盖面够，作业验收时也几乎不会出问题。

2.1 Cminus的规格：变量、函数与控制流的最小可用集

Cminus的典型规格包含两类数据类型：int和void。变量声明支持基本形式和数组形式，声明可以出现在函数外部（全局）和函数内部（局部）。函数定义支持参数列表，参数本身也是int或int数组，返回值可以是int或void。

控制流只有三种：if-else、while、return。表达式部分包含算术（+ - * /）、比较（< <= > >= == !=）、逻辑（&& || !）——注意优先级和结合性需要你自己在bison里声明。语句块用{}包裹，注释用/* */包含但不支持嵌套。数组只支持一维，下标从0开始。这套规格配上后面要说的token定义，基本覆盖了绝大多数课程作业的范围，而且不会引入二义性麻烦。变量和函数的命名用C的标识符规则，数字只考虑无符号整型字面量。

提示：如果你的作业要求里明确写了“不支持逻辑运算符”或“必须支持多维数组”，以作业文档为准。这里给的是一个能跑通、好扩展的基线版本。

2.2 工程目录与文件职责：四个源文件怎么分工

Cminus的工程一般只要四个核心文件，加上一个Makefile就能构建，不必引入autotools或cmake，课程作业没必要把构建系统搞复杂。我常用的目录结构是：

• cminus.l：flex词法文件，负责把字符流变成token流
• cminus.y：bison语法文件，负责把token流变成语法树
• ast.h/ast.c：语法树的节点定义与构造/打印/释放函数
• main.c：入口，带参数解析，支持打印token和打印语法树两种模式
• Makefile：编译规则，负责调用flex、bison和gcc

这个分工的好处是：词法和语法各自的改动互不干扰，AST被单独抽出来之后，后续做语义分析和代码生成时可以直接复用。很多人把AST节点的print函数直接写进.y文件里，初期是省事，但等你开始调试树形结构时，能独立编译的ast.c会舒服得多。

2.3 定义token类型表：词法与语法之间的“通信协议”

flex和bison之间的协作，核心是token定义。bison通过%token声明一套token；flex负责在规则里返回这些token的编号给bison的解析器。cminus.tab.h是由bison用-d选项生成的，里面是一堆#define，flex文件只要#include这个头文件，就能用IF、WHILE、ID这些名字。

token表和语言规格一一对应：

这个表建议贴在代码注释里或者写在README里。写的时候有个细节：==、&&这样的两字符操作符要放在=、&的规则前面，否则flex会先把第一个字符匹配成一个独立token。这是flex最长匹配之外的第二个规则：同样长度时，先出现的规则获胜。

3. 用Flex写Cminus的词法分析器：三条正则规则吃透状态流转

词法分析器要做的事可以概括成一句话：把字符流转成带类型的token流，同时丢弃空白和注释。Flex干这件事靠的是正则规则和动作代码。先给一个能跑通的最小flex文件，再讲里面值得琢磨的几个点。

%{ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "cminus.tab.h" int lineno = 1; %} %option noyywrap %option noinput %option nounput %% [ \t]+ { /* 丢弃水平和垂直空白 */ } \n { lineno++; } "/*"([^*]|\*+[^*/])*\*+"/" { /* 跳过注释，不换行不换列 */ } "int" { return INT; } "void" { return VOID; } "if" { return IF; } "else" { return ELSE; } "while" { return WHILE; } "return" { return RETURN; } [A-Za-z_][A-Za-z0-9_]* { yylval.str = strdup(yytext); return ID; } [0-9]+ { yylval.num = atoi(yytext); return NUM; } "==" { return EQ; } "!=" { return NEQ; } "<=" { return LTE; } ">=" { return GTE; } "&&" { return AND; } "||" { return OR; } "<" { return LT; } ">" { return GT; } "+" { return PLUS; } "-" { return MINUS; } "*" { return TIMES; } "/" { return OVER; } "!" { return NOT; } "=" { return ASSIGN; } "(" { return LPAREN; } ")" { return RPAREN; } "[" { return LBRACKET; } "]" { return RBRACKET; } "{" { return LBRACE; } "}" { return RBRACE; } ";" { return SEMI; } "," { return COMMA; } . { fprintf(stderr, "line %d: illegal character '%s'\n", lineno, yytext); return ERROR_TOKEN; } %%

这段代码的逻辑分成三个层次：先处理空白和注释，再匹配关键字，最后匹配标识符和数字。flex会按规则顺序逐条尝试，取最长匹配。int和IF这些关键字规则写在标识符规则之前，利用的正是“长度相同时先声明者优先”的性质，否则int会被当成一个标识符丢给语法分析器。注释的正则"/*"([^*]|\*+[^*/])*\*+"/"覆盖了/*到*/之间的全部字符，它处理不了嵌套注释，但Cminus规范围里一般明确不要求嵌套，能识别到*/就够用。

注意：yylval.str在bison里对应%union中的char *成员，用strdup是为了避免yytext缓冲区被下一次匹配覆盖。这意味着读到的ID字符串是堆上分配的，后面如果你只想用名字做符号表key，记得在语法动作里拷贝或者妥善管理生命周期。

3.1 为什么需要%option noyywrap

noyywrap告诉flex不要链接yywrap函数。默认情况下，flex生成的扫描器在读到文件末尾时会调用yywrap()询问“还有没有别的输入文件”，如果你不定义它，链接阶段就会报undefined reference to yywrap。灵活的做法是定义自己的yywrap返回1，表示“没有更多输入了”；而在只分析一个输入文件的项目里，直接声明%option noyywrap让扫描器读完就返回0更省事。

另外两个选项noinput和nounput也是同类作用：扫描器不会用到yyinput和yyoutput，不声明这两个选项，链接时同样会缺符号。这三个%option是flex项目常见的“消除链接烦恼三件套”。

3.2 注释、字符串与多行token的两种处理路径

Cminus没有字符串类型，这里不涉及字符串字面量。最常见的翻车点是注释跨越行号和两字符操作符被拆分。注释跨行时，\n规则不触发，lineno不会递增，所以报错信息里的行号会偏移。解决办法有两种：一是把行号更新直接放到注释处理动作里，二是用flex的yylineno选项让扫描器自动维护行号。前者侵入性强，后者更通用，我建议直接打开%option yylineno，然后禁止自己定义lineno，避免和内置变量冲突。

两字符操作符被拆分的问题在==、&&、||上很常见。如果你把"=" { return ASSIGN; }写在"==" { return EQ; }前面，输入==时flex会先匹配到=，然后下一个=被当成非法字符报出来。这不是flex的bug——它确实采用最长匹配规则，但同样长度时先出现的规则优先，而=和==长度不同。如果你把=写在前面，最早匹配到的还是会走到=规则。解法是：长度更长的规则必须先出现，并且两字符操作符不能拆开写。

3.3yylex的返回值与yylval：把信息从词法层送到语法层

yylex的返回值对bison来说只有两个信息：这个token的种类编号，以及token的值。yylval是bison生成的全局变量，类型来自%union。在flex动作里写yylval.num = atoi(yytext)，bison的$1、$2才能在语法规则里取到值。

有一个常见的困惑是“为什么有的token只需要return，有的需要设置yylval”。答案很简单：关键字token的值对语法分析没有意义——int就是int，不需要携带额外数据。但标识符必须带着字符串本身，数字必须带着数值，否则语法树里没法还原源码信息。在实际的.l文件里，你经常能看到“关键字只return，标识符/数字先赋值再return”的结构，这不是随意取舍，而是后面的AST构造阶段真的用得到那些值。

4. 用Bison写Cminus的语法分析器：优先级声明与AST节点怎么搭

词法分析解决的是“这是什么词”的问题，语法分析解决的是“这些词怎么组装”的问题。Bison的输入是一个.y文件，里面含有%token声明、%union定义、优先级声明、语法规则，以及规则对应的C动作。Cminus这种规模的文法，拿到一个正确的.y文件之后，bison基本一遍就能生成解析器，真正的难点在设计AST节点结构和处理shift/reduce冲突。

4.1 从声明块到规则块：bison文件的三段式结构

一个bison文件写清楚三段就能工作。第一段是%{ %}包裹的C头文件和辅助函数声明；第二段是bison声明，包括%union、%token、%type和优先级；第三段是%%之后的语法规则，规则动作用C语言写。下面是一个骨架：

%{ #include <stdio.h> #include <stdlib.h> #include "ast.h" extern int yylex(void); void yyerror(const char *msg) { fprintf(stderr, "syntax error: %s\n", msg); } %} %union { int num; char *str; struct ASTNode *node; } %token <str> ID %token <num> NUM %token INT VOID IF ELSE WHILE RETURN %token PLUS MINUS TIMES OVER LT LTE GT GTE EQ NEQ AND OR NOT ASSIGN %token LPAREN RPAREN LBRACKET RBRACKET LBRACE RBRACE SEMI COMMA %type <node> program declaration-list declaration var-declaration fun-declaration %type <node> params param-list param compound-stmt local-declarations statement-list statement %type <node> expression simple-expression additive-expression term factor call %type <node> var expression-stmt selection-stmt iteration-stmt return-stmt %left OR %left AND %left LT LTE GT GTE EQ NEQ %left PLUS MINUS %left TIMES OVER %right NOT %right ASSIGN %% program : declaration-list { $$ = createProgramNode($1); } ;

这里的关键是%left、%right的声明。%left表示左结合，%right表示右结合，声明顺序从低优先级到高优先级。ASSIGN声明成%right是因为赋值表达式是右结合的——a = b = c要先算右边的b = c。NOT用%right表示它是单目前缀运算符，优先级高于所有二元运算符，低于后面的括号、下标、函数调用。

注意：%type声明的作用是告诉bison“这个非终结符的值类型是AST节点”，这样在规则动作里写$$ = $1时bison才知道如何做类型转换。如果不声明%type，$1的默认类型来自%token声明，类型不匹配会直接编译报错。

4.2 表达式文法：为什么不把所有运算符写在一层

把加法、乘法、比较、逻辑运算全部写成一个表达式层会带来一堆冲突。我见过的典型翻车写法是：

expression : expression PLUS expression | expression TIMES expression | LPAREN expression RPAREN | ID ;

这种写法把a + b * c的优先级留给了bison去猜。虽然%left TIMES能替bison消掉一部分冲突，但可读性和可扩展性都差。更稳的写法是分层：

simple-expression : additive-expression | simple-expression LT additive-expression | simple-expression LTE additive-expression ... ; additive-expression : term | additive-expression PLUS term | additive-expression MINUS term ; term : factor | term TIMES factor | term OVER factor ; factor : LPAREN expression RPAREN | var | call | NUM ;

这种写法的优势在于每个文法符号对应一个实际的语法树节点类型。simple-expression节点只负责比较逻辑，additive-expression只负责加减法，树结构出来之后跟语义分析的层次完全对应。虽然你多写了十几行规则，但换来的是后面AST打印、类型检查、中间代码生成时少走弯路。

4.3 AST节点：语法分析阶段就要为语义分析和代码生成铺路

AST的节点设计决定了后面每一步的舒适度。一个Cminus的AST节点至少要有三样东西：节点类型、节点携带的源码信息（变量名、函数名、数值）、子节点和兄弟节点指针。我常用的定义如下：

// ast.h typedef enum { NODE_PROGRAM, NODE_VAR_DECL, NODE_FUN_DECL, NODE_PARAM, NODE_COMPOUND, NODE_SELECTION, NODE_ITERATION, NODE_RETURN, NODE_ASSIGN, NODE_CALL, NODE_EXP } NodeKind; typedef struct ASTNode { NodeKind kind; char *name; // 用于ID：变量名、函数名 int num; // 用于NUM：整型字面量值 int arraySize; // 用于数组声明 struct ASTNode *child[4]; // 最多四个子节点 struct ASTNode *sibling; // 兄弟链 int line; // 源码行号，报错用 } ASTNode; ASTNode *newNode(NodeKind kind); void freeAST(ASTNode *node); void printAST(ASTNode *node, int indent);

用child[4]而不是动态数组是有意的：Cminus的每个语法构造最多只需要四个子节点。比如if-else是条件、then分支、else分支三个，while是条件加循环体两个，var-declaration是类型加标识符加可选的数组大小。sibling指针用来表达声明列表、语句列表中同一层多节点的情况——program的第一个子节点指向第一条声明，后续声明通过sibling串联。

每个规则动作里的$$ = makeXxxNode($1, $2, $3)都是对这个结构体的实例化。比如函数定义节点，它的子节点分别是参数列表、复合语句，名字字段记录函数名。这样的设计做语义分析的符号表填充时，遍历一次树就能把函数和全局变量都登记完。

5. 避坑：Flex与Bison联调的5条血泪经验

工具链单独用都挺顺，一旦联调就冒出一堆“玄学”问题：编译过了但运行段错误、链接报错、冲突报告看不懂、语法树打印出来是空的。下面这几条是我自己踩过之后沉淀下来的排查路径，每一条都按“现象 → 原因 → 解决”记录。

5.1 现象：链接阶段报yylex、yywrap等一堆undefined reference

原因：flex生成的词法分析器调用了yylex、yywrap、yyinput这些函数，但链接时没有把flex的库libfl加进来，或者bison那边没有声明yylex。另一个常见情况是项目中自己写了main函数，却和libfl里的main冲突了——libfl自带一个main入口，它会调用yylex并打印结果，这种main通常不是你想要的。

解决：在.y文件的声明段里写extern int yylex(void);，链接命令加上-lfl。如果你的系统里libfl位置特殊（macOS上有时叫-lfl或-ll），用pkg-config查不到就直接在Makefile里写死。更干净的做法是不要依赖libfl的main，自己写main.c，链接时只加-lfl里的词法支持函数，不入口进libfl的main。如果遇到yywrap的undefined reference，回到flex文件里加%option noyywrap。

5.2 现象：关键字“int”被识别成了标识符ID

原因：最典型的是flex文件中，标识符规则[A-Za-z_][A-Za-z0-9_]*写在了关键字规则前面。当输入是int时，两个规则匹配长度相同，flex选择先声明的标识符规则，于是int变成了一个携带字符串“int”的ID token。语法分析器接到的就不是INT而是ID，文法当然不认。

解决：把关键字规则全部挪到标识符规则之前。你会注意到这和“最长匹配”不冲突，因为关键字和标识符长度一样，靠规则顺序就能正确区分。还有一个隐蔽情形：如果某个关键字拼写错误，比如把retrun写进规则，输入return时它的匹配长度仍然和标识符规则一样，但规则顺序在标识符之前，于是会被匹配成RETURN……然后在语法层报“unexpected token”。这种问题只能靠阅读flex规则清单抓出来，没有灵丹妙药。

5.3 现象：bison运行时报shift/reduce冲突，生成的可执行文件行为奇怪

原因：文法里有二义性。最常见的是dangling-else（悬垂else）：if (a) if (b) c; else d;中else到底属于哪个if。bison默认偏向shift，也就是else绑定到最近的if，这其实是C语言标准行为，但它会伴随一个shift/reduce冲突报告。如果不处理，作业答辩时老师问起来你会比较被动。

解决：处理方案有两个。方案一是在%token IF ELSE之后声明%nonassoc LOWER_THAN_ELSE、%nonassoc ELSE这类优先级技巧，迫使bison选择归约而不是移进。方案二是改写文法，明确区分“带else的if语句”和“不带else的if语句”两个非终结符。我建议用方案二，因为方案一的优先级声明可读性差，而且它改变了if语句的推导层次，后面构造AST时容易出错。方案二的文法是：

statement : selection-stmt | iteration-stmt | return-stmt | expression-stmt | compound-stmt ; selection-stmt : IF LPAREN expression RPAREN statement | IF LPAREN expression RPAREN statement ELSE statement ;

注意这里statement间接引用了selection-stmt，而selection-stmt又引用statement，形成左递归和右递归混合。bison对这种文法能生成正确的移进/归约表，且不会再报冲突。在动作里构造AST时，if-else节点的三个子节点分别是条件、then分支、else分支，没有else时第三个子节点置NULL，语义分析时遇到NULL就知道是单分支。

5.4 现象：语法树打印出来全是同一个节点，或者深度正确但兄弟链丢了

原因：AST构造动作里没有正确设置sibling指针。比如变量声明列表的处理，如果你的文法动作是$$ = $1，而$1节点的sibling没有从$3串过去，那么后面的声明全部丢失。这类问题很难从解析器的语法树文本里直接看出来，因为文法本身没有报错，只是节点少挂了一部分。

解决：写一个makeDeclarationList之类的辅助函数，把第一条声明放在child位置，后续声明通过sibling串联。核心逻辑就一句话：新声明的sibling永远指向已有的兄弟链尾部。还有一种更隐蔽的情况：打印AST时只递归了child数组，完全没走sibling，导致所有并列声明只显示了第一个。把打印函数写成对每个子节点先递归再沿sibling迭代，这个问题就自然消解。

5.5 现象：扫描器报line 0或行号完全不更新

原因：.l文件里没有维护行号逻辑，也没有打开yylineno，而报错信息里用了某个全局变量。最常见的是注释跨行时\n规则不触发，行号变量停留在注释前的行。

解决：用flex内建的yylineno。在.l里声明%option yylineno，然后所有报错都引用yylineno。要注意yylineno的类型是int，也可能被定义成size_t，以你的flex版本为准。如果你必须在注释处理动作里手动更新行号，那就数一数yytext里有几个换行符，再把这个数目加上去，不要简单lineno++。

6. 最后一公里：把YYDEBUG打开，让语法树打印出来给你看

作业做到能编译、能跑几个样例，只算完成70%。剩下30%在验证和调试体验上：你的解析器拿到一个合法程序时，语法树长什么样；拿到一个非法程序时，报错有没有行号和token上下文。两个手段能大幅度改善这个体验：打开bison的调试输出，和写一个带缩进的AST打印函数。

第一件事，在main.c里加入调试开关：

// main.c extern int yydebug; // 由bison定义，默认0 int main(int argc, char *argv[]) { if (argc > 1 && strcmp(argv[1], "-d") == 0) { yydebug = 1; // 打开解析器的移进/归约轨迹输出 } // 打开文件，调用 yyparse() }

第二件事，AST打印函数的设计。我用的打印格式是每行一个节点，缩进表示深度，节点类型名后跟源码信息。这样对单行表达式、嵌套if、声明列表都能一眼看穿结构：

// ast.c void printASTNode(ASTNode *node, int indent) { if (node == NULL) return; for (int i = 0; i < indent; i++) printf(" "); printf("%s", nodeKindName(node->kind)); if (node->name) printf("(%s)", node->name); if (node->num) printf("[%d]", node->num); if (node->arraySize > 0) printf(" array=%d", node->arraySize); printf("\n"); for (int i = 0; i < 4; i++) { printASTNode(node->child[i], indent + 1); } for (ASTNode *s = node->sibling; s != NULL; s = s->sibling) { printASTNode(s, indent); } }

配套一个测试脚本，把一组正确用例和一组错误用例分别丢进parser，检查退出码和stderr输出。我在实际项目中见过太多人只测“能跑通的例子”，结果一个错误的表达式也能让parser静默退出、输入什么文件都返回0，这种状态下交作业很容易被验收脚本一票否决。测试关键路径就两条：int main(){return 0;}能不能解析出正确的AST结构；int main(){return ;}这类缺操作数的代码能不能报出行号。

我自己的习惯是：每次改动文法后，先跑bison -d -t cminus.y（-t让调试信息保留下来），再跑全部测试用例，最后再用./parser -d test.cminus人工看一遍移进归约轨线。这一步虽然多花五分钟，但能省掉后面的语法树错误排查。希望这篇能帮你在Flex和Bison这条路上少走几个来回，把编译原理的作业顺利收尾。

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