简介北京邮电大学计算机科学与技术专业大三上学期的编译原理课内作业围绕词法分析与语法分析完整实现作业得分97分。资源提供可直接运行的源代码、实验报告、文档说明、PPT与PDF课件代码经过多轮测试且运行成功压缩包整体约2.7MB适合计算机相关专业学生作为课设参考、编译原理进阶练习或项目初期演示的素材。已有123人学习下载尤其适合希望理解词法分析器与语法分析器构建流程的读者。除核心源码与报告外文档部分详细说明了设计思路、关键数据结构和实现过程方便对照梳理实验步骤演示PPT也可用于课程答辩展示。基础较好的读者可在此基础上修改扩展实现其他功能下载后建议先阅读README文档如有如遇运行问题也可联系作者获得远程指导。1. 编译原理课内作业怎么拿 97 分词法分析、语法分析、源代码和文档一体的功夫北京邮电大学计科大三上的编译原理课内作业要求把词法分析和语法分析做出来同时交源代码、文档说明、实验报告、PPT 和 PDF。我最后拿到 97 分一个很反直觉的结论是代码只决定一半分数另一半在“能不能让别人快速跑起来以及你的分析过程是否清楚”。血泪经验是很多人把时间全砸在写识别逻辑上交付时助教跑不动、报告里没有文法定义直接被拉下来。这篇笔记面向正在做编译原理实验、想补课内实现的人把词法分析怎么做、语法分析怎么选、源代码怎么组织、坑在哪和怎么验证一次讲透。2. 词法分析怎么做从 token 定义到状态机三步落地法2.1 为什么先列 token 表而不是直接写代码很多同学拿到题目就开写先把源码按字符读进来再说。这样写到一半必然返工因为识别完数字和标识符之后你会发现注释、多行字符串、运算符“”这种两个字符的组合全是后来补丁。我的习惯是先花半小时把 token 种类列全再动键盘。常见做法是先写一张 token 表关键字、标识符、整数和浮点数、运算符、分隔符、注释。每种 token 对应一个识别动作这样词法分析就从一个模糊的“读字符”任务变成了“遇到哪个分支走哪个状态”的清晰任务。课内作业我建议用手写状态机而不是直接调 re 或者 Lex/Flex原因是手写能精确控制出错位置和行号而正则库在字符偏移上很难带出原始行号Lex/Flex 又多了一层依赖环境助教跑不起来就全盘皆输。核心思路是把字符串当成一个指针流一边读一边维护当前行号。所有分支的判断顺序固定先跳过空白和注释再按数字、标识符、运算符、分隔符的顺序识别最后剩下的字符直接抛错。这个顺序不是随便排的它有优先级关系比如“if”是一个单词而不是两个字母数字“1.2”里的小数点不能单独当运算符。2.2 最小可运行的状态机代码和参数说明下面是一个能直接跑通的最小词法分析器针对一个 C 语言小子集关键字包含 if、else、while、return、int、void支持单行注释、整数和浮点数、单字符与双字符运算符。import sys class Token: def __init__(self, kind, value, line): self.kind kind self.value value self.line line def __repr__(self): return f{self.kind}, {self.value}, line {self.line} KEYWORDS {if, else, while, return, int, void} def lex(source): tokens [] i 0 # 当前读取位置 line 1 # 当前行号 n len(source) while i n: ch source[i] # 跳过空白字符换行要增加行号 if ch in \t\r: i 1 continue if ch \n: line 1 i 1 continue # 处理 // 单行注释 if ch / and i 1 n and source[i 1] /: while i n and source[i] ! \n: i 1 continue # 数字整数和浮点数 if ch.isdigit(): start i while i n and (source[i].isdigit() or source[i] .): i 1 tokens.append(Token(NUMBER, source[start:i], line)) continue # 标识符和关键字 if ch.isalpha() or ch _: start i while i n and (source[i].isalnum() or source[i] _): i 1 word source[start:i] kind KEYWORD if word in KEYWORDS else IDENTIFIER tokens.append(Token(kind, word, line)) continue # 双字符运算符优先判断 two source[i:i2] if two in (, !, , , , ||): tokens.append(Token(OPERATOR, two, line)) i 2 continue # 单字符运算符 if ch in -*/%!: tokens.append(Token(OPERATOR, ch, line)) i 1 continue # 分隔符 if ch in (){}[];,: tokens.append(Token(DELIMITER, ch, line)) i 1 continue # 未知字符直接抛错并带上行号 raise SyntaxError(fUnexpected char {ch!r} at line {line}) tokens.append(Token(EOF, , line)) return tokens if __name__ __main__: source open(sys.argv[1], encodingutf-8, newline).read() for tok in lex(source): print(tok)逻辑说明这个循环就是一台最小状态机每个 if 分支对应一个识别状态。先把换行和空白吃掉再进注释分支避免注释里的“/”“*”被当成运算符。识别数字的循环把小数点和数字一起吞进来但要注意“1.2.3”也会被吞成一个 NUMBER这是最大吞噬的副作用后面再说。识别标识符的分支会用整词查 KEYWORDS 集合避免把 if 拆成 i 和 f。双字符运算符的判断必须先于单字符否则“”会被先拆成两个“”。参数说明KEYWORDS 用集合而不是列表查表时间复杂度是常数。如果你想支持布尔值和空值往集合里加“true”“false”“null”即可。读文件时我用了 newline 并把 \r 放进空白里这是为了兼容 Windows 的 CRLF 换行否则报错行号会偏。数字分支如果不想支持浮点把“or source[i] .”去掉就行如果还想支持数字里的下划线分隔可以再加一个条件判断。2.3 词法分析里 5 个需要提前拍板的边界参数边界条件和评分直接相关建议写代码前就把下面五个问题定下来而不是做到哪算到哪。第一错误处理策略。遇到未知字符是跳过还是抛异常我建议抛异常必须带行号。课内作业的错误输入远远多于正确输入助教给一个乱写的文件你的输出如果是一堆堆栈基本会扣掉错误处理的分。第二最大吞噬回退。像“123abc”这种到底报错还是拆成 NUMBER 和 IDENTIFIER我建议报错因为它更像漏了空格的手误。如果你拆开后面语法分析会更难查。如果坚持拆开就要在数字分支后判断下一个字符是不是字母是字母就回退。第三注释不闭合。“// comment”在文件末尾没换行分号后的“/* comment”也没闭合这两个场景要单独测。文件结束后仍在注释里应该抛错而不是静默通过。第四关键字大小写。mini 语言一般全小写但你要在报告里写清楚“关键字不区分大小写”还是“区分大小写”然后实现里配合做。最容易翻车的是把“If”当标识符这在许多判分脚本里算错误。第五行号对齐。所有的 token 都要带正确的行号这是实验报告里最好展示的一张表。如果你跳过了 \r 却没有更新行号长文件全错位后面语法分析报错也防不住。3. 语法分析选递归下降还是 LR按语言规模和调试成本选3.1 课内作业为什么不建议直接上 Yacc/Bison语法分析器的实现路线常见有两条递归下降和 LR 自动生成器。很多同学会用 Yacc/Bison 或 ANTLR把文法一写就产出解析代码看起来很快。但我带过的课内项目里这条路坑很多生成器版本不匹配、C 代码生成后和手写符号表拼接困难、报错信息是状态栈不直观。一旦文法要小调整重新生成又可能引入新的冲突。相比之下递归下降的每个产生式对应一个函数出错位置就是函数名和行号调试直观代码量也不大。北邮这类课内作业给的语言规模一般就十几个产生式递归下降完全够用。如果你已经会用 Java 写递归下降那套框架也可以但要注意把输出格式对齐到判分脚本。我一般建议用 Python 实现不是因为 Python 有多适合编译器而是它对字符串切片、元组嵌套和快速测试友好。语法分析这层不追求性能追求的是逻辑清晰这恰恰是给分点。3.2 递归下降的骨架代码表达式优先级和括号下面这段代码解析一个带四则运算、括号和数字的表达式并生成一个简单的 AST。它展示了递归下降最核心的“分级下降”写法expr 调 termterm 调 factor每一级吃掉一个优先级。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def advance(self): tok self.tokens[self.pos] self.pos 1 return tok # expr - term (( | -) term)* def expr(self): left self.term() while self.peek().value in (, -): op self.advance() right self.term() left (binop, op.value, left, right) return left # term - factor ((* | /) factor)* def term(self): left self.factor() while self.peek().value in (*, /): op self.advance() right self.factor() left (binop, op.value, left, right) return left # factor - NUMBER | ( expr ) def factor(self): tok self.peek() if tok.kind NUMBER: self.advance() return (num, tok.value) if tok.value (: self.advance() node self.expr() closing self.advance() if closing.value ! ): raise SyntaxError(fexpected ) at line {closing.line}) return node raise SyntaxError(funexpected token {tok.value} at line {tok.line}) def parse(self): ast self.expr() if self.peek().kind ! EOF: raise SyntaxError(funexpected token {self.peek().value} at line {self.peek().line}) return ast逻辑说明这个 Parser 维护一个 token 数组和一个位置指针。expr 先调 term 得到一个左操作数再循环看下一个运算符是不是加减是就继续吃右边的一个 term并拼成左结合的二元节点。term 和 expr 结构对称只是操作符不同这样乘除优先级高于加减的效果就出来了。factor 处理最底层的数字和括号括号里递归调用 expr完成嵌套表达式的解析。整个结构没有显式的文法表每个函数就是文法本身。参数说明这里默认左结合加减乘除都是。如果你要处理赋值符号“”需要再往上包一层 assignment并且让赋值变成右结合那就要把赋值分支改成“先解析右侧的 expr再构造 (‘assign’, name, value)”的结构。如果你要加一元负号在 factor 里加一个判断“- NUMBER”的分支。while 循环后面那行构造节点的代码决定了 AST 是左深还是右深报告里要写清楚。3.3 错误恢复的两种策略panic mode 和错误令牌语法分析最容易丢分的不是解析正确的代码而是解析错误的代码时“直接崩溃”。课内作业基本要求是出一条错误信息继续跑两条策略最常用。一是 panic mode遇到非法 token 时跳过一段输入直到遇到同步点比如分号、右括号或者某个关键字。实现里我会在 catch 异常后循环调用 lexer 的解析入口让位置推进到下一个语句开头。二是错误令牌法在文法里显式加一个 error 产生式把非法部分吞掉。这个方法要改动文法适合你已经有明确同步点的时候。课内报告里我建议把 panic mode 画成一张流程图同步点选分号和右括号即可这个细节在答辩时经常被追问。注意递归下降还有一个隐藏坑左递归文法写进代码会栈溢出。比如“factor - factor * term”这种代码一进去就自己调自己。消除左递归要么把文法改写成右递归要么用 while 循环实现我上面的代码就是用 while 处理的。这个点和 Yacc/Bison 里的冲突处理是两类问题但很多同学混着答扣分很冤。4. 源代码与工程组织让助教十秒跑起来的文件划分和入口设计4.1 文件划分lexer、parser、ast 和测试目录各司其职课内作业的源代码不要追求“一个文件写完”。一个 main.py 塞 800 行助教打开就头疼。我一般按功能拆四到五个文件每个文件控制在 300 行以内这样写实验报告时引用函数名和行号都方便。文件清单如下文件路径职责建议内容main.py命令行入口读文件、调 lexer/parser、打输出lexer.py词法分析Token 类、lex() 函数、token 表parser.py语法分析Parser 类、各产生式对应函数ast.py语法树结构节点类型定义、打印/格式化方法tests/用例目录每个输入文件配一个期望输出文件逻辑说明把 Token 类和 lex() 放一起是因为词法分析返回的列表本身就是 parser 的输入。ast.py 独立出来是为了让 parser.py 只关注文法不混入输出格式逻辑。tests/ 目录下建议一个用例一个子目录包含输入和期望输出这样助教可以跑批量测试你也可以对照 diff。参数说明如果你用 Python 的 dataclasses 定义 Token 或 AST 节点注意报告里要写“Python 3.x 环境”并注明只需要标准库不依赖第三方包。这一点很重要助教在自己的机器上直接 python main.py 就能跑相当于把环境问题从评分项里去掉了。我见过有些作业把错误处理单独拆一个 errors.py统一管理错误码和行号如果时间充裕可以拆但两三百行的课内作业没必要。我的判断原则是文件超过 300 行就拆不超过就合并。测试用例则永远单独放目录因为它们是实验报告里最有力的一页。4.2 命令行入口一条命令跑完三种输出判分脚本最喜欢固定的命令行入口。我建议 main.py 支持三个参数最小化助教的上手成本python main.py test.mini python main.py test.mini --dump-tokens python main.py test.mini --dump-ast第一行只做语法检查通过打印 OK不通过打印错误信息和行号。第二行输出词法 token 序列格式是“种类、值、行号”三列对齐。第三行输出语法树我这边用缩进的嵌套元组表示也可以用 JSON 输出。逻辑说明默认模式对应“这个文件编译通过了”是助教批量验证的路径--dump-tokens 和 --dump-ast 是给老师和答辩现场演示用的能直观展示你的分析和中间表示。实现时在 main.py 里按 argparse 解析参数然后分别调用 lexer 和 parser 的两个导出函数。注意输出格式一旦定了就不要改。判分脚本如果做精确匹配多一个空格都可能全军覆没。建议把输出格式写进 README 的第一段同时提供一个 tests/run_all.sh 或 run_all.bat循环跑完所有用例并 diff这也能证明你的实现是稳定的。4.3 文档说明、实验报告和 PPT 的写作顺序先写设计再写代码文档是 97 分里另一半的来源。我的经验是写作顺序和实现顺序相反先写文法定义再写设计说明再补实现细节最后贴测试结果。这样报告读下来是从抽象到具体老师能快速判断你的理解深度。实验报告的核心结构是这样第一页描述你定义的语言文法用 EBNF 写清楚。第二页画词法状态机和递归下降的函数调用关系。第三页贴关键函数并加注释不要整段贴。第四页列测试用例表格包括正确输入、错误输入、期望输出和实际输出。最后写反思比如为什么选择递归下降而不是 LR、错误恢复选了哪种策略。PPT 只放运行截图、测试矩阵和一张架构图别贴大段代码。PDF 是打印版记得把链接去掉、代码字号统一、行号保留。文档说明则单独放一份 README说明仓库结构、运行方式、实现语言和已知限制。这四样东西对应不同的阅读场景README 是给助教跑的实验报告是给老师判分的PPT 是答辩用的PDF 是打印留档用的内容可以有重叠但侧重点不同。5. 编译原理实验避坑指南现象、原因、解决5.1 行号错乱Windows 换行符把词法分析器带偏现象在记事本里编辑的测试文件词法分析报错信息里的行号比实际多了几行或者把 \r 直接报成未知字符。原因Windows 的换行是 CRLF也就是 \r\n。词法分析只处理了 \n遇到 \r 走了未知字符分支。行号统计也会乱因为每一行都多了一个不可见字符。解决在空白字符判断里加上 \r或者读文件时用 newline 然后统一把 \r 替换掉。我在 2.2 的代码里已经把这个坑提前填了但如果你沿用网上旧模板第一件事就是查这一行。在实验报告里可以补一句“本实现兼容 LF 与 CRLF 换行”这属于加分细节。5.2 左递归导致栈溢出文法一进函数就出不来现象解析“a - b - c”这种连续同优先级表达式时程序直接 RecursionError不是报语法错误。原因你的文法写成了“factor - factor - term”这种左递归形式。递归下降一进 factor 就调用 factor永远没机会读下一个 token栈自然爆。解决把文法改写成“expr - term (op term)*”的右递归或循环结构。我 3.2 的代码已经用 while 循环做了如果你的 parser 是从左递归文法机械翻译过来的这一处要重点检查。写代码之前先扫一遍文法列表凡是非终结符出现在自己产生式最左边的都叫左递归先改写再动手。5.3 关键字被当标识符if 和 while 全输出 IDENTIFIER现象输入 if (a) 时token 种类是 IDENTIFIER 而不是 KEYWORD。语法分析因此报错说“expected IF”。原因标识符识别分支里先按字母拼单词然后直接 append 成 IDENTIFIER没有拼完之后查关键字表。解决把查表挪到“完整单词已经读出来”之后用 word in KEYWORDS 判断类型。这个顺序错位很隐蔽因为代码看起来没问题只有跑测试时才发现。我在 2.2 里先读词再查表就是为了避免这个顺序。排查时可以把 KEYWORDS 集合 print 出来确认它没有被误改成英文逗号分隔的字符串。5.4 注释穿越 EOF 不结束文件末尾卡死现象输入只是“/* comment”没有闭合程序不报错也不结束助教等半天只能强杀。原因注释分支只检查了“遇到 */ 就结束”没有检查 i 是否已经越过文件末尾于是循环永远在等一个不存在的右括号。解决在注释循环内部加一个 i n 的判断发现文件结束时抛错提示“unclosed comment”。同理字符串字面量也要处理“字符串在文件末尾仍未闭合”的场景。这两类错误都属于词法层的“未闭合”应该在 lexer 里就报出来而不是留给 parser 去猜。5.5 输出格式和判分脚本不匹配本地全对助教判全错现象自己手工验证结果都对但助教批量跑判断全挂。原因判分脚本一般按精确匹配比较标准输出。你的输出多了“”提示符或者 token 之间用了多个空格而不是一个都会判错。解决先跑一次 diff把输出对齐到样例格式。同时把输出格式写进 README比如“每个 token 占一行字段间用一个空格分隔”让助教知道你的约定。这个小动作在课内作业里经常值回 5-10 分。这个坑在本地很难发现因为你自己测试时不会用肉眼比较每个空格所以从一开始就要写一个比较输出的脚本而不是靠眼睛。6. 验证你的编译前端测试矩阵和错误恢复的双保险6.1 测试矩阵怎么搭我的做法是建一个 tests/ 目录按“正常输入、边界输入、错误输入”三类组织用例。正常输入至少覆盖空程序、单条语句、嵌套表达式、多行注释、所有运算符。边界输入包括超大整数、连续多个空行、字符串含转义符、注释和代码同行。错误输入包括未闭合括号、缺分号、未闭合注释、未知字符。每个用例一个输入文件和一个期望输出文件用一个脚本批量跑 diff。这个矩阵我一般会在实验报告里直接复制成表格属于加分项。6.2 错误恢复演练答辩现场老师经常做两件事给一个故意写错的程序然后问你的错误信息在哪里。我的习惯是准备三条用例缺少右括号、关键字拼错、数字后面跟字母。每次改完代码都跑一遍这三条确保输出是“可读的错误信息加行号”而不是一段堆栈。这个习惯帮我避免过好几次翻车。6.3 一句经验我印象最深的是第一次交作业把全部时间花在写代码文档最后一天赶结果只有 80 几。后来补上文法定义、状态机图和测试矩阵同样一份代码加上清楚的文档才到 97。编译原理实验的分数有一半在“让别人看懂”验证手段和文档越早做越便宜。希望帮到你。本文还有配套的精品资源点击获取