简介编译原理课程设计学习包面向高校计算机专业学生及需要完成编译原理实验、课程设计的学习者围绕词法分析、语法分析与小型编译器实现提供一套可参考的完整材料。内容覆盖词法分析器设计、LL(1)方法分析简单语句如 ii*i、LR(0)与SLR(1)语法分析、四元式生成及汇编代码生成并附小型编译器课程设计报告便于对照理解从源程序到中间代码、目标代码的基本流程。压缩包共14个文件以cpp、c、h源码为主体配套txt说明与doc实验报告整体约557KB结构紧凑适合在本地编译调试和二次整理。已有2350人学习下载读者可借此复现词法、语法分析实验梳理LL(1)与SLR(1)文法的处理思路并参考报告组织课设文档与实现步骤。1. 期末两周做完一个小型编译器这份课设资源能给你什么期末周最难受的不是不会写是明知道要交什么却拼不起来——编译原理课程设计要求词法分析、语法分析、中间代码、实验报告一条龙单拎哪块都能讲两句合到一起就跑不动。这份资源给的是一套能直接运行的小型编译器读入一段类 C 源码切成 Token、建语法树、生成四元式附实验报告从需求分析到测试用例都有。适合两类人一类是离答辩只剩两周的一类是想亲手摸一遍编译器前端到底长什么的。它不是糊弄人的伪代码词法用手写状态机语法用递归下降中间代码带回填留足了二次开发的下手位置。2. 五段流水线与目录结构从 .src 文件到四元式列表先把整体架子摆清楚后面看代码才不迷路。很多课设翻车不是算法写错是文件职责没分干净词法分析里顺手做了类型判断语法分析里又去查符号表最后改一处崩三处。2.1 五段流水线每一段只认上一段的输出一份合格的课程设计编译器前端分四步走加一层驱动阶段输入输出职责边界词法分析源码字符串Token 列表只认字符不认语法语法分析Token 列表AST只认结构不查类型语义分析AST带类型的 AST查符号表、报重定义中间代码生成带类型 AST四元式列表只做翻译不做优化驱动 main文件路径各阶段 dump串流程、打印中间结果这条线的好处是可切分验证。词法写完先拿一堆 Token 对语法写完先打印 AST 看括号挂对没中间代码写完再拿四元式手推一遍结果。出问题时你能一眼看出是哪一段的输出不对而不是对着最终报错猜。我一般会在main.py里留一个--dump参数把每个阶段的中间结果打出来。答辩现场老师随口说你把 Token 流打出来看看你能立刻打出来这分就稳了。2.2 目录结构与文件职责典型的课设目录不长这样才怪mini-compiler/ ├── main.py # 驱动读文件、串流水线、按 --dump 打印 ├── lexer.py # 词法分析字符流 - Token ├── parser.py # 语法分析Token - AST ├── ast_nodes.py # AST 节点定义只放数据结构 ├── semantic.py # 符号表、重定义与未定义检查 ├── codegen.py # AST - 四元式含回填 ├── errors.py # 统一异常带行号列号的 CompileError ├── examples/ # 用例demo1.src 起手error_*.src 是反例 └── report/ # 实验报告、文法、测试记录ast_nodes.py单独拆出来是个小习惯但很值。解析器和代码生成器都 import 它谁也不用 import 谁避免循环依赖——这个坑在 Python 里特别容易踩一踩就是 ImportError 加一堆看不懂的栈。errors.py里只放一个异常类构造函数收msg、line、col__str__拼成第 3 行第 12 列: 期望 ) 实际 ;。全流程只抛这一种异常main.py里一个except CompileError就能统一收口报错格式整齐实验报告里也好截图。2.3 环境与运行三条命令跑通第一个用例不需要任何第三方包Python 3.8 以上标准库够用。如果课设指定 C/C把同样的结构照搬过去只是字符串处理和内存管理要自己上心尤其 Token 的 text 记得 free。# 1. 看版本避免环境里只有 python2 python3 -V # 2. 不加参数时走默认用例并打印四元式 python3 main.py examples/demo1.src # 3. 需要中间结果时指定要 dump 的阶段 python3 main.py examples/demo1.src --dump tokens,ast,quadsdemo1.src里塞一段十几行的代码就够验证了int a; int b; a 3; b 4; if (a b) { print a b * 2; } else { print b - a; }跑出来的四元式大致长这样_表示该字段不用000: 3 _ a 001: 4 _ b 002: a b t1 003: jf t1 _ 006 004: * b 2 t2 005: a t2 t3 006: print t3 _ _ ...对着这段手推一遍能立刻发现优先级有没有错b * 2排在a t2前面说明乘法的递归层比加法深一层。这种看输出反推代码的验证方式比写十个断言都快。2.4 数据契约Token 与 AST 的字段定死之后流水线能串起来的前提是相邻两段的数据结构约定死中间不许私下加字段。Token 就三个半字段多一个都嫌重from dataclasses import dataclass dataclass class Token: kind: str # 记号类别如 NUM / ID / KW_IF / OP_PLUS / EOF text: str # 原文报错和实验报告里都要用 line: int # 起始行从 1 开始 col: int # 起始列从 1 开始kind用字符串而不用枚举是权衡后的选择课设规模下字符串可读性更重要--dump tokens打出来直接能看调试时省一半时间。真要做大再换成IntEnum改起来也就几十行。AST 节点同理每个节点只放子节点引用和必要字段不放父节点指针这种方便但不必要的东西——加了就要维护维护就要出错class Node: pass dataclass class Num(Node): value: int dataclass class Var(Node): name: str dataclass class BinOp(Node): op: str left: Node right: Node dataclass class Assign(Node): name: str expr: Node dataclass class If(Node): cond: Node then: list other: list dataclass class While(Node): cond: Node body: list dataclass class Print(Node): expr: Nodethen和other用 list 存语句序列天然支持语句块也省掉了单独的 Block 节点。代价是遍历时多一层循环但这点开销换来的结构简单值。3. 词法分析模块手写 DFA 把字符流切成带行号的 Token词法分析是整个流水线里最容易写、也最容易写歪的一段。歪的地方通常集中在两处最长匹配没做和行列号没记对。前面那个会让你把切成两个后面那个会让你的报错信息在答辩时变成笑话。3.1 状态设计四种状态够用了手写 DFA 不需要真的画状态转移表用 if-else 分支表达等价的状态迁移就行关键是心里要有那张图状态吃进什么迁移到产出起始空白起始无起始数字数字态无起始字母或下划线标识符态无数字态数字数字态无数字态非数字起始NUM标识符态字母数字下划线标识符态无标识符态其他起始ID 或关键字这张表就是全部逻辑。别上来就写正则课设要的是你能讲清状态怎么迁移re.findall一行解决战斗但答辩问一句你这个 DFA 有几个状态就答不上来。3.2 扫描主循环一个 while 加三个分发主循环只负责看一眼当前字符属于哪类交给对应的子过程处理不掺业务逻辑KEYWORDS {if, else, while, int, return, print} class Lexer: def __init__(self, src: str): self.src src self.i 0 self.line 1 self.col 1 self.tokens [] def _advance(self) - str: 吃进一个字符同时维护行列号。所有前进都必须走这里。 ch self.src[self.i] self.i 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def _peek(self, k: int 0) - str: 只看不吃越界返回空串省掉一堆边界判断。 j self.i k return self.src[j] if j len(self.src) else def tokenize(self) - list: while self.i len(self.src): ch self._peek() if ch in \t\r\n: self._advance() # 空白直接吞掉不产 Token elif ch.isdigit(): self.tokens.append(self._number()) elif ch.isalpha() or ch _: self.tokens.append(self._ident()) elif ch in -*/(){};,!: self.tokens.append(self._operator()) else: raise CompileError(f非法字符 {ch!r}, self.line, self.col) self.tokens.append(Token(EOF, , self.line, self.col)) return self.tokens几个细节值得说_advance是所有字符前进的唯一入口行号列号只在这里改。新手常犯的错是在_number里直接self.i 1结果数字后面的换行没被算进行号报错就偏一行。_peek越界返回空串这样上层写while self._peek().isdigit()时不用每次判断下标空串的isdigit()是 False循环自然停。末尾一定补一个EOFToken。语法分析里凡是遇到看到文件结尾还不知道该干嘛的情况靠这个哨兵统一处理比到处判self.i len(...)干净得多。3.3 最长匹配与关键字表不能切成两个运算符这块最容易图省事写成单字符然后if (a b)直接报语法错。正确做法是先看两个字符命中双字符运算符再消费第二个def _operator(self) - Token: line, col self.line, self.col ch self._advance() pair ch self._peek() if pair in (, !, , ): self._advance() return Token(OP_ pair, pair, line, col) return Token(OP_ ch, ch, line, col) def _number(self) - Token: line, col self.line, self.col buf [] while self._peek().isdigit(): buf.append(self._advance()) return Token(NUM, .join(buf), line, col) def _ident(self) - Token: line, col self.line, self.col buf [] while self._peek().isalnum() or self._peek() _: buf.append(self._advance()) text .join(buf) # 先按标识符扫完再查关键字表天然满足最长匹配 kind KW_ text.upper() if text in KEYWORDS else ID return Token(kind, text, line, col)关键字的处理方式很值得讲一句不要一开始就按关键字前缀去匹配而是先把整个标识符扫出来再查表。ifx这种标识符如果按前缀匹配就会被切成ifx查表法天然不会错。这就是最大匹配原则最简单的落地形式。_number现在只认整数。要支持小数加一个见过点没有的布尔标志在循环里允许消费一次.再把int(text)换成float(text)要支持十六进制在开头判断0x。改动都在十行以内实验报告里扩展性那一节正好写这个。3.4 错误定位行号列号是给答辩老师看的CompileError的构造函数收三个参数__str__输出成人类能读的格式class CompileError(Exception): def __init__(self, msg: str, line: int, col: int): self.msg, self.line, self.col msg, line, col def __str__(self): return f第 {self.line} 行第 {self.col} 列: {self.msg}main.py里统一捕获打印后sys.exit(1)不吐栈。实验报告的错误处理章节可以直接贴这条报错比贴一坨 Traceback 有说服力。提示列号用 1 开始而不是 0 开始。虽然内部下标是 0 起但面向人的输出统一 1 起别让老师数着数着发现差一位。写到这里词法这一段其实就完整了。跑--dump tokens输入a 3 4 * 2;应该看到ID(a) OP_ NUM(3) OP_ NUM(4) OP_* NUM(2) OP_; EOF顺序和数量都对上再往下走语法。4. 语法分析与中间代码递归下降建 AST回填法出四元式语法分析是课设的重头戏也是实验报告里篇幅最大的一章。它的核心工作只有一句话把线性的 Token 序列变成有层次的树。中间代码生成则是把这棵树再压平成四元式。两件事放一章讲是因为它们共用同一套递归遍历的节奏。4.1 文法改造先把左递归消掉再动手课本上的表达式文法通常长这样E - E T | T T - T * F | F F - ( E ) | id | num这是左递归递归下降直接照着写会无限递归——parse_E()一进来就调parse_E()栈直接爆。必须改写成右递归形式E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id | num但改写之后有个副作用结合性反了。1 - 2 - 3按右递归解析会变成1 - (2 - 3)算出来是 2 而不是 -4。这是课设里最经典的翻车点之一答辩时老师随口给个减法是左结合的例子就能问住。我一般不真的按 E 写而是用循环表达左递归E - T { (|-) T } T - F { (*|/) F } F - ( E ) | id | num循环天然左结合每绕一圈就把左边的结果当成新的左操作数。代码也更短。4.2 表达式解析三层递归一层管一个优先级按上面的文法表达式解析拆成三个方法逐层下降class Parser: def __init__(self, tokens): self.toks tokens self.p 0 def peek(self, k: int 0) - Token: return self.toks[min(self.p k, len(self.toks) - 1)] def eat(self, kind: str None) - Token: tok self.peek() if kind and tok.kind ! kind: raise CompileError(f期望 {kind}实际 {tok.kind}({tok.text}), tok.line, tok.col) self.p 1 return tok # expr : add def parse_expr(self) - Node: return self.parse_add() # add : mul { (|-) mul } def parse_add(self) - Node: node self.parse_mul() while self.peek().kind in (OP_, OP_-): op self.eat().text node BinOp(op, node, self.parse_mul()) # 左结合新节点挂左边 return node # mul : atom { (*|/) atom } def parse_mul(self) - Node: node self.parse_atom() while self.peek().kind in (OP_*, OP_/): op self.eat().text node BinOp(op, node, self.parse_atom()) return node # atom : num | id | ( expr ) def parse_atom(self) - Node: tok self.peek() if tok.kind NUM: self.eat() return Num(int(tok.text)) if tok.kind ID: self.eat() return Var(tok.text) if tok.kind OP_(: self.eat() node self.parse_expr() self.eat(OP_)) return node raise CompileError(f表达式里出现意外的 {tok.kind}({tok.text}), tok.line, tok.col)三个方法的调用关系就是优先级顺序parse_add里的操作数来自parse_mul所以乘法永远比加法先结合成子树。node BinOp(op, node, ...)这行把已有子树放左边是左结合的实现关键写成BinOp(op, ..., node)就变右结合了一个字的位置差别。eat(kind)带默认参数不传就随便吃一个用在已知当前 Token 类型、只想前进的场景。传了就做强校验不匹配直接抛带位置的异常。这种校验前移的写法能让报错停在最接近出错点的地方而不是等三层递归返回后才报一个笼统的错。4.3 语句解析用首 Token 做分发语句层用最朴素的预测分析——看一眼当前 Token 是什么类型就知道该走哪个分支因为每条语句的首记号都不同# program : stmt* def parse_program(self) - list: stmts [] while self.peek().kind ! EOF: stmts.append(self.parse_stmt()) return stmts def parse_stmt(self) - Node: tok self.peek() if tok.kind KW_INT: # int a 3; self.eat() name self.eat(ID).text self.eat(OP_) return Assign(name, self.parse_expr()) if tok.kind KW_IF: # if (c) {...} else {...} self.eat() self.eat(OP_() cond self.parse_expr() self.eat(OP_)) then self.parse_block() other [] if self.peek().kind KW_ELSE: self.eat() other self.parse_block() return If(cond, then, other) if tok.kind KW_WHILE: # while (c) {...} self.eat() self.eat(OP_() cond self.parse_expr() self.eat(OP_)) return While(cond, self.parse_block()) if tok.kind KW_PRINT: # print e; self.eat() expr self.parse_expr() self.eat(OP_;) return Print(expr) if tok.kind ID: # a e; name self.eat().text self.eat(OP_) expr self.parse_expr() self.eat(OP_;) return Assign(name, expr) raise CompileError(f不能作为语句开头: {tok.kind}({tok.text}), tok.line, tok.col) def parse_block(self) - list: self.eat(OP_{) body [] while self.peek().kind ! OP_}: body.append(self.parse_stmt()) self.eat(OP_}) return bodyparse_stmt里if tok.kind ID那一支要放在最后判断因为它最宽泛。如果把 ID 判断写到最前面int这种关键字 Token 类型是KW_INT不会命中倒也不会错但逻辑上不够清晰。分发顺序按越具体越靠前排是让代码自己说明意图。parse_block里while self.peek().kind ! OP_}这个循环没有 EOF 保护如果源码少了个右花括号会一直读到 EOF 然后eat(OP_})抛错。报错位置在文件末尾不够精准但也不会死循环。要更友好一点循环条件里加个 EOF 判断抛缺少 }。4.4 四元式生成回填把待定的跳转目标补上中间代码用四元式(op, arg1, arg2, result)。表达式部分的生成是纯递归把每个子表达式算成一个临时变量名class CodeGen: def __init__(self): self.quads [] self.tmp 0 self.label 0 def new_tmp(self) - str: self.tmp 1 return ft{self.tmp} def emit(self, op: str, a1, a2, res) - int: self.quads.append([op, a1, a2, res]) return len(self.quads) - 1 # 返回下标方便回填 def gen_expr(self, node) - str: if isinstance(node, Num): return str(node.value) if isinstance(node, Var): return node.name if isinstance(node, BinOp): l self.gen_expr(node.left) r self.gen_expr(node.right) t self.new_tmp() self.emit(node.op, l, r, t) return t raise TypeError(f未知表达式节点 {type(node)})emit返回刚生成的那条四元式的下标是整个回填机制的基础。有了这个下标后面发现跳转目标还没确定时就能回到这条指令把res补上。条件跳转的关键在于生成if语句时jf条件为假则跳转的目标位置要等到then块全部生成完才知道。所以先发一条占位的jf记下下标等 then 块生成完再回头填def gen_stmts(self, stmts: list): for s in stmts: self.gen_stmt(s) def gen_stmt(self, node): if isinstance(node, Assign): v self.gen_expr(node.expr) self.emit(, v, _, node.name) elif isinstance(node, Print): v self.gen_expr(node.expr) self.emit(print, v, _, _) elif isinstance(node, If): c self.gen_expr(node.cond) jf self.emit(jf, c, _, None) # 假跳目标待回填 self.gen_stmts(node.then) if node.other: j self.emit(j, _, _, None) # then 结束跳过 else self.quads[jf][3] len(self.quads) # 回填假跳到 else 开头 self.gen_stmts(node.other) self.quads[j][3] len(self.quads) # 回填跳过 else 的出口 else: self.quads[jf][3] len(self.quads) # 无 else直接跳到结尾 elif isinstance(node, While): start len(self.quads) # 循环条件的位置 c self.gen_expr(node.cond) jf self.emit(jf, c, _, None) self.gen_stmts(node.body) self.emit(j, _, _, start) # 无条件跳回条件判断 self.quads[jf][3] len(self.quads) # 条件为假跳出循环len(self.quads)在任何时刻都等于下一条要生成的指令下标所以它天然就是当前位置拿来回填再合适不过。这种技术叫回填backpatching课设里能把它写对实验报告的技术含量就上去了。while那段先记start len(self.quads)生成的循环末尾j直接指向start形成回边。注意j用的是无条件跳转条件判断已经在上面用jf做过了这里不用重复。入口驱动很简单def compile_source(src: str) - list: tokens Lexer(src).tokenize() ast Parser(tokens).parse_program() cg CodeGen() cg.gen_stmts(ast) return cg.quads拿 2.3 那个 demo 跑一遍重点检查两处if的jf目标是else块的第一条else块结束的j目标是整个 if 之后的第一条。这两条对上了控制流就对了。再把while版本的用例跑一下看最后一条j是不是跳回了条件判断的位置。手推一遍比啥都靠谱。5. 避坑与排查七个把课设拖到通宵的问题这一章是本篇里最应该先看的部分。下面这七条每一条我都在不同人的课设里见过代价从两小时到一整晚不等。5.1 减法算出来的结果是反的现象print 10 - 3 - 2;输出 9 而不是 5四元式里能明显看到3 - 2先算。原因照搬课本把左递归改成了右递归形式E - T E改完没管结合性。右递归天然右结合链式减法就从左往右算变成了从右往左算。解决别真的写 E用while循环表达重复部分每轮把已有子树挂到左边。3.2 节那个parse_add就是正确写法node BinOp(op, node, ...)里node在前就保证了左结合。改完拿10 - 3 - 2和10 / 5 / 2各跑一次结果分别是 5 和 1就算过了。5.2被切成两个等号现象写的if (a b)报表达式里出现意外的 OP_或者更隐蔽地条件恒为真。原因词法里运算符只看了单个字符第一个就产出了 Token第二个又产出一次语法分析拿到两个连续的赋值号直接懵。解决在_operator里先拼两个字符看一下命中双字符运算符再消费第二个。注意判断顺序要先长后短先试再试反过来永远匹配不到双字符。词法改完把所有运算符列一遍对着--dump tokens检查 ! - * /十个都要对。5.3 报错的行号总是偏一行现象明明错在第 5 行报错说第 4 行或者列号永远停在 1。原因某些分支里直接写了self.i 1绕过_advance换行符没被计入行号。常见于数字扫描里图快直接加下标。解决全项目搜self.i 除了_advance内部那一处其他全删掉改成调用_advance()。再补一个自测故意在第 3 行末尾放个非法字符跑一次确认报的是第 3 行。这条自测值得写进实验报告的测试记录表。5.4 四元式里打印出None现象--dump quads打出来的跳转指令目标位是None或者运行到一半死循环。原因回填漏了分支。最常见的是if没有else时忘了回填jf的目标或者while的jf忘了指向循环出口。解决在gen_stmt结尾加一条断言遍历self.quads凡是op是jf或j的检查res不为None且落在[0, len(quads)]区间内。这条断言用不了几行但能把回填遗漏从运行半天发现不对提前到生成完立刻报错。另外注意回填的目标允许等于len(quads)也就是跳到末尾这不算越界。5.5 内层变量覆盖了外层同名变量现象int a; { int a; a 1; } print a;打印出 1而按作用域规则外层a应该还是原值或者未定义。原因符号表用了一个全局 dict进块不压栈、出块不弹栈内层定义直接覆盖外层同名项。解决符号表做成栈enter_scope()压一个空 dictexit_scope()弹掉。查找时从栈顶往下找命中即返回定义时只看栈顶那一层有同名就报重复定义。这条改动会牵连语义分析的所有查表调用建议先写两个用例把行为固定下来再动代码。5.6 输入文件读进来第一行就报非法字符现象源文件第一行没写错但词法直接抛非法字符。原因文件开头带了 BOM\ufeffWindows 记事本保存 UTF-8 时默认会加。词法器不认识这个字符。解决读文件时用encodingutf-8-sigPython 会自动吃掉 BOM。这条不算编译原理的内容但确实是真实会卡住人的问题写进实验报告的环境说明里不亏。5.7 答辩演示时用例跑不出结果现象本地跑得好好的换台机器现场演示就报错。原因examples/里用了相对路径或者注释里写了中文但文件不是 UTF-8或者依赖了某个只在本地装过的包。解决入口里所有路径基于os.path.dirname(__file__)拼绝对路径文件读取统一指定encodingutf-8-sig依赖只留标准库。演示前在干净环境里完整跑一遍全部用例包括error_*.src那些反例——反例能正常报错比正例跑通更能说明实现完整。6. 二次开发在骨架上加 for 循环和数组的改法与验证课设交完只是开始真要拿这份东西去应付后续的课程或者面试展示得能往上加东西。这套结构的好处是每个扩展点都落在单一文件里改动边界清楚扩展点改动文件大致工作量验证方式支持for循环parser.py、ast_nodes.py、codegen.py60 行左右降糖成 while 后对比四元式支持复合赋值lexer.py、parser.py20 行展开成a a b后比对支持一维数组全部四个文件150 行左右下标越界与未定义各一个反例支持floatlexer.py、codegen.py30 行混合类型运算的类型提升顺序加常量折叠优化codegen.py 前插一遍40 行四元式条数明显变少最省事的第一个扩展是for因为它不需要改中间代码生成器——在parse_stmt里把for(i0; in; ii1)解析出来直接构造一个While节点返回就行后面的代码生成器根本不知道有 for 这回事# for (init; cond; step) body { init; while (cond) { body; step; } } def parse_for(self) - list: self.eat(KW_FOR) self.eat(OP_() init self.parse_stmt() # 复用语句解析注意它已经吃掉了分号 cond self.parse_expr() self.eat(OP_;) step self.parse_stmt() # 同理i i 1; self.eat(OP_)) body self.parse_block() return [init, While(cond, body [step])]这里有个前提parse_stmt里赋值语句那一支已经吃掉了结尾的分号所以parse_for里不用再eat(OP_;)。这种复用带副作用的解析函数省代码但要求你对每个函数的消费边界心里有数写之前先确认一遍。验证这类语法糖最有效的方法是对比四元式把for版本和手写的等价while版本各编译一次两份四元式列表应该完全一致。不一致就说明降糖过程中语句顺序或跳转目标错了。这个方法我后来用在很多地方——凡是语法糖展开的改动都拿原语写法的输出做黄金基准比肉眼检查可靠得多。数组的改动大一些核心是两件事词法里加[]语法上区分变量和下标访问代码生成里用一条[]或[]四元式表达。符号表要记录每个标识符的类型和长度语义分析时检查下标访问的对象确实是数组。至于常量折叠在gen_expr碰到BinOp且左右都是Num时直接算完返回不发射四元式就行。四行代码但实验报告的优化章节就有了实打实的内容可以写。从我自己的教训说一句每次改动前先把当前所有用例的输出存成一份基线改完逐行 diff。我吃过一次亏为了加个顺手调了_operator里的匹配顺序结果和全反了等到答辩前两小时才发现。从那以后我每次动词法或文法都强制先把全部用例跑一遍存基线再改不管改动看起来多小。希望帮到你。本文还有配套的精品资源点击获取
