简介面向计算机专业学生与编译原理初学者这份北邮编译原理课程设计资料围绕Pascal语言编译器的完整实现展开覆盖词法分析、语法分析、语义分析、代码生成及符号表管理、错误处理等核心环节可作为课程实验与编译器构造入门的参考案例。压缩包共83个文件约123KB以C头文件与源文件承担编辑器、虚拟机和编译流程实现pas与asm文件提供Pascal及汇编测试样例bin、rez、rc等用于运行与界面资源另含Visual C工程配置便于按模块梳理项目结构。已有1195人学习下载说明其在同类课程设计中具有一定参考价值。读者可对照AST构造、上下文无关文法解析、三地址码生成与优化思路结合测试样例观察从源代码到目标代码的转换过程并借鉴符号表组织和错误报告机制为完成自己的编译器课程设计提供可复用的实现框架与排错线索。1. 编译原理课程设计难点不在算法在端到端跑通编译原理课程设计这个题目落到任务书上往往只有一句话给一个精简语言子集实现从源码到三地址码、有条件的话再到简单目标码的完整通路附带错误定位和一组测试用例。真坐下来写才会发现卡人的从来不是那些自动机理论而是词法分析、语法分析、语义检查、中间代码这几段单独拎出来都能跑拼在一起就崩——AST 少了一个节点、作用域离开代码块时没弹栈、临时变量编号撞车、错误信息指到上一行。这篇按一条能端到端跑通的路线往下拆先把语言子集和 AST 钉死再手写扫描器、递归下降解析器、符号表与三地址码生成最后用差分测试验收。适合刚拿到题目不知道从哪下手的人也适合扫描器写完了但 AST 建歪、正准备推倒重来的人。2. 语言子集与词法分析先定 EBNF再写扫描器课程设计的评分看的是完整性和正确性不是语言特性多。我带人做这类题时见过最多的一种翻车是有人一上来就想支持数组、字符串、结构体写到语义分析发现每个特性都要在符号表、类型检查、代码生成三处各改一遍最后交上去的是一个「每样都支持一点、每样都跑不全」的半成品。所以第一件事是把范围砍到能验收的最小集。2.1 用 EBNF 把语言子集写成可验收的清单我一般会把语言写成下面这张表左边是产生式右边写清楚为什么这么定。这张表不只是给自己看的它同时是验收标准产生式里有的必须实现产生式里没有的遇到就报语法错不要偷偷放过。产生式覆盖特性课设里的取舍理由Program → FuncDef至少一个函数强制有入口函数代码生成时有明确起点FuncDef → Type ID ( ParamList? ) Block函数定义参数类型要参与检查返回值要参与 return 校验Type → int | bool | void三种类型两种值类型足够撑起类型检查void 只给函数返回用Stmt → VarDecl | Assign | If | While | Return | Print | Block | ;语句全集八种足够覆盖控制流和副作用VarDecl → Type ID ( Expr)? ;声明带可选初始化初始化表达式要参与类型检查不能只存字面量If → if ( Expr ) Stmt (else Stmt)?条件分支单语句分支会引出悬空 else见 5.1Expr → LogicOr表达式入口分层文法每层一个函数避免一个函数写两百行表达式那几层按优先级从低到高排开LogicOr → LogicAnd (|| LogicAnd)*、LogicAnd → Equality ( Equality)*、Equality → Relational (( | !) Relational)*、Relational → Additive (( | | | ) Additive)*、Additive → Mul (( | -) Mul)*、Mul → Unary ((* | / | %) Unary)*、Unary → (- | !) Unary | Primary。这份文法有个特点全部是右递归的没有一处左递归。写递归下降之前先做这一步改写比写完再对着报错改要省事得多原因在 3.1 展开。提示把这份 EBNF 直接贴进报告里同时把它当成测试用例的设计依据。每条产生式至少配一个用例覆盖率这一项就不用临时补。2.2 从产生式反推 AST 节点AST 节点不够用是最常见的返工点。写完语法分析才发现If没有 else 字段、Call没有存实参列表回头改节点意味着解析器、语义检查、代码生成三处一起改。我的做法是照着产生式逐个列节点产生式右部有几个成分节点就有几个字段。from dataclasses import dataclass, field from typing import List, Optional dataclass class Node: line: int # 起始行号报错和调试都靠它 col: int # 起始列号单行报错时能指到字符 dataclass class Program(Node): funcs: List[FuncDef] field(default_factorylist) dataclass class FuncDef(Node): name: str ret_type: str int params: List[Param] field(default_factorylist) body: Optional[Block] None dataclass class Param(Node): name: str typ: str int dataclass class Block(Node): stmts: List[Node] field(default_factorylist) dataclass class VarDecl(Node): name: str typ: str int init: Optional[Node] None dataclass class Assign(Node): target: str # 先存名字符号表解析放到语义阶段 value: Optional[Node] None dataclass class If(Node): cond: Optional[Node] None then: Optional[Node] None els: Optional[Node] None # 没有 else 就是 None不要用空 Block 占位 dataclass class While(Node): cond: Optional[Node] None body: Optional[Node] None dataclass class Return(Node): value: Optional[Node] None # void 函数里 return; 是合法的所以可空 dataclass class Print(Node): value: Optional[Node] None dataclass class BinOp(Node): op: str left: Optional[Node] None right: Optional[Node] None dataclass class UnaryOp(Node): op: str operand: Optional[Node] None dataclass class Num(Node): value: int 0 dataclass class BoolLit(Node): value: bool False dataclass class Var(Node): name: str dataclass class Call(Node): name: str args: List[Node] field(default_factorylist)这段代码有三个决定值得说清楚。第一line和col放在基类Node上且没有默认值子类字段都有默认值dataclass 的字段顺序正好合法这样每个节点天生带位置报错时不用再回查 token 流。第二Assign.target和Var.name存的是字符串而不是符号表指针因为语法分析阶段还不该建符号表两遍走法先建树、再做语义比一边解析一边查表好调试得多。第三If.els用None表示没有 else而不是塞一个空 Block——语义检查和代码生成里if node.els is not None这个判断比判断「空块」可靠。2.3 手写扫描器最大匹配、行列号与关键字表词法这一层生成器lex/flex 那一类在课设里其实不划算多一个工具链依赖调试时出错位置在生成代码里改一条规则要重新生成。手写一个三百行以内的扫描器逻辑全在眼前出问题直接打断点。核心就两条最大匹配能读多长读多长和位置维护每消费一个字符就更新行列号。KEYWORDS {int, bool, void, if, else, while, return, print, true, false} class Token: __slots__ (kind, text, line, col) def __init__(self, kind, text, line, col): self.kind, self.text, self.line, self.col kind, text, line, col def __repr__(self): return fToken({self.kind},{self.text!r},{self.line}:{self.col}) class Lexer: def __init__(self, src: str): self.src, self.i, self.line, self.col src, 0, 1, 1 def _peek(self, k0): j self.i k return self.src[j] if j len(self.src) else def _advance(self): ch self.src[self.i] self.i 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def tokens(self): out [] while self.i len(self.src): ch self._peek() if ch in \t\r\n: self._advance(); continue if ch / and self._peek(1) /: # 行注释 while self.i len(self.src) and self._peek() ! \n: self._advance() continue if ch.isdigit(): out.append(self._number()); continue if ch.isalpha() or ch _: out.append(self._ident()); continue out.append(self._symbol()) out.append(Token(EOF, , self.line, self.col)) return out def _number(self): line, col self.line, self.col buf [] while self._peek().isdigit(): buf.append(self._advance()) if self._peek().isalpha() or self._peek() _: # 12abc 这种写法必须显式报错静默截断成 12 会让后续错误指向别处 raise SyntaxError(f非法数字 at {line}:{col}) return Token(NUM, .join(buf), line, col) def _ident(self): line, col self.line, self.col buf [] while self._peek().isalnum() or self._peek() _: buf.append(self._advance()) text .join(buf) return Token(KW if text in KEYWORDS else ID, text, line, col) def _symbol(self): line, col self.line, self.col two self.src[self.i:self.i 2] if two in (, !, , , , ||): self._advance(); self._advance() return Token(OP, two, line, col) ch self._advance() if ch in -*/%!: return Token(OP, ch, line, col) if ch in (){};,: return Token(PUNCT, ch, line, col) raise SyntaxError(f未知字符 {ch!r} at {line}:{col})逻辑上分三层tokens()负责跳过空白和注释并分发_number/_ident/_symbol各自做最大匹配。_symbol先查两字符表再退回单字符这就是最大匹配的落地方式——优先于优先于。_advance里\n单独处理因为换行要重置列号如果把行列号更新散在各个分支里一定会漏。参数说明几处容易忽略的_peek(k)越界返回空串而不是抛异常这样所有判断都能写成self._peek() x不用额外判长度EOFtoken 带上当前行列号语法分析报「文件意外结束」时能指到文件末尾而不是 1:1KEYWORDS用集合而不是一长串if/elif加关键字只改一行。词法阶段不要急着建符号表。有人在扫描器里顺手维护一张name - id的哈希表觉得能省事结果语义分析要按作用域区分同名变量时这张全局表反而成了障碍。词法阶段只负责回答「这是个标识符」它叫什么、在哪一层作用域、什么类型全部留给语义分析。3. 语法分析递归下降加优先级爬升递归下降的好处是代码结构和文法一一对应报错位置天然准确代价是要先处理左递归还要自己管结合性。这两件事都有固定套路照着做基本不会翻车。3.1 消除左递归后的函数骨架左递归的产生式写成函数会无限递归。标准改写是把它转成循环E → E T | T改成E → T ( T)*代码形态就是一个while先解析一个 T然后只要当前 token 是就继续吃掉再解析一个 T。原产生式改写后代码形态E → E T | TE → T ( T)*left parse_T(); while cur : ...L → L , ID | IDL → ID (, ID)*items [parse_ID()]; while cur ,: ...S → Stmt S | εS → Stmt*stmts []; while not at(}): ...函数骨架按文法层次逐个写每层一个方法命名和产生式左部对齐回头查错时一眼能对上是哪条规则出的问题。class Parser: def __init__(self, tokens): self.toks, self.p, self.depth tokens, 0, 0 self.errors [] def cur(self): return self.toks[self.p] def at(self, text): return self.cur().text text def eat(self, kindNone, textNone): t self.cur() if kind and t.kind ! kind: raise SyntaxError(f期望 {kind}实际 {t.kind}({t.text!r}) at {t.line}:{t.col}) if text and t.text ! text: raise SyntaxError(f期望 {text!r}实际 {t.text!r} at {t.line}:{t.col}) self.p 1 return t def parse_program(self): funcs [] while self.cur().kind ! EOF: funcs.append(self.parse_func()) return Program(1, 1, funcs) def parse_func(self): t self.eat(KW) # int / bool / void name self.eat(ID).text self.eat(text() params [] if not self.at()): params.append(self.parse_param()) while self.at(,): self.eat(text,) params.append(self.parse_param()) self.eat(text)) body self.parse_block() return FuncDef(t.line, t.col, name, t.text, params, body) def parse_block(self): t self.eat(text{) stmts [] while not self.at(}): stmts.append(self.parse_stmt()) self.eat(text}) return Block(t.line, t.col, stmts) def parse_stmt(self): t self.cur() if t.text {: return self.parse_block() if t.kind KW: if t.text in (int, bool): return self.parse_vardecl() if t.text if: return self.parse_if() if t.text while: return self.parse_while() if t.text return: self.eat(KW) val None if self.at(;) else self.parse_expr() self.eat(text;) return Return(t.line, t.col, val) if t.text print: self.eat(KW); self.eat(text() val self.parse_expr() self.eat(text)); self.eat(text;) return Print(t.line, t.col, val) if t.kind ID and self.toks[self.p 1].text : name self.eat(ID).text self.eat(text) val self.parse_expr() self.eat(text;) return Assign(t.line, t.col, name, val) if t.text ;: self.eat(text;) return Block(t.line, t.col, []) raise SyntaxError(f无法开始的语句 {t.text!r} at {t.line}:{t.col})parse_stmt里Assign那个分支要先看一个 tokenself.toks[self.p 1]这是递归下降处理「ID 开头、后面可能是赋值也可能是函数调用语句」时的常见做法。代价是要保证前瞻不越界EOFtoken 的存在正好兜住了这一点。3.2 优先级爬升左结合、右结合和一元运算分层文法可以一层层写函数但六层优先级写六个函数很啰嗦而且调优先级时要改一串。更省事的做法是优先级爬升一张表存运算符优先级一个函数带min_prec参数往上爬。# 数值越大结合越紧 BIN_PREC { ||: 1, : 2, : 3, !: 3, : 4, : 4, : 4, : 4, : 5, -: 5, *: 6, /: 6, %: 6, } def parse_expr(self, min_prec0): left self.parse_unary() while True: t self.cur() if t.kind ! OP or t.text not in BIN_PREC: break prec BIN_PREC[t.text] if prec min_prec: # 严格小于才退出等于时继续保证左结合 break self.p 1 right self.parse_expr(prec 1) # 1 - 左结合去掉 1 就是右结合 left BinOp(t.line, t.col, t.text, left, right) return left def parse_unary(self): t self.cur() if t.kind OP and t.text in (-, !): self.p 1 return UnaryOp(t.line, t.col, t.text, self.parse_unary()) return self.parse_primary() def parse_primary(self): t self.cur() if t.kind NUM: self.p 1 return Num(t.line, t.col, int(t.text)) if t.kind KW and t.text in (true, false): self.p 1 return BoolLit(t.line, t.col, t.text true) if t.kind ID: self.p 1 if self.at((): self.p 1 args [] if not self.at()): args.append(self.parse_expr()) while self.at(,): self.p 1 args.append(self.parse_expr()) self.eat(text)) return Call(t.line, t.col, t.text, args) return Var(t.line, t.col, t.text) if t.text (: self.p 1 e self.parse_expr() self.eat(text)) return e raise SyntaxError(f无法识别的表达式起始 {t.text!r} at {t.line}:{t.col})min_prec是整个算法的核心参数它表示「当前这一层至少要处理多紧的运算符」。1 - 2 - 3解析时第一个-进入循环右递归调用带prec 1 6第二个-的优先级是 5小于 6直接退出循环返回于是第二个-回到外层处理得到(1-2)-3这就是左结合。把1去掉第二个-会被内层吃掉变成1-(2-3)右结合——赋值运算符如果想要右结合就属于这种写法。parse_unary里递归调用自己是为了处理- -a和!!b这种连续一元运算如果写成if ... return UnaryOp(op, self.parse_primary())--a就只在第一个-上报错。注意和||在真正的编译器里要短路求值上面这个爬升只负责建树短路要在三地址码生成时拆成两个分支别指望 AST 层面自动带上。3.3 panic mode 恢复与一次报多个错课程设计里有个隐藏评分点报错信息质量。如果编译器遇到第一个错误就抛异常退出用户改一处、编一次、再改一处体验很差能一次报出多个错误是「像个真编译器」的关键区别。做法是同步集synchronization set出错后丢弃 token直到遇到;或}这类明确的分隔符再继续解析。SYNC {;, }} def parse_block_recover(self, block): while not self.at(}): try: block.stmts.append(self.parse_stmt()) except SyntaxError as e: self.errors.append(str(e)) while self.cur().kind ! EOF and self.cur().text not in SYNC: self.p 1 # 丢弃到同步集 if self.cur().text in SYNC and self.cur().text ! }: self.p 1 # 吃掉分号从下一条语句继续 if self.cur().kind EOF: break return block这个函数替换掉parse_block里的裸循环语句出错时把错误记进self.errors然后丢 token 到分号为止接着解析下一条。两个细节}不能被当成语句结束符吃掉否则块会提前结束后面全乱EOF必须单独判断并break不然内层循环会在文件结束时原地打转。这套恢复的边界要心里有数它能处理「缺分号」「括号不配对」这类局部错误遇到整段语法结构错乱时恢复质量会明显下降报出几条重复错误。课设里做到这一步就够了不必追求工业级恢复。恢复逻辑本身的 bug 很难靠肉眼发现一定要专门造几个故意写错的源文件看报出的错误条数和位置是否合理。4. 语义分析与三地址码符号表、类型检查与临时变量语法树建对之后语义分析是纯遍历代码生成也是纯遍历这两块反而最容易写「对但漏」——漏了某个节点的检查和生成测试用例刚好绕过去一上难度就现原形。4.1 作用域链与符号表结构符号表用父子链scope chain是最直接的方案进块压一层出块弹一层查找时从内往外走。class Symbol: def __init__(self, name, typ, kind, depth): self.name, self.typ, self.kind, self.depth name, typ, kind, depth self.offset None # 栈帧偏移代码生成阶段回填 self.arity 0 # 函数参数个数变量恒为 0 class Scope: def __init__(self, parentNone): self.parent parent self.table {} self.depth 0 if parent is None else parent.depth 1 def define(self, sym) - bool: if sym.name in self.table: return False # 只有同一层重名才算错遮蔽外层是合法的 self.table[sym.name] sym return True def resolve(self, name): s self while s is not None: if name in s.table: return s.table[name] s s.parent return Nonedefine只在当前层查重名这是有意的{ int x 1; { int x 2; } }在内层声明一个同名变量是合法的语义上叫遮蔽。如果查重名时一路查到最外层这种正常写法会被误报。resolve从内往外走天然实现了「内层优先」。offset先留空是因为语义分析阶段还不知道每个变量在栈帧里占几个字节等代码生成时统一分配再回填两阶段职责清楚。进入Block就新建一个Scope离开时直接丢弃引用即可——不需要显式 pop父作用域的对象还在只是子作用域的引用没人持有垃圾回收自动处理。这一点比手动维护一个栈要省心也少了一类「出块忘弹栈」的 bug。4.2 类型检查规则表类型检查写成一张表比写成一堆if好维护。核心是一张运算符与操作数类型的期望表再加一个返回类型的推导规则。运算左操作数右操作数结果失败处理 - * / %intintint报「算术运算要求 int」 intintbool报「比较运算要求 int」 !任意必须与左一致bool报「两侧类型不一致」boolbool- !一元int / bool—与操作数相同报「一元运算类型不匹配」ARITH {, -, *, /, %} p a hrefhttps://download.csdn.net/download/qq_18223329/9460275 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p