简介面向学习编译原理、需要完成词法分析与语法分析实验的高校学生这套电子科技大学编译原理实验代码提供了可供对照的完整实现。压缩包共21个文件、约203KB主要由5个cpp与4个h源文件构成覆盖输入处理、词法分析、语法分析等模块并配有pas测试源文件、vcxproj与sln工程文件、exe可执行程序及docx运行说明便于在Visual Studio环境中打开、编译和验证。已有2139人学习下载说明其在课程实验场景中具有较高参考价值。读者可从中梳理词法单元识别、token流生成、抽象语法树构建与解析策略的实现脉络也可借助运行说明和可执行程序复现实验结果理解编译器前端各模块的协作方式为课程实验、代码调试和后续语义分析学习提供较扎实的参考。1. 编译原理实验代码一份能一路跑通到目标代码的课程工程很多人对编译原理实验的印象是“四个割裂的小程序”词法一个、语法一个、语义一个、中间代码一个各交各的最后谁也没连起来。这套课程实验代码从一开始就按“一整条流水线”来组织源文件进去Token 序列出来语法树、符号表、四元式一路往下传最后能吐出可执行的结果。它适合正在上编译原理课、被实验报告逼着改代码的同学也适合工作几年后想回头把前端那几个经典算法补扎实的开发者。整套代码量不大但每一层的输入输出约定都写死了改起来有章可循不会一动手就雪崩。2. 工程结构与运行链路五个实验如何拼成一整台编译器2.1 目录分层与模块边界这套代码的第一眼观感是“分层很硬”。作者没有把所有东西塞进一个 main.cpp而是按编译阶段切目录每个阶段只暴露一个头文件给下游。这种切法在课程实验里不算新鲜但它解决了一个很实际的问题实验是分批布置的第三周交词法、第五周交语法如果接口一开始没定死后面每加一层就得回头改前面。目录大致是这样组织的路径职责对外暴露include/token.hToken 定义、关键字表Token结构、TokKind枚举src/lexer/字符流 → Token 序列Lexer::scanAll()src/parser/Token 序列 → 语法树Parser::parseProgram()src/ast/语法树节点定义与打印AstNode及其派生类src/semantic/符号表、类型检查SemanticAnalyzer::run()src/ir/四元式生成、回填QuadEmittersrc/codegen/四元式 → 目标指令CodeGen::emit()tests/词法/语法/语义用例每个阶段独立可跑Makefile分阶段构建目标make lex、make parse等我比较认可这个拆法的地方在于tests/是按阶段独立的。词法阶段你不需要等语法分析器写好make lex就能把.c源文件跑成 Token 列表打印出来。对课程实验来说这种“每一层都能单独验证”的结构比任何架构图都实在——出问题的时候你能立刻定位到是哪一层崩的。需要留意的是include/里只有token.h和ast.h是有实际内容的公共头其余模块之间靠前向声明加返回指针来耦合。这在课程规模下没问题但如果你打算往里加功能比如加个词法错误恢复就得注意别在头文件里塞太多实现细节否则改一处全量重编等编译的时间比调试的时间还长。2.2 数据结构主线Token → AST → 符号表 → 四元式整条链路能串起来靠的是四个核心数据结构。它们不是随便定的每一个的形状都决定了下一层好不好写。第一层是Token。它必须带行号否则报错时你只能告诉用户“有语法错误”说不清在哪一行这是血泪经验。第二层是语法树节点用基类加派生类的多态结构或者更省事的 tagged union课程实验里前者更直观。第三层是符号表本质是作用域栈 哈希表。第四层是四元式(op, arg1, arg2, result)四元组控制流的跳转目标先留空后面回填。它们之间的契约很关键词法分析器不关心语法只保证每个 Token 的lexeme和kind正确语法分析器不查语义看到未声明的标识符也照样建节点语义分析器不改语法树只填符号表上的类型信息并对不合法处报错。这条边界守住了每一层都能用固定的一组测试用例回归改上层不会把下层带崩。我在别的项目里见过反例语法分析阶段顺手做了“变量未声明”的检查。结果是只要文法改一个产生式语义检查就得跟着重写。分层这件事课程代码里看着像形式主义实际上是给你自己留后悔药。2.3 构建与跑通三条命令验证整条流水线环境要求不高g 支持 C17 即可Makefile 里没引第三方库。第一次跑建议按阶段来别一上来就make all。# 1) 只跑词法确认 Token 流正确 make lex SRCtests/input/expr.c # 2) 跑语法打印带缩进的语法树 make parse SRCtests/input/expr.c # 3) 全流程语义 四元式 目标代码 make run SRCtests/input/expr.cSRC这个变量是传给编译产物的入参不是 Makefile 里的固定路径所以你可以直接拿自己的测试源文件来喂。第二步打印出的语法树是缩进格式的缩进层级就是子树深度肉眼扫一遍基本能看出优先级有没有结合错——比如a b * c如果*没挂在的右子节点下面那你的表达式文法八成写成了左递归没消干净。第三步的产物分两段打印先是四元式列表每个四元式带序号然后是目标指令序列。四元式那一段建议每次改完代码都存一份基线因为回填逻辑最容易出错而错误往往表现为“跳转目标指向了一个已经被覆盖掉的序号”光看最终结果不容易发现。提示如果你的环境里make版本较老SRC这种传参方式仍然可用但要注意 Makefile 里对空值做了默认处理不传会退回内置的示例文件别以为是自己代码没执行。3. 词法与语法分析模块拆解从字符流到语法树3.1 词法分析器手写扫描器 状态转移表词法部分给了两套实现一套是纯手写的switch扫描一套是表驱动。手写那套读起来快但状态一多就成一锅粥表驱动那套前期填表烦后面加关键字、加运算符几乎不用改逻辑。课程实验里我更推荐表驱动那套因为它的错误定位天然比手写版清楚。Token 的定义是所有下游的地基长这样// include/token.h enum class TokKind { Id, Num, Keyword, Op, Delim, End, Error }; struct Token { TokKind kind; std::string lexeme; // 原始字面量报错时原样回显 int line 0; // 行号缺了它报错就是耍流氓 int value 0; // 仅 Num 有效提前算好省得下游再转 };value这个字段是给常量折叠留的数字字面量在扫描阶段就转成整数语义分析阶段做2 * 3折叠时就不用再碰字符串。line必须在扫描时维护不要想着“语法分析时再数”因为注释和空白在词法阶段就被吃掉了下游根本数不准。状态转移表的核心是一个二维数组加一个驱动循环// src/lexer/table_lexer.cpp节选 // 状态0START 1ID 2NUM 3OP 4DONE 5ERR static const int kTrans[6][128] { /* START */ {a...z}: 见下方说明, // ... }; Token Lexer::next() { int state 0; std::string buf; while (state ! 4 state ! 5) { char c peek(); if (c \0) { state 4; break; } // 文件尾直接收 if (c \n) { line_; } // 行号在任何状态下都要维护 state kTrans[state][(unsigned char)c]; if (state ! 0 state ! 4) buf.push_back(c); advance(); } if (state 5) return {TokKind::Error, buf, line_}; return classify(buf); // 查关键字表是关键字就改 kind }表的内容这里没法完整贴6×128 太大但思路很明确行下标是当前状态列下标是输入字符的 ASCII 码值是下一个状态。填表时把[ID][a-z] ID、[ID][0-9] ID、[START][0-9] NUM这些规则逐条写进去比写一长串if-else好维护得多加个运算符只需要改两三个格子。classify那一步是查关键字表unordered_mapstring, TokKindif、while、int都在里面。放在最后查而不是在状态机里判断是因为标识符和关键字的字符构成完全一样扫描阶段分不开只能在拿到完整 lexeme 之后补一刀。状态机里有个容易忽略的点行号维护必须放在状态转移之前且对所有字符生效。我见过有实现只在START状态下数换行结果一行中断在字符串里的转义换行就丢了报错行号整体偏移一截查起来极其难受。3.2 语法分析递归下降打底LL(1) 表做对照语法部分的主实现是递归下降另外附了一份 LL(1) 预测分析表的构造代码用来对照验证 FIRST/FOLLOW 集算得对不对。递归下降的好处是可读性接近文法本身一个产生式对应一个函数坏处是左递归必须手工消掉而且回溯控制全靠人肉。表达式那段的写法是这样的// src/parser/expr.cpp节选 // 已消除左递归expr - term { (|-) term } AstNode* Parser::parseExpr() { AstNode* left parseTerm(); // 先啃掉一个 term while (cur_.kind TokKind::Op (cur_.lexeme || cur_.lexeme -)) { std::string op cur_.lexeme; advance(); // 吃掉运算符 AstNode* right parseTerm(); left makeBinary(op, left, right); // 左结合新节点挂在上层 } return left; }这段代码对应的是消完左递归的文法所以用while循环来吸收同级运算符天然保证了左结合。如果你把它写成递归调用parseExpr()就会变成右结合a - b - c算出来是a - (b - c)结果错得悄无声息——这正是语法树阶段最容易翻的车后面第 5 章会细说。parseTerm()内部再处理*/和括号、一元负号层级自下而上优先级递增。整个递归下降解析器的函数调用栈深度就等于你当前解析位置的优先级层级调试的时候看栈帧一眼就知道卡在哪一层。LL(1) 那份表驱动实现主要干两件事算 FIRST 集、算 FOLLOW 集、填预测分析表、用显式栈模拟递归。它的价值在于交叉验证——同一个输入递归下降和表驱动应该产出结构完全一致的语法树。我一般会把两边的树都打印出来 diff 一遍能提前抓出不少文法写错的地方比如某个产生式的 FOLLOW 集漏了)表驱动那边就会在选择时卡死而递归下降可能靠运气混过去。3.3 语法树节点设计与打印AST 节点用的是基类 派生类// include/ast.h节选 struct AstNode { int line 0; virtual ~AstNode() default; virtual void dump(int depth) const 0; // 缩进打印调试主力 }; struct BinaryExpr : AstNode { std::string op; AstNode* lhs; AstNode* rhs; void dump(int d) const override { std::cout std::string(d * 2, ) Binary( op )\n; lhs-dump(d 1); rhs-dump(d 1); } };dump(int depth)这个纯虚函数是整个调试流程里性价比最高的东西。带缩进的先序遍历输出能让语法树的形状直接可视化你不用画图就能看出哪个节点挂错了位置。每个节点都带line是为了在语义分析报“变量重复定义”时能指回源码行。节点里不放父指针是我个人的取舍课程实验里不需要向上遍历加了父指针反而要处处维护容易忘。如果你后面要做代码优化需要向上查找再补也来得及。4. 语义分析与中间代码生成符号表、类型检查与四元式4.1 符号表作用域栈 哈希表的组合符号表是这一层最容易写歪的地方。很多人图省事用一个全局map结果一进函数体就发现同名变量没法区分只能靠改名硬凑。正确做法是作用域链一个vector当栈每个元素是一层作用域的哈希表。// src/semantic/symbol_table.h节选 struct Symbol { std::string name; Type type; // int / float / 函数签名等 int scopeLevel; // 层次用于报错时说明在第几层重定义 int offset; // 栈帧偏移目标代码生成时才用得上 }; class SymbolTable { public: void enterScope() { scopes_.emplace_back(); } // 进 { 时调用 void leaveScope() { scopes_.pop_back(); } // 出 } 时调用 bool insert(const Symbol s) { auto top scopes_.back(); if (top.count(s.name)) return false; // 同层重定义 top.emplace(s.name, s); return true; } Symbol* lookup(const std::string name) { for (auto it scopes_.rbegin(); it ! scopes_.rend(); it) { auto f it-find(name); if (f ! it-end()) return f-second; // 由内向外找 } return nullptr; // 未声明 } private: std::vectorstd::unordered_mapstd::string, Symbol scopes_; };insert只在最内层查重、不往外查这是刻意的内层遮蔽外层是合法行为比如函数参数和全局变量同名报错反而是错的。lookup从rbegin往外走保证先命中最近的声明。这两个函数的行为差异是语义分析里“同名”和“重定义”两个概念的分界线。offset字段在语义阶段只是预留等目标代码生成时按变量声明顺序累加算出栈帧布局。课程实验里变量类型有限直接按 4 字节对齐就够。4.2 语义检查的遍历顺序先声明后使用语义分析的遍历顺序不是随便定的必须是“先扫声明、再扫使用”。函数体内可能出现先调用后定义的情况如果边遍历边查就会误报未声明。做法是两趟第一趟遍历顶层把所有函数名、全局变量登记进符号表记录函数签名参数个数与类型第二趟再进函数体处理局部变量和语句。函数体内部同理先处理块内的声明语句再处理表达式。检查项大致是这几类按报错频率从高到低变量或函数未声明就使用同一作用域内重复定义赋值时左右类型不兼容课程实验里通常只有 int 和 float做隐式提升即可函数调用实参个数或类型与声明不符返回语句出现在非返回类型的函数里除以零这类能在编译期看出来的常量错误。每一条报错都带上 AST 节点里的line输出格式统一成line 12: variable x undeclared。格式统一这件事看着小实际上决定了你调试时能不能用grep快速筛出某一类错误。类型推导只往上走一层二元运算取两个操作数的公共类型赋值以左值类型为准。别在这一层搞太复杂的类型系统课程实验的收益很有限容易把后面的四元式生成拖下水。4.3 四元式生成与回填控制流的关键技巧中间代码用四元式(op, arg1, arg2, result)。表达式部分直译很简单一个节点生成一个四元式临时变量名用t1、t2递增。麻烦的是控制流——if和while在生成跳转指令时根本还不知道要跳到哪一行因为目标代码还没生成完。标准解法是回填// src/ir/emitter.h节选 struct Quad { std::string op, arg1, arg2, result; }; class QuadEmitter { public: int emit(const std::string op, const std::string a1, const std::string a2, const std::string res) { quads_.push_back({op, a1, a2, res}); return (int)quads_.size() - 1; // 返回下标供回填定位 } // 把所有 list 里的四元式的 result 字段统一改成 target void backpatch(const std::vectorint list, int target) { for (int idx : list) quads_[idx].result std::to_string(target); } private: std::vectorQuad quads_; };backpatch之所以改result字段而不是新加字段是因为跳转类四元式的“结果”本来就是目标地址语义上自洽省一个字段也省一次内存布局调整。生成while的时候先emit(j, cond, 0, )拿到一个待回填的下标塞进falseList循环体生成完再emit(j, , , )无条件跳回循环开头最后把falseList回填到循环体之后的第一条。这套流程里最容易错的是回填列表的合并。if-else的if分支执行完要跳过else这个跳过指令的下标得单独存一个nextList等else整体生成完后统一回填。如果两个列表搞混了症状通常是程序能跑但结果偶尔不对而且只在特定嵌套深度下复现非常难查。5. 避坑与排查实验里最容易翻车的五个点5.1 词法与语法阶段看着能跑其实全错现象a - b - c算出来的结果和手算对不上但语法树打印出来“看着挺正常”。原因表达式文法没消左递归直接写成expr - expr - term然后图省事改成了右递归导致结合性反了。解决把同级运算符用while循环吸收即 3.2 节那段写法保证左结合。验证方法是拿10 - 3 - 2跑一遍正确答案是 5右结合会得到 9。这个用例建议直接写进tests/每次改文法都跑。现象报错信息里的行号总是比实际行号小 1或者遇到注释后就彻底乱了。原因行号只在START状态维护或者注释整体跳过时把注释里的换行吞了。解决把line_提到状态机循环最前面对所有字符无条件执行注释扫描走单独的小循环但循环里同样要维护行号。改完后拿一个多行注释跨了好几行的源文件验证报错行号必须和编辑器里看到的一致。5.2 语义与符号表阶段作用域边界没管住现象函数体里定义了一个和全局变量同名的局部变量程序报“重复定义”。原因insert时没有只在最内层查重而是从头到尾全表扫了一遍。解决按 4.1 节的写法insert只查scopes_.back()。验证方式是写一个函数参数名和全局变量名相同能正常编译通过才算对。现象for (int i 0; ...)循环结束后i还能在循环外面被使用语义分析不报错。原因for语句体的enterScope/leaveScope只在循环体{}上调用忽略了初始化语句本身所在的那一层作用域。解决在for的初始化语句之前就enterScope整个for结构结束再leaveScope。这类“作用域比你以为的大一圈”的问题靠读代码很难发现靠写用例最快。5.3 中间代码与运行阶段回填指向了错误位置现象while循环只执行一次就退出或者干脆死循环。原因回填时把“循环体之后”的地址和“循环开头”的地址搞反了条件跳转跳到了自己身上。解决打印四元式列表人工检查每条j和j的result指向的序号确认它落在正确的位置。建议在backpatch里加一句断言assert(target 0 target (int)quads_.size())越界立刻停别让它悄悄生成一条跳到不存在的指令。现象单个测试用例跑得好好的换个嵌套两层的if就崩。原因nextList和falseList在不同嵌套层级之间复用了同一个局部变量内层的回填把外层的列表覆盖了。解决所有回填列表都在函数栈上按层级独立创建绝不用成员变量缓存。这类 bug 的典型特征是“只在特定嵌套深度出现”看到这种规律就先怀疑状态被共享了。6. 二次开发把实验代码改成能跑通真实子集的编译器想拿这套代码继续往深走我建议从“让它在真实源文件上不崩”开始而不是急着加优化。第一步是补错误恢复现在的解析器遇到语法错误基本直接exit改成记录错误、跳到下一个分号或右花括号再继续能让你一次看到十个错误而不是第一个就停。这一步改动集中在Parser::parseProgram的主循环里加个synchronize()函数捕获异常后消费 token 直到同步点工作量不大但体感提升明显。第二步是把四元式接到一个能真跑的出口上。课程代码通常只打印指令你可以写个几十行的栈式虚拟机把四元式逐条解释执行遇到j改pc、遇到算术指令弹两个栈元素算完压回去。有了这个你的编译器就能真跑出结果测试从“看打印对不对”变成“比对程序输出”回归成本直接降一个量级。改造方向主要改动点验证方式错误恢复Parser加同步集main不提前退出故意写错括号看是否报多条错误解释执行新增vm/遍历四元式斐波那契递归跑出正确值常量折叠语义分析阶段改 AST 常量节点折叠前后四元式条数变少、结果不变数组支持符号表加维度信息新增[]四元式声明、赋值、读取三种场景各一个用例第三步再考虑优化而且只做常量折叠和公共子表达式消除两个。这两个的共同点是都在 AST 或四元式上做局部替换不动寄存器分配改错了也能靠关闭开关回退。我踩过最深的一个坑是改造过程中把tests/里的基线输出覆盖了结果后面所有回归都失去了参照只能靠肉眼判断“看起来差不多”。从那以后我每次动核心逻辑之前都强制把当前tests/的输出快照另存一份到tests/baseline/改完 diff 一遍再提交哪怕只改了三行。希望这个习惯能帮到你少走一点回头路。本文还有配套的精品资源点击获取 
长河君 · 2026/11/2 15:59:32 · 阅读 1.2k 编译原理实验全链路：从词法分析到目标代码
简介面向学习编译原理、需要完成词法分析与语法分析实验的高校学生这套电子科技大学编译原理实验代码提供了可供对照的完整实现。压缩包共21个文件、约203KB主要由5个cpp与4个h源文件构成覆盖输入处理、词法分析、语法分析等模块并配有pas测试源文件、vcxproj与sln工程文件、exe可执行程序及docx运行说明便于在Visual Studio环境中打开、编译和验证。已有2139人学习下载说明其在课程实验场景中具有较高参考价值。读者可从中梳理词法单元识别、token流生成、抽象语法树构建与解析策略的实现脉络也可借助运行说明和可执行程序复现实验结果理解编译器前端各模块的协作方式为课程实验、代码调试和后续语义分析学习提供较扎实的参考。1. 编译原理实验代码一份能一路跑通到目标代码的课程工程很多人对编译原理实验的印象是“四个割裂的小程序”词法一个、语法一个、语义一个、中间代码一个各交各的最后谁也没连起来。这套课程实验代码从一开始就按“一整条流水线”来组织源文件进去Token 序列出来语法树、符号表、四元式一路往下传最后能吐出可执行的结果。它适合正在上编译原理课、被实验报告逼着改代码的同学也适合工作几年后想回头把前端那几个经典算法补扎实的开发者。整套代码量不大但每一层的输入输出约定都写死了改起来有章可循不会一动手就雪崩。2. 工程结构与运行链路五个实验如何拼成一整台编译器2.1 目录分层与模块边界这套代码的第一眼观感是“分层很硬”。作者没有把所有东西塞进一个 main.cpp而是按编译阶段切目录每个阶段只暴露一个头文件给下游。这种切法在课程实验里不算新鲜但它解决了一个很实际的问题实验是分批布置的第三周交词法、第五周交语法如果接口一开始没定死后面每加一层就得回头改前面。目录大致是这样组织的路径职责对外暴露include/token.hToken 定义、关键字表Token结构、TokKind枚举src/lexer/字符流 → Token 序列Lexer::scanAll()src/parser/Token 序列 → 语法树Parser::parseProgram()src/ast/语法树节点定义与打印AstNode及其派生类src/semantic/符号表、类型检查SemanticAnalyzer::run()src/ir/四元式生成、回填QuadEmittersrc/codegen/四元式 → 目标指令CodeGen::emit()tests/词法/语法/语义用例每个阶段独立可跑Makefile分阶段构建目标make lex、make parse等我比较认可这个拆法的地方在于tests/是按阶段独立的。词法阶段你不需要等语法分析器写好make lex就能把.c源文件跑成 Token 列表打印出来。对课程实验来说这种“每一层都能单独验证”的结构比任何架构图都实在——出问题的时候你能立刻定位到是哪一层崩的。需要留意的是include/里只有token.h和ast.h是有实际内容的公共头其余模块之间靠前向声明加返回指针来耦合。这在课程规模下没问题但如果你打算往里加功能比如加个词法错误恢复就得注意别在头文件里塞太多实现细节否则改一处全量重编等编译的时间比调试的时间还长。2.2 数据结构主线Token → AST → 符号表 → 四元式整条链路能串起来靠的是四个核心数据结构。它们不是随便定的每一个的形状都决定了下一层好不好写。第一层是Token。它必须带行号否则报错时你只能告诉用户“有语法错误”说不清在哪一行这是血泪经验。第二层是语法树节点用基类加派生类的多态结构或者更省事的 tagged union课程实验里前者更直观。第三层是符号表本质是作用域栈 哈希表。第四层是四元式(op, arg1, arg2, result)四元组控制流的跳转目标先留空后面回填。它们之间的契约很关键词法分析器不关心语法只保证每个 Token 的lexeme和kind正确语法分析器不查语义看到未声明的标识符也照样建节点语义分析器不改语法树只填符号表上的类型信息并对不合法处报错。这条边界守住了每一层都能用固定的一组测试用例回归改上层不会把下层带崩。我在别的项目里见过反例语法分析阶段顺手做了“变量未声明”的检查。结果是只要文法改一个产生式语义检查就得跟着重写。分层这件事课程代码里看着像形式主义实际上是给你自己留后悔药。2.3 构建与跑通三条命令验证整条流水线环境要求不高g 支持 C17 即可Makefile 里没引第三方库。第一次跑建议按阶段来别一上来就make all。# 1) 只跑词法确认 Token 流正确 make lex SRCtests/input/expr.c # 2) 跑语法打印带缩进的语法树 make parse SRCtests/input/expr.c # 3) 全流程语义 四元式 目标代码 make run SRCtests/input/expr.cSRC这个变量是传给编译产物的入参不是 Makefile 里的固定路径所以你可以直接拿自己的测试源文件来喂。第二步打印出的语法树是缩进格式的缩进层级就是子树深度肉眼扫一遍基本能看出优先级有没有结合错——比如a b * c如果*没挂在的右子节点下面那你的表达式文法八成写成了左递归没消干净。第三步的产物分两段打印先是四元式列表每个四元式带序号然后是目标指令序列。四元式那一段建议每次改完代码都存一份基线因为回填逻辑最容易出错而错误往往表现为“跳转目标指向了一个已经被覆盖掉的序号”光看最终结果不容易发现。提示如果你的环境里make版本较老SRC这种传参方式仍然可用但要注意 Makefile 里对空值做了默认处理不传会退回内置的示例文件别以为是自己代码没执行。3. 词法与语法分析模块拆解从字符流到语法树3.1 词法分析器手写扫描器 状态转移表词法部分给了两套实现一套是纯手写的switch扫描一套是表驱动。手写那套读起来快但状态一多就成一锅粥表驱动那套前期填表烦后面加关键字、加运算符几乎不用改逻辑。课程实验里我更推荐表驱动那套因为它的错误定位天然比手写版清楚。Token 的定义是所有下游的地基长这样// include/token.h enum class TokKind { Id, Num, Keyword, Op, Delim, End, Error }; struct Token { TokKind kind; std::string lexeme; // 原始字面量报错时原样回显 int line 0; // 行号缺了它报错就是耍流氓 int value 0; // 仅 Num 有效提前算好省得下游再转 };value这个字段是给常量折叠留的数字字面量在扫描阶段就转成整数语义分析阶段做2 * 3折叠时就不用再碰字符串。line必须在扫描时维护不要想着“语法分析时再数”因为注释和空白在词法阶段就被吃掉了下游根本数不准。状态转移表的核心是一个二维数组加一个驱动循环// src/lexer/table_lexer.cpp节选 // 状态0START 1ID 2NUM 3OP 4DONE 5ERR static const int kTrans[6][128] { /* START */ {a...z}: 见下方说明, // ... }; Token Lexer::next() { int state 0; std::string buf; while (state ! 4 state ! 5) { char c peek(); if (c \0) { state 4; break; } // 文件尾直接收 if (c \n) { line_; } // 行号在任何状态下都要维护 state kTrans[state][(unsigned char)c]; if (state ! 0 state ! 4) buf.push_back(c); advance(); } if (state 5) return {TokKind::Error, buf, line_}; return classify(buf); // 查关键字表是关键字就改 kind }表的内容这里没法完整贴6×128 太大但思路很明确行下标是当前状态列下标是输入字符的 ASCII 码值是下一个状态。填表时把[ID][a-z] ID、[ID][0-9] ID、[START][0-9] NUM这些规则逐条写进去比写一长串if-else好维护得多加个运算符只需要改两三个格子。classify那一步是查关键字表unordered_mapstring, TokKindif、while、int都在里面。放在最后查而不是在状态机里判断是因为标识符和关键字的字符构成完全一样扫描阶段分不开只能在拿到完整 lexeme 之后补一刀。状态机里有个容易忽略的点行号维护必须放在状态转移之前且对所有字符生效。我见过有实现只在START状态下数换行结果一行中断在字符串里的转义换行就丢了报错行号整体偏移一截查起来极其难受。3.2 语法分析递归下降打底LL(1) 表做对照语法部分的主实现是递归下降另外附了一份 LL(1) 预测分析表的构造代码用来对照验证 FIRST/FOLLOW 集算得对不对。递归下降的好处是可读性接近文法本身一个产生式对应一个函数坏处是左递归必须手工消掉而且回溯控制全靠人肉。表达式那段的写法是这样的// src/parser/expr.cpp节选 // 已消除左递归expr - term { (|-) term } AstNode* Parser::parseExpr() { AstNode* left parseTerm(); // 先啃掉一个 term while (cur_.kind TokKind::Op (cur_.lexeme || cur_.lexeme -)) { std::string op cur_.lexeme; advance(); // 吃掉运算符 AstNode* right parseTerm(); left makeBinary(op, left, right); // 左结合新节点挂在上层 } return left; }这段代码对应的是消完左递归的文法所以用while循环来吸收同级运算符天然保证了左结合。如果你把它写成递归调用parseExpr()就会变成右结合a - b - c算出来是a - (b - c)结果错得悄无声息——这正是语法树阶段最容易翻的车后面第 5 章会细说。parseTerm()内部再处理*/和括号、一元负号层级自下而上优先级递增。整个递归下降解析器的函数调用栈深度就等于你当前解析位置的优先级层级调试的时候看栈帧一眼就知道卡在哪一层。LL(1) 那份表驱动实现主要干两件事算 FIRST 集、算 FOLLOW 集、填预测分析表、用显式栈模拟递归。它的价值在于交叉验证——同一个输入递归下降和表驱动应该产出结构完全一致的语法树。我一般会把两边的树都打印出来 diff 一遍能提前抓出不少文法写错的地方比如某个产生式的 FOLLOW 集漏了)表驱动那边就会在选择时卡死而递归下降可能靠运气混过去。3.3 语法树节点设计与打印AST 节点用的是基类 派生类// include/ast.h节选 struct AstNode { int line 0; virtual ~AstNode() default; virtual void dump(int depth) const 0; // 缩进打印调试主力 }; struct BinaryExpr : AstNode { std::string op; AstNode* lhs; AstNode* rhs; void dump(int d) const override { std::cout std::string(d * 2, ) Binary( op )\n; lhs-dump(d 1); rhs-dump(d 1); } };dump(int depth)这个纯虚函数是整个调试流程里性价比最高的东西。带缩进的先序遍历输出能让语法树的形状直接可视化你不用画图就能看出哪个节点挂错了位置。每个节点都带line是为了在语义分析报“变量重复定义”时能指回源码行。节点里不放父指针是我个人的取舍课程实验里不需要向上遍历加了父指针反而要处处维护容易忘。如果你后面要做代码优化需要向上查找再补也来得及。4. 语义分析与中间代码生成符号表、类型检查与四元式4.1 符号表作用域栈 哈希表的组合符号表是这一层最容易写歪的地方。很多人图省事用一个全局map结果一进函数体就发现同名变量没法区分只能靠改名硬凑。正确做法是作用域链一个vector当栈每个元素是一层作用域的哈希表。// src/semantic/symbol_table.h节选 struct Symbol { std::string name; Type type; // int / float / 函数签名等 int scopeLevel; // 层次用于报错时说明在第几层重定义 int offset; // 栈帧偏移目标代码生成时才用得上 }; class SymbolTable { public: void enterScope() { scopes_.emplace_back(); } // 进 { 时调用 void leaveScope() { scopes_.pop_back(); } // 出 } 时调用 bool insert(const Symbol s) { auto top scopes_.back(); if (top.count(s.name)) return false; // 同层重定义 top.emplace(s.name, s); return true; } Symbol* lookup(const std::string name) { for (auto it scopes_.rbegin(); it ! scopes_.rend(); it) { auto f it-find(name); if (f ! it-end()) return f-second; // 由内向外找 } return nullptr; // 未声明 } private: std::vectorstd::unordered_mapstd::string, Symbol scopes_; };insert只在最内层查重、不往外查这是刻意的内层遮蔽外层是合法行为比如函数参数和全局变量同名报错反而是错的。lookup从rbegin往外走保证先命中最近的声明。这两个函数的行为差异是语义分析里“同名”和“重定义”两个概念的分界线。offset字段在语义阶段只是预留等目标代码生成时按变量声明顺序累加算出栈帧布局。课程实验里变量类型有限直接按 4 字节对齐就够。4.2 语义检查的遍历顺序先声明后使用语义分析的遍历顺序不是随便定的必须是“先扫声明、再扫使用”。函数体内可能出现先调用后定义的情况如果边遍历边查就会误报未声明。做法是两趟第一趟遍历顶层把所有函数名、全局变量登记进符号表记录函数签名参数个数与类型第二趟再进函数体处理局部变量和语句。函数体内部同理先处理块内的声明语句再处理表达式。检查项大致是这几类按报错频率从高到低变量或函数未声明就使用同一作用域内重复定义赋值时左右类型不兼容课程实验里通常只有 int 和 float做隐式提升即可函数调用实参个数或类型与声明不符返回语句出现在非返回类型的函数里除以零这类能在编译期看出来的常量错误。每一条报错都带上 AST 节点里的line输出格式统一成line 12: variable x undeclared。格式统一这件事看着小实际上决定了你调试时能不能用grep快速筛出某一类错误。类型推导只往上走一层二元运算取两个操作数的公共类型赋值以左值类型为准。别在这一层搞太复杂的类型系统课程实验的收益很有限容易把后面的四元式生成拖下水。4.3 四元式生成与回填控制流的关键技巧中间代码用四元式(op, arg1, arg2, result)。表达式部分直译很简单一个节点生成一个四元式临时变量名用t1、t2递增。麻烦的是控制流——if和while在生成跳转指令时根本还不知道要跳到哪一行因为目标代码还没生成完。标准解法是回填// src/ir/emitter.h节选 struct Quad { std::string op, arg1, arg2, result; }; class QuadEmitter { public: int emit(const std::string op, const std::string a1, const std::string a2, const std::string res) { quads_.push_back({op, a1, a2, res}); return (int)quads_.size() - 1; // 返回下标供回填定位 } // 把所有 list 里的四元式的 result 字段统一改成 target void backpatch(const std::vectorint list, int target) { for (int idx : list) quads_[idx].result std::to_string(target); } private: std::vectorQuad quads_; };backpatch之所以改result字段而不是新加字段是因为跳转类四元式的“结果”本来就是目标地址语义上自洽省一个字段也省一次内存布局调整。生成while的时候先emit(j, cond, 0, )拿到一个待回填的下标塞进falseList循环体生成完再emit(j, , , )无条件跳回循环开头最后把falseList回填到循环体之后的第一条。这套流程里最容易错的是回填列表的合并。if-else的if分支执行完要跳过else这个跳过指令的下标得单独存一个nextList等else整体生成完后统一回填。如果两个列表搞混了症状通常是程序能跑但结果偶尔不对而且只在特定嵌套深度下复现非常难查。5. 避坑与排查实验里最容易翻车的五个点5.1 词法与语法阶段看着能跑其实全错现象a - b - c算出来的结果和手算对不上但语法树打印出来“看着挺正常”。原因表达式文法没消左递归直接写成expr - expr - term然后图省事改成了右递归导致结合性反了。解决把同级运算符用while循环吸收即 3.2 节那段写法保证左结合。验证方法是拿10 - 3 - 2跑一遍正确答案是 5右结合会得到 9。这个用例建议直接写进tests/每次改文法都跑。现象报错信息里的行号总是比实际行号小 1或者遇到注释后就彻底乱了。原因行号只在START状态维护或者注释整体跳过时把注释里的换行吞了。解决把line_提到状态机循环最前面对所有字符无条件执行注释扫描走单独的小循环但循环里同样要维护行号。改完后拿一个多行注释跨了好几行的源文件验证报错行号必须和编辑器里看到的一致。5.2 语义与符号表阶段作用域边界没管住现象函数体里定义了一个和全局变量同名的局部变量程序报“重复定义”。原因insert时没有只在最内层查重而是从头到尾全表扫了一遍。解决按 4.1 节的写法insert只查scopes_.back()。验证方式是写一个函数参数名和全局变量名相同能正常编译通过才算对。现象for (int i 0; ...)循环结束后i还能在循环外面被使用语义分析不报错。原因for语句体的enterScope/leaveScope只在循环体{}上调用忽略了初始化语句本身所在的那一层作用域。解决在for的初始化语句之前就enterScope整个for结构结束再leaveScope。这类“作用域比你以为的大一圈”的问题靠读代码很难发现靠写用例最快。5.3 中间代码与运行阶段回填指向了错误位置现象while循环只执行一次就退出或者干脆死循环。原因回填时把“循环体之后”的地址和“循环开头”的地址搞反了条件跳转跳到了自己身上。解决打印四元式列表人工检查每条j和j的result指向的序号确认它落在正确的位置。建议在backpatch里加一句断言assert(target 0 target (int)quads_.size())越界立刻停别让它悄悄生成一条跳到不存在的指令。现象单个测试用例跑得好好的换个嵌套两层的if就崩。原因nextList和falseList在不同嵌套层级之间复用了同一个局部变量内层的回填把外层的列表覆盖了。解决所有回填列表都在函数栈上按层级独立创建绝不用成员变量缓存。这类 bug 的典型特征是“只在特定嵌套深度出现”看到这种规律就先怀疑状态被共享了。6. 二次开发把实验代码改成能跑通真实子集的编译器想拿这套代码继续往深走我建议从“让它在真实源文件上不崩”开始而不是急着加优化。第一步是补错误恢复现在的解析器遇到语法错误基本直接exit改成记录错误、跳到下一个分号或右花括号再继续能让你一次看到十个错误而不是第一个就停。这一步改动集中在Parser::parseProgram的主循环里加个synchronize()函数捕获异常后消费 token 直到同步点工作量不大但体感提升明显。第二步是把四元式接到一个能真跑的出口上。课程代码通常只打印指令你可以写个几十行的栈式虚拟机把四元式逐条解释执行遇到j改pc、遇到算术指令弹两个栈元素算完压回去。有了这个你的编译器就能真跑出结果测试从“看打印对不对”变成“比对程序输出”回归成本直接降一个量级。改造方向主要改动点验证方式错误恢复Parser加同步集main不提前退出故意写错括号看是否报多条错误解释执行新增vm/遍历四元式斐波那契递归跑出正确值常量折叠语义分析阶段改 AST 常量节点折叠前后四元式条数变少、结果不变数组支持符号表加维度信息新增[]四元式声明、赋值、读取三种场景各一个用例第三步再考虑优化而且只做常量折叠和公共子表达式消除两个。这两个的共同点是都在 AST 或四元式上做局部替换不动寄存器分配改错了也能靠关闭开关回退。我踩过最深的一个坑是改造过程中把tests/里的基线输出覆盖了结果后面所有回归都失去了参照只能靠肉眼判断“看起来差不多”。从那以后我每次动核心逻辑之前都强制把当前tests/的输出快照另存一份到tests/baseline/改完 diff 一遍再提交哪怕只改了三行。希望这个习惯能帮到你少走一点回头路。本文还有配套的精品资源点击获取