最近把C-Minus的语义分析完整跑通了工具链还是那套经典组合Flex负责词法Bison负责语法中间穿插手写的AST和符号表最后在语义分析阶段把所有类型规则、作用域规则、函数调用规则逐条检查过去。这个项目是很多编译原理课程都会布置的前端作业难度说大不大但真正动手做才会发现词法和语法只是开胃菜语义分析才是决定整个编译器像不像话的关键一环。这篇文章不打算从教科书定义讲起就按我实际做项目时的顺序来先厘清C-Minus这个语言盘子有多大再逐步搭出Flex/Bison前端然后重点展开符号表与类型检查的实现最后把错误恢复、调试技巧和验收前要避的坑一并列出来。无论你是刚开始写编译器还是在调自己的作业这应该都能帮上忙。1. 为什么拿C-Minus练手语言越小语义规则越藏不住1.1 C-Minus的本体麻雀虽小五脏俱全C-Minus是教材里专门为教学裁剪出的一门类C语言它砍掉了struct、指针、枚举、逻辑运算符这些复杂特性只留下int和void两种类型、算术运算符、比较运算符、if/while控制流、函数定义/调用、数组和注释。词法上只有五种基础符号类别关键字、标识符、数字、运算符/分隔符、注释。可恰恰因为语言小语义分析阶段反而更明显。类型系统只有int和void两条支线但变量的声明、函数形参、数组维度、函数返回类型、实参形参匹配这些规则一个都不少。做的时候我最大的体会是在大语言里你可能被细枝末节淹没而在C-Minus里每一条语义规则都会清清楚楚地暴露在检查代码里藏都藏不住。这非常适合练基本功。1.2 语义分析在整个前端中到底在分析什么编译前端可以拆成三个阶段词法分析把源码切成token流语法分析把token流组织成语法树语义分析则是在语法树之下挑毛病——检查类型是否匹配、变量是否有声明、作用域是否合法、函数调用参数是否正确。Flex和Bison的本职工作其实只覆盖前两个阶段。语义分析通常是在Bison的动作代码里构建AST之后单独写一个semantic分析器对AST做遍历。我做的时候把语义分析拆成两件事符号表的建立与维护声明信息记下来作用域进出管理好。类型与正确性检查每个表达式推导类型每种语句验证约束。这两件事之间是有先后顺序的。先做符号表让每个用名的地方能找到对应的声明再做类型检查否则遇到未声明的变量只会报出一堆无意义错误。1.3 我的项目目标定义动手之前我给自己定了一个可验收的目标输入一段合法的C-Minus程序输出一棵完整的AST语义分析通过无报错。输入一段含语义错误的程序能给出格式规范、行号精确、可读性强的错误提示。单个源文件中允许出现多个语义错误分析器不能停在第一个错误上。词的、语法层面的错误也要统一走同一套报告体系方便后续做测试脚本。这个目标看着简单实际做下来最花时间的反而是错误恢复和边角情况。后面单独开一章讲。2. 先把前端骨架搭完整Flex词法、Bison语法与AST构建2.1 Flex词法规则保留字的顺序最容易翻车词法部分我用Flex写文件通常叫lex.l。C-Minus的token类别不算多但有一个特别容易踩的坑*保留字模式必须放在标识符模式之前。*Flex匹配正则时按规则出现的先后顺序尝试如果不把if、else、int、return这些关键字规则写在前面它们就会全部被ID的规则吃掉变成普通标识符后面语法分析直接乱掉。我当时写的核心规则大致长这样%{ #include parser.h %} %% else { return ELSE; } if { return IF; } int { return INT; } return { return RETURN; } void { return VOID; } while { return WHILE; } [0-9] { yylval.num atoi(yytext); return NUM; } [a-zA-Z][a-zA-Z0-9_]* { yylval.name strdup(yytext); return ID; } |||!| ... { /* 多字符运算符要在单字符之前 */ } |-|*|/||||(|)|[|]|{|}|;|, { return *yytext; } /* { comment(); } [ \t\n] { /* 跳过空白 */ } . %%几个细节值得说明多字符运算符、、、!的正则必须写在单字符运算符之前否则会被拆成和。数字和标识符的边界我用了[a-zA-Z][a-zA-Z0-9_]而不是[a-zA-Z_][a-zA-Z0-9_]因为C-Minus官方定义里标识符是字母开头我干脆去掉下划线开头避免和C语言习惯混在一起。注释用状态或递归方式处理我写了一个comment()函数支持嵌套注释是不可能的C-Minus里注释不嵌套所以一个状态机足够。遇到非法字符比如、#这些token之外的东西必须报词法错误并跳过不能让Flex默认ECHO。2.2 Bison文法优先级、悬空else和AST节点挂载语法分析用Bison文件叫parser.y。C-Minus的文法本身是LALR(1)的但有两个点需要额外处理。第一个是算数运算符优先级。文法里虽然可以直接写additive-expression、term这样一层套一层的产生式但我在实际写的时候仍然习惯用Bison的优先级声明来辅助因为这样能让动作代码更集中。操作符声明大致是%left PLUS MINUS %left TIMES OVER %right ASSIGN不过更稳妥的做法是严格按照递归层次写加法/项/因子优先级完全靠文法结构控制。这样出来的AST更规整也不依赖Bison的优先级解析细节。我当时是两层都试过最后提交的版本用的是纯文法层次因为可读性强后续找bug也容易。第二个是悬空else。if语句的经典冲突if (expr) statementif (expr) statement else statementBison默认shift优先正好能把else匹配给最近的if符合C语言语义。所以这个shift/reduce冲突可以直接用%expect 1通过不需要改文法。这里必须清楚自己在做什么而不是无脑把警告消掉。AST节点挂载是语法阶段最重要的活。每条产生式的动作里创建对应节点子节点拼进来。我用一段统一的结构体来组织typedef enum { Node_Program, Node_DeclList, Node_VarDecl, Node_FunDecl, Node_Param, Node_Compound, Node_Select, Node_Iter, Node_Return, Node_Assign, Node_Op, Node_Rel, Node_Call, Node_Index, Node_ArrayDecl, ... } NodeKind; typedef struct ASTNode { NodeKind kind; int type; // 语义分析阶段填充 int line, col; struct ASTNode *child[4]; // 子节点指针具体含义随kind变化 int num; // NUM叶子值 char *name; // ID字符串 } ASTNode;Bison动作里做的是建节点、拼孩子这件事。比如factor到callcall: ID ( args ) { $$ make_node(Node_Call); $$-name $1; // 函数名 $$-child[0] $3; // 参数列表 };语法分析结束根节点就是Program。到了这一步前面的工作产物是一棵完整AST而语义分析器就可以在这棵树上做文章了。2.3 我为什么坚持要拿到完整AST再做语义有不少实现把语义检查直接塞进Bison动作里边reduce边查符号表。这个做法对小项目能跑但扩展性很差同一段代码即要做语法归约又要做类型检查动作函数会无限膨胀而且错误恢复特别难控制。我坚持先建AST再单独做语义分析理由有三点检查逻辑集中在semantic.c里每个节点对应一个visit函数代码量虽然大但非常清晰。语义错误可能需要来回看子树信息比如检查return时要知道当前函数的返回类型这需要一个全局上下文单独遍历比在reduce过程中维护上下文简单得多。后续要扩展中间代码生成、目标代码生成时AST是现成入口Bison动作不需要再动。代价是多写一遍AST遍历代码但这个时间花得非常值。3. 语义分析的核心实现符号表、作用域栈和类型检查3.1 符号表的数据结构与作用域管理C-Minus的作用域只有全局区、函数体、复合语句里的局部声明这几层。我用的方案是作用域栈加哈希表每个作用域是一个ScopeEntry结构里面放一个哈希表存name到Symbol的映射。全局一个栈进入复合语句压栈离开时弹栈。符号查找从栈顶往下逐层找和C语言的标准屏蔽规则一致。结构体大致这样typedef struct Symbol { char *name; SymbolKind kind; // VAR, ARRAY, FUNC, PARAM Type type; // INT, VOID, FUNCTION_INT, FUNCTION_VOID int arrSize; // 数组声明维度 int paramCount; // 函数形参个数 Type *paramTypes; // 函数形参类型数组 int defined; // 是否已有定义 int line, col; struct Symbol *next; } Symbol; typedef struct Scope { Symbol *buckets[64]; struct Scope *parent; } Scope; typedef struct SymTable { Scope *top; int globalScopeLevel; } SymTable;插入和查找都写成一个通用函数。函数名和普通变量在同一个符号表里这样能天然覆盖函数名和变量名冲突这条规则。参数处理在函数声明时开一个新的子作用域还是并入函数体复合语句作用域我的做法是形参直接挂进函数体复合语句的最内层作用域这样函数体内引用形参时查找路径和局部变量完全一致。3.2 C-Minus语义规则检查清单与实现顺序C-Minus的语义规则主要包含下面这些我在实现时把它当成一个清单逐条过类别规则内容报错示例声明同一作用域内不允许重复声明同名变量/函数/参数Duplicate declaration: foo声明void类型不能用于变量声明只能用于函数返回值或空参数列表Variable declared void声明数组维度必须是正整数常量Array size must be a positive integer引用所有标识符在使用前必须已被声明Undefined variable: x函数函数不允许嵌套定义Nested function declaration表达式算术运算符的操作数必须为intInvalid operand type for 表达式比较运算符的操作数必须为intInvalid operand type for 表达式if/while的条件表达式必须为intNon-int condition in if赋值赋值左值必须是变量或数组元素不能是函数名或数组名Invalid assignment target赋值赋值左右操作数必须都是intType mismatch in assignment数组数组下标表达式必须为intNon-int array index调用实参个数必须等于形参个数Function call argument count mismatch调用实参类型必须与形参类型匹配Function call argument type mismatch返回void函数不允许返回带值表达式Void function should not return a value返回int函数返回表达式必须为intReturn type mismatch这里值得多说一句的是数组的处理。C-Minus里数组有两种形态声明是int a[10]或形参int a[]形参数组没有维度。使用上a[expr]是int类型的左值而单独的a是int[]类型不能参与算术运算、不能作为赋值左值、也不能作为普通实参传值——它只能传给形参也是数组的对应位置。这个区分是初学者最容易漏的。3.3 表达式类型推导与检查的代码组织语义分析器我按AST节点类型拆成一组visit函数核心思路是每个表达式节点返回一个Type上层节点拿到子节点的类型后做规则判定。伪代码大致是Type checkExpr(ASTNode *node, SymTable *tbl, FunContext *ctx) { switch (node-kind) { case Node_Op: leftType checkExpr(node-child[0], tbl, ctx); rightType checkExpr(node-child[1], tbl, ctx); if (leftType ! INT || rightType ! INT) { error(node, Invalid operand type for arithmetic operator); return INT; // 错误恢复时给个默认类型 } return INT; case Node_Assign: leftType checkExpr(node-child[0], tbl, ctx); rightType checkExpr(node-child[1], tbl, ctx); if (!isLValue(node-child[0])) error(node, Invalid assignment target); if (leftType ! rightType) error(node, Type mismatch in assignment); return INT; case Node_Call: // 查函数符号逐个参数检查 ... return funcReturnType; case Node_ID: sym lookup(tbl, node-name); if (!sym) { error(node, Undefined variable: %s, node-name); return INT; } return sym-type; case Node_Index: baseType checkExpr(node-child[0], tbl, ctx); // 数组名 idxType checkExpr(node-child[1], tbl, ctx); // 数组名作为索引对象必须是数组符号 return INT; } }有了表达式类型推导这条主线语句级检查就简单了。compound/function声明先插入符号再递归检查子节点if和while检查条件类型return检查当前函数上下文定义的返回类型。整个语义分析要注意的一点是符号插入的时机。我在遍历var-declaration节点时插入当前作用域遍历fun-declaration节点时先处理形参和局部声明再检查函数体语句。这样一条路径走完符号表的声明顺序和程序源码顺序保持一致作用域嵌套也不会乱。4. 错误报告与恢复别让一个错误挡住后面一串检查4.1 三类错误的统一报告格式词法错误、语法错误、语义错误最终都应该统一成同一种格式吐给用户方便写测试脚本做比对。我用的是行号列号错误等级描述的四段式error: %d:%d: %s比如test.c:3:12: error: Undefined variable: count为了拿到列号我在Flex里维护一个全局column计数每次匹配token前记录当前列位置匹配后再根据匹配文本长度累加。行号则用Flex自动维护的yylineno。词法阶段的非法字符错误Bison阶段的语法错误语义分析阶段的手动错误报告全部走同一个error()函数这样看起来非常专业。4.2 语法错误恢复yyerror之外的兜底Bison默认遇到语法错误直接调用yyerror然后返回整个解析就挂了。这样测试脚本没法在一个文件里覆盖多个错误用例。我的做法是给文法加error token让解析器在关键位置做同步恢复。经验是下面这几处加error恢复最有效statement层statement → error ; | error }。遇到语句错误时跳过直到分号或右花括号。expression层expression → error。遇到表达式错误时跳过当前表达式。declaration层declaration → error ;。加了error产生式之后大部分错误都能报出一条消息然后继续解析。不过要小心错误恢复位置选不好会连报几十条噪音。我调了好久才找到一个合适策略只在statement和declaration两个层级做error不往下层扩展因为下层错误往往是上层的连带反应。语义分析出错不涉及恢复因为AST已经完整了。但要注意语法错误之后可能AST并不完整语义分析器必须对空指针做防御性检查。我在AST遍历函数开头统一加了if (!node) return避免因为语法恢复导致空树崩掉。4.3 语义错误收集错误恢复的另一种形态语义分析时遇到错误要不要停下来我的选择是记录错误但不中断遍历。做法是全局维护一个errorCount和错误列表。每个规则检查失败时调用logError()然后把节点类型设成一个默认安全类型通常是INT让上层节点继续检查。遍历结束后返回是否有错由主函数决定退出码。这样做的效果是一个程序里同时存在未声明变量、参数个数不匹配、返回值类型错误时检查器能一口气把所有问题都列出来而不是让用户改一次跑一次。这个体验对项目验收非常加分。5. 测试用例设计与验收前的避坑清单5.1 按语义规则表设计的测试用例我把15条语义规则分别映射成独立测试用例另外再写几个所有规则都合法的正例。测试脚本就是一组.cmin文件加一个shell脚本逐个跑完比对返回码和error输出。测试文件覆盖内容期望结果ok_all.cmin全局变量、数组、函数定义、函数调用、if/else、while、复合语句里的局部声明无错误undecl_var.cmin使用未声明的变量1个未定义错误dup_var.cmin同一作用域重复声明变量重复声明错误arr_dim.cmin数组维度写成负数或变量维度非法错误bad_assign.cmin对函数名赋值、对数组名赋值非法左值错误call_count.cmin实参数与形参不符参数个数错误call_type.cmin实参类型不匹配参数类型错误void_return.cminvoid函数返回表达式返回值错误int_return.cminint函数返回值类型不是int返回类型错误if_cond.cminif条件出现函数调用或数组名条件非int错误这些用例我每个都单独跑确认错误数量和行号完全稳定。另外还写了一个连环错误的测试文件故意在一段代码里埋好几类错误验证收集机制生效。5.2 调试技巧AST打印、yydebug和Valgrind前端项目调试比普通应用要费心因为错误可能发生在三个不同阶段。我发现几个非常好用的办法第一个是AST打印函数。我写了一个dumpAST()按缩进层级打印每个节点的kind、name、num、line。词法、语法一旦不通先看AST长什么样。很多类型检查问题根源不是检查代码逻辑而是AST结构和我想的不一样。第二个是Bison的调试输出。编译时用bison -t加上运行时yyset_debug(1)可以看到整个shift/reduce过程。这个工具在排查什么语法树规则没触发时特别高效。第三个是Valgrind检查内存。我的AST节点和符号表都来自动态内存分配不加检查根本不知道哪里漏了free。虽然课程项目不太会卡内存泄漏但valgrind能顺带暴露很多数组越界的低级bug比如列号计算差一位导致读取越界。5.3 验收前最容易露馅的几个点最后列几个验收现场最容易露馅的细节全部是我自己或者同学实际踩过注释没有正确处理EOF。代码文件末尾如果注释没闭合Flex会一直进状态回不来。验收时一定要测未闭合注释这类输入。数字溢出。atoi把超大数字变成负数但我没做范围检查导致数组维度报错信息很诡异。课程范围内建议补一个溢出提示。else匹配错误。悬空else用%expect 1压掉了但语义分析阶段没有做控制流匹配校验极少数变态测试会给出一堆花括号错乱的代码语法层可能直接恢复失败。不过这种输入已经超出C-Minus验收范围遇到最多算是语法错误不用过度焦虑。空声明列表。C-Minus标准文法里declaration-list至少有一条声明但有些测试会给空文件。我在program节点做了特判避免语法树根节点为空导致语义遍历崩溃。函数调用与数组名混淆。int f(int a[]); 里a在函数体内是可以直接使用的形参数组但数组形参在符号表里是ARRAY且未指定维度不能参与算术运算但可以作为索引基址。这个细节检查漏了就会把合法程序误判为非法。另外还有一个小但常见的坑Flex里匹配完关键字之后要return对应的token但如果yylex()丢失了某些分支的returnBison会把token当0处理导致整个解析过程错乱。我只在写完后把所有分支都检查了一遍然后给yylex函数在文件末尾加了一个默认返回非法token的安全出口。从我的实际体验来看语义分析这部分想做得扎实核心不是代码量而是对规则的拆解是否足够细。先用纸把C-Minus的每一条语义规则写清楚再去设计符号表和visit函数比一边写一边想规则要快得多。调试的时候把错误信息当作第一优先解决的问题行号和列号一旦准了后面所有测试都比对都顺。这个项目做完之后如果要继续扩展我建议下一步可以做中间代码生成——比如把AST翻译成三地址码同一套AST遍历框架直接复用只是在visit函数里增加生成指令的逻辑。符号表的结构也不需要大改给Symbol加上对应的临时变量编号字段就行。语义分析这一步走得稳后面整个编译器都会舒服很多。
