简介一份词法分析器设计实验的完整实验报告面向编译原理课程学习者及需要完成类似实验的本科学生。报告以C语言词法分析器为实例涵盖实验目的、实验内容、程序清单、调试运行结果及思考题系统展示了如何将源代码分解为标识符、保留字、运算符等词法单元并给出SYMBOL.H、BASEDATA.H与Symbol.c等关键模块代码便于理解词法分析程序的实现思路与调试方法。资源为1个doc文档压缩包大小74KB已有489人学习下载。报告来自湖北汽车工业学院实验教学场景内容完整、格式规范既可作为实验报告的写作模板也能帮助读者对照检查自身词法分析器设计方案尤其适合正在学习编译原理、需要快速把握词法分析器设计要点的学生参考借鉴。1. 词法分析器设计实验中真正难的不是“识别”而是“边界”很多人做词法分析器设计实验以为核心是把源码里的单词“认出来”拿到键盘上敲代码时才发现问题全出在“这一个字符到底属于谁”的边界判定上。比如ifx到底该按关键字if多出一个x报错还是按普通标识符整体收下数字后面紧跟字母算一个非法 token 还是两个合法 token字符串里出现换行该不该结束注释到什么位置才算完整。这些判断如果顺序写错语法分析器拿到的 token 流就会“看起来对、接不上”。这一篇顺着“实验一词法分析器设计”该走的完整路线来先立 Token 切分的原理和选型理由再给一份能直接跑的 Python 表驱动实现接着用最小样例和回归测试把行为钉死最后收在几个只有跑大量用例才能发现的问题上。适合正在做编译原理实验的学生也适合需要用脚本解析配置文件的工程师。2. 词法分析器的边界在哪Token 切分粒度、正则到自动机、三种实现选型2.1 Token 粒度的两个常见分歧关键字、复合运算符词法分析器的输出必须是一个有类型、有值、有位置信息的 token 序列而不仅仅是“把字符串切开”。第一个分歧在关键字int应该被单独识别为关键字还是当成一个标识符交给语法层判断常见做法是把它当成独立 token 类型因为后续语法规则的写法会简单很多。另一个分歧是复合运算符比如、、如果把它们拆成两个独立字符语法分析器就得自己做“两个符号拼成一个操作符”的合并这种职责下放会造成大量重复代码。我一般建议实验报告里明确写出 Token 的粒度划分规则关键字完整匹配且必须要求后面是字母、数字或下划线的终结符否则ifx会被误切。运算符与界符按最长匹配原则处理优先于优先于。字面量整数、浮点数、字符串分别建模字符串要考虑转义序列。注释不产生 token但必须被正确跳过而且不能把注释吃掉的内容误报成错误。这个粒度表应该在实验报告第 1 节就出现它是后面状态表设计的直接依据。2.2 从正则到确定有限自动机手算状态表的三种提笔方式词法分析器的经典构造路线是“正则表达式 → NFA → 子集构造法 → DFA → 最小化”但实验报告里真正要写清楚的是“怎么把规则变成能编码的状态表”。常见做法有三种不同人习惯不同第一种是直接画状态转换图每个状态代表“已经读入的字符集合的某种特征”。比如数字识别会分成起始态、整数态、小数点后态、科学计数法指数态。这种方式直观但状态一多容易漏边。第二种是先把所有 Token 的正则表达式写出来然后为每个正则单独画子图最后用一个“总入口状态”合并。合并时要处理冲突比如id和keyword的正则都匹配同一段输入这时一般用优先级解决先判断关键字再做标识符识别只是实现上统一在识别完标识符后查一次关键字表。第三种是直接从正则构造 NFA再计算机器可识别的转移矩阵。对实验报告来说这种方式步骤最完整但工作量最大。若只需要交一个可运行的实验我会用第二种若课程要求体现“编译原理”过程建议交出 NFA 到 DFA 的完整推导。下面给一个最小状态表的构造示意。假设只识别、和数字状态可以按下表组织状态编号含义读入读入数字其他字符S0起始态S1暂存可能是或S2整数态错误S1读过终态A输出终态B输出回退数字终态B输出回退该字符S2整数态终态C输出整数回退S2终态C输出整数回退该字符注意 S1 遇到数字和普通字符时不仅要输出还要把当前字符“退回”输入流因为那个字符不属于这个 token。这个“回退”动作是词法分析器最容易漏掉的设计点后面实战章还会专门讲。2.3 表驱动、手写递归、正则库实验场景怎么选实现词法分析器有这三条常见路线选型直接影响报告篇幅和后续扩展路线典型工具/写法优点缺点适合场景手写状态机Python/Java 循环 状态变量可控性强、无外依赖、状态清晰状态一多代码冗长实验报告首选表驱动状态转移表字典/二维数组 通用循环逻辑和表分离新增 token 只加表表设计初期费时本次实验推荐正则库Pythonre、JavaPattern写起来最快最长匹配和歧义顺序不直观实验对比、生产环境脚本实验类任务多数选表驱动因为“状态表”本身就是报告里最好展示的成果物。但要提醒一点不要用一棵巨大的if-else树写完所有识别逻辑那样既难测试也没有体现出自动机思想。2.4 状态表交互与常见误用交互上有个高频误区状态表只写“读到合法字符怎么办”不写“读到不该读的字符怎么办”。一个完整的词法分析器必须为每个状态定义兜底转移否则非法输入会直接导致数组越界或死循环。此外终态并不一定在读到字符边界时立即返回必须结合“最长匹配”原则选择最后进入的终态。比如应当先输出再把第三个留作下一个 token。使用状态表时还要区分“进入终态就返回”和“读满后再回退”。数字123abc的正确处理是先接受123然后回退abc继续解析而不是在a处直接报“非法字符”并丢弃整个串。这个细节实验报告里值得用一个小例子专门说明。3. 用 Python 写一个表驱动的词法分析器状态表、循环、错误回退3.1 先定义 Token 结构与关键字表动手写代码的第一步不是写识别逻辑而是定义“一种 token 长什么样”。统一结构能减少后续语法分析器对接时的麻烦。下面这份定义包括类型、文本值、行号、列号from dataclasses import dataclass from enum import Enum, auto class TokenType(Enum): KEYWORD auto() IDENTIFIER auto() INT_CONST auto() FLOAT_CONST auto() STRING auto() OP auto() DELIMITER auto() EOF auto() ERROR auto() dataclass class Token: type: TokenType lexeme: str line: int col: int def __repr__(self): return f{self.line}:{self.col}\t{self.type.name:14}\t{self.lexeme}关键字表单独成字典便于扩展。要注意关键字匹配发生在“已经完整读出一个标识符串”之后而不是在读到第一个字母时就判断否则intx会在中途被打断。正确顺序是读完整串 → 查表 → 决定是关键字还是标识符。KEYWORDS {if, else, while, int, float, return, void}3.2 状态表怎么组织字典加默认值表驱动并不要求使用二维数组。Python 里用字典嵌套最直观外层键是当前状态内层键是字符类别值是一个二元组新状态, 动作。这里把字符归类成几个类别而不是存储每个字符这样表尺寸会小得多。# 字符类别依次为 字母/下划线、数字、、!、、、/、引号、空白、其他 CATEGORY_MAP { letter: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_, digit: 0123456789, eq: , noteq: !, lt: , gt: , slash: /, quote: , space: \t\r, }有了CATEGORY_MAP读入一个c就通过查表转换成类别名再把“类别名”作为状态表的第二维键。这样新增一种运算符不需要改识别循环只需要在状态表里多插一行。接下来定义状态和动作。状态命名上用S0、S1、S_ID、S_NUM这种可读性强的字符串报错时也能直接打印状态名帮助定位问题。这里给出一个简化版状态表只覆盖标识符、数字、、、!、!和、、、TRANSITIONS { (START, letter): (ID, accumulate), (START, digit): (NUM, accumulate), (START, eq): (EQ, accumulate), (START, noteq): (NEQ, accumulate), (START, lt): (LT, accumulate), (START, gt): (GT, accumulate), (START, quote): (STR, accumulate), (START, space): (START, skip), (ID, letter): (ID, accumulate), (ID, digit): (ID, accumulate), (NUM, digit): (NUM, accumulate), (NUM, letter): (ERROR, error), (EQ, eq): (START, emit_eq_eq), (NEQ, eq): (START, emit_neq), (LT, eq): (START, emit_lte), (GT, eq): (START, emit_gte), }这里每个动作都对应一个函数或一段逻辑。状态表的优势体现得很清楚识别规则变成数据识别循环变成对数据的解释器。后续若要增加、||只需补充状态和转移不需要动主循环。3.3 主循环与最长匹配核心循环按下面几条规则执行每次读一个字符按CATEGORY_MAP确认类别。查找(当前状态, 类别)对应的转移项。如果查不到进入回退处理。回退处理需要维护一个last_final_state变量记录最近一个能输出 token 的终态以及当时读到的字符位置。到达START且需要保存返回值时输出一个 token继续循环到达终态后再遇到无法转移的字符则按最近的终态位置回退。下面这段是主循环的大致骨架def tokenize(self, text: str): tokens [] i 0 state START lexeme_start 0 last_final_state None last_final_pos -1 n len(text) while i n: c text[i] cat self._categorize(c) key (state, cat) if key in self.transitions: next_state, _ self.transitions[key] state next_state if state in self.final_states: last_final_state state last_final_pos i i 1 else: if last_final_state is not None: lexeme text[lexeme_start:last_final_pos 1] token self._make_token(last_final_state, lexeme, line, col) tokens.append(token) i last_final_pos 1 state START lexeme_start i last_final_state None else: # 无终态可回退报错 raise SyntaxError(fline {line}: 非法字符 {c}) return tokens这段逻辑的关键在last_final_pos的更新频率只在进入终态时记录不到终态不更新。这样在处理和这类冲突时能保证拿到最长的那个匹配。_make_token里负责查关键字表、区分整数和浮点、决定操作符类型等后续工作。注意last_final_pos保存的是“最后一个仍在终态内的字符下标”所以截取字符串要用闭区间加一。3.4 错误处理的三个层次错误处理至少要有三个层次否则实验报告会被扣掉不少分。第一层是“非法字符”。在START状态遇到完全无法归类的字符直接抛出带行列号的异常。这一层最简单但能挡住大多数意外输入。第二层是“中途死亡”。例如在标识符识别过程中进入了一个没有被定义为终态的状态这时需要报“无效标识符”或“无效数字”而不仅仅是“不认识的字符”。常见的例子是12abcNUM状态遇到字母按前面状态表定义应进入ERROR动作此时优先输出已成功的数字 token再把abc单独识别而不是把整段12abc直接当作错误。第三层是“字符串非法”。字符串内的转义序列错误比如\q和未闭合的字符串词法分析器应当给出针对性提示。未闭合字符串的常见处理是读到行尾或文件尾时报错并返回一个ERRORtoken避免整个文件解析中断。4. 把实验跑起来最小样例、行列号输出、回归测试与 3 个常见翻车点4.1 一个覆盖全部 Token 类别的最小样例实验报告要写清楚“这个分析器到底认得了什么”最好的办法是给一个刻意构造的样例文件。它不需要很长但必须覆盖所有 token 类型、运算符优先级、注释跳过和错误路径。下面是我一般会用来做冒烟测试的最小样例int main() { int count 42; float ratio 3.14; if (count 42 flag ! true) { count count 1; } return 0; } // end把这串代码喂给分析器预期输出是关键字、标识符、整数常量、浮点常量、括号/分号界符、//!/操作符分别被识别。注释// end应当被完全跳过不输出任何 token。这个样例能同时验证标识符与关键字之间的冲突处理因为int和main相邻出现。4.2 输出格式带行列号先于语法分析解决定位问题很多实验只输出(type, value)遇到多行代码后调试极其痛苦。词法分析器的输出应当至少包含三列行列号、类型、原文。后续语法分析器报错时直接引用这些行列号能省掉大量“这一步错在哪”的猜测。下面的_make_token里体现这个设计def _make_token(self, state, lexeme, line, col): if state ID: if lexeme in KEYWORDS: return Token(TokenType.KEYWORD, lexeme, line, col) return Token(TokenType.IDENTIFIER, lexeme, line, col) if state NUM: if . in lexeme or e in lexeme or E in lexeme: return Token(TokenType.FLOAT_CONST, lexeme, line, col) return Token(TokenType.INT_CONST, lexeme, line, col) # 其余按运算符和界符处理行列号要在词法分析器里维护而不能等到语法分析阶段再回溯源码重新数行。维护方法很简单读入字符时遇到\n行号加一列号归零其他字符列号加一。这样做对单行字符串字面量也有效因为列号总是指向当前读到的物理位置。4.3 三个常见翻车点翻车点一最长匹配没实现。有些实验在状态机进入第一个终态时就立即返回导致被切成和。修复方法就是前面写的last_final_state记录法要让状态机“再多看一个字符”再决定回退与否。翻车点二EOF 时最后 token 没落盘。输入循环结束后缓冲区里可能还残留一个完整的 token比如文件末尾没有换行符的return 0;后面的0。主循环结束时要单独调用一次flush()逻辑处理last_final_state或者START非空的情况。翻车点三回退实现成了“按字符数回退”。如果代码里用“上次读到的位置减一”来回退遇到多字符回退比如12abc要回退 3 个字符就会错乱。正确做法是保存严格的下标位置回退时直接赋值i last_final_pos 1而不是按回退个数循环递减。4.4 用断言把行为固定下来实验验收时老师会拿不同输入进来测如果只靠“跑一次看不出明显问题”来验收很快会翻车。更可靠的做法是把样例输入和预期 token 序列写进断言用 Python 的unittest或pytest跑回归。下面是一个最小断言示例def test_minimal_c_code(): lexer Lexer() tokens lexer.tokenize(int main() { return 42; }) types [t.type for t in tokens] assert TokenType.KEYWORD in types assert TokenType.IDENTIFIER in types assert TokenType.INT_CONST in types assert all(t.line 1 for t in tokens)这类断言要按“类型序列完全匹配”来写更严格但初期可以先按包含来测等 token 类更稳定后建议改成精确序列对比。精确对比的断言会让实验报告更有说服力因为在表格里可以直接列出“输入 → 期望 token 序列 → 实际输出”的对照一眼能看出覆盖是否完整。5. 词法分析器的验收技巧用“黄金样例 对比”替代肉眼看输出5.1 黄金文件与逐行 diff一个很实用的技巧是把若干典型源码片段整理成一个“黄金文件”提前运行一次确认输出完全正确然后把这次输出作为标准答案保存下来。之后再修改代码只要跑一次 diff就能知道哪些改动影响到了现有行为。对实验报告来说这个方法能证明“改动只影响新增特性没有破坏已有功能”。具体操作分两步。第一步准备好golden.c输入文件和golden.txt期望输出文件第二步跑命令生成实际结果并对比python lexer.py golden.c actual.txt diff -u golden.txt actual.txt如果 diff 没有任何输出说明结果与预期一致。golden 文件里要故意放几个边界输入比如连续多行空行、注释末尾没有换行、字符串里包含转义引号。把这些边界输入和正常代码放在同一个文件里能一次性验证多类行为。5.2 构造边界输入的思路构造边界输入时抓住四个方向基本就能覆盖大多数隐藏 bug。第一是“空输入”源代码是空字符串这时只能输出一个 EOF token不能崩溃。第二是“只有注释”例如一行// nothing分析完应该没有任何实际 token。第三是“相邻运算符连续出现”比如abc! d这里! 中间有空格时应按两个 token 处理! 紧连则按!处理。第四是“长 token 跨行”比如字符串字面量包含转义换行或注释一直延伸到文件末尾这最容易暴露 EOF 处理的不完整。5.3 每次改动后的最小验收清单改动任何状态表之后建议按下面这个小清单快速自查关键字后直接跟数字或字母的行为是否仍正确、、这类复合运算符是否保持最长匹配非法字符报错时行列号是否指向实际出错位置文件末尾无换行时最后一个 token 是否仍然输出。这个清单可以写进实验报告的“测试”一节代替大段的文字描述也方便验收老师快速理解你的测试覆盖策略。词法分析器这类实验写到最后拼的不是识别了多少种 token而是边界行为有没有约束住。状态表能扩展能力黄金样例能守住已有行为把这两样配合好一份实验报告的质量上限会比单纯堆代码高不少。本文还有配套的精品资源点击获取