简介这份资源是华中科技大学2019级编译原理实验的源码合集面向正在学习编译原理、需要动手实现编译器前端的高校学生与自学者。项目围绕词法分析、语法分析、语义分析、抽象语法树生成与优化等核心环节展开虽只完成部分实验但已覆盖编译器前端的主要功能包括关键字与标识符识别、AST构建、符号表管理、静态语义检查、中间代码生成以及基于PL0语言的编译器部分实现适合作为课程实验参考或编译原理练手项目。压缩包共19个文件约878KB以C语言源文件与头文件为主体辅以词法、语法定义文件、Makefile构建脚本、Markdown说明文档和一份SysY2022语言定义PDF结构紧凑、便于导入IDE直接阅读。目前已有32人学习下载读者可从中获取分词与语法分析的具体实现思路、符号表与语义检查的组织方式以及PL0虚拟机代码生成的参考代码适合对照实验要求逐步理解编译器前端的构建流程。1. 编译原理课设到底在造什么从词法到目标代码的一条完整链路很多人第一次看到“基于编译原理的 Hustcompilation2022 项目”这类标题第一反应是“又一个课程作业”然后划走。但如果你真的动手写过一遍会发现它其实是一条从字符流到可执行语义的完整流水线词法分析把源码切成 token语法分析把 token 拼成语法树语义分析往符号表里填类型和作用域中间代码生成把树降成四元式最后目标代码生成把四元式翻译成能跑的指令序列。这条链路里任何一环偷懒后面都会以“玄学 bug”的形式报复你。这个项目适合两类人一类是正在上编译原理课、需要交一份能跑通全流程的课设另一类是工作几年后想补编译底子、但不想啃龙书理论、想直接看可运行代码的工程师。它解决的核心问题是让你亲手实现一个能编译简单语言子集的编译器而不是只会做选择题。下面我按“先立住理论、再动手复现”的顺序把这条链路拆开讲清楚包括每步怎么选型、参数怎么设、坑在哪。2. 词法与语法分析手写递归下降还是上工具生成2.1 词法分析器的状态机设计与 token 表词法分析的本质是把输入字符流按最长匹配原则切成 token。常见做法是手写一个状态机而不是一上来就上 lex/flex。原因很简单课设规模的语言子集通常只有关键字、标识符、数字、运算符、界符这几类手写状态机反而更可控调试时能直接打断点看当前字符位置。我一般会先定义一张 token 类型表用枚举或常量表示然后写一个nextToken()函数每次从当前指针开始扫描。核心逻辑是跳过空白和注释然后根据首字符判断进入哪个分支。首字符是字母或下划线就继续读字母数字下划线读完查关键字表命中就是关键字否则是标识符首字符是数字就读数字和小数点注意处理1.和.5这种边界首字符是运算符就要考虑双字符运算符如、、!的前瞻。# 词法分析器核心扫描逻辑简化版 KEYWORDS {if, else, while, int, float, return} def next_token(self): self.skip_whitespace_and_comment() if self.pos len(self.src): return Token(EOF, None) ch self.src[self.pos] # 标识符或关键字 if ch.isalpha() or ch _: start self.pos while self.pos len(self.src) and (self.src[self.pos].isalnum() or self.src[self.pos] _): self.pos 1 word self.src[start:self.pos] return Token(word if word in KEYWORDS else ID, word) # 数字整数或浮点 if ch.isdigit(): start self.pos while self.pos len(self.src) and self.src[self.pos].isdigit(): self.pos 1 if self.pos len(self.src) and self.src[self.pos] .: self.pos 1 while self.pos len(self.src) and self.src[self.pos].isdigit(): self.pos 1 return Token(FLOAT, float(self.src[start:self.pos])) return Token(INT, int(self.src[start:self.pos])) # 双字符运算符前瞻 two self.src[self.pos:self.pos2] if two in (, !, , , , ||): self.pos 2 return Token(two, two) # 单字符运算符和界符 self.pos 1 return Token(ch, ch)这段代码的关键参数是self.pos这个全局扫描指针所有分支都必须保证在返回前把它推进到正确位置。逻辑说明先跳空白和注释再按首字符分流标识符分支用isalnum()而不是正则避免每次调用重新编译正则的开销数字分支要处理小数点后没有数字的情况实际项目中我会在这里报一个词法错误而不是静默接受。参数上KEYWORDS集合建议用frozenset查询是 O(1)比列表遍历快一个量级。2.2 递归下降语法分析表达式优先级怎么用函数层级表达语法分析我推荐手写递归下降而不是用 yacc/bison 生成。原因是课设语言子集的文法通常不大递归下降的代码结构和文法产生式一一对应改文法时改函数就行不用重新生成解析表。更重要的是递归下降能自然处理表达式优先级把优先级低的运算符放在外层函数优先级高的放在内层函数。典型做法是给表达式写一层层的函数parse_expr处理加减parse_term处理乘除parse_factor处理括号和一元运算。每层函数只负责自己这层运算符遇到更高优先级的运算符就调用下一层函数。这样1 2 * 3会先由parse_expr读到1看到然后调用parse_term去解析2 * 3自然得到正确结合顺序。# 递归下降表达式优先级分层 def parse_expr(self): node self.parse_term() while self.cur.type in (, -): op self.cur.type self.advance() right self.parse_term() node BinOp(op, node, right) return node def parse_term(self): node self.parse_factor() while self.cur.type in (*, /): op self.cur.type self.advance() right self.parse_factor() node BinOp(op, node, right) return node def parse_factor(self): if self.cur.type (: self.advance() node self.parse_expr() self.expect()) return node if self.cur.type in (INT, FLOAT, ID): node Leaf(self.cur) self.advance() return node raise SyntaxError(funexpected token {self.cur.type} at {self.cur.pos})逻辑说明parse_expr和parse_term的 while 循环实现了左结合因为每次都是把当前 node 作为左子树新解析的 right 作为右子树。参数上self.cur是当前 tokenself.advance()负责推进到下一个 token。注意parse_factor里遇到左括号要递归调用parse_expr这样才能处理(12)*3这种嵌套。失败时看SyntaxError里的 token 类型和位置基本能定位到是哪个产生式没覆盖。2.3 语法树节点设计用类继承还是字典语法树节点设计有两种常见做法一种是每个节点一个类比如BinOp、Leaf、IfStmt用继承表达层级另一种是用字典{type: binop, op: , left: ..., right: ...}。课设规模我倾向用类因为后续语义分析和代码生成要对节点做类型判断类继承配合isinstance比字典查 key 更清晰也更容易加方法。节点类至少要有accept(visitor)方法或者直接在每个节点上写gen_code()这样遍历树时不用写一堆if node.type ...。我一般会定义一个基类Node然后BinOp、Leaf、Assign、If、While各自继承。每个节点保存自己的属性比如BinOp保存op、left、rightLeaf保存token。这样语义分析阶段做类型检查时直接isinstance(node, BinOp)就能判断。3. 语义分析与符号表类型检查和作用域链怎么落地3.1 符号表的数据结构选型哈希表加作用域栈符号表的核心需求是进入一个作用域时能新建一层退出时能销毁这层查找变量时从内层往外层找。常见做法是用一个栈栈里每个元素是一个哈希表表示一层作用域。查找时从栈顶往下遍历找到第一个匹配就返回。插入时只往栈顶那层插。class SymbolTable: def __init__(self): self.scopes [{}] # 栈底是全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, type_): if name in self.scopes[-1]: raise SemanticError(fduplicate declaration: {name}) self.scopes[-1][name] type_ def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise SemanticError(fundeclared identifier: {name})逻辑说明scopes列表模拟栈scopes[-1]是当前作用域。declare只查当前层是否重复因为不同作用域允许同名变量。lookup从内往外找实现遮蔽shadowing语义。参数上如果语言支持函数函数名和变量名可以放在同一张表但函数参数需要单独处理进入函数体时先enter_scope再把参数声明进去。失败时看SemanticError的变量名基本能定位到是声明漏了还是作用域没退出。3.2 类型检查二元运算的类型推导规则类型检查的核心是给每个表达式算出一个类型然后检查运算符是否支持这些类型。常见规则是算术运算符 - * /要求两边都是数值类型如果一边是 int 一边是 float结果提升为 float比较运算符要求两边类型可比较结果是 bool赋值运算符要求右边类型能赋给左边。def check_expr(node, symtab): if isinstance(node, Leaf): if node.token.type INT: return int if node.token.type FLOAT: return float if node.token.type ID: return symtab.lookup(node.token.value) if isinstance(node, BinOp): lt check_expr(node.left, symtab) rt check_expr(node.right, symtab) if node.op in (, -, *, /): if lt not in (int, float) or rt not in (int, float): raise SemanticError(farithmetic on non-numeric: {lt}, {rt}) return float if float in (lt, rt) else int if node.op in (, , , , , !): if lt ! rt: raise SemanticError(fcomparison between {lt} and {rt}) return bool raise SemanticError(unknown expression node)逻辑说明check_expr递归下降返回类型字符串。算术运算里只要有一边是 float 就返回 float这是最常见的类型提升规则。比较运算要求两边类型相同避免int float这种隐式转换带来的歧义。参数上symtab是当前符号表查找变量类型时如果变量未声明会抛异常。失败时看异常里的类型名能判断是类型不匹配还是变量没声明。3.3 作用域链与变量生命周期进入和退出块时做什么作用域链的维护要和语法树遍历绑定。常见做法是在遍历到块语句{ ... }时先enter_scope()遍历完块内语句后exit_scope()。函数调用时进入函数体前先enter_scope()把参数声明进去函数体遍历完再exit_scope()。这样变量的生命周期就和语法块对齐退出块后变量不可见。注意一个坑如果语言支持在for循环里声明循环变量循环变量的作用域应该只覆盖循环体而不是整个外层块。我一般会在遍历for节点时单独enter_scope()把循环变量声明进去然后遍历循环体和步进表达式最后exit_scope()。这样循环结束后循环变量就查不到了符合大多数语言的语义。4. 中间代码与目标代码生成四元式到栈式指令的翻译4.1 四元式设计op、arg1、arg2、result 四元组中间代码我推荐用四元式因为结构简单、生成和优化都方便。每条四元式是(op, arg1, arg2, result)比如(, a, b, t1)表示t1 a b。常见操作包括算术运算、赋值、条件跳转、无条件跳转、函数调用、返回。临时变量用t1、t2递增生成标签用L1、L2递增生成。class QuadGen: def __init__(self): self.quads [] self.temp_count 0 self.label_count 0 def new_temp(self): self.temp_count 1 return ft{self.temp_count} def new_label(self): self.label_count 1 return fL{self.label_count} def emit(self, op, arg1None, arg2None, resultNone): self.quads.append((op, arg1, arg2, result)) return result逻辑说明emit是唯一往quads里追加的入口方便后续加优化 pass。new_temp和new_label保证名字不重复。参数上arg1和arg2可以是变量名、常量或临时变量result通常是临时变量或变量名。生成完所有四元式后可以打印出来人工检查这是调试代码生成最有效的手段。4.2 表达式和控制流的四元式生成表达式生成用后序遍历先递归生成左子树和右子树的四元式拿到结果变量再生成当前运算符的四元式。控制流生成用回填backpatching或者先占位后回填标签。常见做法是if语句先生成条件表达式的四元式然后生成条件跳转到else标签的四元式再生成 then 块的代码最后生成else标签和 else 块代码。def gen_expr(node, qg): if isinstance(node, Leaf): return node.token.value if isinstance(node, BinOp): left gen_expr(node.left, qg) right gen_expr(node.right, qg) temp qg.new_temp() qg.emit(node.op, left, right, temp) return temp def gen_if(node, qg): cond gen_expr(node.cond, qg) else_label qg.new_label() end_label qg.new_label() qg.emit(jz, cond, None, else_label) # 条件为假跳 else for stmt in node.then_body: gen_stmt(stmt, qg) qg.emit(jmp, None, None, end_label) qg.emit(label, None, None, else_label) for stmt in node.else_body: gen_stmt(stmt, qg) qg.emit(label, None, None, end_label)逻辑说明gen_expr返回表达式结果所在的变量名或常量。gen_if先生成条件然后jz跳转到 else 标签then 块结束后jmp到 end 标签避免执行 else 块。参数上jz表示“为零跳转”如果条件结果是 bool可以约定 0 为假、非 0 为真。失败时看四元式列表能发现标签重复或跳转目标不存在的问题。4.3 目标代码生成栈式虚拟机的指令选择目标代码生成我推荐先定一个简单的栈式虚拟机指令集比如PUSH、POP、ADD、SUB、MUL、DIV、LOAD、STORE、JMP、JZ、CALL、RET。然后写一个翻译器把四元式逐条翻译成这些指令。栈式虚拟机的好处是表达式求值天然用栈不用考虑寄存器分配课设规模足够用。def gen_target(quads): code [] for op, arg1, arg2, result in quads: if op : code.append(fLOAD {arg1}) code.append(fLOAD {arg2}) code.append(ADD) code.append(fSTORE {result}) elif op jz: code.append(fLOAD {arg1}) code.append(fJZ {result}) elif op label: code.append(f{result}:) elif op jmp: code.append(fJMP {result}) # 其他指令类似处理 return code逻辑说明每条四元式翻译成一段栈指令。算术运算先LOAD两个操作数再执行运算结果STORE到目标变量。jz先LOAD条件再JZ到标签。label直接输出标签定义。参数上LOAD和STORE的操作数可以是变量名或临时变量虚拟机需要维护一个变量表和一个栈。失败时看生成的指令序列能发现栈不平衡或跳转目标错误。5. 避坑与排查编译课设里最容易翻车的五个地方5.1 词法分析把关键字当标识符现象是 if 被解析成变量现象语法分析时报“unexpected ID”但源码里明明写的是if。原因词法分析读完标识符后没有查关键字表直接返回了ID。解决在标识符分支读完字符串后先查KEYWORDS集合命中就返回关键字类型否则返回ID。注意关键字表要用frozenset并且大小写敏感要和语言定义一致。5.2 递归下降左递归导致栈溢出现象是解析表达式时无限递归现象解析123时程序卡死或栈溢出。原因文法写成左递归expr - expr term递归下降直接翻译会无限调用parse_expr。解决把左递归改成循环即parse_expr先调parse_term然后用 while 循环处理后续的和-。这是递归下降的标准做法改完后左结合自然成立。5.3 符号表作用域没退出现象是块内变量在块外还能查到现象在{ int x; }之后还能查到x。原因遍历块语句时只enter_scope()没exit_scope()或者异常路径提前返回导致没退出。解决用try/finally包住块遍历确保无论是否抛异常都exit_scope()。另外检查for循环的循环变量作用域确保只覆盖循环体。5.4 四元式临时变量重复现象是不同表达式用了同一个 t1现象两个不相关的表达式都生成t1导致目标代码里值被覆盖。原因new_temp的计数器在某个分支里被重置或者多个QuadGen实例共享了计数器。解决确保整个编译过程只有一个QuadGen实例temp_count只增不减。如果支持函数每个函数可以独立计数但函数内必须唯一。5.5 目标代码栈不平衡现象是虚拟机执行到一半栈下溢现象运行目标代码时报栈下溢或结果错误。原因某条四元式翻译时LOAD了操作数但没STORE结果或者JZ之前多压了一个值。解决逐条对照四元式和目标指令确保每条四元式翻译后栈深度变化符合预期。算术运算栈深度先加二再减一STORE减一JZ减一。写个简单的栈深度检查器在生成每条指令后断言深度非负。6. 进阶技巧用解释器验证四元式再生成目标代码如果你时间紧或者目标代码生成一直调不通我建议先写一个四元式解释器直接执行四元式列表验证语义是否正确。解释器比目标代码生成简单得多维护一个变量表和一个临时变量表逐条执行四元式遇到就从表里取两个操作数相加存到 result。这样你能快速确认词法、语法、语义、中间代码这条链路是通的把问题隔离在目标代码生成这一环。def interpret(quads): env {} pc 0 labels {q[3]: i for i, q in enumerate(quads) if q[0] label} while pc len(quads): op, arg1, arg2, result quads[pc] if op : env[result] env.get(arg1, arg1) env.get(arg2, arg2) elif op -: env[result] env.get(arg1, arg1) - env.get(arg2, arg2) elif op : env[result] env.get(arg1, arg1) elif op jz: if not env.get(arg1, arg1): pc labels[result] continue elif op jmp: pc labels[result] continue elif op label: pass pc 1 return env逻辑说明env同时存变量和临时变量labels预扫描所有标签的位置。jz和jmp直接改pc注意改完要continue跳过pc 1。参数上env.get(arg1, arg1)的意思是如果arg1是变量就取变量值如果是常量就直接用常量。这个解释器跑通后再用它对照目标代码的执行结果两边一致就说明代码生成正确。验证方法上我一般会准备一组测试用例纯算术表达式、带括号的嵌套表达式、if-else、while 循环、变量声明和赋值。每个用例先用解释器跑一遍记录输出再用目标代码跑一遍对比结果。如果结果不一致就逐条打印四元式和目标指令找到第一条分叉的地方。这个习惯帮我省了很多“后悔药”因为问题定位从“整个编译器不对”缩小到“某条四元式翻译错了”。最后一个技巧把四元式和目标指令都输出到文件用 diff 对比不同版本的变化。改代码生成时diff 能让你一眼看出哪些指令变了避免引入回归。我一般会在项目根目录放一个tests/目录每个用例一个输入文件和一个期望输出文件跑一遍脚本自动对比。这样每次改完编译器跑一遍测试就知道有没有翻车。希望帮到你。本文还有配套的精品资源点击获取