简介面向编译原理课程的大作业资料使用Flex与Bison完成Cminus语言的词法分析与语法分析适合计算机相关专业学生用于课程设计、项目初期演示或毕业设计参考。压缩包共14个文件328KB核心包括C源码、头文件、lex/yacc规则文件、可执行解析器以及实验报告和README说明覆盖从词法规则到语法树构建的完整流程。这份代码已经过运行验证测试通过后上传答辩评审平均分96分可靠性较高若对运行环境不熟悉下载后可私聊咨询提供远程教学。资料中附带的实验报告与文档可帮助梳理Flex/Bison的实现思路便于根据自身需求修改扩展。目前已有106人学习下载内容体量精炼适合快速对照学习编译原理前端实现。1. 编译原理大作业用Flex和Bison对Cminus进行词法分析与语法分析这条路为什么值得选如果你这学期的大作业是编译原理靶子语言十有八九是Cminus工具则固定搭配Flex和Bison。Cminus是虎书里那门教学语言体量比C小得多但函数、数组、if/else、while、表达式优先级全都保留正好能撑起一次完整的词法分析加语法分析实验。Flex负责把源码切成TokenBison负责把Token流推导成语法树比起手写递归下降和状态机这两个工具能把大作业里最机械的部分省掉让你把时间花在文法设计和AST构建上。这篇笔记就从词法需求讲到Bison文法再给你一套能落地的AST写法最后整理五个高频翻车现场。2. 词法分析先行用Flex把Cminus源码切割成Token的最小实现2.1 Cminus的Token需求清单先列全再动手写Flex规则之前第一件事是把Cminus里到底有哪些词法单元列清楚。这一步漏了后面Bison一定会反复报syntax error。Cminus的Token大致分六类关键字、标识符、常数、运算符、分隔符、注释和空白。关键字只有int、void、float、if、else、while、return这七个标识符是字母开头后面可以跟字母数字和下划线常数分整数和浮点两种运算符里需要注意、、、!这几个双字符运算符它们必须作为一个整体被识别不能先匹配再从下一个字符里读分隔符是圆括号、方括号、花括号、分号、逗号和赋值号。分类具体内容Flex里的处理方式关键字int void float if else while return返回对应token编号标识符字母开头后接字母/数字/_返回ID并把名字复制保存整数[0-9]返回NUM_INT值写入yylval浮点[0-9].[0-9]返回NUM_FLOAT值写入yylval运算符 - * / % !返回运算符token或RELOP属性值分隔符( ) [ ] { } ; , 返回对应token空白空格、制表符、换行丢弃注释/* ... */丢弃非法字符上述规则没覆盖的字符报错并继续这里要先理解Flex的匹配规则它做的是最长匹配每次都吃掉能匹配的最长字符串当两个规则匹配到同样长度的内容时写在前面那条规则赢。这就是为什么关键字规则必须放在标识符规则前面。输入if的时候关键字规则匹配到2个字符标识符规则也能匹配到2个字符如果标识符规则靠前if就会变成ID而不是关键字。反过来输入ifx的时候标识符规则匹配到3个字符长度更长所以即使它在后面也会胜出。Flex这种机制决定了规则顺序不是随便排的。2.2 一份能直接改着用的cminus.l骨架下面这份词法文件覆盖了上面的需求清单。注意它依赖Bison生成的头文件所以要先把.y文件里声明好token再用bison -d生成cminus.tab.hflex才能拿到token编号。%{ #include stdio.h #include string.h #include cminus.tab.h /* token编号来自bison -d生成的头文件 */ #define YY_NO_UNPUT 1 int line 1; /* 全局行号yyerror和AST都要用 */ %} %option noyywrap /* 不依赖libfl省去链接flex库的麻烦 */ %option nounput noinput %% [ \t] { /* 空白丢弃 */ } int { return INT; } void { return VOID; } float { return FLOAT; } if { return IF; } else { return ELSE; } while { return WHILE; } return { return RETURN; } { yylval.op LE; return RELOP; } { yylval.op LT; return RELOP; } { yylval.op GE; return RELOP; } { yylval.op GT; return RELOP; } { yylval.op EQ; return RELOP; } ! { yylval.op NE; return RELOP; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } % { return MOD; } ( { return LPAREN; } ) { return RPAREN; } [ { return LBRACKET; } ] { return RBRACKET; } { { return LBRACE; } } { return RBRACE; } ; { return SEMI; } , { return COMMA; } { return ASSIGN; } [0-9]\.[0-9] { yylval.floatVal atof(yytext); return NUM_FLOAT; } [0-9] { yylval.intVal atoi(yytext); return NUM_INT; } [A-Za-z][A-Za-z0-9_]* { yylval.name strdup(yytext); return ID; } /*([^*]|\*[^*/])*\*/ { /* 注释丢弃 */ } \n { line; } . { fprintf(stderr, line %d: unexpected char %s\n, line, yytext); } %%几个参数和写法值得解释。%option noyywrap要保留否则链接时会报yywrap undefined逼你去链接flex库很多大作业翻车就是从这里开始的。注释那一段正则看起来像玄学实际意思是注释里允许出现不是*的字符也允许*连续出现但后面不能紧跟/直到最终遇到*/为止。写成/*.**/也能用但遇到/* a /* b */ c */这类内容时会出错因为flex没有非贪婪匹配.*会一直吃到最后一个*/。浮点规则写在整数规则前面这其实是给你自己看的Flex的最长匹配机制会保证1.5被浮点规则完整匹配哪怕整数规则在前面但浮点写在前面代码可读性更好别人一眼就看出这是两套数字规则。标识符规则里用了strdup保存名字这一点很重要后面避坑章节还会专门说。2.3 不接Bison也能验证词法写个临时驱动读文件词法文件写完后强烈建议先单独测词法不要急着接Bison。原因是错误定位方便如果这一步的token都切不对后面语法分析报的错根本没法判断是哪边的问题。写一个临时main函数循环调用yylex并打印token值连Bison都不用编译/* test_lexer.c */ #include stdio.h #include cminus.tab.h extern int yylex(); extern FILE *yyin; int main(int argc, char **argv) { if (argc 1) { FILE *f fopen(argv[1], r); if (!f) { perror(argv[1]); return 1; } yyin f; } int t; while ((t yylex()) ! 0) { printf(token%d text%s line%d\n, t, yytext, line); } return 0; }编译命令是gcc lex.yy.c test_lexer.c -o lexer因为cminus.l里已经写了noyywrap这里不需要再链接flex的库。跑一个测试文件你会看到每个token对应的整数编号和原文。如果发现被切成了和两个token基本可以确定是双字符运算符规则没被最长匹配命中检查一下正则有没有写错。这一步还能顺手验证line的维护是否正确。如果一个文件里多行程序打出来的行号始终是1多半是\n规则没生效或者Windows的\r\n把\r当成非法字符打进stderr里了。3. 语法分析接力Bison从文法定义到冲突消除的完整路径3.1 先决定Cminus的文法怎么分层词法没问题后进入Bison部分。Bison的任务是把Token流归约成语法树所以第一步不是写代码而是设计文法分层。Cminus的顶层结构是program - declaration_listdeclaration可以继续分成变量声明和函数声明。函数声明里重点是params和compound_stmt其中compound_stmt又包含局部变量声明和语句列表。表达式部分需要单独分层参考虎书的原版文法用expression - simple_expression | simple_expression RELOP simple_expression、additive_expression、term、factor这套经典结构。有一个选型问题值得想清楚要不要用Bison的优先级声明%leftBison支持%left -这样直接声明运算符优先级和结合性表达式规则可以少写几层。我一般不建议大作业这么做原因有三一是Cminus的文法定义本身就是分层写的用层叠文法可以直接对照课本推导二是%left虽然能消掉冲突但它掩盖了冲突产生的本质老师在答辩时问一句%left为什么能让冲突消失你很难用三句话讲清楚LALR的移进/归约决策三是层叠文法在bison的.output文件里每个状态都清清楚楚出问题更容易排查。3.2 Bison三区段结构定义区里先把token和类型声明齐Bison文件分成定义区、规则区、辅助函数区。定义区里要写%union、token声明、%type声明和优先级声明。%union决定了yylval的字段列表flex里写yylval.op、yylval.name都要在%union里找到对应成员。%{ #include stdio.h #include stdlib.h #include string.h #include ast.h extern int yylex(); extern int line; void yyerror(const char *s); ASTNode *root; /* 全局根节点解析完后从root遍历AST */ %} %union { int ival; float fval; char *name; int op; ASTNode *node; } %token ival NUM_INT %token fval NUM_FLOAT %token name ID %token op RELOP %token INT VOID FLOAT %token IF ELSE WHILE RETURN %token PLUS MINUS TIMES DIVIDE MOD %token LPAREN RPAREN LBRACKET RBRACKET LBRACE RBRACE %token SEMI COMMA ASSIGN %type node program declaration_list declaration var_declaration fun_declaration %type node params param_list param type_specifier %type node compound_stmt local_declarations statement_list statement %type node expression_stmt selection_stmt iteration_stmt return_stmt %type node expression var simple_expression additive_expression term factor %type node call args args_list %start program %%注意ival、name这些尖括号里的名字必须与%union里的成员一一对应。比如flex里对ID写了yylval.name strdup(yytext)这里就要求ID声明成%token name ID否则Bison生成的YYSTYPE里没有name字段编译直接在赋值处报错。RELOP用op保存具体是哪个关系运算符这样语法阶段只有一个RELOP token不需要为六个关系符每个单独建tokenAST里也能拿到比较符的类型。3.3 悬空else怎么在文法层面消除matched和unmatched两套statementCminus里的if语句是允许else缺省的这会直接导致经典的悬空else冲突。Bison默认在处理IF expr THEN stmt后面跟ELSE时可以选择把不完整的if归约掉也可以把ELSE移进来看成完整if的一部分这个shift/reduce冲突在bison -v里会明确报出来。最常见的解决方式是用两个非终结符把语句分成matched_statement和unmatched_statement这样文法层面就把“只有完整if-else才能作为if的then分支”这个约束写死了statement: matched_statement { $$ $1; } | unmatched_statement { $$ $1; } ; matched_statement: expression_stmt { $$ $1; } | compound_stmt { $$ $1; } | iteration_stmt { $$ $1; } | return_stmt { $$ $1; } | IF ( expression ) matched_statement ELSE matched_statement { $$ newIfNode($3, $5, $7, line); } ; unmatched_statement: IF ( expression ) statement { $$ newIfNode($3, $5, NULL, line); } | IF ( expression ) matched_statement ELSE unmatched_statement { $$ newIfNode($3, $5, $7, line); } ;这段文法能保证每个else绑定到最近的未匹配if。如果if (a) if (b) x1; else y2;else只能配给内层if因为作为外层if then分支的必须是一个matched_statement而内层if (b) x1;恰好无线else不是matched所以这条输入在文法层就要求内层if必须有else就自然绑定了。用这个方法后bison -v里的shift/reduce冲突数量会直接归零。有的写法会用%prec和虚拟token来压掉冲突比如给无else的if规则声明一个低优先级遇到ELSE时选择移进。这种写法代码更短但它没有把语义约束编码进文法里只是利用了优先级机制。大作业更推荐matched/unmatched写法可解释性完全是不同级别。3.4 表达式的三层塔additive、term、factor就不用%leftCminus的表达式按运算符优先级分成三个层级。每层内部是左递归层与层之间用下一个层级的非终结符连接expression: simple_expression { $$ $1; } | simple_expression RELOP simple_expression { $$ newBinNode($2, $1, $3, line); } ; simple_expression: additive_expression { $$ $1; } ; additive_expression: additive_expression PLUS term { $$ newBinNode(OP_PLUS, $1, $3, line); } | additive_expression MINUS term { $$ newBinNode(OP_MINUS, $1, $3, line); } | term { $$ $1; } ; term: term TIMES factor { $$ newBinNode(OP_TIMES, $1, $3, line); } | term DIVIDE factor { $$ newBinNode(OP_DIVIDE, $1, $3, line); } | term MOD factor { $$ newBinNode(OP_MOD, $1, $3, line); } | factor { $$ $1; } ; factor: LPAREN expression RPAREN { $$ $2; } | var { $$ $1; } | call { $$ $1; } | NUM_INT { $$ newIntNode($1, line); } | NUM_FLOAT { $$ newFloatNode($1, line); } ;这个文法里a b * c先归约b * c到term再参与additive_expression的归约所以乘除天然优先于加减。左递归在LR文法里完全没有问题LALR状态机能处理这种结构不需要像LL文法那样做左公因子提取。newBinNode的第一个参数是运算符种类对应%union里的op字段后面两个是左右子树这里直接把RELOP token里保存的具体运算符从$2传给AST节点。如果你偷懒想用%left写法是%left PLUS MINUS、%left TIMES DIVIDE这种声明然后在文法里让所有表达式都走同一个非终结符靠Bison的优先级决策来归约。这条路能少写不少规则但会牺牲掉对状态机行为的直观理解而且这道题既然叫“编译原理大作业”交一份层叠文法上去比交一份依赖工具特性的文法更稳。3.5 其余规则骨架和带行号的yyerrorprogram、declaration_list、compound_stmt这部分规则比较机械但同样要写。给一个可参考的最小骨架program: declaration_list { root $1; } ; declaration_list: declaration { $$ $1; } | declaration_list declaration { ASTNode *p $1; while (p-next) p p-next; p-next $2; $$ $1; } ; declaration: var_declaration { $$ $1; } | fun_declaration { $$ $1; } ; compound_stmt: LBRACE local_declarations statement_list RBRACE { ASTNode *p newNode(NODE_COMPOUND, line); p-kids[0] $2; p-kids[1] $3; $$ p; } ;函数声明、参数列表、return语句的写法思路一样每个非终结符在语义动作里返回一个AST节点用小规则拼大规则。注意Cminus里void只能作为函数返回类型不能用来声明变量这一条如果不处理后面语义分析阶段会出问题语法阶段可以先不管把type_specifier的节点信息保留下来即可。yyerror建议至少带上行号否则老师拿一个20行的测试文件问你第几行错了你根本答不上来void yyerror(const char *s) { fprintf(stderr, line %d: %s\n, line, s); }行号是flex里那个全局变量line维护的每次匹配到\n就加一。这里提醒一句文件里的换行如果是Windows的\r\n\r会被当成非法字符打印出来你需要先在flex里把\r也归入空白丢弃或者测试用例统一用LF换行。4. 把语法规则变成AST节点设计、语义动作和内存策略4.1 AST节点定义三个子节点加一个兄弟链就够用Bison的归约动作里每个$$最终都应该指向一个AST节点。Cminus的语言结构不复杂节点定义不用做成一堆子类一个结构体加一个kind枚举就够/* ast.h */ typedef enum { NODE_PROGRAM, NODE_VAR_DECL, NODE_FUN_DECL, NODE_PARAM, NODE_COMPOUND, NODE_IF, NODE_WHILE, NODE_RETURN, NODE_ASSIGN, NODE_BIN_EXPR, NODE_REL_EXPR, NODE_INT_CONST, NODE_FLOAT_CONST, NODE_ID, NODE_CALL } NodeKind; typedef struct ASTNode { NodeKind kind; int line; char *name; /* 标识符名字 */ int intVal; float floatVal; int op; /* 运算符或关系符 */ int arrayLen; /* 数组长度-1表示普通变量 */ struct ASTNode *kids[3]; /* 三个子节点 */ struct ASTNode *next; /* 兄弟链用于声明列表和参数列表 */ } ASTNode;三个子节点分别怎么用if节点存condition、then、elsewhile节点存condition、body第三个置NULL赋值节点存左值和右值二元运算节点存左右操作数第三个置NULL。next字段用于把所有变量声明串成链表这样declaration_list规则里就不用维护一个动态数组了。arrayLen字段默认赋成-1表示这是普通变量遇到int a[10]再赋成10。如果malloc后不清零直接给该字段赋值倒也能用但节点里其他没赋值的字段全是随机垃圾值后面遍历AST时一旦误读就会段错误。所以创建节点时统一用calloc所有字段初始为0或NULL再根据情况覆盖。4.2 节点创建函数怎么写从底层new到专门的if节点有了结构体下一步是提供一组创建接口语义动作里只调接口不直接操作结构体字段。下面是三个最常用的函数够你跑通整个Cminus/* ast.c */ #include ast.h #include stdlib.h #include string.h ASTNode *newNode(NodeKind kind, int line) { ASTNode *p (ASTNode *)calloc(1, sizeof(ASTNode)); p-kind kind; p-line line; p-arrayLen -1; /* 默认不是数组 */ return p; } ASTNode *newBinNode(int op, ASTNode *left, ASTNode *right, int line) { ASTNode *p newNode(NODE_BIN_EXPR, line); p-op op; p-kids[0] left; p-kids[1] right; return p; } ASTNode *newIfNode(ASTNode *cond, ASTNode *thenStmt, ASTNode *elseStmt, int line) { ASTNode *p newNode(NODE_IF, line); p-kids[0] cond; p-kids[1] thenStmt; p-kids[2] elseStmt; return p; }calloc在这里是很关键的选择。它把整个结构体清零kids数组是三个NULL指针next是NULL后续无论哪条遍历路径访问到未初始化的分支都不会立刻段错误最多是逻辑判空后跳过。malloc出来的节点不保证清零指针字段是野值一次误判就能让你的程序在老师演示时崩掉。4.3 三个值得抄的语义动作范式第一个范式是声明列表拼接。Cminus的declaration_list是左递归的每归约一次都要把前一个声明的next链到最后。上面3.5给出的动作就是标准写法从头节点遍历到链表尾再挂上新节点$$始终指向链表头。第二个范式是赋值语句。Cminus的文法里expression - var ASSIGN expression语义动作要把赋值操作建成一个NODE_ASSIGN节点expression: var ASSIGN expression { ASTNode *p newNode(NODE_ASSIGN, line); p-kids[0] $1; p-kids[1] $3; $$ p; } | simple_expression { $$ $1; } ;这里有个容易绕晕的细节赋值并不是statement级别的规则而是expression级别的规则。Cminus语言里a 1;是一个expression-stmt所以赋值符号只出现在expression的推导里。如果你把ASSIGN放在statement规则里整个文法结构就对不上原定义了。第三个范式是while循环iteration_stmt: WHILE ( expression ) statement { ASTNode *p newNode(NODE_WHILE, line); p-kids[0] $3; p-kids[1] $5; $$ p; } ;孩子节点位置越固定越好。统一约定kids[0]放条件、kids[1]放循环体后续遍历时只要check kind就知道怎么取。不要在同一个节点类型里换顺序那是给自己埋雷。4.4 千万别在语义动作里直接printf给AST一个独立的输出函数很多同学拿到Bison后第一反应是“在归约成功时printf一下”这种写法短期能让你看到输出但会带来三个问题第一语义动作里的printf时机跟随归约顺序而归约顺序和源码顺序并不完全一致导致打印顺序错乱第二一旦语法错误已经归约的部分打了没归约的部分没打出来的结果半残第三后续如果要做语义分析或中间代码生成你还需要这份结构信息printf出来的东西没有任何复用价值。正确的做法是解析阶段只建树等yyparse返回成功后单独做一个dumpAST函数遍历输出缩进用树的深度控制。这样输出顺序就是源码顺序行为可预测还能方便地和预期结果做diff。AST树上挂的line字段这时候就发挥作用了打印节点时把行号一起打出来排查测试用例的问题会非常直观。血泪经验是一定要先有独立的AST输出再开始调Bison规则。否则你根本分不清是文法写错了还是动作代码写错了。4.5 节点生命周期解析阶段不要free最后一次性释放AST节点的malloc时机在归约动作里但谁负责释放常见做法是解析阶段完全不释放整个AST挂在全局root上等后续语义分析或者中间代码生成用完以后再统一递归释放。递归释放接口长这样void freeAST(ASTNode *p) { if (!p) return; for (int i 0; i 3; i) { freeAST(p-kids[i]); } freeAST(p-next); if (p-name) free(p-name); free(p); }注意$$ $1这种直接把子节点传给父节点的写法节点地址没有复制所有权还是同一份递归释放时不会重复释放同一块内存。怕的是你中途对某个节点又malloc又free后面Bison进入归约时再访问它那就立刻段错误了。我的习惯是把分配和释放分别限定在“建树阶段”和“树用完阶段”中间绝不做局部释放。另外标识符名字的释放要记得和strdup配对。flex里用strdup保存IDAST里直接用这个指针所以freeAST里要free掉name字段否则valgrind会报一堆内存泄露这在部分学校的评分标准里是要扣分的。5. 大作业避坑五个Flex/Bison翻车现场和排查方法5.1 现象flex看起来没问题但一张嘴就是syntax error, unexpected ID症状是解析int main(void)这种最简单的程序都报错但token列表明明打印出INT、ID、LPAREN等。原因大概率是关键字规则和标识符规则顺序反了if、int这些单词被当成了ID。flex在相同匹配长度时优先选靠前的规则如果ID规则写在关键字规则前面所有关键字都会变成IDBison找不到INT token自然报syntax error。解决方法是把关键字规则全部移到标识符规则之前然后重新编译。还有一个细节是Bison生成的token编号每次可能变化如果bison重跑过却没重新编译lex.yy.ctoken编号对不上也会出现类似症状解决办法见5.5。5.2 现象bison -v显示几十个shift/reduce conflict运行起来时好时坏如果冲突数量集中在几行先别急着找神奇写法消除要看具体冲突在哪。用bison -v -d cminus.y生成cminus.output在文件里搜conflict关键字每条冲突都会标出状态编号和涉及的token。看到IF、ELSE字样的冲突就是悬空else用matched_statement/unmatched_statement那套改写看到PLUS、TIMES通常是表达式没有分层检查是不是少了additive_expression到term的传递。bison -v -d cminus.y grep -n conflict cminus.output | head -20如果只是几个shift/reduce冲突Bison也能生成可用的parser因为它默认会选择移进但大作业答辩时老师看到warning都会追一句建议花时间清零。真正危险的是reduce/reduce冲突出现这个说明你的文法有两条规则能同时归约同一个东西必须改文法不能靠默认策略糊弄。5.3 现象AST里所有标识符名字都变成同一个了写一段包含a 1; b 2;的程序建出来的AST里两个变量节点名字都叫b。这是Flex缓冲区生命周期的经典问题。yytext指向flex内部的一个静态缓冲区每次调用yylex都可能被覆盖如果你的flex规则里写的是yylval.name yytextBison在移进下一个token后之前的name就变成新内容了。解决方法是规则里用strdup复制一份[A-Za-z][A-Za-z0-9_]* { yylval.name strdup(yytext); return ID; }这相当于给每个标识符名上了份后悔药。注意strdup返回的指针需要对应free否则valgrind会报内存泄露。如果用不了strdup自己写个循环复制也行核心原则就是一个字必须拷贝。5.4 现象数组声明的arrayLen字段是0或者随机值Cminus支持int a[10];我在AST节点里放了arrayLen字段。翻车点通常出在两条声明规则没有区分开。如果你把普通变量声明和数组声明写进同一条规则只访问$3而$3在第一种情况下是SEMI、不是NUM_INT取出来的值自然不对。需要在文法里明确分开var_declaration: type_specifier ID SEMI { ASTNode *p newNode(NODE_VAR_DECL, line); p-name $2; p-arrayLen -1; /* 普通变量 */ $$ p; } | type_specifier ID LBRACKET NUM_INT RBRACKET SEMI { ASTNode *p newNode(NODE_VAR_DECL, line); p-name $2; p-arrayLen $4; /* 数组长度来自NUM_INT的ival值 */ $$ p; } ;另一个隐蔽问题是malloc内存没清零就使用arrayLen。用calloc创建节点后初始值是0不会出现随机值如果你用malloc这个字段的初值完全取决于堆上残留数据看起来像玄学问题。检查代码时先确认节点创建用的是calloc。5.5 现象新增一个运算符后原来能跑的程序开始段错误给语言加或者之类的运算符改完flex规则重新编译后parser在运行时报段错误。常见原因有三个一是新token加进了.l文件但.y文件的%token声明没加token编号错位二是只重新编译了lex.yy.c没重新编译cminus.tab.c两个编译单元里YYSTYPE布局不一致三是新token在%union里没有对应字段语义动作里又去访问了不存在的yylval成员。解决要点是把头文件依赖写清楚。Makefile里把cminus.tab.h作为lex.yy.c的前置依赖每次.y改动后bison重新生成.tab.c和.tab.hflex和gcc都必须重新跑而不能只重编一半。推荐依赖写进Makefilecminus.tab.c cminus.tab.h: cminus.y bison -d cminus.y lex.yy.c: cminus.l cminus.tab.h flex cminus.l cminus: lex.yy.c cminus.tab.c ast.c gcc -g -o cminus lex.yy.c cminus.tab.c ast.c这样每次修改.y后面所有依赖都会级联重编不会出现新旧头文件混用的问题。我见过的大作业段错误里至少三分之一是增量编译没写对造成的属于最没有技术含量但最要命的坑。加运算符还有一个细节flex规则匹配最长字符串和如果都写了规则会被完整匹配这没问题但如果你只写了输入会被切成两个Bison立刻报错。新加的每一个双字符运算符都要确认有对应的完整正则别只写一个字符的规则。6. 答辩前的最后一道工序自动回归测试与冲突状态检查6.1 用diff替你做回归测试大作业临近交付时最怕改一处文法影响十处旧用例。写一个简单脚本把测试用例跑一遍并与期望输出difffor f in tests/*.cm; do ./cminus $f out/$(basename $f).txt 21 if diff -q expected/$(basename $f).txt out/$(basename $f).txt /dev/null; then echo PASS $f else echo FAIL $f fi done测试用例至少覆盖变量声明、数组声明、函数定义、嵌套if-else、while循环、多参数调用、表达式优先级、语法错误程序报错。合法程序的期望输出用dumpAST的结果固定下来非法程序只比较是否报错不必逐字匹配错误信息。6.2 把Bison当黑匣子用不是好习惯开yydebug看决策过程遇到文法冲突或者归约顺序不对时打开调试输出能看到每一个token的移进和归约int main(int argc, char **argv) { yydebug 1; /* 也可在编译时加-DYYDEBUG */ /* ... */ }打开后输出里会出现Reading a token、Shifting token、Reducing stack by rule这类日志。配合5.2生成的cminus.output状态表对照着自己写的规则逐行看一般都能找到是哪一步归约走错了方向。6.3 AST不只为交差它是语义分析和中间代码生成的前置底牌如果你的大作业还要求类型检查、符号表甚至生成中间代码这份AST直接就能作为入口。var_declaration节点里的arrayLen、name和line足够支撑符号表的插入与重复声明检查bin_expr节点里的op、kids[0]、kids[1]可以直接生成四元式。Cminus没有指针没有struct也没有for循环语言子集小而完整正好适合把前端整条链路走通。最后说一个我的习惯答辩前一定会把cminus.output里的conflict列表清零再跑一遍全部用例然后打开yydebug过两个最复杂的测试文件。编译大作业翻车最多次的地方往往不是文法本身而是工具链的依赖没对齐。希望帮到你。本文还有配套的精品资源点击获取
简介面向编译原理课程的大作业资料使用Flex与Bison完成Cminus语言的词法分析与语法分析适合计算机相关专业学生用于课程设计、项目初期演示或毕业设计参考。压缩包共14个文件328KB核心包括C源码、头文件、lex/yacc规则文件、可执行解析器以及实验报告和README说明覆盖从词法规则到语法树构建的完整流程。这份代码已经过运行验证测试通过后上传答辩评审平均分96分可靠性较高若对运行环境不熟悉下载后可私聊咨询提供远程教学。资料中附带的实验报告与文档可帮助梳理Flex/Bison的实现思路便于根据自身需求修改扩展。目前已有106人学习下载内容体量精炼适合快速对照学习编译原理前端实现。1. 编译原理大作业用Flex和Bison对Cminus进行词法分析与语法分析这条路为什么值得选如果你这学期的大作业是编译原理靶子语言十有八九是Cminus工具则固定搭配Flex和Bison。Cminus是虎书里那门教学语言体量比C小得多但函数、数组、if/else、while、表达式优先级全都保留正好能撑起一次完整的词法分析加语法分析实验。Flex负责把源码切成TokenBison负责把Token流推导成语法树比起手写递归下降和状态机这两个工具能把大作业里最机械的部分省掉让你把时间花在文法设计和AST构建上。这篇笔记就从词法需求讲到Bison文法再给你一套能落地的AST写法最后整理五个高频翻车现场。2. 词法分析先行用Flex把Cminus源码切割成Token的最小实现2.1 Cminus的Token需求清单先列全再动手写Flex规则之前第一件事是把Cminus里到底有哪些词法单元列清楚。这一步漏了后面Bison一定会反复报syntax error。Cminus的Token大致分六类关键字、标识符、常数、运算符、分隔符、注释和空白。关键字只有int、void、float、if、else、while、return这七个标识符是字母开头后面可以跟字母数字和下划线常数分整数和浮点两种运算符里需要注意、、、!这几个双字符运算符它们必须作为一个整体被识别不能先匹配再从下一个字符里读分隔符是圆括号、方括号、花括号、分号、逗号和赋值号。分类具体内容Flex里的处理方式关键字int void float if else while return返回对应token编号标识符字母开头后接字母/数字/_返回ID并把名字复制保存整数[0-9]返回NUM_INT值写入yylval浮点[0-9].[0-9]返回NUM_FLOAT值写入yylval运算符 - * / % !返回运算符token或RELOP属性值分隔符( ) [ ] { } ; , 返回对应token空白空格、制表符、换行丢弃注释/* ... */丢弃非法字符上述规则没覆盖的字符报错并继续这里要先理解Flex的匹配规则它做的是最长匹配每次都吃掉能匹配的最长字符串当两个规则匹配到同样长度的内容时写在前面那条规则赢。这就是为什么关键字规则必须放在标识符规则前面。输入if的时候关键字规则匹配到2个字符标识符规则也能匹配到2个字符如果标识符规则靠前if就会变成ID而不是关键字。反过来输入ifx的时候标识符规则匹配到3个字符长度更长所以即使它在后面也会胜出。Flex这种机制决定了规则顺序不是随便排的。2.2 一份能直接改着用的cminus.l骨架下面这份词法文件覆盖了上面的需求清单。注意它依赖Bison生成的头文件所以要先把.y文件里声明好token再用bison -d生成cminus.tab.hflex才能拿到token编号。%{ #include stdio.h #include string.h #include cminus.tab.h /* token编号来自bison -d生成的头文件 */ #define YY_NO_UNPUT 1 int line 1; /* 全局行号yyerror和AST都要用 */ %} %option noyywrap /* 不依赖libfl省去链接flex库的麻烦 */ %option nounput noinput %% [ \t] { /* 空白丢弃 */ } int { return INT; } void { return VOID; } float { return FLOAT; } if { return IF; } else { return ELSE; } while { return WHILE; } return { return RETURN; } { yylval.op LE; return RELOP; } { yylval.op LT; return RELOP; } { yylval.op GE; return RELOP; } { yylval.op GT; return RELOP; } { yylval.op EQ; return RELOP; } ! { yylval.op NE; return RELOP; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } % { return MOD; } ( { return LPAREN; } ) { return RPAREN; } [ { return LBRACKET; } ] { return RBRACKET; } { { return LBRACE; } } { return RBRACE; } ; { return SEMI; } , { return COMMA; } { return ASSIGN; } [0-9]\.[0-9] { yylval.floatVal atof(yytext); return NUM_FLOAT; } [0-9] { yylval.intVal atoi(yytext); return NUM_INT; } [A-Za-z][A-Za-z0-9_]* { yylval.name strdup(yytext); return ID; } /*([^*]|\*[^*/])*\*/ { /* 注释丢弃 */ } \n { line; } . { fprintf(stderr, line %d: unexpected char %s\n, line, yytext); } %%几个参数和写法值得解释。%option noyywrap要保留否则链接时会报yywrap undefined逼你去链接flex库很多大作业翻车就是从这里开始的。注释那一段正则看起来像玄学实际意思是注释里允许出现不是*的字符也允许*连续出现但后面不能紧跟/直到最终遇到*/为止。写成/*.**/也能用但遇到/* a /* b */ c */这类内容时会出错因为flex没有非贪婪匹配.*会一直吃到最后一个*/。浮点规则写在整数规则前面这其实是给你自己看的Flex的最长匹配机制会保证1.5被浮点规则完整匹配哪怕整数规则在前面但浮点写在前面代码可读性更好别人一眼就看出这是两套数字规则。标识符规则里用了strdup保存名字这一点很重要后面避坑章节还会专门说。2.3 不接Bison也能验证词法写个临时驱动读文件词法文件写完后强烈建议先单独测词法不要急着接Bison。原因是错误定位方便如果这一步的token都切不对后面语法分析报的错根本没法判断是哪边的问题。写一个临时main函数循环调用yylex并打印token值连Bison都不用编译/* test_lexer.c */ #include stdio.h #include cminus.tab.h extern int yylex(); extern FILE *yyin; int main(int argc, char **argv) { if (argc 1) { FILE *f fopen(argv[1], r); if (!f) { perror(argv[1]); return 1; } yyin f; } int t; while ((t yylex()) ! 0) { printf(token%d text%s line%d\n, t, yytext, line); } return 0; }编译命令是gcc lex.yy.c test_lexer.c -o lexer因为cminus.l里已经写了noyywrap这里不需要再链接flex的库。跑一个测试文件你会看到每个token对应的整数编号和原文。如果发现被切成了和两个token基本可以确定是双字符运算符规则没被最长匹配命中检查一下正则有没有写错。这一步还能顺手验证line的维护是否正确。如果一个文件里多行程序打出来的行号始终是1多半是\n规则没生效或者Windows的\r\n把\r当成非法字符打进stderr里了。3. 语法分析接力Bison从文法定义到冲突消除的完整路径3.1 先决定Cminus的文法怎么分层词法没问题后进入Bison部分。Bison的任务是把Token流归约成语法树所以第一步不是写代码而是设计文法分层。Cminus的顶层结构是program - declaration_listdeclaration可以继续分成变量声明和函数声明。函数声明里重点是params和compound_stmt其中compound_stmt又包含局部变量声明和语句列表。表达式部分需要单独分层参考虎书的原版文法用expression - simple_expression | simple_expression RELOP simple_expression、additive_expression、term、factor这套经典结构。有一个选型问题值得想清楚要不要用Bison的优先级声明%leftBison支持%left -这样直接声明运算符优先级和结合性表达式规则可以少写几层。我一般不建议大作业这么做原因有三一是Cminus的文法定义本身就是分层写的用层叠文法可以直接对照课本推导二是%left虽然能消掉冲突但它掩盖了冲突产生的本质老师在答辩时问一句%left为什么能让冲突消失你很难用三句话讲清楚LALR的移进/归约决策三是层叠文法在bison的.output文件里每个状态都清清楚楚出问题更容易排查。3.2 Bison三区段结构定义区里先把token和类型声明齐Bison文件分成定义区、规则区、辅助函数区。定义区里要写%union、token声明、%type声明和优先级声明。%union决定了yylval的字段列表flex里写yylval.op、yylval.name都要在%union里找到对应成员。%{ #include stdio.h #include stdlib.h #include string.h #include ast.h extern int yylex(); extern int line; void yyerror(const char *s); ASTNode *root; /* 全局根节点解析完后从root遍历AST */ %} %union { int ival; float fval; char *name; int op; ASTNode *node; } %token ival NUM_INT %token fval NUM_FLOAT %token name ID %token op RELOP %token INT VOID FLOAT %token IF ELSE WHILE RETURN %token PLUS MINUS TIMES DIVIDE MOD %token LPAREN RPAREN LBRACKET RBRACKET LBRACE RBRACE %token SEMI COMMA ASSIGN %type node program declaration_list declaration var_declaration fun_declaration %type node params param_list param type_specifier %type node compound_stmt local_declarations statement_list statement %type node expression_stmt selection_stmt iteration_stmt return_stmt %type node expression var simple_expression additive_expression term factor %type node call args args_list %start program %%注意ival、name这些尖括号里的名字必须与%union里的成员一一对应。比如flex里对ID写了yylval.name strdup(yytext)这里就要求ID声明成%token name ID否则Bison生成的YYSTYPE里没有name字段编译直接在赋值处报错。RELOP用op保存具体是哪个关系运算符这样语法阶段只有一个RELOP token不需要为六个关系符每个单独建tokenAST里也能拿到比较符的类型。3.3 悬空else怎么在文法层面消除matched和unmatched两套statementCminus里的if语句是允许else缺省的这会直接导致经典的悬空else冲突。Bison默认在处理IF expr THEN stmt后面跟ELSE时可以选择把不完整的if归约掉也可以把ELSE移进来看成完整if的一部分这个shift/reduce冲突在bison -v里会明确报出来。最常见的解决方式是用两个非终结符把语句分成matched_statement和unmatched_statement这样文法层面就把“只有完整if-else才能作为if的then分支”这个约束写死了statement: matched_statement { $$ $1; } | unmatched_statement { $$ $1; } ; matched_statement: expression_stmt { $$ $1; } | compound_stmt { $$ $1; } | iteration_stmt { $$ $1; } | return_stmt { $$ $1; } | IF ( expression ) matched_statement ELSE matched_statement { $$ newIfNode($3, $5, $7, line); } ; unmatched_statement: IF ( expression ) statement { $$ newIfNode($3, $5, NULL, line); } | IF ( expression ) matched_statement ELSE unmatched_statement { $$ newIfNode($3, $5, $7, line); } ;这段文法能保证每个else绑定到最近的未匹配if。如果if (a) if (b) x1; else y2;else只能配给内层if因为作为外层if then分支的必须是一个matched_statement而内层if (b) x1;恰好无线else不是matched所以这条输入在文法层就要求内层if必须有else就自然绑定了。用这个方法后bison -v里的shift/reduce冲突数量会直接归零。有的写法会用%prec和虚拟token来压掉冲突比如给无else的if规则声明一个低优先级遇到ELSE时选择移进。这种写法代码更短但它没有把语义约束编码进文法里只是利用了优先级机制。大作业更推荐matched/unmatched写法可解释性完全是不同级别。3.4 表达式的三层塔additive、term、factor就不用%leftCminus的表达式按运算符优先级分成三个层级。每层内部是左递归层与层之间用下一个层级的非终结符连接expression: simple_expression { $$ $1; } | simple_expression RELOP simple_expression { $$ newBinNode($2, $1, $3, line); } ; simple_expression: additive_expression { $$ $1; } ; additive_expression: additive_expression PLUS term { $$ newBinNode(OP_PLUS, $1, $3, line); } | additive_expression MINUS term { $$ newBinNode(OP_MINUS, $1, $3, line); } | term { $$ $1; } ; term: term TIMES factor { $$ newBinNode(OP_TIMES, $1, $3, line); } | term DIVIDE factor { $$ newBinNode(OP_DIVIDE, $1, $3, line); } | term MOD factor { $$ newBinNode(OP_MOD, $1, $3, line); } | factor { $$ $1; } ; factor: LPAREN expression RPAREN { $$ $2; } | var { $$ $1; } | call { $$ $1; } | NUM_INT { $$ newIntNode($1, line); } | NUM_FLOAT { $$ newFloatNode($1, line); } ;这个文法里a b * c先归约b * c到term再参与additive_expression的归约所以乘除天然优先于加减。左递归在LR文法里完全没有问题LALR状态机能处理这种结构不需要像LL文法那样做左公因子提取。newBinNode的第一个参数是运算符种类对应%union里的op字段后面两个是左右子树这里直接把RELOP token里保存的具体运算符从$2传给AST节点。如果你偷懒想用%left写法是%left PLUS MINUS、%left TIMES DIVIDE这种声明然后在文法里让所有表达式都走同一个非终结符靠Bison的优先级决策来归约。这条路能少写不少规则但会牺牲掉对状态机行为的直观理解而且这道题既然叫“编译原理大作业”交一份层叠文法上去比交一份依赖工具特性的文法更稳。3.5 其余规则骨架和带行号的yyerrorprogram、declaration_list、compound_stmt这部分规则比较机械但同样要写。给一个可参考的最小骨架program: declaration_list { root $1; } ; declaration_list: declaration { $$ $1; } | declaration_list declaration { ASTNode *p $1; while (p-next) p p-next; p-next $2; $$ $1; } ; declaration: var_declaration { $$ $1; } | fun_declaration { $$ $1; } ; compound_stmt: LBRACE local_declarations statement_list RBRACE { ASTNode *p newNode(NODE_COMPOUND, line); p-kids[0] $2; p-kids[1] $3; $$ p; } ;函数声明、参数列表、return语句的写法思路一样每个非终结符在语义动作里返回一个AST节点用小规则拼大规则。注意Cminus里void只能作为函数返回类型不能用来声明变量这一条如果不处理后面语义分析阶段会出问题语法阶段可以先不管把type_specifier的节点信息保留下来即可。yyerror建议至少带上行号否则老师拿一个20行的测试文件问你第几行错了你根本答不上来void yyerror(const char *s) { fprintf(stderr, line %d: %s\n, line, s); }行号是flex里那个全局变量line维护的每次匹配到\n就加一。这里提醒一句文件里的换行如果是Windows的\r\n\r会被当成非法字符打印出来你需要先在flex里把\r也归入空白丢弃或者测试用例统一用LF换行。4. 把语法规则变成AST节点设计、语义动作和内存策略4.1 AST节点定义三个子节点加一个兄弟链就够用Bison的归约动作里每个$$最终都应该指向一个AST节点。Cminus的语言结构不复杂节点定义不用做成一堆子类一个结构体加一个kind枚举就够/* ast.h */ typedef enum { NODE_PROGRAM, NODE_VAR_DECL, NODE_FUN_DECL, NODE_PARAM, NODE_COMPOUND, NODE_IF, NODE_WHILE, NODE_RETURN, NODE_ASSIGN, NODE_BIN_EXPR, NODE_REL_EXPR, NODE_INT_CONST, NODE_FLOAT_CONST, NODE_ID, NODE_CALL } NodeKind; typedef struct ASTNode { NodeKind kind; int line; char *name; /* 标识符名字 */ int intVal; float floatVal; int op; /* 运算符或关系符 */ int arrayLen; /* 数组长度-1表示普通变量 */ struct ASTNode *kids[3]; /* 三个子节点 */ struct ASTNode *next; /* 兄弟链用于声明列表和参数列表 */ } ASTNode;三个子节点分别怎么用if节点存condition、then、elsewhile节点存condition、body第三个置NULL赋值节点存左值和右值二元运算节点存左右操作数第三个置NULL。next字段用于把所有变量声明串成链表这样declaration_list规则里就不用维护一个动态数组了。arrayLen字段默认赋成-1表示这是普通变量遇到int a[10]再赋成10。如果malloc后不清零直接给该字段赋值倒也能用但节点里其他没赋值的字段全是随机垃圾值后面遍历AST时一旦误读就会段错误。所以创建节点时统一用calloc所有字段初始为0或NULL再根据情况覆盖。4.2 节点创建函数怎么写从底层new到专门的if节点有了结构体下一步是提供一组创建接口语义动作里只调接口不直接操作结构体字段。下面是三个最常用的函数够你跑通整个Cminus/* ast.c */ #include ast.h #include stdlib.h #include string.h ASTNode *newNode(NodeKind kind, int line) { ASTNode *p (ASTNode *)calloc(1, sizeof(ASTNode)); p-kind kind; p-line line; p-arrayLen -1; /* 默认不是数组 */ return p; } ASTNode *newBinNode(int op, ASTNode *left, ASTNode *right, int line) { ASTNode *p newNode(NODE_BIN_EXPR, line); p-op op; p-kids[0] left; p-kids[1] right; return p; } ASTNode *newIfNode(ASTNode *cond, ASTNode *thenStmt, ASTNode *elseStmt, int line) { ASTNode *p newNode(NODE_IF, line); p-kids[0] cond; p-kids[1] thenStmt; p-kids[2] elseStmt; return p; }calloc在这里是很关键的选择。它把整个结构体清零kids数组是三个NULL指针next是NULL后续无论哪条遍历路径访问到未初始化的分支都不会立刻段错误最多是逻辑判空后跳过。malloc出来的节点不保证清零指针字段是野值一次误判就能让你的程序在老师演示时崩掉。4.3 三个值得抄的语义动作范式第一个范式是声明列表拼接。Cminus的declaration_list是左递归的每归约一次都要把前一个声明的next链到最后。上面3.5给出的动作就是标准写法从头节点遍历到链表尾再挂上新节点$$始终指向链表头。第二个范式是赋值语句。Cminus的文法里expression - var ASSIGN expression语义动作要把赋值操作建成一个NODE_ASSIGN节点expression: var ASSIGN expression { ASTNode *p newNode(NODE_ASSIGN, line); p-kids[0] $1; p-kids[1] $3; $$ p; } | simple_expression { $$ $1; } ;这里有个容易绕晕的细节赋值并不是statement级别的规则而是expression级别的规则。Cminus语言里a 1;是一个expression-stmt所以赋值符号只出现在expression的推导里。如果你把ASSIGN放在statement规则里整个文法结构就对不上原定义了。第三个范式是while循环iteration_stmt: WHILE ( expression ) statement { ASTNode *p newNode(NODE_WHILE, line); p-kids[0] $3; p-kids[1] $5; $$ p; } ;孩子节点位置越固定越好。统一约定kids[0]放条件、kids[1]放循环体后续遍历时只要check kind就知道怎么取。不要在同一个节点类型里换顺序那是给自己埋雷。4.4 千万别在语义动作里直接printf给AST一个独立的输出函数很多同学拿到Bison后第一反应是“在归约成功时printf一下”这种写法短期能让你看到输出但会带来三个问题第一语义动作里的printf时机跟随归约顺序而归约顺序和源码顺序并不完全一致导致打印顺序错乱第二一旦语法错误已经归约的部分打了没归约的部分没打出来的结果半残第三后续如果要做语义分析或中间代码生成你还需要这份结构信息printf出来的东西没有任何复用价值。正确的做法是解析阶段只建树等yyparse返回成功后单独做一个dumpAST函数遍历输出缩进用树的深度控制。这样输出顺序就是源码顺序行为可预测还能方便地和预期结果做diff。AST树上挂的line字段这时候就发挥作用了打印节点时把行号一起打出来排查测试用例的问题会非常直观。血泪经验是一定要先有独立的AST输出再开始调Bison规则。否则你根本分不清是文法写错了还是动作代码写错了。4.5 节点生命周期解析阶段不要free最后一次性释放AST节点的malloc时机在归约动作里但谁负责释放常见做法是解析阶段完全不释放整个AST挂在全局root上等后续语义分析或者中间代码生成用完以后再统一递归释放。递归释放接口长这样void freeAST(ASTNode *p) { if (!p) return; for (int i 0; i 3; i) { freeAST(p-kids[i]); } freeAST(p-next); if (p-name) free(p-name); free(p); }注意$$ $1这种直接把子节点传给父节点的写法节点地址没有复制所有权还是同一份递归释放时不会重复释放同一块内存。怕的是你中途对某个节点又malloc又free后面Bison进入归约时再访问它那就立刻段错误了。我的习惯是把分配和释放分别限定在“建树阶段”和“树用完阶段”中间绝不做局部释放。另外标识符名字的释放要记得和strdup配对。flex里用strdup保存IDAST里直接用这个指针所以freeAST里要free掉name字段否则valgrind会报一堆内存泄露这在部分学校的评分标准里是要扣分的。5. 大作业避坑五个Flex/Bison翻车现场和排查方法5.1 现象flex看起来没问题但一张嘴就是syntax error, unexpected ID症状是解析int main(void)这种最简单的程序都报错但token列表明明打印出INT、ID、LPAREN等。原因大概率是关键字规则和标识符规则顺序反了if、int这些单词被当成了ID。flex在相同匹配长度时优先选靠前的规则如果ID规则写在关键字规则前面所有关键字都会变成IDBison找不到INT token自然报syntax error。解决方法是把关键字规则全部移到标识符规则之前然后重新编译。还有一个细节是Bison生成的token编号每次可能变化如果bison重跑过却没重新编译lex.yy.ctoken编号对不上也会出现类似症状解决办法见5.5。5.2 现象bison -v显示几十个shift/reduce conflict运行起来时好时坏如果冲突数量集中在几行先别急着找神奇写法消除要看具体冲突在哪。用bison -v -d cminus.y生成cminus.output在文件里搜conflict关键字每条冲突都会标出状态编号和涉及的token。看到IF、ELSE字样的冲突就是悬空else用matched_statement/unmatched_statement那套改写看到PLUS、TIMES通常是表达式没有分层检查是不是少了additive_expression到term的传递。bison -v -d cminus.y grep -n conflict cminus.output | head -20如果只是几个shift/reduce冲突Bison也能生成可用的parser因为它默认会选择移进但大作业答辩时老师看到warning都会追一句建议花时间清零。真正危险的是reduce/reduce冲突出现这个说明你的文法有两条规则能同时归约同一个东西必须改文法不能靠默认策略糊弄。5.3 现象AST里所有标识符名字都变成同一个了写一段包含a 1; b 2;的程序建出来的AST里两个变量节点名字都叫b。这是Flex缓冲区生命周期的经典问题。yytext指向flex内部的一个静态缓冲区每次调用yylex都可能被覆盖如果你的flex规则里写的是yylval.name yytextBison在移进下一个token后之前的name就变成新内容了。解决方法是规则里用strdup复制一份[A-Za-z][A-Za-z0-9_]* { yylval.name strdup(yytext); return ID; }这相当于给每个标识符名上了份后悔药。注意strdup返回的指针需要对应free否则valgrind会报内存泄露。如果用不了strdup自己写个循环复制也行核心原则就是一个字必须拷贝。5.4 现象数组声明的arrayLen字段是0或者随机值Cminus支持int a[10];我在AST节点里放了arrayLen字段。翻车点通常出在两条声明规则没有区分开。如果你把普通变量声明和数组声明写进同一条规则只访问$3而$3在第一种情况下是SEMI、不是NUM_INT取出来的值自然不对。需要在文法里明确分开var_declaration: type_specifier ID SEMI { ASTNode *p newNode(NODE_VAR_DECL, line); p-name $2; p-arrayLen -1; /* 普通变量 */ $$ p; } | type_specifier ID LBRACKET NUM_INT RBRACKET SEMI { ASTNode *p newNode(NODE_VAR_DECL, line); p-name $2; p-arrayLen $4; /* 数组长度来自NUM_INT的ival值 */ $$ p; } ;另一个隐蔽问题是malloc内存没清零就使用arrayLen。用calloc创建节点后初始值是0不会出现随机值如果你用malloc这个字段的初值完全取决于堆上残留数据看起来像玄学问题。检查代码时先确认节点创建用的是calloc。5.5 现象新增一个运算符后原来能跑的程序开始段错误给语言加或者之类的运算符改完flex规则重新编译后parser在运行时报段错误。常见原因有三个一是新token加进了.l文件但.y文件的%token声明没加token编号错位二是只重新编译了lex.yy.c没重新编译cminus.tab.c两个编译单元里YYSTYPE布局不一致三是新token在%union里没有对应字段语义动作里又去访问了不存在的yylval成员。解决要点是把头文件依赖写清楚。Makefile里把cminus.tab.h作为lex.yy.c的前置依赖每次.y改动后bison重新生成.tab.c和.tab.hflex和gcc都必须重新跑而不能只重编一半。推荐依赖写进Makefilecminus.tab.c cminus.tab.h: cminus.y bison -d cminus.y lex.yy.c: cminus.l cminus.tab.h flex cminus.l cminus: lex.yy.c cminus.tab.c ast.c gcc -g -o cminus lex.yy.c cminus.tab.c ast.c这样每次修改.y后面所有依赖都会级联重编不会出现新旧头文件混用的问题。我见过的大作业段错误里至少三分之一是增量编译没写对造成的属于最没有技术含量但最要命的坑。加运算符还有一个细节flex规则匹配最长字符串和如果都写了规则会被完整匹配这没问题但如果你只写了输入会被切成两个Bison立刻报错。新加的每一个双字符运算符都要确认有对应的完整正则别只写一个字符的规则。6. 答辩前的最后一道工序自动回归测试与冲突状态检查6.1 用diff替你做回归测试大作业临近交付时最怕改一处文法影响十处旧用例。写一个简单脚本把测试用例跑一遍并与期望输出difffor f in tests/*.cm; do ./cminus $f out/$(basename $f).txt 21 if diff -q expected/$(basename $f).txt out/$(basename $f).txt /dev/null; then echo PASS $f else echo FAIL $f fi done测试用例至少覆盖变量声明、数组声明、函数定义、嵌套if-else、while循环、多参数调用、表达式优先级、语法错误程序报错。合法程序的期望输出用dumpAST的结果固定下来非法程序只比较是否报错不必逐字匹配错误信息。6.2 把Bison当黑匣子用不是好习惯开yydebug看决策过程遇到文法冲突或者归约顺序不对时打开调试输出能看到每一个token的移进和归约int main(int argc, char **argv) { yydebug 1; /* 也可在编译时加-DYYDEBUG */ /* ... */ }打开后输出里会出现Reading a token、Shifting token、Reducing stack by rule这类日志。配合5.2生成的cminus.output状态表对照着自己写的规则逐行看一般都能找到是哪一步归约走错了方向。6.3 AST不只为交差它是语义分析和中间代码生成的前置底牌如果你的大作业还要求类型检查、符号表甚至生成中间代码这份AST直接就能作为入口。var_declaration节点里的arrayLen、name和line足够支撑符号表的插入与重复声明检查bin_expr节点里的op、kids[0]、kids[1]可以直接生成四元式。Cminus没有指针没有struct也没有for循环语言子集小而完整正好适合把前端整条链路走通。最后说一个我的习惯答辩前一定会把cminus.output里的conflict列表清零再跑一遍全部用例然后打开yydebug过两个最复杂的测试文件。编译大作业翻车最多次的地方往往不是文法本身而是工具链的依赖没对齐。希望帮到你。本文还有配套的精品资源点击获取
)
