编译原理实验课代码与报告：从词法分析到代码生成的完整复现路径

简介这份资源是四川大学编译原理课程的实验课配套资料面向正在学习编译原理、需要动手实现编译器各阶段组件的高校学生。内容按周次组织覆盖词法分析、语法分析、语义分析与代码生成等核心环节并配有课程设计PPT与说明文档便于对照实验要求逐步推进。压缩包共53个文件、约2.24MB以txt测试用例、h头文件、c与c-源码、tny示例、makefile构建脚本、docx说明文档和pptx课件为主另含README.md与dfa.gv等辅助文件可支撑从记号流识别到抽象语法树构建、再到目标代码生成的完整练习。目前已有158人学习下载。读者可借助源码工程与测试用例复现各阶段实验结合说明文档理解提交要求与实现思路在真实编码中巩固编译流程与语言设计知识。1. 编译原理实验课代码与报告从词法分析到代码生成的完整复现路径很多同学学完编译原理的理论课龙书翻了大半本一到实验课要动手写词法分析器就卡住了。四川大学这门编译原理课程的实验课代码与实验报告解决的正是这个断层问题——它把课堂上的形式语言与自动机理论落成了可编译运行的词法分析器、语法分析器、语义分析和中间代码生成模块。这套材料适合正在上编译原理课、需要完成实验作业的本科生也适合想通过动手实现来真正理解编译器前端工作流程的自学者。核心价值不在于代码本身多复杂而在于它提供了一条从正则表达式到 DFA、从文法到语法树的完整实现链路每一段代码都对应着理论课上的一个知识点。拿到这套源码和说明书之后关键不是直接跑通就完事而是理解每个模块的设计取舍知道为什么用递归下降而不是 LR 分析知道符号表该怎么组织才不容易翻车。2. 实验环境搭建与源码结构拆解先搞清楚每个目录在干什么2.1 编译原理实验的典型工具链选型编译原理实验课通常不会限制死语言和工具但不同选择直接影响你调试的难度。常见的做法是用 C/C 或 Java 写词法分析和语法分析也有用 Python 快速原型验证的。四川大学这套材料从热搜词里能看到 java编译原理 和 python 相关的检索说明两种语言都有同学在关注。我一般会建议如果你时间紧、想快速看到结果用 Python 写词法分析和递归下降语法分析代码量少、调试方便如果你想把实验做扎实、后续还想扩展成完整的编译器前端用 C 或 Java 更合适因为符号表管理、内存控制这些在强类型语言里更接近真实编译器的做法。选型时还要考虑实验报告的要求。有些老师要求画出完整的 DFA 状态转移图有些要求对比不同语法分析算法的效率。这些在动手写代码之前就要确认清楚否则写到一半发现方向不对返工成本很高。2.2 源码目录的典型组织方式与阅读顺序拿到一套编译原理实验代码不要上来就从 main 函数开始读。典型的目录结构会按编译阶段划分比如 lexer/、parser/、semantic/、codegen/ 这样的分层。阅读顺序应该是先看词法分析器的输入输出定义再看语法分析器怎么调用词法分析器的结果然后看符号表在哪个阶段被填充和查询最后看中间代码或目标代码的生成逻辑。# 典型的编译原理实验项目目录结构 project/ ├── src/ │ ├── lexer/ # 词法分析模块 │ │ ├── token.h # Token 类型定义 │ │ └── lexer.cpp # 词法分析器实现 │ ├── parser/ # 语法分析模块 │ │ ├── ast.h # 抽象语法树节点定义 │ │ └── parser.cpp # 递归下降或 LR 分析器 │ ├── semantic/ # 语义分析模块 │ │ ├── symbol_table.h # 符号表数据结构 │ │ └── type_check.cpp # 类型检查逻辑 │ └── codegen/ # 代码生成模块 │ └── ir_gen.cpp # 中间代码生成 ├── test/ # 测试用例 │ ├── lexer_test/ │ └── parser_test/ ├── docs/ # 实验报告与说明文档 └── Makefile # 构建脚本这个结构不是固定的但核心思路是按编译阶段分层。阅读时先确认每个模块的输入是什么、输出是什么。词法分析器输入源程序字符串输出 Token 序列语法分析器输入 Token 序列输出语法树语义分析遍历语法树填充符号表并做类型检查代码生成再把语法树转成中间表示。搞清楚这条数据流后面看代码就不会迷路。2.3 编译运行的最小验证步骤在深入每个模块之前先确保整个项目能编译通过、能跑通一个最简单的测试用例。这一步看起来简单但很多同学卡在环境配置上。# 进入项目根目录后先看 Makefile 或构建脚本 cd project/ make clean make # 如果没有 Makefile手动编译以 C 为例 g -stdc17 -o compiler src/main.cpp src/lexer/lexer.cpp src/parser/parser.cpp # 跑一个最简单的测试输入 echo int main() { return 0; } test/simple.c ./compiler test/simple.c编译成功后观察输出是什么。有些实验代码会打印 Token 序列有些会输出语法树有些直接生成中间代码。确认输出格式和实验报告要求是否一致。如果编译报错先检查依赖库是否安装、编译器版本是否支持代码中用到的特性。C17 的 structured binding、Python 3.8 的海象运算符这些在老版本环境上会直接报语法错误。提示如果项目里带了 CMakeLists.txt优先用 cmake 构建比手写 g 命令可靠。遇到链接错误时先确认所有 .cpp 文件都加入了编译命令漏文件是新手最常见的翻车点。3. 词法分析与语法分析的核心实现从正则到语法树的落地细节3.1 词法分析器正则表达式到 DFA 的转换与手写实现词法分析的本质是把源程序的字符流切分成有意义的 Token 流。理论课上讲的是正则表达式转 NFA 再转 DFA但实际实验里大多数同学会选择手写词法分析器而不是用 lex 或 flex 自动生成。手写的好处是可控性强遇到边界情况好调试。手写词法分析器的核心逻辑是一个循环每次从输入流中读取字符根据当前字符判断进入哪个 Token 的识别分支。标识符和关键字通常用同一个识别逻辑先按标识符规则读入完整字符串再查关键字表决定是关键字还是普通标识符。# 手写词法分析器的核心循环Python 示例 KEYWORDS {int, float, if, else, while, return} def tokenize(source): tokens [] i 0 while i len(source): ch source[i] # 跳过空白字符 if ch.isspace(): i 1 continue # 识别标识符和关键字 if ch.isalpha() or ch _: start i while i len(source) and (source[i].isalnum() or source[i] _): i 1 word source[start:i] if word in KEYWORDS: tokens.append((KEYWORD, word)) else: tokens.append((IDENTIFIER, word)) continue # 识别数字常量 if ch.isdigit(): start i while i len(source) and source[i].isdigit(): i 1 tokens.append((NUMBER, source[start:i])) continue # 识别运算符和界符 if ch in -*/(){};,: tokens.append((OPERATOR, ch)) i 1 continue raise SyntaxError(f非法字符 {ch} 在位置 {i}) return tokens这段代码的逻辑很直白按字符类型分流标识符和关键字共用识别逻辑数字单独处理运算符和界符逐个匹配。参数方面KEYWORDS 集合决定了哪些字符串被识别为关键字这个集合要和语法分析器的文法定义保持一致。如果文法里把void当关键字但词法分析器的 KEYWORDS 里没有语法分析阶段就会把void当成普通标识符导致解析失败。实际实验中词法分析器还需要处理注释、字符串常量、浮点数等。注释的处理通常是在主循环里加一个分支遇到//就跳到行尾遇到/*就跳到*/。字符串常量要处理转义字符这个容易出 bug建议单独写一个函数处理。3.2 递归下降语法分析文法改写与 FIRST/FOLLOW 集的实际应用语法分析是编译原理实验里最容易翻车的部分。理论课上讲的 LL(1) 分析需要计算 FIRST 集和 FOLLOW 集构造预测分析表。但实际手写时递归下降更直观每个非终结符对应一个函数函数内部根据当前 Token 决定走哪条产生式。递归下降的前提是文法不能有左递归也不能有回溯。左递归需要改写成右递归形式比如E - E T | T要改成E - T E和E - T E | ε。这个改写过程在实验报告里通常要求写出来也是考试常考的点。# 递归下降语法分析器示例简化版表达式文法 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): if self.pos len(self.tokens): return self.tokens[self.pos] return (EOF, ) def consume(self, expected_typeNone): token self.peek() if expected_type and token[0] ! expected_type: raise SyntaxError(f期望 {expected_type}实际得到 {token}) self.pos 1 return token # E - T E def parse_E(self): node self.parse_T() return self.parse_E_prime(node) # E - T E | ε def parse_E_prime(self, left): if self.peek() (OPERATOR, ): self.consume() right self.parse_T() new_node (ADD, left, right) return self.parse_E_prime(new_node) return left # T - F T def parse_T(self): node self.parse_F() return self.parse_T_prime(node) # T - * F T | ε def parse_T_prime(self, left): if self.peek() (OPERATOR, *): self.consume() right self.parse_F() new_node (MUL, left, right) return self.parse_T_prime(new_node) return left # F - ( E ) | NUMBER def parse_F(self): token self.peek() if token (OPERATOR, (): self.consume() node self.parse_E() self.consume((OPERATOR, ))) return node elif token[0] NUMBER: self.consume() return (NUM, token[1]) raise SyntaxError(f意外的 Token: {token})这段代码展示了递归下降的核心模式每个非终结符一个函数函数内部根据当前 Token 决定产生式。parse_E_prime和parse_T_prime处理的是消除左递归后引入的新非终结符。参数方面self.pos是当前解析位置peek()看下一个 Token 但不移动位置consume()消费当前 Token 并前移。这种设计的好处是调试方便出错时能直接定位到哪个函数、哪个 Token 出了问题。实际实验中语法分析器要处理的文法比表达式复杂得多包括变量声明、控制流语句、函数定义等。建议先用简单的表达式文法跑通再逐步扩展。每加一条产生式就加一个对应的测试用例不要一次性写完再调试那样出错很难定位。3.3 符号表的设计与作用域管理符号表是语义分析的核心数据结构用来记录变量、函数、类型的信息。实验课上常见的符号表实现有链表、哈希表、栈式结构几种。链表实现简单但查找慢哈希表查找快但需要处理冲突栈式结构适合管理作用域。作用域管理是符号表最容易出问题的地方。进入一个块比如 if 语句的花括号时要压入一个新的作用域退出块时要弹出该作用域的所有符号。如果忘记弹出内层变量会泄漏到外层导致重复定义或引用错误。# 栈式符号表实现支持作用域嵌套 class SymbolTable: def __init__(self): self.scopes [{}] # 栈底是全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() def declare(self, name, type_info): current self.scopes[-1] if name in current: raise NameError(f重复定义: {name}) current[name] type_info def lookup(self, name): # 从最内层作用域向外查找 for scope in reversed(self.scopes): if name in scope: return scope[name] raise NameError(f未定义的标识符: {name})这个实现用列表模拟栈每个元素是一个字典代表一个作用域。declare只在当前作用域声明lookup从内向外查找。参数方面self.scopes[-1]始终指向当前作用域reversed(self.scopes)保证内层作用域优先。实际实验中符号表还需要记录变量的类型、维度、存储位置等信息这些根据实验要求扩展即可。注意符号表的查找效率直接影响编译速度如果实验要求处理大规模源程序建议把字典换成哈希表或平衡树。但在课程实验的规模下Python 字典足够快。4. 语义分析与中间代码生成类型检查与三地址码的工程实现4.1 类型检查的基本规则与实现方式语义分析阶段的核心任务是类型检查和作用域检查。类型检查要确保运算符的操作数类型匹配比如不能对整数和字符串做加法函数调用的实参类型要和形参匹配赋值语句左右两边类型兼容。实现类型检查通常是在语法树上做一次遍历每个节点根据子节点的类型计算自己的类型。如果类型不匹配就报错。这个过程叫类型推导或类型合成。# 类型检查的简化实现 def type_check(node, symbol_table): if node[0] NUM: return int elif node[0] IDENTIFIER: return symbol_table.lookup(node[1]) elif node[0] ADD: left_type type_check(node[1], symbol_table) right_type type_check(node[2], symbol_table) if left_type ! int or right_type ! int: raise TypeError(f加法操作数类型不匹配: {left_type} {right_type}) return int elif node[0] ASSIGN: var_type symbol_table.lookup(node[1]) expr_type type_check(node[2], symbol_table) if var_type ! expr_type: raise TypeError(f赋值类型不匹配: {var_type} {expr_type}) return var_type else: raise ValueError(f未知节点类型: {node[0]})这段代码递归遍历语法树每个节点返回自己的类型。ADD节点要求两个操作数都是intASSIGN节点要求左右类型一致。参数方面symbol_table用来查询标识符的类型node是语法树节点。实际实验中类型系统可能更复杂包括数组、结构体、指针等但核心思路是一样的自底向上推导类型遇到不匹配就报错。4.2 三地址码的生成策略与优化空间中间代码生成是编译原理实验的最后一个核心模块。三地址码是最常见的中间表示形式每条指令最多有三个操作数形式如x y op z。生成三地址码的过程通常是在语法树上做后序遍历为每个子表达式分配临时变量。# 三地址码生成示例 class IRGenerator: def __init__(self): self.temp_count 0 self.instructions [] def new_temp(self): self.temp_count 1 return ft{self.temp_count} def generate(self, node): if node[0] NUM: return node[1] elif node[0] IDENTIFIER: return node[1] elif node[0] ADD: left self.generate(node[1]) right self.generate(node[2]) temp self.new_temp() self.instructions.append(f{temp} {left} {right}) return temp elif node[0] MUL: left self.generate(node[1]) right self.generate(node[2]) temp self.new_temp() self.instructions.append(f{temp} {left} * {right}) return temp elif node[0] ASSIGN: value self.generate(node[2]) self.instructions.append(f{node[1]} {value}) return node[1]这段代码为每个运算符生成一条三地址指令临时变量用t1、t2这样的名字。参数方面temp_count保证临时变量名不重复instructions列表按顺序存储生成的指令。实际实验中还需要处理控制流语句比如 if 和 while 要生成标签和跳转指令。这部分容易出错的地方是标签的生成和管理建议用统一的标签计数器不要手动指定标签名。三地址码生成之后通常还有一步优化比如常量折叠、公共子表达式消除、死代码删除。课程实验对优化的要求不高但如果你想把实验做得出彩可以加一两个简单的优化 pass在实验报告里对比优化前后的指令数量。4.3 从语法树到中间代码的完整调用链把词法分析、语法分析、语义分析和中间代码生成串起来就是一个完整的编译器前端。调用链通常是源程序字符串 → 词法分析 → Token 序列 → 语法分析 → 语法树 → 语义分析 → 带类型信息的语法树 → 中间代码生成 → 三地址码序列。# 完整的编译流程调用示例 def compile_source(source): # 第一步词法分析 tokens tokenize(source) # 第二步语法分析 parser Parser(tokens) ast parser.parse_E() # 第三步语义分析 symbol_table SymbolTable() # 这里需要先遍历 AST 收集声明再做类型检查 type_check(ast, symbol_table) # 第四步中间代码生成 ir_gen IRGenerator() ir_gen.generate(ast) return ir_gen.instructions # 测试 source x 1 2 * 3 instructions compile_source(source) for inst in instructions: print(inst)这个调用链看起来简单但每一步的输入输出格式要对齐。词法分析器输出的 Token 类型要和语法分析器期望的一致语法树节点的结构要和语义分析、代码生成模块约定好。实际项目中这些接口定义通常放在头文件或单独的模块里修改时要同步更新所有使用方。提示调试时可以在每个阶段结束后打印中间结果比如词法分析后打印 Token 序列语法分析后打印语法树。这样出错时能快速定位是哪个阶段的问题。5. 实验报告撰写与代码调试的避坑指南5.1 实验报告里必须写清楚的几个关键点实验报告不是代码的流水账老师想看的是你对编译原理的理解。几个必须写清楚的点DFA 的状态转移图要画完整包括每个状态的含义和转移条件文法改写的过程要写出来特别是消除左递归和提取左公因子的步骤符号表的数据结构要说明为什么选这种实现时间复杂度是多少测试用例要覆盖边界情况比如空输入、非法字符、类型不匹配等。常见的问题是报告里只贴代码不解释或者解释得太笼统。比如写“用递归下降实现语法分析”但不写为什么选递归下降而不是 LR不写文法怎么改写的不写 FIRST/FOLLOW 集怎么算的。这样的报告即使代码跑通了分数也不会高。5.2 词法分析器调试时最容易翻车的三个地方第一个坑是标识符和关键字的边界。比如int是关键字但integer是标识符。如果词法分析器先匹配关键字再匹配标识符integer会被错误地切成int和eger。正确的做法是先按标识符规则读入完整字符串再查关键字表。第二个坑是数字常量的处理。123是整数123.456是浮点数123.和.456是否合法要看语言定义。如果实验要求支持浮点数词法分析器要能区分整数和小数还要处理科学计数法。第三个坑是注释的嵌套。C 语言不支持嵌套注释但有些实验要求支持。如果按简单的/*到*/匹配嵌套注释会提前结束。处理嵌套注释需要维护一个计数器遇到/*加一遇到*/减一减到零才结束。5.3 语法分析器报错时的排查思路语法分析器报错通常有两种一种是文法本身有问题比如有左递归或回溯另一种是代码实现和文法不一致。排查时先确认文法是否已经消除了左递归FIRST 集和 FOLLOW 集是否计算正确。然后检查代码里每个函数的产生式是否和文法一一对应。如果报错信息是“期望 X 但得到 Y”先看 Y 是不是词法分析器输出的 Token 类型和语法分析器期望的不一致。比如词法分析器把识别为OPERATOR但语法分析器期望的是PLUS这种命名不一致会导致解析失败。5.4 符号表和作用域相关的常见错误符号表最常见的错误是作用域没有正确弹出。比如解析完一个函数体后忘记调用exit_scope()导致函数内的局部变量泄漏到全局作用域。另一个错误是查找时没有从内向外遍历导致内层变量被外层同名变量遮蔽。还有一种情况是前向引用。比如函数 A 调用了函数 B但 B 定义在 A 后面。如果符号表只记录已声明的符号解析 A 的时候 B 还没被声明就会报未定义。解决办法是先做一遍声明收集把所有函数和全局变量先加入符号表再做类型检查。5.5 中间代码生成的验证方法中间代码生成后怎么验证生成的代码是对的最直接的方法是用一个简单的解释器执行三地址码看结果和预期是否一致。比如x 1 2 * 3应该生成类似t1 2 * 3、t2 1 t1、x t2的指令执行后 x 应该等于 7。如果没有现成的解释器可以手动模拟执行。把每条指令的操作数替换成实际值逐步计算。这个方法虽然笨但对小规模测试用例很有效。另外可以对比不同输入生成的指令数量如果某个输入生成的指令明显偏多可能是代码生成逻辑有冗余。6. 从课程实验到真实编译器的距离几个值得深挖的进阶方向课程实验的编译器前端通常只支持一个很小的语言子集离真实编译器还有很大距离。但如果你对这个方向感兴趣有几个进阶方向值得投入时间。第一个方向是错误恢复。课程实验里遇到语法错误通常直接抛异常退出但真实编译器需要尽可能多地报告错误而不是遇到第一个错误就停。实现错误恢复需要在语法分析器里加入同步机制比如遇到错误时跳到下一个分号或右花括号然后继续解析。第二个方向是中间代码优化。课程实验生成的三地址码通常没有经过任何优化指令数量多、临时变量多。可以尝试实现常量折叠、公共子表达式消除、死代码删除这几个经典优化 pass。优化前后的指令数量对比是实验报告里很出彩的内容。第三个方向是目标代码生成。从三地址码生成汇编代码需要处理寄存器分配、指令选择、栈帧布局等问题。这部分难度较大但能让你真正理解编译器后端的运作方式。如果时间有限可以先从简单的栈式分配入手所有变量都放在栈上用寄存器做临时计算。第四个方向是扩展语言特性。课程实验的语言通常只有基本类型和简单控制流可以尝试加入数组、结构体、函数指针、闭包等特性。每加一个特性都要同步修改词法分析、语法分析、语义分析和代码生成四个模块这个过程能让你深刻理解编译器各阶段之间的耦合关系。我自己的习惯是每完成一个实验就把代码整理成一个独立的模块加上清晰的接口定义和测试用例。这样后面做课程设计或者毕业设计时可以直接复用之前的模块不用从头再来。编译原理的实验代码写的时候觉得麻烦但整理好了就是一笔可以反复使用的资产。希望帮到你。本文还有配套的精品资源点击获取