简介西南科技大学编译原理实验报告1是一份设计型实验报告围绕词法分析程序从正则表达式到最小DFA的完整设计流程展开适合高校计算机专业学生进行编译原理课程设计或撰写实验报告时参考。报告以TEST语言为对象详细给出标识符、保留字、无符号整数、分界符、运算符、注释符等词法规则的正则表达式并完整演示了NFA构造、NFA合并、确定化、最小化DFA的过程同时设计了单词分类与输出方案附有具体示例和基于Python的DFA状态转移表及词法分析核心代码可帮助读者理解词法分析器的实现原理与调试思路为后续语法分析、语义分析等环节打下基础。压缩包内含1个doc格式报告文档整体大小约444KB内容组织规范包含实验目的、实验设计、实验过程、程序实现等完整章节可供直接查阅或参照改写。目前已有477人在CSDN学习或下载对需要完成编译原理实验、理解自动机理论应用的同学具有较好的参考价值。1. 编译原理实验报告1一份能直接复现的词法分析器设计与避坑清单拿到这份“编译原理实验报告1”时我的第一反应是词法分析器代码量不大难的是把正则、NFA、DFA这一串理论真正落成一份能跑通、能交差、还能讲明白为什么这么设计的实验报告。这份《编译系统综合设计》实验一报告完整覆盖了“正则规则→NFA合并→确定化→最小化→Python实现→错误定位→最长匹配讨论”的整条链路报告正文里就带了一份状态转移表驱动的词法分析程序和一组带非法字符的测试用例。它适合两类人正在写编译原理实验的学生可以照着这份材料的章节结构补齐自己的推导过程工作里要手写小语言前端、不想上 flex/lex 的开发者可以直接拿这份状态表当模板改。接下来我按报告顺序拆开讲重点放在实现细节和几个一跑就翻车的坑上。2. 词法规则的正则表达与NFA/DFA转化状态转移表是怎么被推导出来的2.1 各词法规则的正则写法先约定语言边界再写表达式写词法分析器之前第一步不是写代码而是把 TEST 语言里哪些 Token 合法这件事定死。报告把词法分成六类标识符、保留字、无符号整数、分界符、运算符、注释符。每类对应一个正则正则是后面构造 NFA 的输入也是程序验收时判断“你是不是真懂”的关键。标识符的正则写成(letter)(letter|digit)*展开就是 (a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*。这个写法有两个隐含约定一是首字符只能是字母字母后可以跟零个或多个字母或数字二是下划线不在字符集里说明 TEST 语言不允许下划线开头的标识符。如果以后要扩展成 C 语言风格把下划线加进 letter 集合再调整首字符判断就行代价是 NFA 多两个状态。无符号整数的正则用了这样一条((1|...|9)(0|1|...|9)*)|0它表达的是两种合法形态单独的 0或者 1 到 9 开头后跟任意位数字。也就是说“012345”这种带前导 0 的写法按这个正则应该被拒绝。这个细节后面会跟报告的分类表对不上先记着。保留字正则是if|else|for|while|do|int|write|read注意 do 在这里出现了但第 3 章要讲的单词分类表里关键字列表没有 do。报告前后不一致真实课程答辩时这种点很容易被问住。我的处理习惯是以关键字分类表为准要么把 do 补进分类表要么从正则里删掉两个版本必须同步。运算符正则是|-|*|/||||||!|难点在双字符运算符与单字符运算符共享前缀 和 、 和 、 和 、! 和 !。DFA 处理到 时要预读一个字符下一个是 就走双字符状态否则把 当作单字符运算符输出。这就是报告最后讨论的最长匹配原则在源码里的落点。注释符正则实际是 //。报告里写成了 /|/属于笔误语义上应该是两个斜杠连续出现才算注释开始。2.2 从正则到NFA再到最小DFA手工推导的落地顺序每个正则先独立构造一个 NFA这是 Thompson 构造法的标准流程。标识符的正则本质上是“首字符分支 后续循环”的结构首字符集合有 52 个字母分别引向中间状态再通过 ε 转移合并到循环体无符号整数的 NFA 是“0”的独立分支加上“1-9 开头循环数字”的另一个分支运算符则是一堆并行的单字符转移其中双字符运算符的 NFA 要做两级状态。合并 NFA 的做法是加一个公共起始状态用 ε 转移连到每个子 NFA 的起始状态。这一步的关键是不要让子 NFA 互相干扰每个子 NFA 的接受状态只属于自己合并后要记录“哪个接受状态属于哪个词法类别”后面确定化时才好给 DFA 接收状态标记类型。确定化走子集构造法先算公共起始状态对每个输入字符类别的 ε-闭包把它作为 DFA 的初始状态集再对每个状态集、每个输入类别求 move 后的 ε-闭包直到没有新状态集产生。手工推导时我一般不用画图法直接列一个“状态集编号 → 子集成员 → 各输入类别的跳转”表格哪怕多算几轮也比对着图猜状态靠谱。这步属于看着理论性强、实际可以机械完成的体力活。最小化用划分法先把所有 DFA 状态分成接收状态和非接收状态两组然后反复检查同一组里的状态对每个输入类别是否转移到同一大组转移目标不一致就拆开直到各组不再变化。自动机理论到这里看起来像玄学实际上只要字符类别控制在 5 个以内手工两步就能拆完。这里的关键是最小化之后状态数量会明显减少报告代码里 7 个状态就是这么缩出来的。2.3 状态转移表与DFA状态图的对应检查把最小化后的 DFA 套到报告代码里就是 7 个状态、5 个输入类别。状态包括 START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR输入类别是 ALPHABET字母、DIGIT数字、OPERATOR_DELIMITER运算符与分界符、SLASH斜杠、WHITESPACE空白。这张表有一个明显的状态冗余OPERATOR 和 DELIMITER 在报告代码里共用同一个输入类别但状态转移表里 DELIMITER 没有从任何初始状态到达的路径也就是说 DELIMITER 是个永远进不去的状态。这属于实现简化时的遗留问题不影响主流程但说明手工画图与代码落表时要专门做一遍“每个状态是否能到达”的检查。我习惯拿到 DFA 表先问三个问题哪些状态能到达哪些状态能到接收态哪些输入类别会导致 ERROR这三个问题过完表的结构问题基本就暴露了。到这里正则、NFA、DFA 三层就推完了。接下来进入单词分类和输出方案的设计。3. 单词分类与输出方案先把Token契约定死再写扫描器3.1 单词分类表的定义逻辑七类边界怎么切DFA 只负责把字符串切成一段段至于每一段叫什么名字要看单词分类方案。报告给的分类是七类这里直接列一个表类别英文名代表单词识别依据关键字Keywordint, if, else, while, for, read, write保留字表直接匹配标识符IdentifierID, var123, variable字母开头后续字母数字无符号整数Unsigned Integer123, 0一个或多个数字分界符Delimiter{, }, (, ), ;单字符分隔运算符Operator, -, *, /, , , , , , !, 单字符或多字符运算符注释符Comment//...以 // 开头到行尾保留字Reserved Wordint与关键字重复定义这个表里有几个边界值得注意。第一关键字和保留字在报告里重复了int 既在关键字列表里又在保留字列表里。实际工程里这两项通常会合并成一张关键字表词法分析器识别出标识符形态的单词后去表里查一下命中就标为关键字没命中就是普通标识符。第二do 在正则里出现了分类表里没有同样是不一致。第三无符号整数这里写的是“一个或多个数字”跟第 2 章正则里“不允许前导 0”冲突。3.2 输出方案从源码到Token流的完整映射报告给了一个很具体的示例程序int x; if (x 0) { write x 1; }对应的输出是Keyword: int Identifier: x Delimiter: ; If: if Parenthesis: ( Identifier: x Operator: Unsigned Integer: 0 Parenthesis: ) Curly Brace: { Write: write Identifier: x Operator: Unsigned Integer: 1 Delimiter: ; Curly Brace: }注意这里的输出格式并不是严格的“类型 空格 值”而是把关键字进一步拆成了 If、Write、Keyword 等更细的标签。这种写法适合实验报告展示因为老师一眼能看到你识别到了哪些关键字。真正工程化的词法分析器一般输出二元组Token 类型编号单词原文类型用枚举值而不是字符串。这个示例也暴露了一个隐藏条件所有 token 之间有空格或者换行所以报告里的 DFA 实现才能正确切分。如果把 if (x 0) 写成 if(x0)问题就会冒出来这点第 5 章会详细展开。输出到文件时我一般会把每行写成“行号:类型:单词”的格式方便后续语法分析阶段直接定位错误。3.3 正则与分类表不一致时该信谁把第 2 章的正则和第 3.1 节的分类表放一起对比能发现三处矛盾。第一是 do 的归属第二是前导 0 问题第三是“保留字”和“关键字”两个名词重复定义概念边界不清。前导 0 是最需要较真的。按正则定义012345 不合法按分类表定义一个或多个数字012345 合法。报告后面测试源程序里正好有一行“abc 012345;”而实验四的结果里并没有报 012345 的错误说明实现里大概率按“一个或多个数字”放行了。老师在答辩时如果追问这个就是最容易被扣分的点。我的建议是选定一个口径然后在报告里全局统一比如把正则改成 (0|1|...|9)(0|1|...|9)*或者把分类表改成“不允许前导 0 的多位数字”。改哪一个都行但不能两边矛盾。这三处矛盾解释清楚之后第 4 章来看程序本身是怎么按 DFA 实现的。4. 基于最小DFA编写词法分析程序Python实现与参数解读4.1 字符分类函数get_char_category 的类别粒度设计程序的第一步是把输入字符归类。报告里的 get_char_category 返回六种类别ALPHABET、DIGIT、OPERATOR_DELIMITER、WHITESPACE、SLASH、OTHER。类别粒度决定了 DFA 状态表有多少列粒度太粗会分不清运算符和分界符太细则状态表爆炸。这里把运算符和分界符合并成 OPERATOR_DELIMITER是一个明显简化后面会看到它带来的副作用。值得先指出一个坑判断顺序里代码先把 / 包含在 OPERATOR_DELIMITER 集合里后面又写了 elif char / 返回 SLASH导致 SLASH 分支永远不会被执行DFA 表里 START 到 COMMENT 的路径是死的。这是原报告调试记录里“不能处理除运算符号、处理注释符出错”的根源。第 5 章会给修正。这里先把原版代码完整贴出来方便对照。报告里的核心代码如下# 状态定义 states {START, ID, NUM, OPERATOR, DELIMITER, COMMENT, ERROR} # 定义输入字符类别 def get_char_category(char): # 判断单个字符属于哪一类输入 if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char in {, -, *, /, , , , !, (, ), {, }, ;, :}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE elif char /: return SLASH # 这个分支实际走不到因为 / 已经被上面收走了 else: return OTHER # DFA 状态转移表 dfa { START: {ALPHABET: ID, DIGIT: NUM, OPERATOR_DELIMITER: OPERATOR, SLASH: COMMENT, OTHER: ERROR}, ID: {ALPHABET: ID, DIGIT: ID, OPERATOR_DELIMITER: ID, SLASH: ID, OTHER: ERROR}, NUM: {ALPHABET: ERROR, DIGIT: NUM, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR}, OPERATOR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: OPERATOR, SLASH: ERROR, OTHER: ERROR}, DELIMITER: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: DELIMITER, SLASH: ERROR, OTHER: ERROR}, COMMENT: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: COMMENT, OTHER: ERROR}, ERROR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR} } # 词法分析函数 def lex_analysis(input_string): current_state START current_token tokens [] for char in input_string: category get_char_category(char) if category in dfa[current_state]: # 当前状态存在该输入类别的转移吸收字符 current_state dfa[current_state][category] current_token char else: # 当前状态无法吸收该字符说明一个 token 已经结束 if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) current_state START current_token if category ! WHITESPACE: # 新 token 从当前字符开始 current_state dfa[current_state][category] current_token char # 处理最后一个 token if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) return tokens # 示例输入 input_code int x; if (x 0) { write x 1; } # 执行分析 result lex_analysis(input_code) for token in result: print(fToken: {token[1]}, Type: {token[0]})这段代码的逻辑分三层。第一层是 get_char_category它把一个字符映射成一个类别字符串类别是后续 DFA 查询的 key。参数 char 只接受单个字符函数返回值一定是上面六个类别之一因为最后一个 else 兜底返回 OTHER。第二层是 dfa 表它是一个两层字典第一层 key 是当前状态第二层 key 是输入类别value 是转移后的状态。第三层是 lex_analysis 主循环它逐字符读入当前状态能转移就吸收字符不能转移就先提交当前 token再尝试用当前字符开启新 token。这里有个容易忽略的设计点dfa 表里没有 WHITESPACE 状态空白字符完全靠“当前状态对 WHITESPACE 没有转移”来触发提交从而起到分隔 token 的作用。也就是说这份代码能跑通报告里的示例输入是因为示例里 token 之间都有空格或换行。把 x 0 改成 x0结果就完全不一样了后面第 5 章会实际演一遍。提交 token 的条件也需要注意进入 ERROR 的字符不会被 append 到 tokens 里只会在主循环里无声跳过。报告后面测试文件里的 、$ 这类非法字符用这份原版代码跑是拿不到“错误位置”的因为 ERROR 分支没有做位置记录。这也是第 5 章要补的一块。5. 词法分析器避坑排查/歧义、状态粘连与非法字符定位5.1 除号与注释符冲突遇到 / 时如何预判现象测试程序第一行是{ //This a test program.运行原版代码时注释里的字母逐个报 ERROR除号/也经常被误吞单独写a / b时除号识别不稳定。原因有两个。第一个在 get_char_category 里/被写进了 OPERATOR_DELIMITER 集合且这个判断在 SLASH 判断之前导致char /的 SLASH 分支是永远走不到的死代码。DFA 表里 START 遇到 SLASH 进 COMMENT 的路径从一开始就是断的。第二个在 DFA 表本身即便把 / 单独分出来COMMENT 状态的转移表也只允许 SLASH 保持在 COMMENT注释内容里的字母数字都会触发 ERROR。单行注释本质上应该吸收除换行外的所有字符而不是只吸收斜杠。解决把 / 从 OPERATOR_DELIMITER 集合中删掉并将 SLASH 判断提前。COMMENT 状态单独写一段进入 COMMENT 后持续吸收直到遇到换行符再回到 START这比硬套 DFA 表更省事。修正后的字符分类函数如下def get_char_category(char): # 修正版/ 单独成类且判断顺序提前 if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char /: return SLASH # 注释符与除法的公共开头 elif char in {, -, *, , , , !, (, ), {, }, ;, :}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE else: return OTHER对应到主循环处理 / 时要做一次预读下一个字符也是 /说明是注释开始否则把 / 作为运算符提交。这个预读逻辑就是最长匹配原则的一部分也是报告第 3 节调试记录里“增加判断语句”的真正含义。5.2 无空格代码的token粘连状态转移表把ID/NUM写宽了现象把样例改成if(x0){write x1;}原版代码会把x0{write这种串粘成一个超长 token输出里出现 Token: x0{write, Type: ID。原因在 DFA 表的 ID 状态ID: {ALPHABET: ID, DIGIT: ID, OPERATOR_DELIMITER: ID, ...}。这等于告诉扫描器标识符遇到运算符或分界符时继续归并到标识符里。从自动机理论看这是把不该转移的转移写上了。原版示例能跑对纯粹是因为 token 之间都有空格空格会先触发提交。解决把 ID 和 NUM 状态对 OPERATOR_DELIMITER 的转移改成交付动作而不是状态跳转。常见做法是挂起当前字符识别到一个标识符正在扫描突然遇到先提交当前标识符再把作为新 token 的首字符重新进入起始判断。这也是第 6 章验证最长匹配时要检查的核心点。5.3 非法字符的错误定位ERROR状态不能只吞不报现象测试文件里有int abc123$;和int 123;原版代码跑完没有任何报错输出因为 ERROR 状态的 token 在提交条件里被排除了。要求的“报告词法错误及其位置”实际没实现。原因主循环里if current_state not in {WHITESPACE, COMMENT, ERROR}直接从输出里滤掉了 ERROR而且整个循环没有维护行列号就算把 ERROR 加回去也不知道错在第几行第几列。解决在循环里增加 line 和 col 两个计数器每读一个字符更新一下遇到 OTHER 类别或进入 ERROR 状态时把行号列号非法字符原文记进错误列表。这样既保住了合法 token 的 lex.txt 输出又能顺便交付错误清单。# 在 lex_analysis 内增加行列号维护 line, col 1, 1 errors [] for char in input_string: if char \n: line 1 col 1 else: col 1 category get_char_category(char) next_state dfa[current_state].get(category, ERROR) if next_state ERROR or category OTHER: errors.append((line, col, char)) current_state START current_token continue5.4 关键字与标识符的识别顺序DFA不查保留字表现象输入int x;时输出是 Token: int, Type: ID而不是关键字类型。报告期望的输出是 Keyword: int。原因DFA 只能识别“字母开头、后续字母数字”的形状它不知道 int 是关键字。形状识别和关键字查表是两层工作原版代码少了后面这层。解决ID token 提交后用保留字集合做一次查表。我一般会维护一个 Python setkeywords {int, if, else, for, while, do, read, write} if token_type ID and current_token in keywords: token_type KEYWORD注意查表动作一定要在 ID 提交时做不能提前。提前查会导致integer这种以 int 开头的标识符被误判成关键字。6. 最长匹配原则的验证方法用一组边界输入证明扫描器行为6.1 最长匹配在代码里的落点双字符运算符的预读处理报告里说本设计满足最长匹配原则依据是不会被拆成和。这句话理论上没问题但代码里要落到一个具体动作读取之后必须预读下一个字符才能决定走单字符分支还是双字符分支。预读失败时要能回退不然后面紧跟空格时会把空格吞掉。我在验证词法分析器时最常用的方法是构造一组“无空格粘连”输入因为这类输入最能暴露最长匹配是否真的实现。下面这段验证脚本跑在修正版逻辑上专门检查双字符运算符和注释符的边界test_cases [ x2, # 期望 x, , 2 x2, # 期望 x, , 2 a//b, # 期望 a, 注释到行尾 a/b, # 期望 a, /, b if(x0){y!1;}, # 无空格场景 ] # 对每组输入打印 token 序列用于人工核对 for code in test_cases: print(code, , lex_analysis_fixed(code))6.2 一组可执行的验证输入与预期Token序列输入期望Token序列说明x2ID(x), OP(), NUM(2)双字符运算符优先x2ID(x), OP(), NUM(2)单字符运算符独立a//b\na/bID(a), COMMENT, ID(a), OP(/), ID(b)注释与除法的区分if(x0){y!1;}KEYWORD(if), DELIMITER((), ID(x), OP(), NUM(0), DELIMITER()), DELIMITER({), ID(y), OP(!), NUM(1), DELIMITER(;), DELIMITER(})无空格的完整场景abc$123ID(abc), ERROR($), NUM(123)非法字符位置记录最后一行的期望输出说明了一个容易被忽略的点abc$123如果只是看正则$ 是非法字符但好的实现会把 abc、$、123 三段都识别出来而不是一错到底。这也是为什么我在第 5 章坚持要加行列号错误报告的价值在于“指出哪里错同时保住剩余合法 token”不在于整行丢弃。我把这套验证表放在词法分析器交付前必跑清单里。从那以后我每次写扫描器都强制自己先列一张最长匹配输入清单把、、!、、//、a/b这些边界全过一遍再谈代码能不能交。词法分析器看着小真正翻车的地方往往不在理论推导而在这些一个字符的边界判断上。这份实验报告的最大价值就是把这些边界和修正路径都摆在了明面上希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 16:59:35 · 阅读 1.2k 词法分析器设计与避坑：从正则到最小DFA的完整实现指南
简介西南科技大学编译原理实验报告1是一份设计型实验报告围绕词法分析程序从正则表达式到最小DFA的完整设计流程展开适合高校计算机专业学生进行编译原理课程设计或撰写实验报告时参考。报告以TEST语言为对象详细给出标识符、保留字、无符号整数、分界符、运算符、注释符等词法规则的正则表达式并完整演示了NFA构造、NFA合并、确定化、最小化DFA的过程同时设计了单词分类与输出方案附有具体示例和基于Python的DFA状态转移表及词法分析核心代码可帮助读者理解词法分析器的实现原理与调试思路为后续语法分析、语义分析等环节打下基础。压缩包内含1个doc格式报告文档整体大小约444KB内容组织规范包含实验目的、实验设计、实验过程、程序实现等完整章节可供直接查阅或参照改写。目前已有477人在CSDN学习或下载对需要完成编译原理实验、理解自动机理论应用的同学具有较好的参考价值。1. 编译原理实验报告1一份能直接复现的词法分析器设计与避坑清单拿到这份“编译原理实验报告1”时我的第一反应是词法分析器代码量不大难的是把正则、NFA、DFA这一串理论真正落成一份能跑通、能交差、还能讲明白为什么这么设计的实验报告。这份《编译系统综合设计》实验一报告完整覆盖了“正则规则→NFA合并→确定化→最小化→Python实现→错误定位→最长匹配讨论”的整条链路报告正文里就带了一份状态转移表驱动的词法分析程序和一组带非法字符的测试用例。它适合两类人正在写编译原理实验的学生可以照着这份材料的章节结构补齐自己的推导过程工作里要手写小语言前端、不想上 flex/lex 的开发者可以直接拿这份状态表当模板改。接下来我按报告顺序拆开讲重点放在实现细节和几个一跑就翻车的坑上。2. 词法规则的正则表达与NFA/DFA转化状态转移表是怎么被推导出来的2.1 各词法规则的正则写法先约定语言边界再写表达式写词法分析器之前第一步不是写代码而是把 TEST 语言里哪些 Token 合法这件事定死。报告把词法分成六类标识符、保留字、无符号整数、分界符、运算符、注释符。每类对应一个正则正则是后面构造 NFA 的输入也是程序验收时判断“你是不是真懂”的关键。标识符的正则写成(letter)(letter|digit)*展开就是 (a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*。这个写法有两个隐含约定一是首字符只能是字母字母后可以跟零个或多个字母或数字二是下划线不在字符集里说明 TEST 语言不允许下划线开头的标识符。如果以后要扩展成 C 语言风格把下划线加进 letter 集合再调整首字符判断就行代价是 NFA 多两个状态。无符号整数的正则用了这样一条((1|...|9)(0|1|...|9)*)|0它表达的是两种合法形态单独的 0或者 1 到 9 开头后跟任意位数字。也就是说“012345”这种带前导 0 的写法按这个正则应该被拒绝。这个细节后面会跟报告的分类表对不上先记着。保留字正则是if|else|for|while|do|int|write|read注意 do 在这里出现了但第 3 章要讲的单词分类表里关键字列表没有 do。报告前后不一致真实课程答辩时这种点很容易被问住。我的处理习惯是以关键字分类表为准要么把 do 补进分类表要么从正则里删掉两个版本必须同步。运算符正则是|-|*|/||||||!|难点在双字符运算符与单字符运算符共享前缀 和 、 和 、 和 、! 和 !。DFA 处理到 时要预读一个字符下一个是 就走双字符状态否则把 当作单字符运算符输出。这就是报告最后讨论的最长匹配原则在源码里的落点。注释符正则实际是 //。报告里写成了 /|/属于笔误语义上应该是两个斜杠连续出现才算注释开始。2.2 从正则到NFA再到最小DFA手工推导的落地顺序每个正则先独立构造一个 NFA这是 Thompson 构造法的标准流程。标识符的正则本质上是“首字符分支 后续循环”的结构首字符集合有 52 个字母分别引向中间状态再通过 ε 转移合并到循环体无符号整数的 NFA 是“0”的独立分支加上“1-9 开头循环数字”的另一个分支运算符则是一堆并行的单字符转移其中双字符运算符的 NFA 要做两级状态。合并 NFA 的做法是加一个公共起始状态用 ε 转移连到每个子 NFA 的起始状态。这一步的关键是不要让子 NFA 互相干扰每个子 NFA 的接受状态只属于自己合并后要记录“哪个接受状态属于哪个词法类别”后面确定化时才好给 DFA 接收状态标记类型。确定化走子集构造法先算公共起始状态对每个输入字符类别的 ε-闭包把它作为 DFA 的初始状态集再对每个状态集、每个输入类别求 move 后的 ε-闭包直到没有新状态集产生。手工推导时我一般不用画图法直接列一个“状态集编号 → 子集成员 → 各输入类别的跳转”表格哪怕多算几轮也比对着图猜状态靠谱。这步属于看着理论性强、实际可以机械完成的体力活。最小化用划分法先把所有 DFA 状态分成接收状态和非接收状态两组然后反复检查同一组里的状态对每个输入类别是否转移到同一大组转移目标不一致就拆开直到各组不再变化。自动机理论到这里看起来像玄学实际上只要字符类别控制在 5 个以内手工两步就能拆完。这里的关键是最小化之后状态数量会明显减少报告代码里 7 个状态就是这么缩出来的。2.3 状态转移表与DFA状态图的对应检查把最小化后的 DFA 套到报告代码里就是 7 个状态、5 个输入类别。状态包括 START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR输入类别是 ALPHABET字母、DIGIT数字、OPERATOR_DELIMITER运算符与分界符、SLASH斜杠、WHITESPACE空白。这张表有一个明显的状态冗余OPERATOR 和 DELIMITER 在报告代码里共用同一个输入类别但状态转移表里 DELIMITER 没有从任何初始状态到达的路径也就是说 DELIMITER 是个永远进不去的状态。这属于实现简化时的遗留问题不影响主流程但说明手工画图与代码落表时要专门做一遍“每个状态是否能到达”的检查。我习惯拿到 DFA 表先问三个问题哪些状态能到达哪些状态能到接收态哪些输入类别会导致 ERROR这三个问题过完表的结构问题基本就暴露了。到这里正则、NFA、DFA 三层就推完了。接下来进入单词分类和输出方案的设计。3. 单词分类与输出方案先把Token契约定死再写扫描器3.1 单词分类表的定义逻辑七类边界怎么切DFA 只负责把字符串切成一段段至于每一段叫什么名字要看单词分类方案。报告给的分类是七类这里直接列一个表类别英文名代表单词识别依据关键字Keywordint, if, else, while, for, read, write保留字表直接匹配标识符IdentifierID, var123, variable字母开头后续字母数字无符号整数Unsigned Integer123, 0一个或多个数字分界符Delimiter{, }, (, ), ;单字符分隔运算符Operator, -, *, /, , , , , , !, 单字符或多字符运算符注释符Comment//...以 // 开头到行尾保留字Reserved Wordint与关键字重复定义这个表里有几个边界值得注意。第一关键字和保留字在报告里重复了int 既在关键字列表里又在保留字列表里。实际工程里这两项通常会合并成一张关键字表词法分析器识别出标识符形态的单词后去表里查一下命中就标为关键字没命中就是普通标识符。第二do 在正则里出现了分类表里没有同样是不一致。第三无符号整数这里写的是“一个或多个数字”跟第 2 章正则里“不允许前导 0”冲突。3.2 输出方案从源码到Token流的完整映射报告给了一个很具体的示例程序int x; if (x 0) { write x 1; }对应的输出是Keyword: int Identifier: x Delimiter: ; If: if Parenthesis: ( Identifier: x Operator: Unsigned Integer: 0 Parenthesis: ) Curly Brace: { Write: write Identifier: x Operator: Unsigned Integer: 1 Delimiter: ; Curly Brace: }注意这里的输出格式并不是严格的“类型 空格 值”而是把关键字进一步拆成了 If、Write、Keyword 等更细的标签。这种写法适合实验报告展示因为老师一眼能看到你识别到了哪些关键字。真正工程化的词法分析器一般输出二元组Token 类型编号单词原文类型用枚举值而不是字符串。这个示例也暴露了一个隐藏条件所有 token 之间有空格或者换行所以报告里的 DFA 实现才能正确切分。如果把 if (x 0) 写成 if(x0)问题就会冒出来这点第 5 章会详细展开。输出到文件时我一般会把每行写成“行号:类型:单词”的格式方便后续语法分析阶段直接定位错误。3.3 正则与分类表不一致时该信谁把第 2 章的正则和第 3.1 节的分类表放一起对比能发现三处矛盾。第一是 do 的归属第二是前导 0 问题第三是“保留字”和“关键字”两个名词重复定义概念边界不清。前导 0 是最需要较真的。按正则定义012345 不合法按分类表定义一个或多个数字012345 合法。报告后面测试源程序里正好有一行“abc 012345;”而实验四的结果里并没有报 012345 的错误说明实现里大概率按“一个或多个数字”放行了。老师在答辩时如果追问这个就是最容易被扣分的点。我的建议是选定一个口径然后在报告里全局统一比如把正则改成 (0|1|...|9)(0|1|...|9)*或者把分类表改成“不允许前导 0 的多位数字”。改哪一个都行但不能两边矛盾。这三处矛盾解释清楚之后第 4 章来看程序本身是怎么按 DFA 实现的。4. 基于最小DFA编写词法分析程序Python实现与参数解读4.1 字符分类函数get_char_category 的类别粒度设计程序的第一步是把输入字符归类。报告里的 get_char_category 返回六种类别ALPHABET、DIGIT、OPERATOR_DELIMITER、WHITESPACE、SLASH、OTHER。类别粒度决定了 DFA 状态表有多少列粒度太粗会分不清运算符和分界符太细则状态表爆炸。这里把运算符和分界符合并成 OPERATOR_DELIMITER是一个明显简化后面会看到它带来的副作用。值得先指出一个坑判断顺序里代码先把 / 包含在 OPERATOR_DELIMITER 集合里后面又写了 elif char / 返回 SLASH导致 SLASH 分支永远不会被执行DFA 表里 START 到 COMMENT 的路径是死的。这是原报告调试记录里“不能处理除运算符号、处理注释符出错”的根源。第 5 章会给修正。这里先把原版代码完整贴出来方便对照。报告里的核心代码如下# 状态定义 states {START, ID, NUM, OPERATOR, DELIMITER, COMMENT, ERROR} # 定义输入字符类别 def get_char_category(char): # 判断单个字符属于哪一类输入 if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char in {, -, *, /, , , , !, (, ), {, }, ;, :}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE elif char /: return SLASH # 这个分支实际走不到因为 / 已经被上面收走了 else: return OTHER # DFA 状态转移表 dfa { START: {ALPHABET: ID, DIGIT: NUM, OPERATOR_DELIMITER: OPERATOR, SLASH: COMMENT, OTHER: ERROR}, ID: {ALPHABET: ID, DIGIT: ID, OPERATOR_DELIMITER: ID, SLASH: ID, OTHER: ERROR}, NUM: {ALPHABET: ERROR, DIGIT: NUM, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR}, OPERATOR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: OPERATOR, SLASH: ERROR, OTHER: ERROR}, DELIMITER: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: DELIMITER, SLASH: ERROR, OTHER: ERROR}, COMMENT: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: COMMENT, OTHER: ERROR}, ERROR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR} } # 词法分析函数 def lex_analysis(input_string): current_state START current_token tokens [] for char in input_string: category get_char_category(char) if category in dfa[current_state]: # 当前状态存在该输入类别的转移吸收字符 current_state dfa[current_state][category] current_token char else: # 当前状态无法吸收该字符说明一个 token 已经结束 if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) current_state START current_token if category ! WHITESPACE: # 新 token 从当前字符开始 current_state dfa[current_state][category] current_token char # 处理最后一个 token if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) return tokens # 示例输入 input_code int x; if (x 0) { write x 1; } # 执行分析 result lex_analysis(input_code) for token in result: print(fToken: {token[1]}, Type: {token[0]})这段代码的逻辑分三层。第一层是 get_char_category它把一个字符映射成一个类别字符串类别是后续 DFA 查询的 key。参数 char 只接受单个字符函数返回值一定是上面六个类别之一因为最后一个 else 兜底返回 OTHER。第二层是 dfa 表它是一个两层字典第一层 key 是当前状态第二层 key 是输入类别value 是转移后的状态。第三层是 lex_analysis 主循环它逐字符读入当前状态能转移就吸收字符不能转移就先提交当前 token再尝试用当前字符开启新 token。这里有个容易忽略的设计点dfa 表里没有 WHITESPACE 状态空白字符完全靠“当前状态对 WHITESPACE 没有转移”来触发提交从而起到分隔 token 的作用。也就是说这份代码能跑通报告里的示例输入是因为示例里 token 之间都有空格或换行。把 x 0 改成 x0结果就完全不一样了后面第 5 章会实际演一遍。提交 token 的条件也需要注意进入 ERROR 的字符不会被 append 到 tokens 里只会在主循环里无声跳过。报告后面测试文件里的 、$ 这类非法字符用这份原版代码跑是拿不到“错误位置”的因为 ERROR 分支没有做位置记录。这也是第 5 章要补的一块。5. 词法分析器避坑排查/歧义、状态粘连与非法字符定位5.1 除号与注释符冲突遇到 / 时如何预判现象测试程序第一行是{ //This a test program.运行原版代码时注释里的字母逐个报 ERROR除号/也经常被误吞单独写a / b时除号识别不稳定。原因有两个。第一个在 get_char_category 里/被写进了 OPERATOR_DELIMITER 集合且这个判断在 SLASH 判断之前导致char /的 SLASH 分支是永远走不到的死代码。DFA 表里 START 遇到 SLASH 进 COMMENT 的路径从一开始就是断的。第二个在 DFA 表本身即便把 / 单独分出来COMMENT 状态的转移表也只允许 SLASH 保持在 COMMENT注释内容里的字母数字都会触发 ERROR。单行注释本质上应该吸收除换行外的所有字符而不是只吸收斜杠。解决把 / 从 OPERATOR_DELIMITER 集合中删掉并将 SLASH 判断提前。COMMENT 状态单独写一段进入 COMMENT 后持续吸收直到遇到换行符再回到 START这比硬套 DFA 表更省事。修正后的字符分类函数如下def get_char_category(char): # 修正版/ 单独成类且判断顺序提前 if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char /: return SLASH # 注释符与除法的公共开头 elif char in {, -, *, , , , !, (, ), {, }, ;, :}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE else: return OTHER对应到主循环处理 / 时要做一次预读下一个字符也是 /说明是注释开始否则把 / 作为运算符提交。这个预读逻辑就是最长匹配原则的一部分也是报告第 3 节调试记录里“增加判断语句”的真正含义。5.2 无空格代码的token粘连状态转移表把ID/NUM写宽了现象把样例改成if(x0){write x1;}原版代码会把x0{write这种串粘成一个超长 token输出里出现 Token: x0{write, Type: ID。原因在 DFA 表的 ID 状态ID: {ALPHABET: ID, DIGIT: ID, OPERATOR_DELIMITER: ID, ...}。这等于告诉扫描器标识符遇到运算符或分界符时继续归并到标识符里。从自动机理论看这是把不该转移的转移写上了。原版示例能跑对纯粹是因为 token 之间都有空格空格会先触发提交。解决把 ID 和 NUM 状态对 OPERATOR_DELIMITER 的转移改成交付动作而不是状态跳转。常见做法是挂起当前字符识别到一个标识符正在扫描突然遇到先提交当前标识符再把作为新 token 的首字符重新进入起始判断。这也是第 6 章验证最长匹配时要检查的核心点。5.3 非法字符的错误定位ERROR状态不能只吞不报现象测试文件里有int abc123$;和int 123;原版代码跑完没有任何报错输出因为 ERROR 状态的 token 在提交条件里被排除了。要求的“报告词法错误及其位置”实际没实现。原因主循环里if current_state not in {WHITESPACE, COMMENT, ERROR}直接从输出里滤掉了 ERROR而且整个循环没有维护行列号就算把 ERROR 加回去也不知道错在第几行第几列。解决在循环里增加 line 和 col 两个计数器每读一个字符更新一下遇到 OTHER 类别或进入 ERROR 状态时把行号列号非法字符原文记进错误列表。这样既保住了合法 token 的 lex.txt 输出又能顺便交付错误清单。# 在 lex_analysis 内增加行列号维护 line, col 1, 1 errors [] for char in input_string: if char \n: line 1 col 1 else: col 1 category get_char_category(char) next_state dfa[current_state].get(category, ERROR) if next_state ERROR or category OTHER: errors.append((line, col, char)) current_state START current_token continue5.4 关键字与标识符的识别顺序DFA不查保留字表现象输入int x;时输出是 Token: int, Type: ID而不是关键字类型。报告期望的输出是 Keyword: int。原因DFA 只能识别“字母开头、后续字母数字”的形状它不知道 int 是关键字。形状识别和关键字查表是两层工作原版代码少了后面这层。解决ID token 提交后用保留字集合做一次查表。我一般会维护一个 Python setkeywords {int, if, else, for, while, do, read, write} if token_type ID and current_token in keywords: token_type KEYWORD注意查表动作一定要在 ID 提交时做不能提前。提前查会导致integer这种以 int 开头的标识符被误判成关键字。6. 最长匹配原则的验证方法用一组边界输入证明扫描器行为6.1 最长匹配在代码里的落点双字符运算符的预读处理报告里说本设计满足最长匹配原则依据是不会被拆成和。这句话理论上没问题但代码里要落到一个具体动作读取之后必须预读下一个字符才能决定走单字符分支还是双字符分支。预读失败时要能回退不然后面紧跟空格时会把空格吞掉。我在验证词法分析器时最常用的方法是构造一组“无空格粘连”输入因为这类输入最能暴露最长匹配是否真的实现。下面这段验证脚本跑在修正版逻辑上专门检查双字符运算符和注释符的边界test_cases [ x2, # 期望 x, , 2 x2, # 期望 x, , 2 a//b, # 期望 a, 注释到行尾 a/b, # 期望 a, /, b if(x0){y!1;}, # 无空格场景 ] # 对每组输入打印 token 序列用于人工核对 for code in test_cases: print(code, , lex_analysis_fixed(code))6.2 一组可执行的验证输入与预期Token序列输入期望Token序列说明x2ID(x), OP(), NUM(2)双字符运算符优先x2ID(x), OP(), NUM(2)单字符运算符独立a//b\na/bID(a), COMMENT, ID(a), OP(/), ID(b)注释与除法的区分if(x0){y!1;}KEYWORD(if), DELIMITER((), ID(x), OP(), NUM(0), DELIMITER()), DELIMITER({), ID(y), OP(!), NUM(1), DELIMITER(;), DELIMITER(})无空格的完整场景abc$123ID(abc), ERROR($), NUM(123)非法字符位置记录最后一行的期望输出说明了一个容易被忽略的点abc$123如果只是看正则$ 是非法字符但好的实现会把 abc、$、123 三段都识别出来而不是一错到底。这也是为什么我在第 5 章坚持要加行列号错误报告的价值在于“指出哪里错同时保住剩余合法 token”不在于整行丢弃。我把这套验证表放在词法分析器交付前必跑清单里。从那以后我每次写扫描器都强制自己先列一张最长匹配输入清单把、、!、、//、a/b这些边界全过一遍再谈代码能不能交。词法分析器看着小真正翻车的地方往往不在理论推导而在这些一个字符的边界判断上。这份实验报告的最大价值就是把这些边界和修正路径都摆在了明面上希望帮到你。本文还有配套的精品资源点击获取