手写微型编译器：从词法分析到三地址码的五步实战-北京尧图网络

简介本资源是重庆理工大学《编译原理》课程设计的完整报告文档面向计算机专业本科生及编译技术初学者聚焦编译器全流程开发实践解决理论理解与工程实现脱节问题。报告系统覆盖词法分析、语法分析、语义分析、中间代码生成、优化及目标代码生成六大核心模块包含语言规范设计、Lex/Yacc工具应用、语法树构建、三地址代码生成与优化等关键实现细节并附有典型示例程序的端到端编译流程演示。压缩包为ZIP格式共含若干文档类文件具体类型未提供整体大小4.52MB结构清晰、图文结合便于对照学习与复现。已有140人下载学习读者可直接获取规范的课程设计报告模板、分阶段实现思路、常见语义错误排查方法及龙书《编译原理》知识点在项目中的落地映射是开展编译器实践与撰写高质量课程报告的重要参考。1. 编译原理课程设计报告不是交差文档而是你亲手造出的“微型编译器黑匣子”如果你正被《编译原理》课设压得喘不过气——对着龙书啃了三遍词法分析还是写不出一个能跑通的 scanner语法树画得比流程图还乱中间代码生成像在猜谜最后交上去的 PDF 里全是截图和文字描述……那这份课程设计报告很可能就是你第一次真正把理论拧成可执行逻辑的临界点。它不是模板套用的 Word 填空而是一份完整记录你如何从零构建 lexer → parser → AST → 中间代码 → 目标代码哪怕只是三地址码的实操日志。我带过 7 届计科本科生做这门课设90% 的翻车都卡在“以为懂了一写就崩”比如正则表达式写对了但状态机跳转漏边、LL(1) 分析表填错一行导致整个预测分析器死循环、语义动作嵌在产生式里却忘了同步更新符号表指针。这份报告的价值恰恰在于它强制你暴露所有断点——哪里语法检查没覆盖空语句哪里类型检查放过了隐式转换哪里寄存器分配时变量生命周期算错了。适合正在调试递归下降 parser 卡在 if-else 二义性、或纠结于四元式要不要加临时变量标记的实战派不适合只想抄个 GitHub 项目改改 README 的同学。2. 从源码到三地址码五步闭环实现路径与关键决策点课程设计的核心不是写报告而是让一段类 C 的子集比如支持 int/float 变量、−*/、if/while、简单函数真正跑起来。下面这条链路是我带学生踩坑后验证过的最小可行路径每一步都对应报告中必须呈现的技术细节而非泛泛而谈。2.1 词法分析器手写 DFA 还是 flex选型依据与状态机落地很多同学直接flex一把梭结果调试时发现注释没吞掉、浮点数识别错位、标识符长度截断——因为没看懂.lex文件里正则的优先级和回溯机制。我建议初学者手写 DFA哪怕只支持 5 类 tokenID、NUM、OP、KEYWORD、SEMI理由很实在能强制你理解 NFA→DFA 的子集构造过程报告里画状态转换图比贴 flex 命令更有说服力遇到和混淆时你能立刻定位到状态后是否该接受形成而不是查 flex 文档后续 parser 需要 token 的 line/column 信息手写时天然可嵌入位置追踪。# 示例简化版整数识别 DFAPython 实现非生产环境 def scan_number(input_str, pos): start pos # 状态 0: 初始1: 读到数字2: 读到小数点后数字 state 0 while pos len(input_str): ch input_str[pos] if state 0: if ch.isdigit(): state 1 else: break elif state 1: if ch.isdigit(): pass elif ch .: state 2 else: break elif state 2: if ch.isdigit(): pass else: break pos 1 if state in (1, 2): # 成功识别 return (NUM, input_str[start:pos], start, pos-1) return None注意这里state 2时若遇到非数字字符如3.14abc应只取3.14并回退pos到小数点后一位否则后续 token 会错位。这是手写 DFA 最易漏的边界——回退逻辑必须显式编码flex 默认帮你做了但你得知道它怎么做的。2.2 语法分析器为什么放弃 Yacc/Bison坚持递归下降Yacc 生成的 LALR(1) 分析器对初学者像黑匣子报错说 “shift/reduce conflict”你得去翻冲突表改个文法加个左递归整个分析表重算调试成本爆炸。而递归下降 parser 是你写的每一行if-elif-else对应一条产生式match(token)调用就是一次预测。我们课程设计限定文法为 LL(1)关键决策点有三个First/Follow 集必须手算验证比如Stmt → if ( Expr ) Stmt | while ( Expr ) Stmt | { StmtList }if和while的 First 集不相交但{和if的 First 集也不相交否则StmtList的调用时机无法确定左递归必须消除Expr → Expr Term | Term必须改写为Expr → Term ExprExpr → Term Expr | ε否则递归下降会无限调用错误恢复策略要写进代码当match())失败时不能直接抛异常而要跳过直到找到同步记号如;或}否则一个括号错导致后面全报错。# 递归下降核心节选处理 if 语句 def parse_if_stmt(): match(if) # 消耗 if token match(() # 消耗 ( cond parse_expr() # 解析条件表达式 match()) # 消耗 ) then_body parse_stmt() # 解析 then 分支 if lookahead.type else: # 预读判断是否有 else match(else) else_body parse_stmt() return IfNode(cond, then_body, else_body) else: return IfNode(cond, then_body, None) # else 分支为空逻辑说明lookahead是预读的下一个 token避免match()消耗后才发现无 elseIfNode是 AST 节点类其cond字段必须是 ExprNode 子类保证类型一致性——这点常被忽略导致后续语义分析时cond居然是 IDNode。2.3 抽象语法树AST不只是节点拼接而是语义承载容器AST 不是语法树的简化版它是语义动作的执行载体。比如a b c语法树只告诉你结构是Assign → ID Expr但 AST 节点必须携带AssignNode.left指向IDNode(a)且该节点需记录符号表索引如symtab.get(a).addrAssignNode.right是BinaryOpNode(, b_node, c_node)其eval_type字段必须是int或float用于后续类型检查每个节点的gen_code()方法返回三地址码序列如t1 b c; a t1。class BinaryOpNode(ASTNode): def __init__(self, op, left, right): self.op op self.left left self.right right self.eval_type self._infer_type() # 类型推导逻辑 def _infer_type(self): # 规则int int → intint float → floatfloat int → float lt self.left.eval_type rt self.right.eval_type if lt float or rt float: return float return int def gen_code(self, ir_gen): # ir_gen 是中间代码生成器实例 t1 ir_gen.new_temp() # 申请新临时变量 code1 ir_gen.emit(t1, self.left.gen_code(ir_gen), self.op, self.right.gen_code(ir_gen)) return t1 # 返回本节点计算结果的临时变量名参数说明ir_gen.emit()接收目标临时变量、左操作数、操作符、右操作数生成形如t1 t2 t3的四元式self.gen_code()返回的是该子表达式计算结果的存放位置临时变量名或寄存器供父节点使用——这是 AST 与 IR 生成耦合的关键接口。3. 符号表与类型检查让编译器真正“懂”变量而非机械搬运没有符号表的编译器就像没有地图的司机——能开车但不知道目的地在哪。课程设计里符号表不是一张静态哈希表而是分层作用域的动态结构直接影响变量查找、类型匹配、作用域退出时的内存回收。3.1 分层符号表设计为什么嵌套作用域必须用栈C 风格语言允许{ int x; { int x; } }内层x隐藏外层x。若用单层哈希表insert(x, ...)会覆盖外层定义lookup(x)永远返回内层值。正确做法是维护一个作用域栈全局作用域level 0初始化时压栈遇到{时新建局部作用域level 1,2...并压栈遇到}时弹出当前作用域lookup(name)从栈顶向下搜索首次命中即返回insert(name, entry)总是在栈顶作用域插入。class SymbolTable: def __init__(self): self.scopes [{}] # 栈底是全局作用域 def enter_scope(self): self.scopes.append({}) # 新建局部作用域 def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() # 弹出最内层作用域 def insert(self, name, entry): self.scopes[-1][name] entry # 插入当前作用域 def lookup(self, name): # 从内向外搜索 for scope in reversed(self.scopes): if name in scope: return scope[name] return None # 未声明关键细节entry必须包含typeint/float、kindvar/func/param、offset相对于帧指针的偏移、is_global布尔值。offset在进入函数作用域时从 -4 开始保存旧 ebp每声明一个 int 变量减 4float 减 8——这个细节决定你生成的目标代码能否在真实栈上运行。3.2 类型检查规则从“能编译”到“不崩溃”的生死线类型检查不是锦上添花而是防止生成非法 IR 的闸门。常见错误包括if (x)中x是 float 类型C 允许但课程设计通常要求 bool 表达式a b c中b是 intc是 float但目标平台不支持混合运算函数调用时实参类型与形参声明不匹配。检查逻辑必须嵌入 AST 构建过程IDNode创建时lookup()返回的entry.type赋给self.typeBinaryOpNode构造时调用_infer_type()并校验left.type和right.type是否兼容AssignNode构造时比较left.type和right.type不兼容则报错。class AssignNode(ASTNode): def __init__(self, left, right): self.left left self.right right # 类型检查左值必须是变量且类型匹配 if not isinstance(left, IDNode): raise TypeError(fLeft side of assignment must be identifier, got {type(left).__name__}) if left.type ! right.type: raise TypeError(fType mismatch in assignment: {left.type} {right.type}) self.type left.type血泪经验很多同学把类型检查放在 AST 构建后统一扫描结果AssignNode的left和right已经是 AST 节点但left.type还没赋值因为IDNode的type是lookup()时才确定的。必须在节点初始化时完成类型绑定否则后续 IR 生成会因NoneType报错。3.3 常见问题排查符号表与类型检查的四大典型翻车点现象 → 原因 → 解决每条直击课设现场现象if (x)编译通过但生成的汇编里x被当作整数比较实际x是 float原因IDNode的type字段未在lookup()后赋值AssignNode的类型检查跳过if节点未做类型约束解决在IDNode.__init__()中强制self.type symtab.lookup(name).type并在IfNode构造时添加if cond.type not in (int, bool): raise TypeError现象嵌套函数内访问外层变量失败报 “undefined identifier”原因lookup()搜索顺序错误从栈底向上搜应从栈顶向下解决修正SymbolTable.lookup()循环为for scope in reversed(self.scopes):现象同一变量在不同作用域声明为不同类型如外层int a;内层float a;编译器不报错原因insert()未检查同名变量在当前作用域是否已存在解决在SymbolTable.insert()中添加if name in self.scopes[-1]: raise RedeclarationError现象a b c生成t1 b c; a t1但b和c是数组元素t1地址计算错误原因ArrayAccessNode的gen_code()返回的是地址如b[i]但BinaryOpNode误将其当数值参与运算解决为 AST 节点增加is_address标志BinaryOpNode.gen_code()中检测left.is_address则先load再运算4. 中间代码生成三地址码不是终点而是连接 AST 与目标平台的桥梁课程设计的中间代码通常限定为三地址码TAC形式为x y op z或x y。它的价值不在“多酷”而在可验证、可优化、可映射——你能在报告里清晰展示AST 的每个节点如何一步步变成 TACTAC 如何被调度成目标指令。别陷入“生成汇编”的幻觉先确保 TAC 逻辑自洽。4.1 四元式 vs 三元式为什么课程设计首选四元式四元式(op, arg1, arg2, result)如(, b, c, t1)result显式命名便于后续寄存器分配三元式(op, arg1, arg2)result隐含为该三元式序号如(, b, c)表示结果存于#0引用时写#0课程设计选四元式调试时一眼看出t1是谁t1 b c和a t1的依赖关系清晰三元式需要额外维护序号映射初学者极易混淆#2是哪个表达式的结果。class IRGenerator: def __init__(self): self.code [] # 四元式列表 self.temp_count 0 def new_temp(self): self.temp_count 1 return ft{self.temp_count} def emit(self, result, arg1, op, arg2None): # 四元式(op, arg1, arg2, result) if arg2 is None: self.code.append((op, arg1, None, result)) else: self.code.append((op, arg1, arg2, result)) def dump(self): for i, (op, a1, a2, res) in enumerate(self.code): if a2 is None: print(f{i}: {res} {op} {a1}) else: print(f{i}: {res} {a1} {op} {a2})逻辑说明emit()是 IR 生成的核心 API所有 AST 节点的gen_code()方法最终都调用它dump()输出格式严格按res a1 op a2方便人工核对——这是课程设计报告里必须附上的“可读性证据”。4.2 控制流语句的 TAC 生成if/while 的 goto 陷阱if和while的难点不在语法而在跳转标签的延迟绑定。你不能在解析if时就生成goto L1因为L1对应的语句还没解析完。标准解法是维护两个标签栈true_labels满足条件时跳转的目标、false_labels不满足时跳转的目标if解析开始时压入待填的L1then 入口和L2else 入口或 if 结束解析完then分支后emit(goto, None, None, L2)并填L1解析完else分支后填L2。# 简化版 if TAC 生成逻辑 def gen_if_code(self, node): # 1. 生成条件表达式代码得到条件结果 temp cond_temp node.cond.gen_code(self) # 2. 生成条件跳转若 cond_temp 0 则跳过 then L1 self.new_label() # then 入口标签 L2 self.new_label() # if 结束标签 self.emit(if_false, cond_temp, None, L1) # 条件假时跳 L1 # 3. 生成 then 分支代码 then_code node.then_body.gen_code(self) # 4. 跳过 else如果存在 self.emit(goto, None, None, L2) # 5. 填写 L1else 入口或空 self.patch_label(L1) # 此处填入当前 code 索引 if node.else_body: else_code node.else_body.gen_code(self) # 6. 填写 L2if 结束 self.patch_label(L2)参数说明new_label()返回唯一标签名如L1001patch_label(label)将该标签在emit()时预留的位置填为当前code列表长度。没有patch_label你的 goto 永远指向 0 地址——这是课设里最隐蔽的 bug。4.3 函数调用的 TAC参数传递与返回值的显式约定课程设计通常不实现栈帧管理但必须明确调用约定参数按从左到右顺序压栈或存入临时变量返回值存入固定临时变量如t_ret函数体以return语句结束生成t_ret ...和goto end。def gen_func_call(self, node): # 1. 生成所有实参的 TAC结果存入临时变量 args [] for arg in node.args: arg_temp arg.gen_code(self) args.append(arg_temp) # 2. 按约定传递参数示例存入 t_arg0, t_arg1... for i, arg_temp in enumerate(args): self.emit(, arg_temp, None, ft_arg{i}) # 3. 调用函数 self.emit(call, node.func_name, None, None) # 4. 返回值默认存入 t_ret return t_ret关键细节call四元式不带 result因为返回值由函数体内的return语句决定t_ret必须在函数定义时声明为输出变量否则return x的x无处安放——函数签名里的返回类型必须映射到 TAC 的t_ret类型检查。5. 报告撰写与答辩避坑让老师一眼看到你的技术纵深课程设计报告不是实验记录流水账而是技术决策的辩护状。老师想看的不是“我做了什么”而是“我为什么这么做以及当它崩了我怎么修”。以下四条是答辩时高频被问、也是报告里最易失分的点务必前置准备。5.1 词法分析部分必须回答“为什么不用正则库”老师大概率会问“Python 有re模块为什么手写 DFA”正确回答re库的贪婪匹配和回溯机制在复杂词法如嵌套注释/* ... */中不可控而手写 DFA 的状态转移完全透明课程目标是理解词法分析本质re是工具DFA 是原理我实现了/* ... */的嵌套注释处理状态机中增加IN_COMMENT和IN_NESTED_COMMENT状态re无法优雅处理嵌套。避坑提示不要说“为了作业要求”要说清技术权衡。如果真用了flex必须展示你修改了哪些默认行为如%option noyywrap、%option yylineno并解释为何这些选项必要。5.2 语法分析部分必须能画出 FIRST/FOLLOW 集计算过程老师会随机抽一条产生式让你现场算 FIRST 集。例如Stmt → if ( Expr ) Stmt | while ( Expr ) Stmt | { StmtList }问FIRST(Stmt)是什么标准答案FIRST(if) {if}FIRST(while) {while}FIRST({) {{}三者互斥无 ε 产生式故FIRST(Stmt) {if, while, {}FOLLOW(Stmt)需考虑Stmt出现在StmtList → Stmt StmtList | ε中故FOLLOW(Stmt) FOLLOW(StmtList) ∪ {, }}。血泪经验很多同学背下结论但不会推导。报告里必须附手写计算过程的照片或 LaTeX 公式证明你真算过——这是区分“抄代码”和“真理解”的分水岭。5.3 AST 设计部分必须解释节点字段的语义含义老师指着你的BinaryOpNode问“eval_type字段在什么场景下会被修改如果操作数一个是int一个是floateval_type是int还是float”正确回答eval_type在节点构造时由_infer_type()一次性确定后续不修改规则是“向 float 提升”所以int float → float这影响后续 IR 生成float类型的操作数需调用fadd指令而非add否则硬件会出错。避坑提示不要只写“类型提升”要说出具体规则C 标准的 usual arithmetic conversions和后果IR 指令选择。5.4 中间代码部分必须能手写一段代码对应的 TAC老师给你一段代码if (a b) { c a b; } else { c a - b; }要求你手写 TAC。标准答案0: t1 a b 1: if_false t1 goto L1 2: t2 a b 3: c t2 4: goto L2 5: L1: t3 a - b 6: c t3 7: L2:关键细节if_false是条件跳转指令非if_truegoto L2必须在then分支末尾L1和L2标签位置必须准确——少一行或多一行整个控制流就错。6. 从报告到可运行一个硬核验证技巧与我的终身习惯课程设计最大的幻觉是以为报告交了就结束了。真正的终点是你能用自己生成的 TAC手动模拟执行一遍验证每条指令的输入输出是否符合预期。这不是加分项而是及格线——因为所有编译器 bug最终都会在 TAC 执行时暴露。6.1 TAC 手动模拟验证法三步锁定 90% 的 IR 错误我带学生答辩前必做这个练习挑一段含 if/while/赋值的代码生成 TAC 后用纸笔模拟执行。步骤如下初始化符号表列出所有变量初始值如a5, b3, c0逐行执行 TAC对每条x y op z查符号表得y,z值计算结果存入x对if_false t1 goto L1查t1值决定是否跳转对比预期结果比如if (ab)应走 then 分支c最终应为8若模拟得c2说明t1 a b计算错误或跳转逻辑反了。示例代码 int a5, b3, c; if (a b) c a b; else c a - b; TAC 0: t1 a b // t1 1 (true) 1: if_false t1 goto L1 // t11不跳执行下一行 2: t2 a b // t2 8 3: c t2 // c 8 4: goto L2 5: L1: t3 a - b // 跳过 6: c t3 // 跳过 7: L2: 模拟结果c 8 ✓为什么有效TAC 是扁平化的指令序列无隐藏状态每步计算可验证一旦模拟结果与预期不符错误必然在 TAC 生成逻辑中如if_false写成if_true或t1计算用而非。6.2 我的终身习惯每次 commit 前强制跑三组验证用例从第一版 lexer 开始我就养成一个雷打不动的习惯基础用例int a; a 1 2;—— 验证词法、语法、AST、TAC 全链路边界用例if (1) { int x; x 2; }—— 验证作用域嵌套、符号表进出、临时变量回收错误用例int a; a b 1;—— 验证未声明变量报错且错误位置精准line 2, col 5。执行方式写一个test_runner.py自动调用你的编译器捕获 stdout/stderr比对期望输出。教训有次我优化 parser 性能删掉了lookahead的深度克隆结果if (x) { if (y) ... }的第二层if读错了lookahead但单元测试只跑了单层 if没发现。从那以后我每次git commit前都强制python test_runner.py跑完三组用例再git push。希望帮到你。本文还有配套的精品资源点击获取

手写微型编译器：从词法分析到三地址码的五步实战

相关推荐

基于PJ85718DM与STM32F031C6的双温度监测方案设计与实现

TCGA-BRCA聚类分析：R语言层次聚类与PCA实战指南

OpenClaw 搭建智能运维巡检工作流实践：用 Skill 编排 Agent 自动巡检

更多资讯

统一配置抽象层cua：解决微服务配置优先级与热加载难题

知识图谱推荐引擎毕业设计：从Neo4j构建到TransE路径推理全流程

easyread还能卷多久？阅读工具如何构建长期护城河

基于SpringBoot的高校课程智能选课系统-附源码

2026亲测有效：6款降AI工具盘点，教你如何彻底降低AIGC机器痕迹

2024-2026.5 ClaudeCode 时间线：从 Agent 到 MCP、Skills 的 SDK 演进路线图

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？