四川大学编译原理实验课：从源码到实验报告的完整复现路径

简介这份资源是四川大学编译原理课程的实验课配套资料面向正在学习编译原理、需要完成课程实验或课程设计的高校学生。内容按周次组织覆盖词法分析、语法分析、语义分析与代码生成等编译器核心阶段并配有tiny与c-两套语言的测试用例便于对照验证各阶段实现效果。压缩包共53个文件、约2.24MB以txt测试用例、h头文件、c与c-源码、tny样例、makefile构建脚本为主另有docx说明文档、pptx课程设计讲稿和README.md项目概述源码与文档相互配套方便理解工程结构与实验要求。目前已有158人学习。读者可借助各周实验的源码与说明文档梳理从记号流到抽象语法树再到目标代码的完整实现路径结合测试用例调试自己的分析器与代码生成模块并参考课程设计讲稿把握实验重点与提交要求适合作为课程作业参考与期末复习的实践材料。1. 四川大学编译原理实验课从源码到实验报告的完整复现路径如果你正在搜“四川大学编译原理课程-实验课相关代码与实验报告”大概率是三种人之一正在上这门课、被 lex/yacc 或递归下降卡住的学生想拿一套完整实现对照自己代码的开发者或者准备把这套实验当作编译原理入门练手项目的自学者。这个标题背后其实是一套典型的编译原理实验体系词法分析、语法分析、语义分析、中间代码生成外加一份把设计思路和测试结果写清楚的实验报告。它解决的核心问题是——让你不用从零猜“老师到底想要什么”而是有一份可运行、可对照、可改参数的参考实现。适合谁适合已经学过形式语言与自动机、但一动手就不知道从哪写起的同学也适合想用 Python 或 Java 把编译前端跑通、顺便理解符号表和语法制导翻译的工程师。下面我按“先跑通、再改对、最后写明白”的顺序把这条路拆开讲。2. 编译原理实验课到底在做什么四类实验与选型逻辑2.1 词法分析、语法分析、语义分析、代码生成各自的任务边界编译原理实验课通常不是让你写一个完整编译器而是把前端拆成几个可独立验证的模块。词法分析负责把字符流切成 token输出类型, 值序列语法分析负责按文法把 token 序列组织成语法树语义分析负责填符号表、做类型检查代码生成负责把语法树或中间表示翻译成四元式、三地址码或目标汇编。这四步的输入输出必须严格对齐否则后面全崩。常见做法是词法分析输出 token 文件语法分析读 token 文件建 AST语义分析遍历 AST 填符号表代码生成再遍历一次 AST 输出中间代码。每一步都留一个可单独测试的入口这样调试时不用每次从头跑。选型上词法分析可以用手写状态机也可以用 lex/flex语法分析可以用递归下降、LL(1)、LR(1)也可以用 yacc/bison。四川大学这类课程实验通常要求手写递归下降或 LL(1)因为能逼你理解 FIRST/FOLLOW 集和预测分析表。如果你只是想快速跑通用 Python 的 PLY 或 Java 的 JavaCC 也能交差但报告里最好写清楚你用的是工具生成还是手写避免答辩时被追问“预测分析表怎么构造的”答不上来。2.2 为什么先跑通词法语法再补语义和代码生成血泪经验一上来就同时写四个模块最后一定是一锅粥。正确顺序是先让词法分析能正确切出所有 token再用这些 token 喂给语法分析确认能建出正确的语法树。这两步跑通后语义分析和代码生成才有稳定的输入。具体操作先写一个lexer.py读源文件输出 token 列表再写一个parser.py读 token 列表输出 AST 的 JSON 或缩进树然后写semantic.py遍历 AST输出符号表和类型检查结果最后写codegen.py输出四元式。每一步都写一个main函数支持命令行传文件名。这样你可以单独测试每一步比如只跑词法分析看 token 对不对不用每次都跑完整流程。参数上词法分析要定义好关键字表、运算符表、界符表以及标识符和常数的正则。语法分析要定义好文法产生式并计算 FIRST 和 FOLLOW 集。语义分析要定义符号表结构通常用栈式符号表或哈希表加作用域链。代码生成要定义四元式的格式比如(op, arg1, arg2, result)。这些结构一旦定下来后面改起来成本很高所以最好在实验报告里先写清楚你的设计再动手写代码。2.3 实验报告里必须写清楚的五个部分实验报告不是代码的附属品它要能独立说明你的设计。常见结构是实验目的、实验环境、实验设计文法、数据结构、算法描述、实验步骤关键代码和测试用例、实验结果与分析正确性、边界情况、复杂度。其中实验设计部分要放文法产生式、FIRST/FOLLOW 集、预测分析表或 LR 分析表实验步骤要放核心代码片段和输入输出示例实验结果要放至少三组测试用例包括正常程序、含错误的程序、边界情况空文件、只有注释、超长标识符。如果你用的是 Python可以在报告里贴lexer.py和parser.py的关键函数如果用的是 Java贴类图和核心方法。注意报告里不要只贴代码不解释每段代码后面要写清楚它对应哪个算法步骤、参数怎么设、为什么这么设。3. 用 Python 手写递归下降从源码到可运行的最小闭环3.1 词法分析器的状态机实现与 token 定义先定义一个 token 类包含类型和值。然后写一个Lexer类维护当前位置、行号、列号。核心是一个next_token方法用 while 循环跳过空白和注释然后根据当前字符判断是标识符、数字、字符串还是运算符。标识符用[a-zA-Z_][a-zA-Z0-9_]*数字用[0-9]运算符和界符用字典匹配。关键字在标识符识别后查表转换类型。# lexer.py import re class Token: def __init__(self, type_, value, line, col): self.type type_ self.value value self.line line self.col col class Lexer: def __init__(self, text): self.text text self.pos 0 self.line 1 self.col 1 self.keywords {if, else, while, int, float, return} def next_token(self): while self.pos len(self.text): ch self.text[self.pos] if ch in \t\r: self._advance() elif ch \n: self.line 1 self.col 1 self.pos 1 elif ch / and self.pos 1 len(self.text) and self.text[self.pos1] /: while self.pos len(self.text) and self.text[self.pos] ! \n: self._advance() else: break if self.pos len(self.text): return Token(EOF, , self.line, self.col) ch self.text[self.pos] if ch.isalpha() or ch _: return self._read_identifier() if ch.isdigit(): return self._read_number() return self._read_operator() def _advance(self): self.pos 1 self.col 1 def _read_identifier(self): start self.pos while self.pos len(self.text) and (self.text[self.pos].isalnum() or self.text[self.pos] _): self._advance() value self.text[start:self.pos] type_ KEYWORD if value in self.keywords else ID return Token(type_, value, self.line, self.col - len(value)) def _read_number(self): start self.pos while self.pos len(self.text) and self.text[self.pos].isdigit(): self._advance() return Token(NUM, self.text[start:self.pos], self.line, self.col - (self.pos - start)) def _read_operator(self): for op in [, !, , , , ||]: if self.text.startswith(op, self.pos): self.pos len(op) self.col len(op) return Token(OP, op, self.line, self.col - len(op)) ch self.text[self.pos] self._advance() return Token(OP, ch, self.line, self.col - 1)这段代码的逻辑是先跳过空白、换行和单行注释然后根据首字符判断是标识符、数字还是运算符。标识符识别后查关键字表决定是KEYWORD还是ID。数字只处理整数浮点数可以扩展。运算符优先匹配双字符运算符再匹配单字符。参数上keywords集合可以根据你的文法调整_read_operator里的运算符列表也要和文法保持一致。测试时输入一段简单程序打印所有 token检查类型和值是否正确。3.2 递归下降语法分析表达式、语句与语法树节点递归下降的核心是每个非终结符对应一个函数。比如parse_expr处理加减parse_term处理乘除parse_factor处理括号和数字。语句层面parse_stmt根据当前 token 决定是赋值、if、while 还是 return。语法树节点用类表示比如BinOp、Num、Assign、If。# parser.py from lexer import Lexer, Token class ASTNode: pass class BinOp(ASTNode): def __init__(self, left, op, right): self.left left self.op op self.right right class Num(ASTNode): def __init__(self, value): self.value value class Assign(ASTNode): def __init__(self, name, expr): self.name name self.expr expr class Parser: def __init__(self, lexer): self.lexer lexer self.current self.lexer.next_token() def eat(self, type_): if self.current.type type_: self.current self.lexer.next_token() else: raise SyntaxError(fExpected {type_}, got {self.current.type} at line {self.current.line}) def parse(self): stmts [] while self.current.type ! EOF: stmts.append(self.parse_stmt()) return stmts def parse_stmt(self): if self.current.type ID: name self.current.value self.eat(ID) self.eat(OP) # 假设赋值是 expr self.parse_expr() return Assign(name, expr) elif self.current.type KEYWORD and self.current.value if: self.eat(KEYWORD) self.eat(OP) # ( cond self.parse_expr() self.eat(OP) # ) body self.parse_stmt() return (if, cond, body) else: raise SyntaxError(fUnexpected token {self.current.type} at line {self.current.line}) def parse_expr(self): node self.parse_term() while self.current.type OP and self.current.value in (, -): op self.current.value self.eat(OP) right self.parse_term() node BinOp(node, op, right) return node def parse_term(self): node self.parse_factor() while self.current.type OP and self.current.value in (*, /): op self.current.value self.eat(OP) right self.parse_factor() node BinOp(node, op, right) return node def parse_factor(self): if self.current.type NUM: value self.current.value self.eat(NUM) return Num(value) elif self.current.type OP and self.current.value (: self.eat(OP) node self.parse_expr() self.eat(OP) # ) return node else: raise SyntaxError(fUnexpected token {self.current.type} at line {self.current.line})这段代码的逻辑是parse循环读取语句直到 EOFparse_stmt根据当前 token 判断语句类型parse_expr和parse_term处理二元运算的优先级parse_factor处理数字和括号。参数上运算符优先级由函数调用层次决定parse_expr处理最低优先级parse_term处理较高优先级。测试时输入x 1 2 * 3打印 AST检查乘号是否在加号下面。注意这里假设赋值符号是实际实验里可能是:或其他需要根据文法调整。3.3 语义分析符号表填充与类型检查的最小实现语义分析遍历 AST维护一个符号表。符号表可以用字典加作用域链或者简单的列表。每个变量声明时插入符号表使用时查找。类型检查可以简单到只检查变量是否声明、赋值左右类型是否一致。# semantic.py class SymbolTable: def __init__(self): self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, type_): if name in self.scopes[-1]: raise SemanticError(fVariable {name} already declared) self.scopes[-1][name] type_ def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise SemanticError(fVariable {name} not declared) class SemanticAnalyzer: def __init__(self): self.symtab SymbolTable() def analyze(self, node): if isinstance(node, Assign): type_ self.analyze(node.expr) self.symtab.declare(node.name, type_) elif isinstance(node, BinOp): left_type self.analyze(node.left) right_type self.analyze(node.right) if left_type ! right_type: raise SemanticError(fType mismatch: {left_type} vs {right_type}) return left_type elif isinstance(node, Num): return int else: raise SemanticError(fUnknown node type {type(node)})这段代码的逻辑是SymbolTable用栈维护作用域declare在当前作用域插入变量lookup从内到外查找。SemanticAnalyzer遍历 AST赋值时先分析表达式类型再声明变量二元运算要求左右类型一致。参数上类型系统可以扩展为int、float、bool等。测试时输入x 1 2应该能声明x为int输入x 1 y应该报y未声明。注意这里没有处理变量重复声明和未使用变量实际实验里可能需要。4. 语法分析选型递归下降、LL(1) 与 LR(1) 的取舍与参数4.1 三种方法的适用场景与实验报告里的对比写法递归下降适合手写代码直观但需要消除左递归和提取左公因子。LL(1) 适合用预测分析表需要计算 FIRST 和 FOLLOW 集适合文法简单的语言。LR(1) 功能最强能处理几乎所有上下文无关文法但分析表构造复杂通常用工具生成。实验报告里可以列一个对比表方法、优点、缺点、适用文法、实现难度。比如方法优点缺点适用文法实现难度递归下降代码直观易调试需要消除左递归LL(1)低LL(1)表驱动结构清晰文法限制多LL(1)中LR(1)功能强适用广表构造复杂LR(1)高选型建议如果实验要求手写优先递归下降如果要求用工具可以用 yacc/bison 生成 LR 分析器。报告里要写清楚你为什么选这种方法以及你的文法是否满足该方法的要求。4.2 FIRST/FOLLOW 集计算与预测分析表构造LL(1) 的核心是 FIRST 和 FOLLOW 集。FIRST(A) 是 A 能推导出的首终结符集合FOLLOW(A) 是 A 后面可能紧跟的终结符集合。计算规则对于产生式 A → αFIRST(α) 加入 FIRST(A)如果 α 能推导出 ε则 FOLLOW(A) 加入 FOLLOW(A)。预测分析表 M[A, a] 填产生式 A → α其中 a 在 FIRST(α) 中或者 a 在 FOLLOW(A) 中且 α 能推导出 ε。# first_follow.py def compute_first(grammar): first {nt: set() for nt in grammar} changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: if not prod: if not in first[nt]: first[nt].add() changed True else: for sym in prod: if sym in grammar: before len(first[nt]) first[nt].update(first[sym] - {}) if not in first[sym]: break if len(first[nt]) before: changed True else: if sym not in first[nt]: first[nt].add(sym) changed True break return first def compute_follow(grammar, first, start): follow {nt: set() for nt in grammar} follow[start].add($) changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym in grammar: rest prod[i1:] if rest: first_rest set() for s in rest: if s in grammar: first_rest.update(first[s] - {}) if not in first[s]: break else: first_rest.add(s) break before len(follow[sym]) follow[sym].update(first_rest) if len(follow[sym]) before: changed True if all(s in grammar and in first[s] for s in rest): follow[sym].update(follow[nt]) else: follow[sym].update(follow[nt]) return follow这段代码的逻辑是compute_first迭代计算每个非终结符的 FIRST 集直到不再变化compute_follow根据产生式右部计算 FOLLOW 集。参数上grammar是字典键是非终结符值是产生式列表每个产生式是符号列表。测试时用一个简单文法验证比如E → T EE → T E | εT → F TT → * F T | εF → ( E ) | id。注意这里没有处理左递归实际使用前要先消除左递归。4.3 用 PLY 或 JavaCC 快速生成分析器的配置要点如果不想手写可以用 PLYPython Lex-Yacc或 JavaCC。PLY 的用法是定义 token 列表和文法规则然后调用yacc.yacc()生成分析器。配置要点token 列表要和词法分析器一致文法规则用函数定义每个函数对应一个产生式优先级用precedence元组定义。JavaCC 需要写.jj文件定义 token 和产生式然后生成 Java 代码。参数上PLY 的yacc.yacc()可以传debugTrue输出分析过程JavaCC 可以配置LOOKAHEAD参数解决冲突。注意工具生成的分析器虽然快但实验报告里要写清楚你用的是工具以及工具生成的代码和你手写的部分如何衔接。5. 避坑与排查编译原理实验里最容易翻车的五个点5.1 词法分析把关键字识别成标识符现象输入iftoken 类型是ID而不是KEYWORD。原因关键字表没有在标识符识别后查表或者查表时大小写不一致。解决在_read_identifier里读完标识符后立即查keywords集合如果在里面就返回KEYWORD否则返回ID。注意关键字表要和文法里的关键字完全一致不要漏掉else、while等。5.2 语法分析遇到左递归直接栈溢出现象递归下降分析器在解析表达式时无限递归报RecursionError。原因文法里有左递归比如E → E T。解决消除左递归改成E → T EE → T E | ε。然后在代码里对应修改parse_expr和parse_expr_prime。注意消除左递归后语法树的结合性会变需要调整代码保证左结合。5.3 语义分析符号表作用域没退出导致变量泄漏现象在 if 块里声明的变量出了块还能访问。原因enter_scope和exit_scope没有成对调用或者exit_scope没有弹出作用域。解决在遍历块语句时进入块前调用enter_scope离开块后调用exit_scope。注意函数参数也要在当前作用域声明不要漏掉。5.4 代码生成四元式顺序错乱导致结果不对现象生成的中间代码执行结果和预期不符。原因遍历 AST 时先生成了结果四元式后生成了操作数四元式。解决后序遍历 AST先处理子节点再生成当前节点的四元式。注意临时变量编号要全局唯一不要重复使用。5.5 实验报告里测试用例太少被扣分现象报告只贴了一个正常程序没有错误处理和边界情况。原因只关注正确路径忽略了异常路径。解决至少准备三组测试用例正常程序含赋值、运算、if、while、错误程序含语法错误、语义错误、边界情况空文件、只有注释、超长标识符、嵌套括号。每组用例都要贴输入和输出并分析结果。6. 从能跑到能交实验报告的验证方法与一个具体技巧最后一章说一个我反复用的技巧把实验报告当成“可复现的说明书”来写而不是“代码的注释”。具体做法是在报告里放一个“一键复现”章节写清楚运行环境、依赖安装、编译命令、测试命令。比如# 安装依赖 pip install ply # 运行词法分析 python lexer.py test.c # 运行语法分析 python parser.py test.c # 运行完整流程 python main.py test.c然后放一个测试用例表列出输入文件、预期输出、实际输出、是否通过。这样答辩时老师可以直接照着跑不用猜你的代码怎么用。验证方法上除了自己测还可以用“交叉验证”用你的词法分析器输出 token再用工具生成的词法分析器输出 token对比两者是否一致。如果一致说明你的词法分析基本正确如果不一致看是关键字表不同还是正则不同。另一个技巧是“错误注入”故意在测试程序里加一个语法错误看你的分析器能不能报出正确的行号和错误类型。很多实验只要求能分析正确程序但实际编译器必须能处理错误。如果你的分析器遇到错误就崩溃报告里要写清楚你做了什么错误恢复比如跳过当前语句直到分号。我自己的习惯是每写完一个模块先写一个最小的测试用例跑通后再写下一个模块。这样出问题时能快速定位是哪个模块的锅。希望帮到你。本文还有配套的精品资源点击获取