编译原理课内作业：词法分析与递归下降语法分析实战指南

简介：北京邮电大学计算机科学与技术专业大三上学期的编译原理课内作业，作业得分97，是一份完整的词法分析与语法分析课程设计资料。整个资源包约2.7MB，内含源代码、文档说明、实验报告以及配套的PPT和PDF，适合计算机相关专业学生参考学习，也可用于课程设计、项目初期演示或代码二次开发。代码已经过测试并成功运行，配套文档对实现思路和关键流程做了说明，能帮助读者较快理解词法分析、语法分析的整体设计与编码实现。目前已有122人学习下载，适合正在学习编译原理、需要完成类似作业或想提升代码实现能力的在校学生。下载后可参考文档和报告梳理实验脉络，再结合源码逐步验证，也可在原有基础上扩展功能用于毕设或课设。若运行遇到问题，可联系作者获取远程讲解支持。

1. 一份 97 分的编译原理课内作业，到底在交什么

北邮大三上的编译原理课内作业，输出包里最常见的组合是：词法分析 + 语法分析的源代码、文档说明、实验报告、PPT 和 PDF。得分 97 的作业，不是把一门课程子集语言从头到尾解析一遍就算完，而是让老师能按你的文档复现整个分析过程，也能在答辩现场追问你“这里为什么选递归下降而不是 LR(1)”。真正拉开差距的，是交付方式。

这份作业适合两类人：正在写编译原理实验、想拿一个稳妥高分的在校生，以及想借助一门课把词法分析、语法分析的底层逻辑补齐，回头能直接啃开源编译器源码的从业者。作业本身不难，难的是把它做成一个能讲、能跑、能扩展的小工程。做完它，你收获的是一套完整的编译前端心智模型。

2. 词法分析落地：从正则到状态机的三条实现路径

词法分析干的事很纯粹：把源文件里的字符流切成带类型的 token 流。token 要带上类型、字面值、行号、列号，后面语法分析才报得出准确错误。这一步也是课内作业里最容易“跑起来像对了、一细问就露馅”的环节。

2.1 手写扫描器、自动生成器、正则库：三条路线怎么选

先看三条常见路线，它们的取舍直接决定你后面答辩的体验。

我一般写课内作业选手写扫描器。原因不是自动生成器不好，而是课内作业要求你在答辩现场讲清每个状态为什么存在。flex 生成的表你对着源代码都说不清状态转移，老师一眼就看出来你没消化。正则库逐条匹配的问题更大：它天然是“哪个先匹配到算哪个”，作业里如果定义==和=同时存在，正则库很容易把a==b切成a = = b。这里还要提一句：别一上来就翻“编译原理清华大学出版社第三版第二章答案”里那种把状态图直接画好的资料，第二章的课后题考的就是亲手画状态转换图的功底，你的作业状态图和扫描器必须对得上。

2.2 最小词法扫描器代码骨架：先切单词再查关键字

一个能跑的最小骨架，我用 Python 写，换成 C/Java 只是把枚举改结构体，逻辑不变。

# token_types.py from enum import Enum class TokenType(Enum): IDENT = 1 NUMBER = 2 KEYWORD = 3 OPERATOR = 4 DELIMITER = 5 UNKNOWN = 6 EOF = 7 class Token: def __init__(self, type_, value, line, col): self.type = type_ self.value = value self.line = line self.col = col def __repr__(self): return f"Token({self.type.name}, {self.value!r}, {self.line}:{self.col})"

# scanner.py from token_types import Token, TokenType KEYWORDS = {"if", "else", "while", "return", "int", "void"} OPERATORS = {"=", "==", "<", "<=", ">", ">=", "+", "-", "*", "/"} DELIMITERS = {"(", ")", "{", "}", ";", ","} def tokenize(source: str): tokens = [] i, n = 0, len(source) line, col = 1, 1 while i < n: ch = source[i] if ch in (' ', '\t'): i += 1 col += 1 continue if ch == '\n': i += 1 line += 1 col = 1 continue # 先切完整单词，再判断是关键字还是标识符 if ch.isalpha() or ch == '_': start = i while i < n and (source[i].isalnum() or source[i] == '_'): i += 1 word = source[start:i] t = TokenType.KEYWORD if word in KEYWORDS else TokenType.IDENT tokens.append(Token(t, word, line, col)) col += i - start continue # 数字：当前只支持十进制整数 if ch.isdigit(): start = i while i < n and source[i].isdigit(): i += 1 tokens.append(Token(TokenType.NUMBER, source[start:i], line, col)) col += i - start continue # 运算符：先判断两字符，再判断单字符，这就是最长匹配 if ch in '=<>+-*/': two = source[i:i+2] if two in OPERATORS: tokens.append(Token(TokenType.OPERATOR, two, line, col)) i += 2 col += 2 continue tokens.append(Token(TokenType.OPERATOR, ch, line, col)) i += 1 col += 1 continue if ch in DELIMITERS: tokens.append(Token(TokenType.DELIMITER, ch, line, col)) i += 1 col += 1 continue # 未识别字符不直接抛异常，先作为 UNKNOWN 继续，让统一错误报告处理 tokens.append(Token(TokenType.UNKNOWN, ch, line, col)) i += 1 col += 1 tokens.append(Token(TokenType.EOF, "", line, col)) return tokens

这套骨架的核心思想是先切出完整单词，再用集合判断身份。顺序反了会出大事：如果先判断ch是不是字母，再逐字符累加，那intx会被切成int和x两个 token，关键字和标识符的边界直接崩掉。

参数说明要盯三个点。KEYWORDS集合必须和你在实验报告里定义的语言文法保持一致，加新关键字记得两边同步。NUMBER分支目前只吃十进制整数，遇到小数点、十六进制前缀、负数，要先扩展词法再加代码。负号我建议留在语法层处理，否则-3会被切成-和3两个 token，语法分析拿不到“负数”这个整体语义。运算符分支先判两字符再判单字符，这就是最简单的最长匹配实现。

提示：UNKNOWN token 不要在这里抛异常。你的作业如果只能报第一个错误，老师会拿一个包含多处错误语义的测试文件直接扣分。UNKNOWN 继续走，错误报告统一在语法分析出口做，一次报全。

2.3 最长匹配、关键字边界、行号列号：三个必须写对的细节

第一个坑是运算符最长匹配。我见过不少同学把判断顺序写反，a==b被切成a = = b，语法分析调一晚上都对不上。这就是血泪经验：所有两字符运算符的测试用例必须单独列一张表，==、<=、>=一个都不能少。

第二个细节是关键字边界。int是关键字，intx必须是标识符，_tmp也要识别。解决办法就是上面代码里的顺序：先取完整字母数字串，再查关键字集合，而不是第一个字符命中i就开始猜它是int。

第三个细节是行号列号。列号的更新必须和消费的字符数绑定，换行后col要复位成 1。很多作业的报错行号全错位，就是因为col += 1写在了continue之后，或者多行注释里的换行没统计。调试时对着源代码逐行核对行号，能省掉一半排错时间。

3. 语法分析调通：递归下降与错误恢复的必调参数

语法分析拿到 token 流之后，要判定它是否符合你定义的语言文法，同时输出语法树或者错误序列。课内作业里，这一章的调试成本远高于词法分析。

3.1 LL(1)、LR(1)、递归下降：为什么我最后选了递归下降

三条常见路线各有利弊。LL(1) 要求消左递归、提左公因子，还要手工算 FIRST 和 FOLLOW 集合，分析表错一格，后面所有推导全乱。LR/LALR 用 yacc/bison 自动生成，处理表达式文法是天然优势，但答辩被问“分析表怎么来的”，你要是只能说出“工具生成的”，这题基本就翻车了。

递归下降的好处是每条文法对应一个函数，出问题能单步跟。表达式1 + 2 * 3走哪几个函数，一行一行跟下来就明白。课程作业选它，调试效率最高。用 Python 还是 Java 写编译原理实验决定不了成绩，决定成绩的是你调试的效率——递归下降能让你在十分钟内定位“是词法切错了还是语法调错了”。

3.2 表达式优先级的递归下降骨架：左结合用循环，不消费 token 必死

下面是基于上一章 token 流的表达式解析骨架，支持+ - * /和括号，优先级靠函数嵌套天然实现。

# parser.py 基于上一章的 token 流 class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos] def expect(self, value): tok = self.peek() if tok.value != value: self.error(f"期望 {value}，实际 {tok.value}（行 {tok.line}:{tok.col}）") self.pos += 1 return tok def error(self, msg): raise SyntaxError(msg) # expression := term { + term | - term } def parse_expression(self): node = self.parse_term() while self.peek().value in ('+', '-'): op = self.expect(self.peek().value) rhs = self.parse_term() node = (op.value, node, rhs) return node # term := factor { * factor | / factor } def parse_term(self): node = self.parse_factor() while self.peek().value in ('*', '/'): op = self.expect(self.peek().value) rhs = self.parse_factor() node = (op.value, node, rhs) return node # factor := NUMBER | IDENT | ( expression ) def parse_factor(self): tok = self.peek() if tok.type == TokenType.NUMBER: self.pos += 1 return ('num', tok.value) if tok.type == TokenType.IDENT: self.pos += 1 return ('id', tok.value) if tok.value == '(': self.expect('(') node = self.parse_expression() self.expect(')') return node self.error(f"无法解析的因子: {tok.value}")

优先级通过函数嵌套体现：* /在 term 层，+ -在 expression 层，()在 factor 层，所以1 + 2 * 3一定先解出2 * 3。左结合通过 while 循环实现；如果要支持右结合的幂运算**，把 while 改成递归即可。要让-3成为负数，在parse_factor开头加一个单目负号判断；这些都属于必调参数，必须自己在测试里覆盖。

这套骨架扩展语句很容易。在parse_statement里先expect关键字（if、while、return），再parse_expression解析条件或返回值，最后expect(';')。分号是语句结束的同步点，后面错误恢复会用到它。符号表这层作业可以先只搞一个全局dict存“名字到类型”，等作业要求支持作用域，再把它换成栈结构。别一上来就设计嵌套作用域，调试成本翻倍，对 97 分反而没帮助。

3.3 错误恢复与同步集合：一次报出所有错误

语法分析最常见的失败模式是遇见第一个错误就崩，老师测试时只看到一条报错，然后扣分。你看一下历年高分作业的设计说明就会发现，它们都要求“能定位多处错误”。标准做法是 panic mode，也叫恐慌模式：出错后跳过一段输入，直到遇到同步集合里的 token，再继续解析。

# 错误恢复：跳到同步集合或 EOF 才停 def synchronize(self): while self.peek().type != TokenType.EOF: if self.peek().value in (';', '}', '{', ')'): return self.pos += 1

同步集合选哪些 token 是有讲究的。我一般选; } { )，因为分号是语句终结符，花括号是块边界，右括号是表达式边界。集合太小，错误恢复不了；集合太大，错误会蔓延成几十条假错误。经验值是“每层函数最多跳一个 token 就尝试继续”，宁可少报，不能乱报。

报错信息格式要固定成“行:列: 期望 X，实际 Y”。固定格式的目的是让测试能断言。你的回归测试脚本可以 grep 报错文本，老师也能 5 秒读懂。别在错误信息里打印一大段调用栈，答辩现场没人看那个。

4. 实验报告、文档说明、PPT、PDF：把作业打包成别人能继承的交付物

得分 97 的作业，源代码只是其中一半，另一半是文档。这部分不是形式主义，而是让老师能按你的思路复现你的工作。

4.1 实验报告怎么写：五段式结构比炫技排版更拿分

实验报告的结构，我建议固定在五段。

开头段别写“我们实现了词法分析和语法分析”这种空话。直接写清楚：“本作业定义的语言支持 int、void 两种类型，支持 if/else/while/return 控制流，运算符优先级从低到高为赋值、比较、加减、乘除。”语言定义写清楚了，后面所有设计才有依据。状态转换图是词法分析章节的必配图，没有状态图的词法分析报告基本等于空谈。报告里不用全文贴代码，贴关键函数和它的设计意图就行，老师要的是你讲得清，不是代码行数。

4.2 README 与文档说明：别人 5 分钟能跑起来才算完

文档说明和实验报告是两份东西。实验报告给评分的人看，文档说明给复现的人看。README 的第一屏必须回答三个问题：怎么装、怎么跑、跑出来长什么样。

# 推荐目录结构 tree -L 2

一个合理的最小目录是src/放源代码，tests/放测试用例，docs/放实验报告和文档说明。没有 tree 命令就用find . -maxdepth 2代替。运行命令直接给一行最简形式：

python main.py --input tests/case_01.c --dump-ast

这里的参数要在文档说明里给一张表：

文档说明还要写已知边界，比如“数字仅支持十进制整数，负数需用括号包裹”，这样老师测试时不会拿你没支持的特性当 bug 上报。这一步很能体现工程交付意识，也是容易被忽视的加分项。

4.3 PPT 和 PDF 的配图与导出：四类图撑起答辩

PPT 控制在 8 到 12 页：封面、语言定义、词法设计、语法设计、测试结果、总结展望。配图不用多，四类足够：状态转换图、语法树示例、运行输出截图、模块调用关系图。状态转换图说明词法，语法树示例说明优先级，这两张图是答辩现场的救命图。

PDF 导出有一个高频翻车点：中文字体乱码。从 Word 或 LaTeX 导出 PDF 时，要检查字体嵌入设置，别拿系统默认字体直接转。代码块在 PPT 里要用等宽字体并且高亮关键字，字号不小于 18，否则后排老师看不清。最后打包成 zip 时，第一层放一个带学号和作业名的目录，里面分src/、tests/、docs/，不要出现压缩包套压缩包。这些看似无所谓的细节，答辩老师见一次扣一次分。

5. 编译原理课内作业的 5 个踩坑记录：现象、原因、解决

词法分析和语法分析的排错，九成是下面五个坑。每一条我都按现象、原因、解决写，你对着排查就行。

5.1 关键字与标识符撞车：int 到底算谁

现象：输入int main()，扫描器把int切成IDENT，或者把变量名intx切成了int和x两截，语法分析报错没法看。

原因：切词和查关键字顺序错了。先查关键字再继续读字符，或者没取完整单词就判断身份，都会把边界切断。

解决：先取完整的字母数字串，再查KEYWORDS集合。顺序固定为“先切词、后查表”，并且测试里专门放intx、_tmp、int_main这类用例，保证只有精确命中的int才是关键字。

5.2 左递归把调用栈打爆

现象：程序一启动就报RecursionError，或者 Java/C 直接段错误崩溃。

原因：文法写成expr -> expr + term | term没有改写，递归下降函数第一行又调用自己，永远不消费 token。

解决：把左递归改写成右递归加循环，就是第 3.2 节那个 while 循环的形态。同时加一个自检习惯：任何递归入口必须先peek()并确认当前 token 属于本函数该处理的集合，否则直接报错而不是递归。这样左递归的“不消费 token 死循环”会在第一轮就被打断。

5.3 报错行号全部错位

现象：语法错误提示12:5，实际位置在9:3，对着源代码怎么都找不到。

原因：常见三个来源。Windows 换行\r\n里的\r被当作普通字符，列号多算；注释里的换行没统计；col更新写在continue之后，字符消费了但列号没跟上。

解决：读文件时保留原始换行，词法层统一把\r\n按一个换行处理；注释和字符串内部的换行也要走统一的行号累加逻辑。测试集里放一个混用\n和\r\n的样例，专门验证行号。

5.4 123abc 被静默切成两个 token

现象：int x = 123abc不报错，被切成123和abc两个 token，语法分析以为这是合法的数字后跟标识符。

原因：扫描数字只看isdigit()，遇到字母就停，然后字母作为新标识符继续读。词法层没有检查“数字后面紧跟字母/下划线”这种非法组合。

解决：数字扫描结束时，检查下一个字符，如果是字母或下划线，整个片段标记为UNKNOWNtoken，错误报告统一报“非法数字字面量”。这属于词法层就能抓的错误，不要留给语法分析去猜。

5.5 交付包“能跑”但没人知道怎么跑

现象：老师解压源码包，找不到入口文件，或者环境版本不对跑不起来，只能按“不能复现”处理。

原因：README 只写了“环境依赖 Python 3”，没写运行命令；或者写了命令但测试用例是硬编码在main函数里的，没法换输入。

解决：README 第一屏直接给一行可复制的命令，比如python main.py --input tests/case_01.c --dump-ast。tests/目录放下所有测试用例，docs/放一份“从零复现”的 checklist：装什么、在哪跑、输出什么样。这样老师 5 分钟能跑通，你的文档说明就是加分项。

提示：第 5.5 条最容易被当成“不相关”，但它恰恰是你和最高分差距最大的地方。作业交付本质上是给自己的代码写一份可继承的说明书。

6. 用三层测试和回归集把词法、语法分析钉在 97 分

词法分析、语法分析这种代码，最怕的不是写不出来，是改着改着把之前对的东西改坏。我自己的教训是：为了修一个边界 bug 去改扫描器，结果把==的最长匹配改坏了，回归测试当场揪出来。从那以后，“先跑回归再改代码”成了固定习惯。

我的测试分三层。第一层是最小用例：每个 token 类型一个文件，每个产生式一个用例，比如只测+、只测==、只测括号嵌套。第二层是边界用例：空文件、只有注释、100 层嵌套括号、512 字符的标识符、123abc、\r\n混排换行。第三层是回归集：把之前所有翻过车的输入收集进tests/regression/，跑一遍，把输出固化下来。

# 回归脚本：每次改代码后先跑一遍 mkdir -p out for c in tests/regression/*.c; do python main.py --input "$c" --dump-ast > "out/$(basename "$c").out" done diff -r expected/ out/

diff 输出的每一行，就是这次改动改坏的一条用例。期望输出一旦固定，你就能在提交作业前把翻车风险压到最低。这个习惯我从课内作业一直带到后来的项目里，成本是一个脚本，回报是答辩现场从不心虚。

三次答辩下来，我发现老师最爱问的永远是那几个问题：为什么选这条实现路线？和另一条路线的边界在哪？以后想支持函数调用要从哪里扩展？这些问题，只要你把词法状态图和语法函数对应表想透了，都能答上。希望帮到你。

本文还有配套的精品资源，点击获取