简介编译原理大作业中词法分析与语法分析是常见难点一套基于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才有对应字段。假如某个非终结符忘了写%typebison会把它默认当成未声明类型处理这时写$$ $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); #endif3.3 优先级与二义性if-else悬空怎么默认解决负数要不要加Cminus的表达式优先级从低到高是关系运算、加减、乘除、括号和调用。Bison用%left/%right声明token优先级和结合性声明在规则之前%left LT LE GT GE EQ NE %left PLUS MINUS %left TIMES DIV声明的顺序越靠后优先级越高。有了这些声明shift/reduce冲突自动消掉ab*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. 避坑FlexBison大作业里最常翻车的5个问题4.1 编译期与链接期的三个坑坑1undefined 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以相同签名编译。坑2make 报 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命令也检查一遍同样的错误会在那里再出现一次。坑3bison -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所有标识符打印出来都一样或者字符串内容随机乱码。现象输入a1; b2;AST里两个变量的名字都是b输入超长标识符时程序崩溃。原因yylval.sval保存的是yytext指针yytext生命周期只到下一次匹配。Bison在归约时才读语义值那时缓冲区内容已经被后续输入覆盖。解决flex规则里对带sval的token一律做strdup。建立一条原则凡是进yylval的字符串字段必须拷贝出缓冲区凡是进ival的整数字段立即用strtol解析并检查溢出别用裸atoi。坑5bison警告很多conflicts程序还能跑但结果随输入漂移。现象编译通过但是输入while(ab)aa1;时有的测试用例正确有的把比较和赋值归约错位不仔细看警告根本发现不了。原因运算符优先级没声明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代码再编译。我一般用这样一套MakefileCC gcc CFLAGS -Wall -g -stdgnu11 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.hflex的.l包含这个头文件所以lex.yy.c的生成依赖cminus.tab.h编译lex.yy.o时头文件也必须可见。-stdgnu11是为了让strdup这类POSIX函数有声明换成-stdc11会报隐式声明警告这是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即可但如果编译时用-DYYDEBUG0强制关闭了需要重新生成解析器。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目录每个用例只测一类特性并配上期望输出| 用例文件 | 覆盖点 | 期望结果 | | t01_decl.cminus | 变量声明、数组声明、数组维度为整数常量 | AST含NODE_VAR_DECL维度正确 | | t02_fun.cminus | 函数定义、参数、void返回 | AST含NODE_FUN_DECL参数列表完整 | | t03_arith.cminus | 加减乘除优先级、括号 | 运算符优先级正确括号兜底 | | t04_if.cminus | if、if-else悬空 | else绑定最近的ifAST两层if | | t05_while.cminus | while、嵌套语句 | while子树含循环体条件节点正确 | | t06_call.cminus | 函数调用、实参列表 | 调用节点实参个数与参数声明一致 | | t07_err.cminus | 非法字符、缺分号、未闭合注释 | 词法或语法错误能定位到行号 |每跑一个用例把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递归释放子节点和svalvalgrind跑得干干净净再交。这套FlexBison的前端做完你对词法分析、语法分析、AST、错误定位就有一条完整的闭环经验了之后看LLVM IR、写解释器都建立在同样的心智模型上。希望帮到你。本文还有配套的精品资源点击获取