编译原理课程设计：词法分析到三地址码的递归下降实现

简介这份编译原理课程设计资料包面向正在学习编译原理、需要完成课程实验或小型编译器实践的高校学生与自学者内容覆盖词法分析、LL(1)语法分析、LR(0)与SLR(1)语法分析、四元式生成及汇编代码生成等关键环节可用来对照理解从源程序到目标代码的完整流程。压缩包共14个文件包含4个cpp、3个c、3个头文件及3个txt、1个doc源码文件对应词法分析器、语法分析程序与小型编译器实现文本文件便于放置文法、测试输入或说明doc则为课程设计实验报告整体约557KB体量轻便。已有2350人学习下载说明其作为课程设计参考具有一定认可度。读者可从中获得LL(1)与SLR(1)文法的具体样例、针对ii*i等简单语句的分析思路、四元式与汇编生成的实现线索以及一份可对照撰写的实验报告框架适合用于实验复盘、代码阅读和课设整理。1. 从一段现场手写的源码说起这套课设到底要交付什么验收现场最常出现的场面是这样老师不看你的报告随手在白板上写三行代码——一个while里套if条件里带和比较运算——让你当场编译一遍。如果实现的编译器只认得自己那份测试文件里的写法多一层嵌套就崩报告写得再厚也救不回来。编译原理课程设计词法分析 语法分析 小型编译器 实验报告真正要交的东西是三样一份自己划定的语言子集、一套能自证正确的实现、一份把取舍讲清楚的报告。它适合正在赶这门课设的学生也适合想给团队做一套 DSL 前端原型的工程师——词法、语法、语义、中间代码这条流水线跑通一次后面看任何语言的解析器都不再是黑匣子。下面这套结构是我带过几轮之后固定下来的做法。2. 需求与技术选型先砍出一个讲得清的语言子集2.1 最小可交付子集三类语句、两类声明、一套表达式这类课设失败最多的地方是一上手照搬 C 语言文法结构体、指针、多维数组、switch全写进产生式结果到验收前一天连a b c * d;的优先级都还没调对。我一般会先把语言子集砍到能在两页纸内写完 BNF 的程度剩下的时间全部投在「跑通 报错准 报告有话说」上。一个够用又不寒酸的子集大致是这些类别支持的语法是否必做声明int a;int a 1;int f(int x) {...}必做赋值a expr;必做分支if (expr) stmt/if (expr) stmt else stmt必做循环while (expr) stmt必做输入输出print(expr);read(a);必做返回return expr;函数版必做表达式 - * /、 !、注释//行注释、/* */块注释必做扩展数组、for、float、字符串选做答辩加分项砍到这个程度整个语言的非终结符不超过 20 个每个非终结符对应一个递归下降函数代码量和可读性都在可控范围内。选做项留一两个报告里能写出「扩展设计」答辩时也有话说。提示先写一份sample/目录放 5 个能覆盖全部语法的样例程序任何一次改动都先跑这 5 个。这比事后写调试日志有用得多。2.2 手写递归下降还是上工具课程设计里的真实取舍四种做法都有人用效果差别很大方案工作量可调试性报告可写性答辩风险手写递归下降中高断点能停在具体函数高消除左递归、FIRST 集都能写低问什么答什么LL(1) 预测分析表中高中出错要看栈很高能画分析表中表写错就全错Yacc / Bison低低冲突提示难懂低容易变成「调工具」高被问「你自己做了什么」ANTLR 之类生成器低低低高我的建议是词法、语法都手写。原因很实际课程设计的评分点集中在「你是否理解了分析过程」手写代码里每一行都能对应到课本上的一个概念报告直接截图讲用生成器报告里只剩几句配置说明答辩时老师一问「这个冲突怎么解决的」就卡住。真要做表驱动也行但那是另一条路别两套混着上——见过太多人词法手写、语法用生成器最后连语法树的节点结构都对不齐。如果课设硬性要求 C/C结构完全一样Token改成struct关键字表改成std::unordered_map扫描主循环用switch分派递归下降函数照样一个非终结符一个函数。语言不是问题分层才是。2.3 工程分层五个目录边界划清报告就自动有了骨架我固定的目录结构是这样的mini_compiler/ ├── lexer.py # 词法字符流 → 记号流 ├── tokens.py # 记号类型、关键字表、运算符表三层共用 ├── ast_nodes.py # 语法树节点定义只有数据结构 ├── parser.py # 语法记号流 → 语法树 ├── symbols.py # 符号表作用域、类型、重定义检查 ├── codegen.py # 语义检查 三地址码生成 ├── main.py # 命令行入口串起流程、统一打印错误 └── tests/ # 正例、反例各一组报告里的测试表就从这来分层的意义不只是好看。第一错误收集能统一每一层只往自己的errors列表里追加带行列号的错误main.py一次性打印不会出现「词法报错后语法层继续乱解析、最后喷出两百行红字」的经典场面。第二报告章节可以直接按目录写第 3 章词法、第 4 章语法、第 5 章语义与中间代码每一节对应一个文件写起来不空。第三答辩演示时你能指着文件说流程比翻一屏几百行的单文件强太多。单文件写法在 300 行以内还能忍超过就再也改不动了这是血泪经验。3. 词法分析器从字符流到记号流的完整实现3.1 记号表与状态迁移先画 DFA再写代码词法这一层的核心其实只有一句话把字符流按最长匹配切成记号。但写之前一定要先定表不然代码里会到处是if。记号类型我一般定这几类KW关键字、ID标识符、NUM整数常量、OP运算符与界符、EOF结束符。关键字不单独设类型扫描出标识符后查一次关键字表再改类型这样加关键字只改一个集合。状态迁移用文字加表格说清楚就够了画在报告里也好看当前状态读入字符下一状态动作初态字母或下划线标识符态继续读字母数字标识符态非字母数字初态回退一格查关键字表产出 KW/ID初态数字数字态继续读数字数字态非数字初态回退一格产出 NUM初态运算符首字符运算符态尝试匹配二元运算符初态空白/换行初态跳过维护行列号初态其他错误态记录非法字符跳过继续先把这张表写在纸上代码基本就是照抄。报告里的「词法分析器设计」一节直接放这张表加一段说明比贴一百行代码有说服力。3.2 最长匹配与回退扫描主循环怎么写最容易翻车的是运算符匹配。如果被切成和语法分析会在一个莫名其妙的位置报错而错误信息完全指不到真正的原因。解决办法是把运算符表按长度倒序排列逐个用startswith试。# lexer.py —— 记号流的生产者只负责切分不做任何语法判断 from tokens import Token, KEYWORDS, OPERATORS # OPERATORS 已按长度倒序 class Scanner: def __init__(self, src: str): self.src, self.i src, 0 self.line, self.col 1, 1 self.errors [] # 只收集不中断 def _peek(self, k0): 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, self.col self.line 1, 1 else: self.col 1 return ch def _skip_blank_and_comment(self): while self.i len(self.src): c self._peek() if c in \t\r\n: self._advance() elif self.src.startswith(//, self.i): while self.i len(self.src) and self._peek() ! \n: self._advance() elif self.src.startswith(/*, self.i): start_line self.line self._advance(); self._advance() while self.i len(self.src) and not self.src.startswith(*/, self.i): self._advance() if self.i len(self.src): self.errors.append(f第{start_line}行: 块注释没有闭合) else: self._advance(); self._advance() else: return def tokens(self): out [] while True: self._skip_blank_and_comment() if self.i len(self.src): out.append(Token(EOF, , self.line, self.col)) return out c self._peek() if c.isalpha() or c _: out.append(self._scan_ident()) elif c.isdigit(): out.append(self._scan_number()) else: out.append(self._scan_operator()) def _scan_ident(self): line, col, buf self.line, self.col, while self._peek().isalnum() or self._peek() _: buf self._advance() kind KW if buf in KEYWORDS else ID return Token(kind, buf, line, col) def _scan_number(self): line, col, buf self.line, self.col, while self._peek().isdigit(): buf self._advance() if self._peek().isalpha(): # 12abc 这种要单独报错不能静默切两半 self.errors.append(f第{line}行第{col}列: 数字后面紧跟字母 {buf}{self._peek()}) return Token(NUM, buf, line, col) def _scan_operator(self): line, col self.line, self.col for op in OPERATORS: # 倒序遍历即最长匹配 if self.src.startswith(op, self.i): for _ in op: self._advance() return Token(OP, op, line, col) bad self._advance() # 非法字符吃掉、记错、继续扫 self.errors.append(f第{line}行第{col}列: 非法字符 {bad}) return Token(OP, ;, line, col) # 用分号占位避免语法层连锁崩溃几个设计点要说明。_advance里把行列号的维护收在一处是整个错误定位能准的前提任何绕过它的写法迟早出错。_scan_operator用倒序表实现最长匹配比写一堆if peek()的条件分支清晰得多加运算符只改tokens.py。非法字符不抛异常而是产出一个占位记号继续扫是为了让一次编译把所有词法错误都报出来——验收时老师常会故意塞几个错字一次报全和报一个就停观感差很多。Token里带line和col两个字段看起来是小事实际是后面所有报错的地基。少了它语法分析只能说「这里期望一个分号」加上它就能说「第 7 行第 12 列期望 ;实际 )」。报告里把这句话截图放进去是加分项。3.3 错误定位与错误表让报错指到第几行第几列词法错误通常只有四类做成一张表报告里直接放代码里按表分类错误码现象触发条件处理方式L01非法字符出现不在字符集里的符号如$跳过该字符继续扫描L02数字后接字母123abc报告并继续L03块注释未闭合到文件尾没找到*/定位到/*所在行L04非法转义如有字符串\q保留原字符并提示配套的做法是给每次编译输出一个汇总# main.py —— 统一出口所有层的错误在这里一次性打印 def compile_source(src: str): sc Scanner(src) toks sc.tokens() if sc.errors: # 词法有错就不进语法层避免误报滚雪球 return {stage: lexer, errors: sc.errors, code: []} ps Parser(toks) tree ps.parse_program() if ps.errors: return {stage: parser, errors: ps.errors, code: []} gen CodeGen() gen.visit(tree) return {stage: done, errors: gen.errors, code: gen.code}这段的意义是错误分阶段截断。词法有错就别往下走否则语法分析会用那堆占位记号解析出完全虚构的错误一屏红字里真正有用的那条被埋掉——这个坑几乎每个人都踩过一次。4. 语法分析递归下降、语法树与三地址码4.1 改造文法消除左递归与提取左公因子递归下降要求文法是 LL(1)直接照搬课本的表达式文法会死循环E - E T | T进入parse_E第一件事又调parse_E栈直接爆。所以写代码前必须先改文法这一步只是纸面工作但省不掉。表达式部分消除左递归改前E - E T | T T - T * F | F F - ( E ) | id | num 改后E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id | num语句部分提取左公因子if和while都以关键字开头天然不冲突真正要处理的是声明和赋值的公共前缀两者都以ID开头。惯用做法是把判断推迟到看见第二个记号ID之后是就是赋值是(就是函数调用语句否则按声明处理。用一个记号的前瞻就能定不需要回溯报告里写「提取左公因子后用 FOLLOW 集区分」逻辑就对上了。实际编码时不必真去写E这样的非终结符函数循环展开更简单也更好读parse_expr里一个while就等价于E报告里说明「循环实现右递归展开」即可这两件事是一回事。4.2 语法树节点与递归下降函数语法树节点只存结构不带任何计算逻辑# ast_nodes.py —— 纯数据结构便于打印、遍历、画图 from dataclasses import dataclass, field dataclass class Node: kind: str # Program/Block/If/While/Assign/BinOp/Num/Id/Call... value: str # 运算符或字面量 kids: list field(default_factorylist)Parser的骨架是「一个非终结符一个方法」# parser.py class Parser: def __init__(self, toks): self.toks, self.p toks, 0 self.errors [] def cur(self): return self.toks[self.p] def at(self, text): return self.cur().text text def at_kind(self, k): return self.cur().kind k def eat(self, text): if self.at(text): self.p 1 return True t self.cur() self.errors.append(f第{t.line}行第{t.col}列: 期望 {text}实际 {t.text or EOF}) return False def parse_program(self): body [] while not self.at_kind(EOF): body.append(self.parse_stmt()) return Node(Program, kidsbody) def parse_stmt(self): if self.at({): self.eat({); body [] while not self.at(}) and not self.at_kind(EOF): body.append(self.parse_stmt()) self.eat(}) return Node(Block, kidsbody) if self.at(if): self.eat(if); self.eat(() cond self.parse_expr(); self.eat()) then self.parse_stmt() other None if self.at(else): # 悬空 else 就近匹配这里天然正确 self.eat(else); other self.parse_stmt() return Node(If, kids[cond, then] ([other] if other else [])) if self.at(while): self.eat(while); self.eat(() cond self.parse_expr(); self.eat()) return Node(While, kids[cond, self.parse_stmt()]) if self.at_kind(ID): name self.cur().text; self.p 1 self.eat() e self.parse_expr(); self.eat(;) return Node(Assign, name, [e]) t self.cur() self.errors.append(f第{t.line}行第{t.col}列: 无法识别的语句起始 {t.text}) self.p 1 # 跳过当前记号做错误恢复防止死循环 return Node(Error) def parse_expr(self): node self.parse_term() while self.at() or self.at(-): op self.cur().text; self.p 1 node Node(BinOp, op, [node, self.parse_term()]) return node def parse_term(self): node self.parse_factor() while self.at(*) or self.at(/): op self.cur().text; self.p 1 node Node(BinOp, op, [node, self.parse_factor()]) return node def parse_factor(self): t self.cur() if t.kind NUM: self.p 1; return Node(Num, t.text) if t.kind ID: self.p 1; return Node(Id, t.text) if self.at((): self.eat((); e self.parse_expr(); self.eat()) return e self.errors.append(f第{t.line}行第{t.col}列: 表达式里出现非法记号 {t.text}) self.p 1 return Node(Num, 0)关键在几处细节。parse_expr里的while就是消除左递归后的E优先级靠函数调用层次体现parse_expr处理加减parse_term处理乘除parse_factor处理括号和原子层次压住了优先级不需要在代码里写任何优先级数字。错误恢复那一句self.p 1是保命的——如果报错后不推进指针parse_stmt会在同一个记号上无限循环程序卡死很多人调半天以为是文法写错其实是这一行漏了。Node(Error)这种占位节点让语法树保持完整后面打印或画图时不会中断。注意else的悬挂问题在递归下降里自动就近匹配不需要额外处理但如果文法是 LL(1) 表驱动就必须在报告里说明「else 归约到最近的 if」这个约定否则老师会问。4.3 从语法树到三地址码符号表与临时变量小型编译器要「编」出点东西来最省事又像样的目标是三地址码每条指令最多一个运算符形如t1 a b。它比直接生成汇编容易验证又比只输出语法树有分量。符号表先用单层就够dict存名字 - 类型遇到重复声明报错# symbols.py class SymbolTable: def __init__(self): self.table, self.errors {}, [] def declare(self, name, typ, line0): if name in self.table: self.errors.append(f第{line}行: 变量 {name} 重复定义) return False self.table[name] typ return True def lookup(self, name, line0): if name not in self.table: self.errors.append(f第{line}行: 变量 {name} 未声明就使用) return None return self.table[name]生成器用后序遍历语法树回溯时把所有子节点的结果合成一条指令# codegen.py class CodeGen: def __init__(self): self.code, self.n, self.syms [], 0, SymbolTable() self.errors [] def new_tmp(self): self.n 1 return ft{self.n} def emit(self, s): self.code.append(s) def visit(self, node): m getattr(self, v_ node.kind, None) if m is None: self.errors.append(f不支持的节点类型: {node.kind}) return return m(node) def v_Num(self, node): return node.value def v_Id(self, node): self.syms.lookup(node.value) return node.value def v_BinOp(self, node): a self.visit(node.kids[0]) b self.visit(node.kids[1]) t self.new_tmp() self.emit(f{t} {a} {node.value} {b}) # 后序先算子节点再发指令 return t def v_Assign(self, node): val self.visit(node.kids[0]) self.syms.declare(node.value, int) self.emit(f{node.value} {val}) def v_If(self, node): cond self.visit(node.kids[0]) l_else, l_end self.new_label(), self.new_label() self.emit(fifFalse {cond} goto {l_else}) self.visit(node.kids[1]) if len(node.kids) 3: self.emit(fgoto {l_end}) self.emit(f{l_else}:) self.visit(node.kids[2]) self.emit(f{l_end}:) else: self.emit(f{l_else}:) def v_While(self, node): l_beg, l_end self.new_label(), self.new_label() self.emit(f{l_beg}:) cond self.visit(node.kids[0]) self.emit(fifFalse {cond} goto {l_end}) self.visit(node.kids[1]) self.emit(fgoto {l_beg}) self.emit(f{l_end}:) def new_label(self): self.n 1 return fL{self.n}设计上有两点值得在报告里写。第一后序遍历保证「子表达式的临时变量先生成」a b * c会先产出t1 b * c再产出t2 a t1优先级由语法树结构天然带入生成阶段不需要再判优先级这是把复杂度前移到语法层的好处。第二if和while的标签生成用计数器统一编号输出稳定可复现测试时可以直接拿两份输出做 diff比人眼看快得多。输出的三地址码序列还能做一件便宜但效果很好的事常量折叠。遇到BinOp两个子节点都是Num时直接算出结果不生成临时变量。代码不到十行报告里却可以独立成节讲「局部优化」答辩时是个现成的亮点。5. 避坑与排查这类课设最容易翻车的五个点5.1 报错行号整体偏移一行或一列现象报错说第 7 行实际错误在第 6 行永远差一。原因几乎都是行列号维护没做在唯一入口有的分支里直接self.i 1绕过_advance换行时列号没重置或者初始行号写成了 0。解决方式是把所有指针推进强制收敛到_advance一个函数里再写一个自测给它一段故意在第 3 行第 5 列出错的源码断言错误信息里包含第3行第5列。这个测试一旦立住后面所有报错都可信。5.2 表达式优先级错乱a b * c算成(ab)*c现象语法树画出来一塌糊涂跑出来的结果和手算不一致。原因多半是parse_expr里把乘除也收进了同一个while或者parse_term直接递归回了parse_expr。解决方式是按优先级层次拆函数加减一层、乘除一层、原子一层每层只处理自己那一级的运算符改完打印语法树验证*的节点必须在的下方。如果语言里有比较和逻辑运算就在加减之上再插两层顺序是「逻辑或 → 逻辑与 → 比较 → 加减 → 乘除 → 原子」层次不能乱。5.3 一路报错几百行真正有用的那条被淹没现象编译一个故意写错的样例控制台刷出两三百行错误全是后面的连锁反应。原因是没有做错误恢复和阶段截断词法出错后仍往下走语法层拿着占位记号乱解析语义层再对空指针报一遍。解决方式是分阶段短路词法有错直接返回语法层每报一次错就跳过至少一个记号语义检查只在语法树无错时执行。判据很直白故意塞一个错字输出应该只有一行错而不是一屏。5.4 递归下降写成了死循环程序卡住不返回现象编译一个空文件也卡死CPU 占满没有任何输出。原因通常是某个while循环里没有推进指针或者报错分支只记录不前进最常见的是parse_stmt遇到不认识的记号后原地打转。排查手法是加一个保险在循环里判断「本次迭代指针是否前进」没前进就强制self.p 1并记一条内部错误。更早的预防是给所有解析函数入口加一条断言打印当前记号卡住时看最后一条日志就知道死在哪。5.5 报告里的文法与实际代码对不上现象答辩时老师对着报告的 BNF 问「这个E在代码哪一行」翻半天找不到。原因很常见——论文先写完后来代码改文法没同步。解决方式是让报告里的文法成为唯一权威把产生式单独放在grammar.txt代码注释里引用产生式编号# E - T E改文法时先改这个文件。还有一个细节报告里贴的代码必须是能跑的那份别为了好看手抄一遍精简版抄的过程必然出错被问到对不上就是硬伤。6. 验收与答辩用一组测试样例自证正确性这套东西最怕的不是跑不起来而是跑起来了但你证明不了它是对的。我固定的做法是先准备一张测试表每个用例对应一个明确要验证的点跑完把预期输出和实际输出并排放在报告里答辩时直接翻这页。编号输入要点验证目标预期结果T01int a 1 2 * 3;优先级与临时变量生成t1 2 * 3、t2 1 t1T02if嵌套if无else悬挂 else 匹配语法树中 else 归属内层T03while内嵌if标签生成不冲突标签编号连续且唯一T04int a; int a;重复定义检查报「重复定义」定位到行T05a b 1;b 未声明未声明使用报「未声明就使用」T06int a 12abc;词法错误定位报第几行第几列数字后接字母T07if (a 1 {括号不匹配报「期望 )」指向行号准备完这张表答辩的节奏基本就定了。老师问「你怎么保证正确」你翻到测试表指 T01 讲优先级、指 T04 和 T05 讲语义检查、指 T07 讲错误恢复三句话讲完比念十页设计更有用。有个小技巧把所有测试用例做成tests/下的文件对一个输入一个期望输出用一个几行的脚本跑回归改完代码一条命令看全绿这比手动点十几个样例稳得多。老师万一现场改一段源码让你编译你只要不慌先看它落在测试表哪一类把对应样例的结论套上去。还有一个高频提问值得提前想好答案「你的编译器支持到什么程度」。标准答法是承认边界——支持哪些语句、哪些运算符、哪些错误类型明确说数组、for、浮点是扩展点目前没做。主动划边界比被问出来强因为老师真正在意的不是功能多少而是你知不知道自己做到哪。从那以后我每次带这类课设都强制自己先写测试表和grammar.txt再动一行解析代码——顺序反过来的那几次最后都在答辩前一晚改文法改到崩。希望这套结构能帮你少走一遍这条路。本文还有配套的精品资源点击获取