简介面向编译原理课程设计与编译器前端初学者这份课程设计报告围绕“一个简单文法编译器前端”给出完整实现说明。内容覆盖词法分析的 Token 生成流程、递归下降语法分析、语义分析与四元式中间代码生成并展示了常量、数组、if-else、while 等文法扩展以及递归子程序栈在每一步分析中的跟踪方式报告还简要说明了后端如何将四元式转换为目标代码。包内为 1 个 docx 文档大小 381KB整体结构符合本科课程设计报告规范章节包含课程设计任务要求、总体流程、各模块功能与算法、数据结构、程序流程图、实验结果、结论和设计分工可对照设计规范快速搭建整体框架也可直接参考其中的写作结构与排版层次用于答辩讲解。资源已有 693 人学习既能帮助建立从词法分析到目标代码生成的完整认知也适合正在完成编译器前端实践项目或准备课程设计答辩的读者参考。1. 一个简单文法编译器前端把源代码变成语法树的三道关卡一个简单文法编译器前端要处理的事说白了就是把一段按文法书写的源代码依次送进词法分析、语法分析、语义分析三道关卡最后得到一棵结构完整的语法树AST。很多从业者第一次听到「编译器前端」就往汇编和机器码上想其实它和编辑器完全是两码事——编译器前端不负责语法高亮和自动补全它只负责「读懂」程序文本并且把读懂的结论结构化地表达出来。这个方向非常适合手写验证用几百行 Python 就能跑通完整闭环而且无论之后去啃 GCC 的 C 前端、V8 的 JavaScript 前端还是自己做一个 DSL 解析器骨架都是一样的。前端面试题里经常出现的「手写一个四则运算解释器」本质考的就是这一套能力。2. 词法分析手写 Scanner 把源代码切成 token 流词法分析是整个编译器前端的入口它把原始字符串按文法中的终结符切分成 token。这里我以一个支持变量赋值和四则运算的简单文法为例它足够小但包含了编译器前端会遇到的绝大多数核心问题program : stmt* stmt : IDENT expr ; | expr ; expr : term (( | -) term)* term : factor ((* | /) factor)* factor : NUMBER | IDENT | ( expr )2.1 先定 token 表终结符、字面量和 EOF 一个都不能少写词法分析之前第一件事是把 token 类型定下来。这个表不是随手列的它严格对应文法里的每个终结符和字面量加号、减号、乘号、除号、括号、赋值号、分号外加 NUMBER 和 IDENT 两类字面量以及一个容易被新手忽略的 EOF。EOF 必须单独占一个类型语法分析阶段判断「程序是否结束」全靠它。# tokens.py from enum import Enum, auto class TokenType(Enum): NUMBER auto() # 数字字面量如 123、3.14 IDENT auto() # 标识符如变量名 a、b PLUS auto() # MINUS auto() # - STAR auto() # * SLASH auto() # / LPAREN auto() # ( RPAREN auto() # ) ASSIGN auto() # SEMI auto() # ; EOF auto() # 文件结束符 class Token: def __init__(self, type_, value, line, col): self.type type_ self.value value self.line line self.col col def __repr__(self): return fToken({self.type.name}, {self.value!r}, line{self.line}, col{self.col})Token 的 value 字段用于存放字面量的实际值比如 NUMBER 对应数字值、IDENT 对应变量名字符串运算符类 token 的 value 通常就是运算符字符本身。line 和 col 两个字段看着不起眼但到了语法分析报错阶段就是救命稻草——没有位置信息用户看到报错只能干瞪眼完全不知道错在源码的哪一行。我见过不少初学编译器开发的人省掉这两个字段后面排查问题成本翻倍属于典型的「省小钱吃大亏」。2.2 逐字符扫描跳过空白、扫数字、扫标识符Scanner 的核心是一个「前视一个字符」的循环。peek() 看当前位置但不消费advance() 消费一个字符并推进位置。这样设计的好处是词法分析里常见的「最长匹配」逻辑写起来非常顺先 peek 判断当前字符类型再决定进入哪个扫描子程序。# scanner.py from tokens import TokenType, Token class Scanner: def __init__(self, source: str): self.source source self.pos 0 self.line 1 self.col 1 def peek(self, offset0): idx self.pos offset if idx len(self.source): return return self.source[idx] def advance(self): ch self.source[self.pos] self.pos 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def skip_whitespace(self): while self.peek() and self.peek().isspace(): self.advance() def _scan_number(self): start self.pos while self.peek() and (self.peek().isdigit() or self.peek() .): self.advance() text self.source[start:self.pos] if text.count(.) 1: raise SyntaxError(f非法数字字面量 {text!r} at {self.line}:{self.col}) return Token(TokenType.NUMBER, float(text) if . in text else int(text), self.line, self.col) def _scan_ident(self): start self.pos while self.peek() and (self.peek().isalnum() or self.peek() _): self.advance() return Token(TokenType.IDENT, self.source[start:self.pos], self.line, self.col) def next_token(self): self.skip_whitespace() if self.pos len(self.source): return Token(TokenType.EOF, None, self.line, self.col) ch self.peek() if ch.isdigit(): return self._scan_number() if ch.isalpha() or ch _: return self._scan_ident() single { : TokenType.PLUS, -: TokenType.MINUS, *: TokenType.STAR, /: TokenType.SLASH, (: TokenType.LPAREN, ): TokenType.RPAREN, : TokenType.ASSIGN, ;: TokenType.SEMI, } if ch in single: self.advance() return Token(single[ch], ch, self.line, self.col) raise SyntaxError(f无法识别的字符 {ch!r} at {self.line}:{self.col})这里的核心逻辑分三块skip_whitespace 把空格、换行、制表符全部吃掉因为它对文法没有意义_scan_number 在遇到数字开头时连续吞掉数字和小数点_scan_ident 在遇到字母或下划线开头时连续吞掉字母、数字和下划线。有一点要注意_scan_number 里对小数点做了防重检查1.2.3这种输入会直接报错而不是被切成三个 token 留到语法分析阶段才炸——词法阶段能拦截的错误尽量别往后甩。2.3 最长匹配与位置信息词法阶段的两个隐藏考点词法分析里有个词叫「最长匹配」意思是当一个字符既能作为某个 token 的开头、又能延伸出更长 token 时必须选更长的那个。比如123abc如果只扫数字就会切成 NUMBER(123) 和 IDENT(abc)这种切法在简单文法里也许能勉强跑过去但报错信息会非常迷惑人。更稳的做法是在 _scan_number 返回前检查下一个字符是不是字母或下划线如果是就直接抛错。这个坑我在第 5 章会专门展开。位置信息的维护也值得多说一句。上面代码里 advance() 每消费一个字符就同步更新 line 和 col遇到换行就 line 1 且 col 归 1。这个成本几乎为零但换来了所有 token 都自带坐标。等语法分析抛「期望 ; 但遇到 )」这样的错误时你才能在异常消息里打印出具体行列。没有这组坐标排错基本靠猜属于典型的黑匣子式开发体验。3. 语法分析用递归下降把 token 流构造成语法树词法分析结束后手里是一串线性 token。语法分析的任务是按照文法规则把这些 token 组织成一棵有层次的树——语法树。树的结构直接反映文法的嵌套关系比如a 3 4 * 2;里的乘法会比加法低一层因为它的优先级更高。3.1 为什么手写递归下降而不是上 lex/yacc面对「简单文法」我一般会直接手写递归下降解析器而不是引入 flex/bison 或 ANTLR 这类生成器。理由有三条第一递归下降的代码结构和文法产生式一一对应每个非终结符就是一个函数读代码的人能直接对照文法检查逻辑第二报错位置和错误信息完全可控生成器给出的默认错误信息往往又臭又长对使用者不友好第三这个规模的项目引入生成器光是学配置语法和调试生成代码的时间就够手写三遍了。等将来文法膨胀到几百条产生式再考虑 ANTLR 不迟。递归下降属于自顶向下的预测分析它要求文法满足 LL(1) 条件——也就是在任何一步只看当前一个 token 就能唯一决定走哪个产生式分支。我们前面给的文法恰好满足这个条件parse_stmt 里 peek 一下 IDENT 后头是不是 ASSIGN就能判断是赋值语句还是表达式语句。3.2 AST 节点与 Parser 主体一个非终结符一个函数先定义 AST 节点。这里我把节点类型压到最少Program、Assign、BinOp、Number、Ident足够表达当前文法。BinOp 用来表示所有二元运算op 字段直接存 TokenType 里的 PLUS、MINUS、STAR、SLASH省掉再建一套运算符枚举。# ast.py class Node: pass class Program(Node): def __init__(self, stmts): self.stmts stmts class Assign(Node): def __init__(self, name, expr): self.name name # 变量名字符串 self.expr expr # 右侧表达式 AST class BinOp(Node): def __init__(self, op, left, right): self.op op # TokenType.PLUS / MINUS / STAR / SLASH self.left left self.right right class Number(Node): def __init__(self, value): self.value value class Ident(Node): def __init__(self, name): self.name name# parser.py from tokens import TokenType from ast import Program, Assign, BinOp, Number, Ident class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def advance(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, type_): tok self.advance() if tok.type ! type_: raise SyntaxError( f期望 {type_.name}但遇到 {tok.type.name} at {tok.line}:{tok.col}) return tok def parse_program(self): stmts [] while self.peek().type ! TokenType.EOF: stmts.append(self.parse_stmt()) return Program(stmts) def parse_stmt(self): if (self.peek().type TokenType.IDENT and self.tokens[self.pos 1].type TokenType.ASSIGN): ident self.advance() # 吃掉 IDENT self.advance() # 吃掉 expr self.parse_expr() self.expect(TokenType.SEMI) return Assign(ident.value, expr) expr self.parse_expr() self.expect(TokenType.SEMI) return expr def parse_expr(self): node self.parse_term() while self.peek().type in (TokenType.PLUS, TokenType.MINUS): op self.advance() right self.parse_term() node BinOp(op.type, node, right) return node def parse_term(self): node self.parse_factor() while self.peek().type in (TokenType.STAR, TokenType.SLASH): op self.advance() right self.parse_factor() node BinOp(op.type, node, right) return node def parse_factor(self): tok self.peek() if tok.type TokenType.NUMBER: self.advance() return Number(tok.value) if tok.type TokenType.IDENT: self.advance() return Ident(tok.value) if tok.type TokenType.LPAREN: self.advance() node self.parse_expr() self.expect(TokenType.RPAREN) return node raise SyntaxError(f无法解析的 token {tok.type.name} at {tok.line}:{tok.col})这块代码的核心是 parse_expr 和 parse_term 里的循环结构。文法expr : term ((|-) term)*里的星号在代码中对应 while 循环先解析一个 term然后反复检查下一个 token 是不是加号或减号是就继续吞掉并再解析一个 term把新的子树挂到左边。这样写出来的 AST 对1 - 2 - 3会自然形成(1 - 2) - 3的左结合结构因为每一次循环都是把已经建好的 node 当成左操作数。如果改成node BinOp(op, right, node)结合性就反了算出来的结果会错得不着边际。3.3 左递归递归下降唯一的大敌递归下降解析器有个严格限制文法不能包含左递归。所谓左递归就是产生式左边第一个符号还是这个非终结符自己比如expr :: expr term。如果照着这条规则写 parse_expr函数第一步就调用 parse_expr永远不消费 token直接栈溢出。很多第一次接触编译器前端的人在这里翻车报错还不是语法错误而是 Python 的 RecursionError看起来特别像「玄学问题」。解决办法有两个。常见做法是把左递归文法改写成等价的 EBNF 形式也就是我们前面用的term ((|-) term)*用循环代替递归。还有一个通用做法是套用左递归消除算法把A :: Aα | β改写为A :: βA、A :: αA | ε但改写出来的文法可读性差不少对简单文法来说没必要。只要在设计文法阶段就避免左递归递归下降写起来会非常顺手。注意这里说的左递归不仅包括expr :: expr ...这种直接左递归还包括 A 依赖 B、B 又依赖 A 的间接左递归。遇到文法先做一遍检查别等运行时爆栈才回头找。4. 语义分析与符号表给 AST 加作用域和类型检查语法分析生成的 AST 能表达「这段代码长什么样」但表达不了「这段代码是否合理」。x y 1;在语法上完全合法但如果 y 从未被赋予过值程序就是错的。语义分析阶段就是回答这类问题而这个阶段的核心数据结构叫符号表。4.1 为什么 AST 不够还需要符号表AST 里 Ident(a) 和 Ident(b) 只是两个名字不同的叶子节点它们背后是同一个变量还是不同变量AST 本身判别不了。厘清这件事需要符号表一张记录了「名字 → 属性」的映射表。属性可以是类型、作用域、初始状态等。对简单文法来说先做两件事就够检查变量是否重复定义、检查变量使用时是否已定义。有一个常见误区是试图在语法分析阶段顺便把符号表也建了。这种做法在简单文法里能跑但一旦文法引入块级作用域或者「先使用后声明」的规则语法分析和语义分析就得解耦。我习惯的做法是把语义分析做成独立一遍遍历先把 AST 完整建出来再单独走一趟检查。这样做的好处是每个阶段的职责单一排查问题时能明确知道是「树建错了」还是「检查写错了」。4.2 符号表结构单层 dict 不够要支持作用域链很多从零开始写编译器前端的人会把符号表做成一个简单的 dict全局共用一个。这在只有全局作用域的语言里没问题但一旦出现函数或代码块内层作用域需要能遮蔽外层同名变量同时内层查不到时还得能逐层向上找。最朴素的实现是给每个作用域一个 dict再用 parent 指针串成链。# symbols.py class SymbolTable: def __init__(self, parentNone): self.symbols {} self.parent parent def define(self, name, typ): if name in self.symbols: raise NameError(f变量 {name} 重复定义) self.symbols[name] typ def lookup(self, name): if name in self.symbols: return self.symbols[name] if self.parent is not None: return self.parent.lookup(name) return Nonedefine 和 lookup 是符号表最基本的两个操作。lookup 的递归向上查找实现了作用域链当前作用域找不到就找外层一直到最外层还没有就返回 None。这个设计在后续引入函数作用域、块作用域时能直接复用不必推倒重来。define 里检查重复定义会抛 NameError这个行为是刻意的——把语义错误尽早暴露出来比等到生成代码阶段才炸要好处理得多。4.3 遍历 AST 做检查赋值即声明使用前先查表有了符号表接下来写一个简单的访问器遍历 AST。这里我用 isinstance 分发到不同的 visit 方法简单直接比你为此引入一套 visitor 框架要划算得多。对于当前文法语义规则就三条赋值语句把变量名登记进符号表标识符出现时必须能查到二元运算两侧必须都是数值类型。# analyze.py from ast import Program, Assign, BinOp, Number, Ident class Analyzer: def __init__(self): self.globals SymbolTable() self.current self.globals def visit(self, node): if isinstance(node, Program): for stmt in node.stmts: self.visit(stmt) elif isinstance(node, Assign): typ self.visit(node.expr) self.current.define(node.name, typ) elif isinstance(node, BinOp): left self.visit(node.left) right self.visit(node.right) if left is None or right is None: return None return number elif isinstance(node, Number): return number elif isinstance(node, Ident): typ self.current.lookup(node.name) if typ is None: raise NameError(f未定义变量 {node.name} at 第 {node.line} 行) return typ return None这段代码里我把所有数值统一成 number 类型因为当前文法里没有别的类型区分 int 和 float 只会徒增复杂度。真正值得关注的是 BinOp 的检查逻辑如果左右两侧任一操作数查不到类型就直接返回 None不再继续传播。因为错误已经在 Ident 访问时抛出来了这里继续纠结类型没有意义。整个语义分析阶段的目标是「拦截明显错误的程序」而不是「证明程序完全正确」后者需要形式化验证不在简单文法的范畴内。5. 常见问题与排查左递归、优先级和词法边界的翻车现场写这种几百行的简单前端我踩过的坑比写出来的代码还多。这一章把最典型的四类问题按「现象 → 原因 → 解决」的顺序复盘一遍全部是血泪经验照着排查能省下大量调试时间。5.1 现象RecursionError 栈溢出 → 原因文法左递归没消除现象很直接运行 Parser 解析1 2还没出结果就先抛 RecursionError: maximum recursion depth exceeded。新手第一反应通常是怀疑 Python 递归深度限制太严其实是文法写错了。原因把产生式写成了expr :: expr term。parse_expr 执行后的第一件事是调用 parse_expr而这一调用没有消费任何 token于是无限递归。解决把文法改写成expr : term ((|-) term)*对应代码里就是那个 while 循环。还有个自查技巧凡是「产生式右部以自己开头」的规则在递归下降里统统不能直接写改写优先级高于一切参数调优。5.2 现象1 2 * 3 算出 9 → 原因优先级被压平了如果你图省事把文法写成expr : expr (|-|*|/) expr并且做了左递归消除那么1 2 * 3解析出来的 AST 很可能是(1 2) * 3最终算成 9。这在语法层面完全正确——你的文法就是定义成了从左到右平级运算。原因优先级不是解析器自动识别的而是靠文法分层「编码」进去的。解决把表达式拆成多层乘除法所在的 term 比加减法所在的 expr 低一层factor 又比 term 低一层。每多一层就多一级优先级。这也是业界最通用的做法GCC 解析 C 表达式时用的还是这个思路。要检查自己的文法层级是否正确最简单的办法是拿1 2 * 3手动画一棵 AST看乘法节点是否比加法节点更深。5.3 现象123abc 被拆成两个 token → 原因词法边界没做后视检查输入x 123abc;Scanner 先切出 NUMBER(123)再把 abc 当 IDENT 切出来Parser 随后在期望 SEMI 时报错报错位置指向 abc 而不是真正的非法点。这种报错完全不指向根因排查起来极其恼火。原因_scan_number 停止扫描时只看当前字符是否还是数字或小数点没看下一个字符是什么。解决在扫完数字后加一个后视检查如果下一个字符是字母或下划线立刻抛明确的语法错误# scanner.py 中 _scan_number 的收尾部分 def _scan_number(self): start self.pos while self.peek() and (self.peek().isdigit() or self.peek() .): self.advance() text self.source[start:self.pos] if text.count(.) 1: raise SyntaxError(f非法数字字面量 {text!r} at {self.line}:{self.col}) nxt self.peek() if nxt and (nxt.isalpha() or nxt _): raise SyntaxError( f数字 {text!r} 后紧跟非法字符 {nxt!r} at {self.line}:{self.col}) return Token(TokenType.NUMBER, float(text) if . in text else int(text), self.line, self.col)这行后视检查几乎是白送的却能把一个让新手困惑半小时的报错变成一眼能看懂的提示。同样的思路也适用于标识符扫描扫完 IDENT 后检查下一个字符如果既不是字母、数字也不是下划线且不可能是合法运算符就应该报错而不是把它留给语法分析阶段处理。5.4 现象一处少分号报错 40 条 → 原因没有错误恢复机制用户写a 1忘加分号Parser 在 expect(SEMI) 处抛异常。如果你的 parse_program 不做任何处理异常会一直往外抛整个解析终止。更糟的情况是你在外层写了 try 继续循环但循环没有同步 token 位置导致后续每个 token 都被当成新语句开头错误信息雪崩式增长。原因语法分析器在遇到错误后没有回到一个稳定的同步点。解决采用经典的 panic mode 错误恢复。在 parse_program 的主循环里捕获 SyntaxError然后跳到下一个分号或右括号附近再继续# parser.py 中带错误恢复的版本 def parse_program(self): stmts [] while self.peek().type ! TokenType.EOF: try: stmts.append(self.parse_stmt()) except SyntaxError as e: print(f语法错误: {e}) self.synchronize() return Program(stmts) def synchronize(self): while self.peek().type not in (TokenType.SEMI, TokenType.EOF): self.advance() if self.peek().type TokenType.SEMI: self.advance()synchronize 的逻辑是一直吞 token直到遇到分号或文件结束。分号在这门语言里是语句天然的终止符拿它做同步点最稳。需要注意的是这种恢复方式会丢弃出错那条语句剩余的内容但它的目标是「一次只报一个错、报完还能继续检查后面的代码」对一个简单文法编译器前端来说完全够用。更精细的错误恢复需要在每个产生式上维护 follow 集合那是商用编译器才值得投入的复杂度。6. 用一个求值器验证你的前端AST dump 加表驱动测试代码写完了怎么证明它对光靠「编译不报错」远远不够。我通常会再加两层验证先做 AST dump 看树结构对不对再写一个极简求值器对 AST 直接求值用表驱动测试守住回归。AST dump 就是把树打印成缩进文本一两行代码的事def dump(node, indent0): pad * indent if isinstance(node, BinOp): print(f{pad}BinOp({node.op.name})) dump(node.left, indent 1) dump(node.right, indent 1) elif isinstance(node, Number): print(f{pad}Number({node.value})) elif isinstance(node, Ident): print(f{pad}Ident({node.name}))配合求值器一起用才能验证语义是否正确def evaluate(node, env): if isinstance(node, BinOp): l, r evaluate(node.left, env), evaluate(node.right, env) return {PLUS: l r, MINUS: l - r, STAR: l * r, SLASH: l / r}[node.op.name] if isinstance(node, Number): return node.value if isinstance(node, Ident): return env[node.name]输入期望结果a 3 4 * 2;a 11b (a 1) / 2;接上b 6.0c 10 - 2 - 3;c 5而不是 9d 1 2 * 3;d 7这四个用例分别检验了优先级、括号、左结合性等最容易出问题的点。把用例放进一个列表循环断言之后每次改动解析器都能立刻知道有没有破坏已有行为。这套验证方法再往下延伸就是编译器开发的下一步把 AST 转换成三地址码中间表示然后进入编译器优化和目标代码生成阶段。我自己的习惯是每实现一个阶段就先写对应的 dump 和测试用例确认无误再动下一块这样整套前端做下来几乎不会出现「前面错了但到很后面才暴露」的情况。希望帮到你。本文还有配套的精品资源点击获取