从EBNF到三地址码：编译原理课程设计端到端实现

简介：面向计算机专业学生与编译原理初学者，这份北邮编译原理课程设计资料围绕Pascal语言编译器的完整实现展开，覆盖词法分析、语法分析、语义分析、代码生成及符号表管理、错误处理等核心环节，可作为课程实验与编译器构造入门的参考案例。压缩包共83个文件，约123KB，以C++头文件与源文件承担编辑器、虚拟机和编译流程实现，pas与asm文件提供Pascal及汇编测试样例，bin、rez、rc等用于运行与界面资源，另含Visual C++工程配置，便于按模块梳理项目结构。已有1195人学习下载，说明其在同类课程设计中具有一定参考价值。读者可对照AST构造、上下文无关文法解析、三地址码生成与优化思路，结合测试样例观察从源代码到目标代码的转换过程，并借鉴符号表组织和错误报告机制，为完成自己的编译器课程设计提供可复用的实现框架与排错线索。

1. 编译原理课程设计：难点不在算法，在端到端跑通

编译原理课程设计这个题目，落到任务书上往往只有一句话：给一个精简语言子集，实现从源码到三地址码、有条件的话再到简单目标码的完整通路，附带错误定位和一组测试用例。真坐下来写才会发现，卡人的从来不是那些自动机理论，而是词法分析、语法分析、语义检查、中间代码这几段单独拎出来都能跑，拼在一起就崩——AST 少了一个节点、作用域离开代码块时没弹栈、临时变量编号撞车、错误信息指到上一行。

这篇按一条能端到端跑通的路线往下拆：先把语言子集和 AST 钉死，再手写扫描器、递归下降解析器、符号表与三地址码生成，最后用差分测试验收。适合刚拿到题目不知道从哪下手的人，也适合扫描器写完了但 AST 建歪、正准备推倒重来的人。

2. 语言子集与词法分析：先定 EBNF，再写扫描器

课程设计的评分看的是完整性和正确性，不是语言特性多。我带人做这类题时见过最多的一种翻车，是有人一上来就想支持数组、字符串、结构体，写到语义分析发现每个特性都要在符号表、类型检查、代码生成三处各改一遍，最后交上去的是一个「每样都支持一点、每样都跑不全」的半成品。所以第一件事是把范围砍到能验收的最小集。

2.1 用 EBNF 把语言子集写成可验收的清单

我一般会把语言写成下面这张表，左边是产生式，右边写清楚为什么这么定。这张表不只是给自己看的，它同时是验收标准：产生式里有的，必须实现；产生式里没有的，遇到就报语法错，不要偷偷放过。

表达式那几层按优先级从低到高排开：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_factory=list) @dataclass class FuncDef(Node): name: str = "" ret_type: str = "int" params: List["Param"] = field(default_factory=list) body: Optional["Block"] = None @dataclass class Param(Node): name: str = "" typ: str = "int" @dataclass class Block(Node): stmts: List[Node] = field(default_factory=list) @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_factory=list)

这段代码有三个决定值得说清楚。第一，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 f"Token({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, k=0): 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:1；KEYWORDS用集合而不是一长串if/elif，加关键字只改一行。

词法阶段不要急着建符号表。有人在扫描器里顺手维护一张name -> id的哈希表，觉得能省事，结果语义分析要按作用域区分同名变量时，这张全局表反而成了障碍。词法阶段只负责回答「这是个标识符」，它叫什么、在哪一层作用域、什么类型，全部留给语义分析。

3. 语法分析：递归下降加优先级爬升

递归下降的好处是代码结构和文法一一对应，报错位置天然准确；代价是要先处理左递归，还要自己管结合性。这两件事都有固定套路，照着做基本不会翻车。

3.1 消除左递归后的函数骨架

左递归的产生式写成函数会无限递归。标准改写是把它转成循环：E → E '+' T | T改成E → T ('+' T)*，代码形态就是一个while，先解析一个 T，然后只要当前 token 是+就继续吃掉再解析一个 T。

函数骨架按文法层次逐个写，每层一个方法，命名和产生式左部对齐，回头查错时一眼能对上是哪条规则出的问题。

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, kind=None, text=None): 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那个分支要先看一个 token（self.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_prec=0): 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, parent=None): 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 None

define只在当前层查重名，这是有意的：{ int x = 1; { int x = 2; } }在内层声明一个同名变量是合法的，语义上叫遮蔽。如果查重名时一路查到最外层，这种正常写法会被误报。resolve从内往外走，天然实现了「内层优先」。offset先留空，是因为语义分析阶段还不知道每个变量在栈帧里占几个字节，等代码生成时统一分配再回填，两阶段职责清楚。

进入Block就新建一个Scope，离开时直接丢弃引用即可——不需要显式 pop，父作用域的对象还在，只是子作用域的引用没人持有，垃圾回收自动处理。这一点比手动维护一个栈要省心，也少了一类「出块忘弹栈」的 bug。

4.2 类型检查规则表

类型检查写成一张表，比写成一堆if好维护。核心是一张运算符与操作数类型的期望表，再加一个返回类型的推导规则。

ARITH = {"+", "-", "*", "/", "%"} <p> <a href="https://download.csdn.net/download/qq_18223329/9460275" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>