简介一套面向编译原理课程设计与实验的完整资源包涵盖词法分析、LL(1)语法分析、LR(0)与SLR(1)语法分析、四元式生成及汇编代码生成等核心环节并配有小型编译器及课程设计报告适合高校计算机相关专业学生完成实验、课程设计或复习备考使用。资源共14个文件以C/C源代码为主4个cpp、3个c、3个h另有3个txt文法和1个doc实验报告压缩包整体仅557KB结构紧凑便于按模块查看与复用。当前已有2347人学习下载是编译原理实践入门的高性价比参考。文件内含多个LL(1)文法和一个SLR(1)文法可直接运行验证分析过程配套报告对小型编译器的设计思路、算法流程与实现细节进行了说明有助于快速理解从词法分析到代码生成的整体框架。1. 编译原理课程设计一个能跑通的小型编译器从词法分析到三地址码编译原理课程设计最让人心里没底的几乎都是同一个问题词法分析、语法分析、语义分析每一章单独学都能跟上但要把它们串成一个能跑的小型编译器就到处是窟窿。这篇拆的是一个以 Python 为宿主语言实现的课程设计项目词法分析器手写扫描状态机语法分析用递归下降模式最终生成三地址码并完成符号表管理不是贴一段 flex 脚本就交差的半成品。适合正在做课程设计的学生也适合要复习编译原理细节、想快速在简历里写一个有落地成果的开发者。全篇的前提只有一个你至少知道 Token、终结符、递归下降这些概念但还没完整实现过一个小型编译器。2. 词法分析与 Token 流手写扫描器的状态机设计词法分析处在整个编译器最前端它读入的是赤裸裸的源代码字符串吐出来的是带类型和位置标注的 Token 序列。课程设计里这部分不需要做得像 Go 编译器那样庞大但 Token 的类型划分、位置记录、边界处理必须严格否则语法分析器拿到的就是一份脏数据。2.1 词法分析器的职责与 Token 类型定义词法分析器负责把字符串切词每个 Token 至少要有三个属性类型、原始文本、行列号。类型决定语法分析器怎么处理这个 Token原始文本保留给后续阶段使用行列号则在报错时直接定位源代码位置。类型匹配规则例子KEYWORD保留字表内if、else、while、printIDENT字母或下划线开头后跟字母/数字/下划线x、sum、count_1NUMBER十进制整数或浮点数123、3.14OPERATOR运算符、-、*、/、、、、DELIMITER分隔符(、)、{、}、;在实现里我会用一个 Token 类的构造器来保存位置信息。列号从 1 开始行号换行自增这是调试时最重要的元数据。词法分析器扫描时最经典的错误是碰到数字后接着字符比如123abc它既不是合法数字也不是合法标识符必须在扫描数字时看到非数字字符后停下来并检查下一个字符是否属于标识符字符集如果是就要抛词法异常。2.2 手写状态机而不是 flex三个选择理由很多课程设计用 Flex 自动生成词法分析器几行正则就能生成 C 代码。但我的建议是自己写一个几十行的手写扫描器理由有三个。第一flex 生成的代码是黑匣子报错信息不直观交课程报告时老师问“你的状态转换图怎么对应代码”你很难答清楚。第二课程设计通常只有两到三周flex 的安装、配置、生成 C 文件、链接主程序这一套流程本身就要浪费一天。第三手写状态机之后你能直观地在每个字符读取位置上设断点这是调试最方便的方式。以数字识别为例手写时的核心问题是“贪心匹配但不越界”。扫描数字时只要当前字符是数字就一直跳过遇到小数点则重置小数标志后继续读数字这样3.14能被正确识别。但如果输入是3.14.15第二个小数点出现时必须判定为非法数字因为小数标志已经置位。2.3 一个可运行的 Python 词法器实现下面是词法分析器核心代码不依赖任何第三方库直接复制到一个lexer.py文件里就能跑。# lexer.py class Token: def __init__(self, kind, value, line, col): self.kind kind self.value value self.line line self.col col def __repr__(self): return f{self.kind}({self.value}, {self.line}:{self.col}) class Lexer: def __init__(self, src): self.src src self.pos 0 self.line 1 self.col 1 self.keywords {if, else, while, print} def scan(self): tokens [] while self.pos len(self.src): c self.src[self.pos] if c.isspace(): if c \n: self.line 1 self.col 1 else: self.col 1 self.pos 1 elif c.isalpha() or c _: tokens.append(self._scan_ident()) elif c.isdigit(): tokens.append(self._scan_number()) else: tokens.append(self._scan_operator_or_delim()) tokens.append(Token(EOF, , self.line, self.col)) return tokens def _scan_ident(self): start_line, start_col self.line, self.col start self.pos while self.pos len(self.src) and ( self.src[self.pos].isalnum() or self.src[self.pos] _): self.pos 1 self.col 1 text self.src[start:self.pos] kind KEYWORD if text in self.keywords else IDENT return Token(kind, text, start_line, start_col) def _scan_number(self): start_line, start_col self.line, self.col start self.pos has_dot False while self.pos len(self.src): if self.src[self.pos].isdigit(): self.pos 1 self.col 1 elif self.src[self.pos] . and not has_dot: has_dot True self.pos 1 self.col 1 else: break if self.pos len(self.src) and (self.src[self.pos].isalpha() or self.src[self.pos] _): raise SyntaxError(finvalid number at {start_line}:{start_col}) return Token(NUMBER, self.src[start:self.pos], start_line, start_col) def _scan_operator_or_delim(self): start_line, start_col self.line, self.col c self.src[self.pos] two self.src[self.pos:self.pos2] self.pos 1 self.col 1 if two in (, , , !): self.pos 1 self.col 1 return Token(OPERATOR, two, start_line, start_col) if c in -*/: return Token(OPERATOR, c, start_line, start_col) if c in (){};: return Token(DELIMITER, c, start_line, start_col) raise SyntaxError(funknown char {c} at {start_line}:{start_col})这个扫描器的逻辑要点是区分单字符和双字符运算符。_scan_operator_or_delim里先取当前位置开始的两个字符如果匹配、、、!就按双字符处理并跳过两个位置否则退化成单字符处理。_scan_number里的has_dot标志控制小数点只能出现一次同时数字后如果紧跟字母或下划线就直接抛异常这一步是课程设计里最常见的遗漏点。关键参数有两个self.keywords这个集合决定哪些单词被识别为保留字如果你要支持for或return只需要在集合里追加一个字符串has_dot标志位决定数字字面量是否支持浮点数。如果你的题目只要求整数把这个标志位相关代码删掉即可。报错统一用SyntaxError而不是print这样上层调用者可以通过异常捕获拿到错误上下文。3. 语法分析与 AST 构建递归下降解析器的实现细节词法分析把x 10 3切成 IDENT、OPERATOR、NUMBER、OPERATOR、NUMBER 五个 Token 后语法分析器的任务是决定这个序列是否符合文法并按文法的嵌套结构生成抽象语法树。3.1 为什么选递归下降而不是 LR 工具有同学用过 yacc/bison 生成 LR 语法分析器但我建议课程设计里手写递归下降。原因很实在递归下降每个非终结符对应一个函数你看到哪个函数没被调用、哪一步递归没返回直接用调试器跟栈帧就能找到问题。而 LR 表驱动是查表动作的堆叠出错时你面对的是一个巨大的状态表课程设计报告里没法把你对文法的理解写进状态表里。递归下降的代价是文法必须满足LL(1)条件也就是没有左递归、没有公共左因子。对于课程设计要写的表达式、赋值语句、if 语句来说这个限制完全够用。3.2 表达式文法设计与左递归消除经典算术表达式文法替换为所需的文法。左结合通过用循环而不是递归来表示。任何expr - expr term的形式是左递归会让递归下降陷入无限调用必须改写成expr - term {(|-) term}。递归下降的代码实现里parse_expr先解析一个 term然后观察下一个 Token 是加号还是减号如果是就循环解析新的 term 并当场与左结合。parse_term同理处理乘除。最后一个parse_factor处理原子项数字、标识符、括号表达式。3.3 AST 定义与 Parser 实现AST 节点用一个统一的 Node 类表示每个节点有一个 type、一个可选 value、一个 children 列表。Binop 节点是二元操作它的 value 是运算符children 包含左右子树。# ast.py class Node: def __init__(self, type, valueNone, childrenNone): self.type type self.value value self.children children if children is not None else [] def __repr__(self): return fNode({self.type}, {self.value}, {self.children})# parser.py from lexer import Token from ast import Node class Parser: def __init__(self, tokens): self.tokens tokens self.idx 0 def peek(self): return self.tokens[self.idx] def advance(self): tok self.tokens[self.idx] if tok.kind ! EOF: self.idx 1 return tok def expect(self, value): tok self.peek() if tok.value ! value: raise SyntaxError(fexpect {value} at {tok.line}:{tok.col}, got {tok.value}) return self.advance() def parse_program(self): statements [] while self.peek().kind ! EOF: statements.append(self.parse_stmt()) return Node(program, childrenstatements) def parse_stmt(self): tok self.peek() if tok.kind IDENT and self.tokens[self.idx 1].value : return self.parse_assign() if tok.value if: return self.parse_if() if tok.value print: return self.parse_print() raise SyntaxError(funexpected token at {tok.line}:{tok.col}) def parse_assign(self): tok self.advance() # IDENT self.expect() value self.parse_expr() self.expect(;) return Node(assign, tok.value, [value]) def parse_if(self): self.expect(if) self.expect(() cond self.parse_expr() self.expect()) then_branch self.parse_stmt() else_branch None if self.peek().value else: self.advance() else_branch self.parse_stmt() return Node(if, children[cond, then_branch, else_branch]) def parse_print(self): self.expect(print) self.expect(() value self.parse_expr() self.expect()) self.expect(;) return Node(print, children[value]) def parse_expr(self): node self.parse_term() while self.peek().value in (, -): op self.advance() right self.parse_term() node Node(binop, op.value, [node, right]) return node def parse_term(self): node self.parse_factor() while self.peek().value in (*, /): op self.advance() right self.parse_factor() node Node(binop, op.value, [node, right]) return node def parse_factor(self): tok self.peek() if tok.kind NUMBER: self.advance() return Node(num, tok.value) if tok.kind IDENT: self.advance() return Node(ident, tok.value) if tok.value (: self.advance() node self.parse_expr() self.expect()) return node raise SyntaxError(funexpected token at {tok.line}:{tok.col})解析器最需要注意的位置是parse_expr和parse_term里的 while 循环。它用的是循环而不是递归来表达左结合这样1 - 2 - 3会被解析成(1-2)-3而不是1-(2-3)数学语义正确。parse_stmt里对赋值语句和 if 语句的判断方法是看当前 Token 和下一个 Token 的组合值这是 LL(1) 判断的一个简单前置处理用于挑选产生式。AST 中的 Node 实例不带源码位置信息如果要做更严格的错误报告可以给 Node 增加 line/col 字段但我建议保持简洁把这些诊断信息放在语义分析的错误里重新计算。4. 语义分析与三地址码生成从 AST 到可执行中间表示AST 构建成功只说明语法层面没问题x y 1中 y 是否定义过、两边类型是否匹配这些问题归语义分析管。课程设计里语义分析通常与代码生成合并在一起遍历 AST 的同时维护符号表并产出后端可执行的中间表示。4.1 符号表一个字典就能撑起的作用域链小型语言的符号表最简单模型就是一个字典键是变量名值是类型。但如果支持嵌套作用域就得用链表结构把每一层作用域串联起来。课程设计最简方案一个全局字典和可选的一个局部字典集合。# symbol_table.py class SymbolTable: def __init__(self): self.scopes [{}] def push_scope(self): self.scopes.append({}) def pop_scope(self): if len(self.scopes) 1: self.scopes.pop() def define(self, name): self.scopes[-1][name] True def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return True return Falsepush_scope在进入 if 块时调用pop_scope在离开时调用。lookup从最内层向外层搜索找到就返回 True。这个模型没有类型检查功能要想支持类型差异每一项的值需要从 True 扩展为int或float这类类型字符串define 时传入类型lookup 时返回类型值。课程设计里你只要保证“先定义后使用”代码生成才会稳定。4.2 三地址码生成的遍历策略三地址码是每条指令至多一个运算符、三个地址的中间表示例如t1 a b。从 AST 到三地址码的生成器本质上是一个后序遍历每遇到一个 binop 节点就生成一个临时变量存放运算结果遇到赋值节点就把右边表达式的临时结果写入左边变量名。# codegen.py from symbol_table import SymbolTable class CodeGen: def __init__(self): self.quads [] self.temp_index 0 self.symbols SymbolTable() def new_temp(self): self.temp_index 1 return ft{self.temp_index} def gen(self, node): if node.type num: return node.value if node.type ident: if not self.symbols.lookup(node.value): raise Exception(fundefined variable: {node.value}) return node.value if node.type binop: left self.gen(node.children[0]) right self.gen(node.children[1]) temp self.new_temp() self.quads.append((, left, right, temp, node.value)) return temp if node.type assign: value self.gen(node.children[0]) self.quads.append((, value, None, node.value, copy)) return None if node.type print: value self.gen(node.children[0]) self.quads.append((print, value, None, None, None)) return None raise Exception(funknown node type: {node.type})这里我用了五元组来表示指令(操作源1源2目的运算)。binop节点生成的指令里源1是左子树的地址源2是右子树的地址目的是新临时变量最后一条字段填运算符。赋值指令的源是右侧表达式的临时变量目的是变量名。print 指令只打印一个值。new_temp每调用一次临时变量索引加 1保证同一个编译过程内不会出现两个不同的变量共用同一个临时变量名。这是最容易忽略的一点如果你在代码生成里重用临时变量而没有重新计数中间代码的赋值顺序会互相覆盖。4.3 一个完整例子的执行过程假设源码是x 1 2 * 3; print(x);Parser 产出的 AST 是 program 下挂一个 assign 节点和一个 print 节点。CodeGen 遍历 assign 节点时先递归调用gen进入右侧 binop再进到三层因子得到如下三地址码列表三元运算符t1 2 * 3 t2 1 t1 x t2 print x这个输出就对应了正确的运算优先级因为parse_term把乘除的节点构建在了表达式树的更深处CodeGen 的后序遍历先处理它临时变量的生成顺序自动遵循优先级。5. 编译原理课程设计避坑指南四个最容易翻车的点这部分是我自己把这些问题逐一踩过后总结出来的血泪经验每一条都按照“现象 → 原因 → 解决”的方式写出来按顺序排查基本能覆盖课程设计里最常见的崩溃点。5.1 关键词和标识符识别冲突现象输入ifx 10;被词法分析器识别成关键字if加标识符x。原因词法扫描在读到i、f两个字符后就停下来去查关键字表没有把整个单词扫描完导致ifx被拆分。正确的做法是贪心匹配整个完整单词再判断是否为关键字而不是匹配到关键字表里的一个前缀就停。解决词法器里_scan_ident先把字母和下划线开头的完整序列吃掉直到遇到非字母数字下划线字符才停止然后拿整个文本查keywords集合。这样ifx就永远不会被误判为if只有独立且完整等于if的单词才命中关键字。5.2 左递归导致语法分析器栈溢出现象运行 Parser 时报RecursionError: maximum recursion depth exceeded或者程序直接卡死。原因文法写成了expr - expr term而parse_expr函数第一行又调用自身形成无限递归。LL(1) 文法不允许左递归但很多同学照抄课本上的 BNF 表示忘了改造。解决所有左递归产生式改写成右递归加循环。expr - term {(|-) term}对应的分析函数先解析第一个 term再用 while 循环匹配剩余运算符和优先级相同的 term。检查你文法表里的每一条产生式只要产生式右侧第一个符号和左侧相同就必须做这个改写。5.3 变量未定义错误的位置不对现象代码已经生成了几行三地址码然后在x y处报undefined variable: y但报错的行号或上下文信息很模糊你很难定位到源代码的哪一行出了问题。原因语义分析放在了代码生成后期而 CodeGen 里用异常抛错时没有把 AST 节点的行列信息带出来导致用户面对一个只有变量名没有位置的错误。解决在代码生成开始前先做一次独立的符号表遍历遍历 AST 中所有 ident 节点逐个检查存在性遇到未定义变量时抛出带源码行列的异常。Node 类里预留line、col字段Parser 在创建 Node 时填充tok.line、tok.col这样语义错误信息直接指向源代码位置。5.4 浮点数与标识符边界导致的词法误报现象输入3.14.15或者3.14x时词法器分别识别成了两个 Number 或一个 Number 加一个 Ident而语法分析器竟然能继续跑下去不报错最后生成一段错误的三地址码。原因_scan_number的小数点处理没限定只能出现一次也没检查数字后紧邻的字符类型。3.14.15会被拆成两个数字造成语法分析时出现两个连续常量实际上语法分析器报了错但你对错误提示看不懂。解决数字扫描里维护has_dot标志第二个小数点直接抛词法异常。数字扫描结束后如果下一个字符是字母或下划线同样抛SyntaxError。这样词法错误在预处理阶段就被拦截语法分析器不会收到畸形 Token 流承担不该它处理的任务。6. 验证方法与实验报告的打磨技巧词法、语法、语义、代码生成四个阶段都写完以后如何证明这个小编译器是可靠的取决于你测试用例的覆盖面。课程设计评审老师通常不会一行行看代码而是会看你的测试输入和输出是否覆盖了正常、边界、异常三类情况。6.1 测试用例矩阵类型输入预期结果正常运算a 1 2 * 3;三地址码t12*3; t21t1; at2括号优先级a (1 2) * 3;先加后乘变量调用a 10; b a 5;bt1; t1a5未定义变量a bb;报错undefined variable: bb词法错误x 1.2.3;报错invalid number错误运算符x 1 2;报错unknown char 6.2 用最小测试脚本驱动集成验证写一个test.py把源码字符串直接传给 Lexer再把 Token 流传给 Parser最后把 AST 传给 CodeGen四行代码完成端到端测试。# test.py from lexer import Lexer from parser import Parser from codegen import CodeGen source x 1 2 * 3; print(x); tokens Lexer(source).scan() ast Parser(tokens).parse_program() gen CodeGen() gen.gen(ast) for quad in gen.quads: print(quad)测试时我会刻意挑选边界输入比如只含有一个数字的表达式、空括号、以及一个很深的嵌套表达式这样能同时检验递归下降深度和三地址码临时变量的数量。一个课程设计要做到让程序在测试文件里跑起来然后把输出截图放进实验报告的验证结果一章这比任何空泛的小结更有说服力。实验报告里我一般会用一张模块划分表描述实现语言、词法器手写、语法分析使用递归下降、代码生成采用三地址码再用一段话解释每个模块的边界和接口。把那句“以后每次写完代码生成器我都会先用一个最小化测试用例做端到端验证确认四阶段调用链是通的再往后做”当作习惯写进报告开头比堆一大段设计理论更让评审老师相信你是真做过一遍的人。希望这篇拆解能帮你少走一段弯路。本文还有配套的精品资源点击获取