Flex+Bison构建Cminus语法树：完整链路与避坑指南

简介这是一份编译原理课程大作业完整方案使用Flex与Bison对Cminus语言进行词法分析和语法分析内含全部源代码、实验报告与README说明。压缩包共14个文件以C源文件、头文件、词法规则.l、语法规则.y及doc实验文档为主zip包仅328KB结构紧凑便于快速部署学习。其中词法规则与语法规则文件分别承担token识别和语法树构建C源文件与头文件组成完整分析流程代码已经完整测试并成功运行项目答辩平均分96分适合计科、人工智能等专业学生用于课程设计、毕业设计或编译原理入门进阶也可在此基础上修改扩展实现自定义语法或中间代码生成等功能。目前已有106人学习下载下载后依据实验报告和README即可复现分析流程若为小白不熟悉运行环境还可私聊作者获取远程教学支持快速跑通整个项目。1. 一份 FlexBison 的 Cminus 课设从文件堆到能跑的完整链路如果你正被编译原理大作业卡住最直接的痛感是Flex 和 Bison 的教程能搜到一大堆真正把 Cminus教材里那个“小C语言”跑通到语法树的成品却不多。这份资源从词法分析、语法分析到语法树构建再配三个测试输入是一个能直接运行的完整前端适合课设卡壳的学生拿来对照也适合作为脚手架改成其他教学语言。我先说拆完的结论代码本身是能跑的但拿到手别急着 make你得先把 bison、flex、gcc 的生成顺序理清再处理几个一看到报错就想不到原因的小坑。这篇笔记就把完整链路和这些坑一次讲透。2. 词法分析 lexical.lToken 清单、正则规则与 lex.yy.c 的生成2.1 Cminus 词法要覆盖的 TokenCminus 是标准的“小C语言”保留了 C 最核心的子集程序由声明列表组成声明分变量声明和函数声明类型只有 int 和 void支持一维数组语句只有复合语句、if、while、return 和表达式语句。词法层面要认出的东西其实很少6 个关键字、标识符、整数、运算符、分隔符外加注释和空白。所以 lexical.l 通常只有 80120 行别看到 flex 生成的 lex.yy.c 有几千行就被吓住那是生成代码不是让你手维护的。Token 类别正则形态示意示例关键字else / if / int / return / void / whileif、while标识符[a-zA-Z][a-zA-Z0-9]*i、sum、find整数字面量[0-9]0、42运算符 - * / ! 分隔符; , ( ) [ ] { }( 、)注释/* ... *//* comment */这 6 个关键字和运算符集合不是随便定的它对应语法层每一条产生式。写词法之前先对着 syntax.y 里的%token列表数一遍能避免“漏 token”导致的诡异 syntax error。很多同学上来就写标识符正则结果else、while全被当成 ID语法分析器读到一个ID而不是ELSE报错位置完全没法看。另一个常见误解是老师让画状态转换图以为要在代码里实现 NFA/DFA其实 Flex 里每条正则就等价于一张状态转换图工具替你完成了图到代码的转换你只需要把图翻译成正则规则。2.2 lexical.l 的三段式结构Flex 文件由三个区段组成用%%分隔定义区写 C 头文件、宏和%option规则区写“正则 动作”用户代码区放辅助函数。这份资源里 lexical.l 的典型形态如下%{ #include stdio.h #include stdlib.h #include string.h #include syntax.tab.h %} %option noyywrap yylineno %% else { return ELSE; } if { return IF; } int { return INT; } return { return RETURN; } void { return VOID; } while { return WHILE; } [0-9] { yylval.intval atoi(yytext); return NUM; } [a-zA-Z][a-zA-Z0-9]* { yylval.string strdup(yytext); return ID; } { return LTE; } { return GTE; } { return EQ; } ! { return NEQ; } |-|*|/||||;|,|(|)|[|]|{|} { return yytext[0]; } [ \t\n] ; /*([^*]|*[^/])**/ ; . { fprintf(stderr, line %d: unexpected char %s\n, yylineno, yytext); } %%这段代码有四个位置需要看懂。第一#include syntax.tab.h里的头文件是 bison 用-d参数生成的里面定义了ELSE、NUM这些 token 的宏编号所以生成顺序必须是先 bison 后 flex这个下一节细说。第二yylval.intval和yylval.string由 syntax.y 里的%union定义词法规则里是在返回 token 之前把语义值塞进全局变量yylval语法分析器那边通过$1、$2取回。第三操作符规则合并成一条正则动作里return yytext[0]直接返回单字符本身这样在 syntax.y 里可以用(、这样的字面量直接当 token 名省掉一大串无意义命名。第四空白和注释规则没有 return 语句匹配后自动跳到下一个规则继续扫描这就是 Flex 里“什么都不做就继续”。%option noyywrap表示只有一个输入流、读完直接返回 0不再调用yywrap()询问是否拼接下一个文件%option yylineno让 Flex 自动维护全局变量yylineno语法错误时能报准确行号。如果你在手写别的版本看到有人在文件尾部补一个int yywrap() { return 1; }那是用函数替代 option 的等价写法两种方式选一种就行别同时写。还有一条容易被忽略的规则顺序关键字规则必须写在标识符规则之前。if的长度是 2标识符正则也能匹配长度为 2 的串Flex 对相同长度的匹配采用“先出现先得”关键字规则放前面才能保证if返回IF而不是ID。这不是玄学是 Flex 的确定性规则。2.3 从 lexical.l 到 lex.yy.c生成顺序与第一个坑编译这套工程的标准命令序列是bison -d syntax.y flex lexical.l cc -o parser main.c lex.yy.c syntax.tab.c -lfl第一条命令生成syntax.tab.c和syntax.tab.h第二条生成lex.yy.c第三条把主程序、词法分析器和语法分析器一起编译。注意依赖顺序lexical.l 里 include 了syntax.tab.h如果先跑flex lexical.l会直接报fatal error: syntax.tab.h: No such file or directory。这时候别怀疑规则写错就是生成顺序反了。更省事的做法是写一个简单的 Makefile 或用资源里自带的 run 脚本把这三条命令按顺序固化成一步。链接选项这里有个判断技巧只要 lexical.l 里写了%option noyywrap-lfl其实可以去掉因为 Flex 的运行库 libfl 主要是为了补yywrap和main这两个符号。很多同学一遇到链接报错就拼命加-lfl -ly其实-lyBison 库在这类工程里通常完全用不上加多了反而可能在有的系统上引发隐式 main 符号冲突。我的习惯是先检查 option 区再动链接参数。3. 语法分析 syntax.y产生式、语义动作与语法树的构建3.1 为什么是 Bison 而不是递归子程序法选 Bison 不是图省事而是 Cminus 的文法形态天然适合 LALR(1)。课程实验里常见的替代方案是递归子程序法也就是针对 LL(1) 文法的预测分析法为每个非终结符写一个函数靠函数调用模拟推导过程。这两种做法差别很大用一张表可以看得很清楚方案左递归处理表达式优先级与 Cminus 文法的匹配度递归子程序法预测分析法要手工消除左递归改写过粗容易丢语义只能靠函数分层代码量翻倍表达式一多就难维护Bison LALR(1)原生支持左递归文法%left声明或文法分层声明、表达式、语句几乎逐条直译如果用手写递归子程序法做 Cminusexpression - additive_expression - term - factor这条链要拆成四层函数每层还要手工维护 FIRST/FOLLOW 来选产生式工作量全花在推导过程上而不是语义动作上。Bison 生成的是 LR 自动机左递归直接写冲突由优先级声明消解你只需要把精力放在“归约时建什么树节点”上这一条就足够说服课程设计里选 Bison 了。3.2 syntax.y 的三段式结构与核心动作Bison 文件和 Flex 一样也是三段式声明区、规则区、用户代码区。声明区里最关键的是%union、%token、%type它们共同定义了语义值的类型和各符号能携带的语义值。语法树节点本身的定义放在 tree.h 里资源里的典型实现长这样typedef struct TreeNode { NodeKind nodeKind; /* StmtK 语句节点 / ExpK 表达式节点 */ Kind kind; /* 具体类型OpK、IdK、ConstK、AssignK */ int op; /* OpK 时的运算符字符如 、* */ int value; /* ConstK 时的整数值 */ char *name; /* IdK 时的变量名 */ int lineno; /* 行号调试定位用 */ struct TreeNode *children[4]; /* 最多 4 个孩子足够装下 Cminus 全部产生式 */ } TreeNode; TreeNode *newNode(NodeKind nk, int line) { TreeNode *t (TreeNode *)malloc(sizeof(TreeNode)); memset(t, 0, sizeof(TreeNode)); t-nodeKind nk; t-lineno line; return t; }注意children数组必须清成 NULL否则递归打印语法树时会段错误这是后面避坑章要展开的情节。有了节点结构syntax.y 里的规则动作就是在归约时调用newNode组织这棵树%{ #include stdio.h #include stdlib.h #include string.h #include tree.h extern int yylineno; void yyerror(const char *msg); int yylex(void); TreeNode *root NULL; %} %union { int intval; char *string; TreeNode *node; } %token IF ELSE INT RETURN VOID WHILE %token intval NUM %token string ID %type node program declaration_list declaration var_declaration fun_declaration %type node type_specifier params param_list param compound_stmt local_declarations %type node statement_list statement expression_stmt selection_stmt iteration_stmt %type node return_stmt expression var simple_expression additive_expression %type node term factor call %% program : declaration_list { root $1; } ; declaration_list : declaration_list declaration { $$ newNode(StmtK, yylineno); $$-kind DeclK; $$-children[0] $1; $$-children[1] $2; } | declaration { $$ $1; } ; expression : simple_expression | var expression { $$ newNode(ExpK, yylineno); $$-kind AssignK; $$-children[0] $1; $$-children[1] $3; } ; additive_expression : additive_expression term { $$ newNode(ExpK, yylineno); $$-kind OpK; $$-op ; $$-children[0] $1; $$-children[1] $3; } | term { $$ $1; } ; term : term * factor { $$ newNode(ExpK, yylineno); $$-kind OpK; $$-op *; $$-children[0] $1; $$-children[1] $3; } | factor { $$ $1; } ;$1、$2是产生式右部各符号的语义值$$是把值赋给左部非终结符。以additive_expression term为例$1拿到左操作数的树节点$3拿到右操作数的树节点动作里新建一个OpK节点挂两个孩子。子树挂载顺序要注意左子树放children[0]右子树放children[1]递归打印时按这个顺序输出语法树才是人类能读的表达式。如果挂反了语法树打印出来左右颠倒a - b会变成b - a的结构排查时极其隐蔽。这种分层写法的优先级原理很直白additive_expression可以包含term但term内部才能出现乘除。遇到a b * c加法规则归约时右孩子是b * c这个OpK *节点乘号在树的更深层正好得到先乘后加的语义。这就是用文法层次表达优先级比%left声明更直观答辩时也更容易讲清楚。3.3 优先级处理%left 声明与文法分层的取舍如果觉得每层都写完整产生式太长Bison 允许在声明区直接给终结符指定优先级和结合性%left - %left * /%left表示左结合谁写在后面谁优先级高所以这里的* /比 -优先级高。加了这两行之后前面那段additive_expression、term的分层可以压缩成少数几条产生式规则区短一半。但需要知道这种方案的边界%left只能作用于终结符如果文法里有悬空 else 这种非终结符选择问题优先级声明帮不上忙冲突还得靠 Bison 默认的 shift 行为和%expect来消解。如果你用的 Cminus 文法版本包含单目负号才需要引入一个伪 token 配合%prec%nonassoc UMINUS %% factor : - factor %prec UMINUS ;%nonassoc UMINUS只声明优先级不声明结合性%prec UMINUS让这条产生式临时借用UMINUS的优先级从而压过二元乘除。教材标准版 Cminus 没有单目负号所以这份资源里一般用不上学有余力再扩展。我的建议是表达式部分用%left省力声明、语句部分老老实实写产生式这样语法错误定位最直观。资源里两个方式混用的痕迹很明显读代码时不用觉得奇怪。4. 串起整条链路main.c 调用顺序、yylval 传递与报错恢复4.1 main.c 与 yyparse 的调用顺序词法和语法两部分写完后入口是 main.c。Bison 生成的yyparse()函数每次从全局输入流yyin读字符内部反复调用yylex()取 token触发归约时执行 syntax.y 里的动作代码。main.c 只负责开文件、调yyparse、打印结果#include stdio.h #include syntax.tab.h #include tree.h extern int yyparse(void); extern FILE *yyin; extern TreeNode *root; int main(int argc, char **argv) { if (argc 1) { yyin fopen(argv[1], r); if (!yyin) { perror(argv[1]); return 1; } } if (yyparse() ! 0) { fprintf(stderr, parse failed\n); return 1; } if (root) { printTree(root, 0); } return 0; }yyin是 Flex 暴露出来的输入文件指针默认指向 stdinargv[1]存在时改成打开指定测试文件这样命令行直接./parser input1.c就能跑。yyparse()返回 0 表示语法分析成功、语法树构建完成非 0 说明有语法错误。如果root非空就调用printTree按缩进打印整棵树。这里有个工程习惯不要在不确认yyin是否等于 stdin 的情况下直接fclose(yyin)课设规模程序进程退出时系统会回收文件句柄关闭反而可能因为关闭标准输入导致后续诡异行为。资源里的 run 脚本做的事等价于bison -d syntax.y flex lexical.l cc -o parser main.c lex.yy.c syntax.tab.c -lfl ./parser input1.c前三条命令在 2.3 已经见过最后一条才是真正跑测试。如果yyparse返回非 0脚本会继续执行下一条命令所以想看清错误输出时建议把三条命令拆开手动跑别让脚本把有用的报错刷掉。4.2 Token 值怎么传yylval 与 %unionyylex返回的是 token 类型编号一个 int光有这个还不够整数字面量的值、标识符的名字、语法树节点指针都必须跟着 token 一起传给分析器。Bison 定下的机制是全局变量yylval词法规则里先把语义值存进去语法规则里再通过$1、$2取出来。yylval要装多种类型所以声明区用%union定义字段。课设里有三种常见做法。最早期的写法把yylval定义成 int只传数值标识符靠查符号表返回编号扩展性差也有人把yylval定义成char*数字也存成字符串语法动作里到处atoi能跑但很别扭。这份资源用的是标准做法也就是 3.2 节%union里写的intval / string / node三个字段。这里有一个全工程最值得记住的细节词法规则里对标识符必须写成yylval.string strdup(yytext)不能直接写yylval.string yytext。yytext指向的是 Flex 内部缓冲区读完下一个 token 内容就被覆盖直接存指针语法树里所有标识符最后都会变成同一个字符串。strdup复制一份独立内存后指针才真正安全。至于复制出来的内存要不要 free课设规模不用专门管进程退出时操作系统统一回收把精力放在语法功能上比纠结内存泄漏更有价值。4.3 yyerror 与错误恢复语法错误时 Bison 默认调用yyerror。课设里最常见的实现就是打印行号和错误信息void yyerror(const char *msg) { extern int yylineno; fprintf(stderr, line %d: %s\n, yylineno, msg); }yylineno由 2.2 节的%option yylineno维护在 syntax.y 里用extern int yylineno声明就能访问。错误信息输出格式通常长这样line 4: syntax error虽然朴素但行号是老师最容易追问的点必须保证准确。错误后 Bison 进入错误恢复模式丢弃当前 token持续读入后续 token直到遇到能同步的符号分号、右花括号这类再尝试继续解析。这种“恐慌模式”的好处是一个文件里可以连续报多个错误而不是第一个错就全盘退出测试多错误用例时非常有用。如果你想观察错误恢复的完整过程把yydebug打开就能看到每一步的动作具体方法留在最后一章。5. 测试与避坑input1 到 input3 覆盖点与五个真实踩坑记录5.1 三个测试输入覆盖了什么压缩包里三个测试文件按难度递增安排这种命名习惯在课设里很常见。它们的作用可以理解为三层递进的自测测试文件常见的覆盖内容主要验证点input1.c全局变量声明、int 函数定义、赋值和算术表达式表达式优先级、叶子节点值、语法树整体结构input2.cif-else 嵌套、while 循环、比较运算符悬空 else 的归属、控制流节点在树中的位置input3.c函数调用、return、一维数组的声明与下标访问call 节点、形参实参个数、数组维度处理具体文件内容以压缩包里的实际代码为准但验证方法是一致的运行程序后看printTree输出的文本树数节点数量和层次。叶子节点数应该等于标识符加整数字面量的总数内部节点数对应运算和语句结构。最常见的异常信号是运算符节点比预期多出几个说明优先级写错a b * c被归约成了(a b) * c如果 IF 节点的子树数量与教材文法不一致多半是悬空 else 的规则动作挂错了分支。三个文件从小到大跑一遍每个文件输出的人工检查顺序固定为先看行号是否递增再看叶子节点值最后看运算符层次。5.2 五个坑与排查思路坑一链接时 undefined reference to yywrap现象cc编译链接最后一步报undefined reference to yywrap但词法规则看起来完全没问题。原因Flex 生成的扫描器默认带一个yywrap调用它用来判断输入文件是否读完、要不要切换下一个文件。工程里没有定义这个函数也没链接 Flex 运行库。解决三选一。最推荐在 lexical.l 定义区加%option noyywrap或者编译命令加-lfl或者在 lexical.l 用户代码区补int yywrap() { return 1; }。只做一种就行我一般直接写死 option省得每次编译都纠结参数。坑二语法树里标识符全部变成同一个名字现象打印语法树所有IdK节点的 name 都是同一个串通常是源文件里最后一个标识符。比如int x; int y;打出来两个节点都叫 y。原因词法规则里写了yylval.string yytext。yytext是 Flex 内部共享缓冲区指针每匹配一个新 token 就被覆盖实际存的是“最后一次匹配的指针”。解决改成yylval.string strdup(yytext);复制出一块独立内存。排查这个坑时直接搜 lexical.l 里所有yytext赋值凡是没有strdup的都有嫌疑。坑三报错行号永远是 0现象输入一个明显有语法错误的文件yyerror打出来的行号固定是line 0。原因词法文件没启用行号维护。Flex 默认不自增行号你在规则里也没手动维护yylineno它保持初始化值 0。解决lexical.l 加%option yylineno同时注意别在规则里自己写yylineno数换行否则会和选项自增重复计数。如果已经加了 option 行号还是 0检查 syntax.y 里有没有extern int yylineno;只声明不 extern 同样拿不到值。坑四bison 报 1 shift/reduce conflict现象执行bison -d syntax.y时终端输出warning: 1 shift/reduce conflict程序还能跑但心里不踏实。原因Cminus 文法里最常见的冲突源是 if-else 悬空 else。遇到if (a) if (b) stmt; else stmt;这个 else 既可以匹配内层 if 也可以匹配外层 ifBison 默认用 shift 让 else 匹配最近的 if这正是教材期望的行为。解决先确认冲突数。只有这一个冲突可以明确接受在声明区加%expect 1消掉警告并写明意图。如果冲突数到了两位数多半是表达式优先级没声明或者声明位置写错回到 3.3 检查%left顺序。不要用yydebug盲猜先看冲突数对不对再决定改文法还是加声明。坑五语法树只有根节点或者一运行就段错误现象输入完全正确的文件root 非空但孩子节点全是空另一个变体是程序一运行直接段错误。原因newNode里children数组没初始化成 NULL递归打印时判断不了叶子节点或者某条规则的动作里把叶子节点的children[0]又赋值了一次破坏了树结构。解决tree.h 的newNode里用memset把整个节点清空打印函数递归前先判空。排查时先喂一个int x;的最小样例确认能打出两个节点再叠加表达式每加一条语法规则重新跑一遍段错误的定位范围就能从整棵树缩小到刚加的那条规则。6. 进阶验证用 yydebug 观察移进-归约把语法树导出成文本答辩被问“你怎么证明语法树是对的”时光说跑通还不够两个轻量手段能拿出来当证据。第一个是在 main.c 里加extern int yydebug; yydebug 1;Bison 会把每一步分析动作打到 stderr输出大致长这样Starting parse Entering state 0 Reading a token Next token is token ID (1.1) Shifting token ID (1.1) Entering state 1 Reducing stack by rule 34 (expression - var) - $$ nterm var (1.1)Shifting token是读入符号入栈Reducing stack by rule xx说明用第 xx 条产生式做了一次归约括号里的(行.列)是 token 位置。对照 syntax.y 里产生式的编号可以亲眼看到2 3 * 4先把3 * 4归约成 term再参与加法归约优先级是否正确一目了然。第二个手段是printTree的文本输出把./parser input3.c重定向到文件后得到类似这样的树ExpK: OpK ExpK: IdK (x) ExpK: OpK * ExpK: IdK (y) ExpK: ConstK 2左子树在 children[0]、右子树在 children[1]递归打印后中序可读展示在实验报告里比任何流程图都直观。拆这套代码时我排第一个语法错误排了半个晚上后来养成的习惯是新拿到任何一套 FlexBison 工程先看 syntax.y 的%union和优先级声明再看 lexical.l 有没有%option noyywrap最后才按 bison、flex、gcc 的顺序编译。这个顺序帮我避开了大半的课设翻车。希望帮到你。本文还有配套的精品资源点击获取