简介这是北京邮电大学计算机科学与技术专业大三上学期编译原理课程的一份课内作业完整方案面向计科、人工智能、通信工程、自动化等专业学生也适合正在完成编译原理课程设计、毕业设计或初期项目演示的学习者。作业聚焦词法分析和语法分析两大核心环节最终得分九十七分源代码经过测试运行成功并配套文档说明、实验报告以及演示文稿和PDF讲义既可用来理解编译原理从词法到语法的实现流程也可直接作为课程作业、答辩展示的参考模板。压缩包整体约2.7MB内容以源代码、实验报告、说明文档、演示文稿和PDF讲义为主目录结构清楚便于按需取用。目前已有122人浏览学习。除代码与报告外还附有答辩评审平均九十六分的项目备注初学者可据此对照理解实现思路若运行遇到问题也可私聊咨询适合从入门到进阶的编译原理学习者。1. 编译原理课内作业冲97分的起点词法分析和语法分析到底在交什么编译原理课内作业的分数其实没什么黑匣子。把大三上的词法分析语法分析实验拆开看97分的提交和80分的提交差距通常不在算法有多惊艳而在三件事Token划分够不够严谨、错误恢复能不能快速收敛、交付物能不能让老师十分钟看懂你在做什么。这篇笔记按“词法状态机怎么建模→语法策略怎么选→作业包怎么组织→哪些地方容易翻车→用什么方法兜底”的顺序把一个能稳定冲高分的编译原理课内作业完整拆开。适合正在写实验报告和准备答辩的计算机专业学生也适合想把旧代码整理成可复用模板的开发者。2. 词法分析怎么做才不丢分Token建模、状态机与最小实现很多同学的词法分析器能跑但一问到“状态怎么转移、边界怎么处理”就说不清。词法分析这道题的得分关键不是代码多少而是能不能用一张状态转换图和一份Token定义表把设计讲明白。我的习惯是先建Token类型再设计扫描主循环最后才补边界分支。顺序反了代码越写越乱报告也无从下手。2.1 Token类型与保留字表词法分析的第一张图纸词法分析的本质是把字符流切成Token流同时记录每个Token的位置。Token类型至少分五类关键字、标识符、常量、运算符、界符。常量里我习惯再拆成整数、浮点、字符串三类因为语法分析阶段要根据常量类型做不同处理报告里也更容易展示分类逻辑。清华大学出版社第三版的编译原理教材第二章的课后题就是围绕“先把Token类型表和状态转换图画出来”展开的结构可以直接参考但实验报告里得画自己的自动机。我见过不少作业直接把教材答案里的表抄上去代码里却对不上答辩时一问就露馅。Token类型表是给代码定图纸不是给报告凑字数。from enum import Enum class TokenType(Enum): KEYWORD KEYWORD IDENTIFIER IDENTIFIER INT_CONST INT_CONST FLOAT_CONST FLOAT_CONST STRING STRING OPERATOR OPERATOR DELIMITER DELIMITER EOF EOF class Token: __slots__ (type, lexeme, line, col) def __init__(self, type_: TokenType, lexeme: str, line: int, col: int): self.type type_ self.lexeme lexeme self.line line self.col col def __repr__(self): return fToken({self.type.value}, {self.lexeme!r}, {self.line}:{self.col}) KEYWORDS {int, float, char, if, else, while, return, void}Token记录line和col是底线。语法分析报错时“第3行第5列期望分号”比“语法错误”有用得多老师看错误恢复功能好不好第一眼看的就是错误信息有没有位置。用__slots__省内存是顺手的事更重要的理由是Token对象一旦创建就不该被改保持只读语义后续语法分析调试时少一半的赋值麻烦。KEYWORDS用集合而不是列表查表是O(1)代码里也只需要一行if lexeme in KEYWORDS。用它来区分关键字和标识符比“识别到字母就判断是不是关键字”更干净因为收词形的逻辑只有一条路径。2.2 手工状态机的扫描循环最长匹配的落地方式词法分析器的实现路线有两条用flex这类生成器自动生成或者手写状态机。课内作业我一般建议手写哪怕flex出来的代码更稳。道理很现实实验报告要写状态转换图答辩要讲清楚每个状态的意义flex生成的跳转表是一坨黑盒老师问两句就答不上来。手写状态机的代码量不大但每一行都能对上报告里的图。手写状态机的核心接口只有两个peek()看当前字符advance()消费当前字符。这两个接口配合起来所有边界情况都围绕“文件末尾怎么办”展开。先把EOF统一处理成\0所有循环条件里都检查它可以避免一大半死循环问题。import sys class Lexer: def __init__(self, source: str): self.source source self.pos 0 self.line 1 self.col 1 def peek(self, offset: int 0) - str: idx self.pos offset if idx len(self.source): return \0 return self.source[idx] def advance(self) - str: ch self.peek() if ch \0: return \0 self.pos 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def next_token(self) - Token: # 跳过空白与注释行注释、块注释都在这层处理语法层更干净 while True: ch self.peek() if ch \0: break if ch.isspace(): self.advance() continue if ch / and self.peek(1) /: while self.peek() not in (\n, \0): self.advance() continue if ch / and self.peek(1) *: start_line, start_col self.line, self.col self.advance() self.advance() while not (self.peek() * and self.peek(1) /): if self.peek() \0: raise SyntaxError( f第{start_line}行 第{start_col}列 块注释未闭合 ) self.advance() self.advance() self.advance() continue break line, col self.line, self.col ch self.peek() if ch \0: return Token(TokenType.EOF, , line, col) # 标识符与关键字先收完整词形再查保留字表 if ch.isalpha() or ch _: start self.pos while self.peek().isalnum() or self.peek() _: self.advance() lexeme self.source[start:self.pos] if lexeme in KEYWORDS: return Token(TokenType.KEYWORD, lexeme, line, col) return Token(TokenType.IDENTIFIER, lexeme, line, col) # 整数与浮点小数点后必须跟数字否则在词法层直接报错 if ch.isdigit(): start self.pos while self.peek().isdigit(): self.advance() if self.peek() .: if self.peek(1).isdigit(): self.advance() while self.peek().isdigit(): self.advance() return Token(TokenType.FLOAT_CONST, self.source[start:self.pos], line, col) raise SyntaxError( f第{line}行 第{col}列 数字常量 {self.source[start:self.pos]!r} 小数点后缺少数字 ) return Token(TokenType.INT_CONST, self.source[start:self.pos], line, col) # 字符串字面量遇 EOF 未闭合直接抛错 if ch : self.advance() start self.pos while self.peek() ! : if self.peek() \0: raise SyntaxError(f第{line}行 第{col}列 字符串缺少右引号) self.advance() lexeme self.source[start:self.pos] self.advance() return Token(TokenType.STRING, lexeme, line, col) # 双字符运算符优先于单字符避免 被拆成 和 two self.source[self.pos:self.pos 2] if two in {, !, , , , ||, , --, , -}: for _ in two: self.advance() return Token(TokenType.OPERATOR, two, line, col) if ch in -*/%!: self.advance() return Token(TokenType.OPERATOR, ch, line, col) if ch in (){}[];,: self.advance() return Token(TokenType.DELIMITER, ch, line, col) raise SyntaxError(f第{line}行 第{col}列 无法识别的字符 {ch!r}) def tokenize(self): tokens [] while True: t self.next_token() tokens.append(t) if t.type TokenType.EOF: break return tokens这段词法分析器的核心设计在三个地方。一是注释和空白在上层吃掉语法分析器永远看不到注释Token省掉后续所有环节对注释的特判。二是数字状态里明确约束“小数点后必须跟数字”1.会在词法层报错而不是丢给语法层猜错误位置更准。三是双字符运算符先匹配不会被拆成和这是最长匹配原则最朴素的应用场景。块注释这里没有支持嵌套课内作业的测试用例一般也不会写嵌套块注释。如果你要求严格在块注释分支里维护一个嵌套深度计数器碰到/*加一碰到*/减一减到零才算结束。这个扩展写进报告里是加分项但实现时要注意深度计数器的复位位置否则/* /* */这种输入一测就翻车。3. 语法分析选型递归下降为什么是课内作业的最优解词法分析把字符流变成Token流语法分析要把Token流变成一棵语法树或者至少验证其结构是否符合文法。课内作业里最常见的两个方案是递归下降和LR(1)自动机。我的判断很明确除非老师明确要求用Yacc/Bison这类生成器否则手写递归下降是最稳的选择。维度递归下降LR(1) / Yacc文法限制LL(1)需要消除左递归覆盖绝大多数上下文无关文法代码量每个非终结符一个函数直白需要维护状态表理解成本高错误定位函数调用栈天然带位置信息需要额外做错误恢复报告可讲性代码结构与文法产生式一一对应需要解释移进归约过程课内作业得分过程能逐步展示成果展示容易过程难展开递归下降在课内作业里的优势是“过程可见”。老师问到表达式怎么分析时你直接打开parse_expr()指给他看循环里处理加减运算符的逻辑用Yacc的话你只能指着生成表说“这里走的是移进下一步是归约”几句话就把自己讲成黑匣子了。实验报告的写作成本也差很多递归下降的每一段代码都能对应到文法产生式写设计说明时几乎不用额外解释。3.1 递归下降的适用边界左递归与公共前缀递归下降要求文法满足LL(1)最常踩的限定条件是左递归。像E - E T这种左递归产生式直接翻译成函数就是parse_expr()里先调自己永远不消费Token一跑就栈溢出。解决标准是改写成右递归形式E - T { (|-) T }用循环代替递归。另一个边界是公共前缀导致FIRST集冲突。比如两个产生式都以IDENTIFIER开头就得提取公因子或者用“多看一个Token”来区分。课内作业的小语言一般不会复杂到这种程度但报告里写清楚“我检查过每个非终结符的FIRST集有几个公共前缀做了提取公因子处理”老师就知道你不是第一次写语法分析器。我在动手写Parser之前一定要先把文法定稿否则代码写一半改文法函数结构全乱。给一个能当查找表用的精简文法program : stmt* stmt : decl | assign | if_stmt | while_stmt decl : type IDENT [ expr ] ; assign : IDENT expr ; if_stmt : if ( expr ) stmt [ else stmt ] while_stmt : while ( expr ) stmt expr : term ( ( | -) term )* term : factor ( (* | /) factor )* factor : NUMBER | IDENT | ( expr )这个文法故意把表达式放在最后层term里只处理乘除expr里处理加减优先级就通过层次关系自然体现。实验报告里把这个文法一放再放一张1 2 * 3的分析树图语法分析的思路就讲完了。用Java还是Python写都无所谓结构一致。3.2 递归下降Parser的最小实现与错误同步策略递归下降的Parser骨架很固定每个非终结符对应一个parse_xxx()函数互相调用遇到不符合预期的Token就报错并尝试恢复。这里最难的部分不是解析本身而是错误恢复。我的做法是“恐慌模式加同步符号”报错后跳过一串Token直到遇到分号、右括号、EOF这类安全位置再从那里继续解析保证一次错误只报一条不会滚雪球。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.errors [] self.sync_set {TokenType.EOF, TokenType.DELIMITER} self.max_errors 10 def peek(self, offset0): idx self.pos offset if idx len(self.tokens): return self.tokens[-1] return self.tokens[idx] def advance(self): t self.peek() if t.type ! TokenType.EOF: self.pos 1 return t def expect(self, token_type, lexemeNone): t self.peek() if t.type token_type and (lexeme is None or t.lexeme lexeme): return self.advance() self.error(f期望 {lexeme or token_type.value}实际 {t.lexeme!r}) self.synchronize() return t def error(self, msg): t self.peek() self.errors.append(f第{t.line}行 第{t.col}列: {msg}) if len(self.errors) self.max_errors: raise RuntimeError(错误数量超过上限停止分析) def synchronize(self): while self.peek().type not in self.sync_set: self.advance() if self.peek().type ! TokenType.EOF: self.advance() def parse_program(self): while self.peek().type ! TokenType.EOF: self.parse_stmt() def parse_stmt(self): t self.peek() if t.type TokenType.KEYWORD and t.lexeme in (int, float, char): self.parse_decl() elif t.type TokenType.KEYWORD and t.lexeme if: self.parse_if() elif t.type TokenType.KEYWORD and t.lexeme while: self.parse_while() elif t.type TokenType.IDENTIFIER: self.parse_assign() else: self.error(f语句起始符不合法收到 {t.lexeme!r}) self.synchronize() def parse_decl(self): self.advance() self.expect(TokenType.IDENTIFIER) if self.peek().type TokenType.OPERATOR and self.peek().lexeme : self.advance() self.parse_expr() self.expect(TokenType.DELIMITER, ;) def parse_assign(self): self.expect(TokenType.IDENTIFIER) self.expect(TokenType.OPERATOR, ) self.parse_expr() self.expect(TokenType.DELIMITER, ;) def parse_if(self): self.expect(TokenType.KEYWORD, if) self.expect(TokenType.DELIMITER, () self.parse_expr() self.expect(TokenType.DELIMITER, )) self.parse_stmt() if self.peek().type TokenType.KEYWORD and self.peek().lexeme else: self.advance() self.parse_stmt() def parse_while(self): self.expect(TokenType.KEYWORD, while) self.expect(TokenType.DELIMITER, () self.parse_expr() self.expect(TokenType.DELIMITER, )) self.parse_stmt() def parse_expr(self): self.parse_term() while self.peek().type TokenType.OPERATOR and self.peek().lexeme in (, -): self.advance() self.parse_term() def parse_term(self): self.parse_factor() while self.peek().type TokenType.OPERATOR and self.peek().lexeme in (*, /): self.advance() self.parse_factor() def parse_factor(self): t self.peek() if t.type in (TokenType.INT_CONST, TokenType.FLOAT_CONST): self.advance() elif t.type TokenType.IDENTIFIER: self.advance() elif t.type TokenType.DELIMITER and t.lexeme (: self.advance() self.parse_expr() self.expect(TokenType.DELIMITER, )) else: self.error(ffactor 不能以 {t.lexeme!r} 开头) self.synchronize()expect()是这个Parser的正确性核心。它负责三件事检查当前Token类型、消费匹配的Token、在不匹配时报错并调用synchronize()恢复。注意synchronize()里每次报错后至少会多消费一个Token这是死循环的刹车片如果同步符号就是出错位置的那个Token里层的advance()会把指针推走保证解析不原地踏步。sync_set选的EOF和DELIMITER对应文件尾和分号、括号、花括号这类语句边界。错误恢复时跳过一切非法内容直到遇到分号或右括号再从那里继续符合人对代码错误的直觉一个表达式写错了后面的语句通常还是完整的。max_errors设成10条防止一个错误引发连锁错误刷屏这份克制在演示环节特别有用不然一个错误输出50行报错老师第一印象就崩了。如果需要输出语法树而不是只做验证最省事的做法是给每个parse_xxx()加一个返回值返回一个Node对象。Node只需要两个字段节点名和子节点列表。比如parse_expr()就返回Node(expr, [left, op_token, right])。报告里打印这棵树比打印Token流更直观答辩演示时也更容易讲到“你看这个子树对应2*3”。4. 作业包怎么组才能冲97源代码、文档说明、实验报告和PPT的分工词法和语法的代码写完只算完成一半。从标题里的交付物结构能看出来一份97分的作业是“源代码文档说明实验报告PPTPDF”的完整组合。代码写得再好最后一周才开始排报告、做PPT质量必然打折。这一章讲清楚每个交付物该装什么、怎么组织才能对得上老师的评分习惯。4.1 一个能直接交的目录结构代码、测试、文档彻底分开助教拿到压缩包后第一件事是找源码和运行说明。目录结构要是乱七八糟代码和报告混在一层目录里观感分先丢一截。我习惯的作业包结构长这样compiler-lab/ ├── src/ │ ├── token.py # Token类型与数据结构定义 │ ├── lexer.py # 词法分析器 │ ├── parser.py # 语法分析器 │ └── main.py # 入口读文件、跑分析、打印结果 ├── tests/ │ ├── valid_program.c │ ├── invalid_program.c │ ├── edge_cases.c │ └── run_tests.py ├── docs/ │ ├── 状态转换图.png │ ├── 语法树示例.png │ └── 设计说明.md ├── 实验报告.pdf └── 答辩PPT.pptx源代码拆成四个文件而不是一个大文件每个文件只干一件事。token.py放Token类型和KEYWORDS表lexer.py只放扫描循环parser.py只放语法分析函数main.py负责把前三个模块串起来。这样做的好处是报告里写“各模块职责”时直接列文件名就行引用代码也方便。文档说明不叫README叫设计说明.md更贴切。里面有四段必写内容运行环境Python版本、是否有第三方依赖、目录结构说明、命令行调用方式、已知限制。这里有个容易被忽视的点限制要主动写。比如“不支持嵌套块注释”“不支持科学计数法浮点”写出来是诚实的不写老师测出来就是扣分项。给个文件头注释的范本 lexer.py 词法分析器将字符流转换为Token流。 采用手工状态机支持 // 行注释与 /* */ 块注释。 主循环时间复杂度 O(n)n 为源文件字符数。 调用方式Lexer(source).tokenize() 注释不需要逐行但要有设计级说明。每个函数在docstring里写清输入是什么、返回什么、什么情况抛异常。老师问“这个函数为什么要拆出来”你能指着头注释说“这里负责状态转移里的数字分支”比代码里堆满# 这里是数字判断有用得多。4.2 实验报告和PPT的分工什么该写进去什么不该写进去实验报告和答辩PPT内容高度重合但定位完全不同。报告是让别人慢慢读的PPT是让别人三分钟抓住重点的。很多人的问题是报告写成PPT的加长版或者PPT把报告原文贴上去。这里给一份我常用的内容分配表模块实验报告答辩PPTToken分类表完整表格含正则说明只放分类数强调“共7类”状态转换图全图标注转移条件只放标识符和数字两个子图语法分析设计每个非终结符对应一个函数的说明放一个表达式语法树图测试用例表格输入、期望输出、实际输出关键报错截图一页遇到的问题2-3个真实坑含原因和解法挑一个最有说头的坑展开实验报告本身建议写成五段式实验要求与分析、设计思路、关键实现、测试验证、总结与反思。这五段恰好对应助教评分表里的维度少一段都不好办。测试验证那一段最容易被水过去只写“测试用例全部通过”没有任何表格和数据。稍微认真的做法是把测试输入、对应覆盖的分支、实际输出列成一张表说明每个用例验证了词法分析的哪个状态或语法分析的哪个非终结符。PDF导出时的细节也要注意。代码块用等宽字体排版能选中复制就不要截图否则老师想跑一下你的样例还得手敲代码。状态图导出分辨率至少300dpiPPT里放大不糊。页数控制在12到16页之间太薄显得工作量不足太厚没人看完。文件命名按“学号_姓名_实验名称”来很多学校的收件系统会自动按照这个顺序排序带数字前缀的作业在助教眼里就是比命名为“新建文档1”的舒服。PPT的演示顺序建议固定成一个流程先跑一个合法文件展示Token流和“语法分析成功”再跑一个错误文件展示错误恢复后的报错信息最后翻到状态转换图指着图解释刚才输出里某条报错对应哪个状态。这套流程能跑下来比任何口头包装都有说服力。5. 编译原理作业避坑指南5个让词法语法分析器翻车的真实场景下面这些坑没有一个算法上的全是边界和状态管理问题但每个都能让演示当场翻车。前四个在代码层第五个在文档层都是我给这类作业把关时反复看到的。5.1 关键字被识别成标识符查表时机差一步现象输入int a 1;词法分析输出IDENTIFIER(int)语法分析阶段报错“期望类型关键字”。原因扫描器看到i就把整个词形收完但只按字母还是数字分了类没有查保留字表。或者查了表但查表代码放在了字母分支最前面每个字母都先查一遍把状态机的分派顺序搞乱了。解决先收完整词形再统一查KEYWORDS表。收词形时不判断关键字让所有字母开头的词走同一条路径收完int、if这些完整字符串后一次性查集合。第2章代码里的写法就是标准答案if lexeme in KEYWORDS返回KEYWORD否则返回IDENTIFIER。动作越统一越不容易漏状态。5.2 文件末尾的EOF状态没被处理词法分析器死循环现象程序跑完最后一个字符后卡死CPU拉满终端里光标一直闪。原因peek()越界后的返回值没有统一设计。比如字符串分支里写while self.peek() ! 源文件少写一个右引号peek()到EOF后永远等不到循环条件不退出死循环就出现了。解决统一让peek()在越界时返回\0所有循环条件里同时判断\0。我的字符串分支里就是while self.peek() ! 但循环体第一行就判断if self.peek() \0: raise。块注释分支同理提前抛“块注释未闭合”。让错误在词法层炸出来附带行列号比卡死让老师直接关掉进程好一百倍。5.3 数字常量边界1. 和 1.2.3 不报错现象输入float x 1.;分析结果是INT_CONST(1)加一个.运算符语法分析报一条奇怪的错输入1.2.3结果拆成FLOAT_CONST(1.2)和.3报错位置错位。原因数字状态机只处理了“数字点数字”的美好路径没有约束“小数点后必须跟数字”和“浮点后不能再跟点”。解决在词法层做约束。第2章的代码里已经写成if self.peek() . and not self.peek(1).isdigit(): raise让1.直接在词法层报“小数点后缺少数字”。错误在越靠近本源的地方抛出来报错信息越可靠语法分析阶段就不用猜。注意错误最好在词法层抛不要让语法分析做二次猜测。语法层拿到一个1加一个.它不知道这是浮点漏了数字只会按“表达式结尾出现意外符号”处理位置定位全偏了。5.4 错误恢复把Parser带进死循环现象输入一个语法错误Parser连续输出几十上百条错误甚至直接卡死。原因expect()发现不匹配后只调用error()没有调用synchronize()或者sync_set选得不合适同步符号正好是出错位置那个Token同步代码跳过所有Token后停在该符号上原地反复报错。解决expect()里报错后强制调用synchronize()并在同步函数里保证报错后至少消费一个Token。第3章的synchronize()里最后一个if self.peek().type ! TokenType.EOF: self.advance()就是干这个的。再加一层保险max_errors上限超过10条直接抛RuntimeError终止分析。错误收敛比错误恢复完整更重要宁可停止不要刷屏。5.5 文档和代码两张皮报告画了图代码没那回事现象实验报告画了一版状态转换图包含八进制数字的转移分支代码里根本没有对应逻辑。答辩时老师问一句“你图上这个0开头整数的分支在哪”当场卡住。原因先写报告后改代码或者从网上抄了状态图没有对着源码核对。文字可以打太极图可不行图上的状态必须能在代码里找到对应函数。解决把状态转换图和Token表的每一行与源码函数做映射。一个可操作的办法报告里的每个状态编号在源码注释里标出来比如# 状态3跳过块注释。老师问起来你能直接指到代码行这比任何解释都有说服力。改代码必须同步改图这两者永远是一对。6. 提分技巧用测试脚本和状态覆盖表让作业挑不出毛病6.1 三行测试脚本把合法、非法和边界输入一次跑完测试不是可选项是报告里“测试验证”一节的材料来源。手跑几个用例截个图效率太低我用一个脚本批量跑所有输入文件并把退出码和期望值比较。给个可以直接改用的版本# run_tests.py import subprocess import sys CASES [ (valid_program.c, 0), (invalid_program.c, 1), (edge_cases.c, 0), ] for name, expected_rc in CASES: r subprocess.run( [sys.executable, src/main.py, ftests/{name}], capture_outputTrue, textTrue ) passed (r.returncode expected_rc) print(f{name}: {PASS if passed else FAIL}) if not passed: print(r.stderr)脚本维护起来很便宜但价值很高。每次改完代码跑一遍三条样例全绿再提交能在交作业前兜住一半低级错误。跑完的输出直接粘进实验报告比截图“测试全部通过”清爽得多。6.2 用状态覆盖表证明你的分析器够健壮报告里除了放测试结果再加一张状态覆盖表表里每一行写“输入什么、覆盖了词法/语法的哪个分支”。比如输入用例覆盖的分支int a 1;关键字、标识符、整数、分号float x 1.2;浮点状态、float声明// comment行注释跳过/* block */块注释跳过if (a b)双字符运算符、if语句1..2非法数字报错老师看到这张表第一反应是你考虑过边界第二反应是你知道这些用例能证明什么。每行用例都在tests/目录里有对应文件和表格形成闭环这份严谨本身就值回几条分。我带过的作业里能拿高分的几乎都有一个共性文档里写了自己踩过的坑而且每个坑都有对应的用例兜底。这个习惯我从课内作业一路带到生产环境写词法分析器先列边界分支再写状态机省掉了大量调试时间。希望帮到你。本文还有配套的精品资源点击获取