简介：西南科技大学编译原理实验报告围绕“设计词法分析程序”这一主题，完整记录了从实验目的、实验设计到实验过程、程序实现的全部环节，适合正在学习编译原理、准备期末课程设计或需要完成类似词法分析实验的学生参考。报告以TEST语言为研究对象，详细给出了标识符、保留字、无符号整数、分界符、运算符、注释符等词法规则对应的正则表达式，并逐步演示了如何构造非确定有限自动机（NFA）、合并子自动机、确定化为确定有限自动机（DFA）并化简得到最小DFA的完整过程。内容还定义了七类单词的分类标准与输出格式，并附带了基于Python的词法分析程序框架，包括字符类别判断函数、状态转移表以及主扫描逻辑，能够帮助读者直观理解词法分析器的设计思路。资源为单个doc文档，大小约444KB，结构清晰、便于编辑；已有477人学习/下载。通过该报告，读者既能掌握正则表达式到自动机转换、DFA最小化等核心知识点，也能借鉴实验报告规范严谨的撰写方式。
1. 编译原理实验：词法分析这关，理论到代码隔着一整条DFA
“编译原理”课设里，词法分析往往是第一个动手环节。某高校的 TEST 语言词法分析实验要求走完一整套链路：正则表达式描述词法规则、构造 NFA、合并确定化、化简成最小 DFA，最后基于 DFA 写识别程序。很多人觉得理论推导清楚，代码却写不出来，问题出在中间的映射没有理顺——状态图是画在纸上的，程序里的状态转移表是按字典写的，这两者之间差了几个关键的边界处理。这篇笔记把实验里的设计过程、Python 实现细节和调试记录全拆开讲，适合正在做词法分析设计型实验的人参考。
2. 词法规则建模：从正则表达式到最小DFA的完整推导
2.1 七类Token的正则表达式：边界怎么定义才不出歧义
TEST 语言的词法规则拆出来是七类：标识符、保留字、无符号整数、分界符、运算符、注释符，外加一个研究中常被忽略的空白符。正则表达式是整条链路的起点，写得不严谨，后面 NFA、DFA 全都会跟着错。
标识符这条规则，大多数教材都写成：
(a|b|...|z|A|...|Z)(0|1|...|9|a|b|...|z|A|...|Z)*这个写法的关键是首字符必须是字母，后续字符是字母或数字。看起来简单，但它隐含了一个重要决策：下划线算不算合法字符？很多语言允许下划线开头，但 TEST 语言的规则没有包含它，这意味着遇到_var，词法分析器应该报错而不是识别为标识符。这个取舍要提前定，别等到写程序时再纠结。
保留字用的是并列形式：if|else|for|while|do|int|write|read。这里要注意一个经典陷阱：保留字集合跟标识符规则是重叠的——int既能被标识符规则匹配，又是保留字。实验常见做法是先按标识符规则识别，再查保留字表，命中就标记为关键字类型。这个策略后面第 3 章会详细说。
无符号整数写成了((1|...|9)(0|...|9)*)|0，这个表达式的优点是天然排除了前导零的情况，比如012345会被分解成0和12345。很多实现里会把整数定义简写成digit+，那样就会接受带前导零的串，虽然大多数场景没问题，但这一版的 TEST 语言明确要求采用排除前导零的写法，所以后面测试用例里专门设计了012345这个输入。
运算符部分我觉得是整份正则定义里最容易被低估的地方。+|-|*|/|=|<|>|>=|<=|!=|==这里把单字符与双字符运算符混在一个正则里，合并 NFA 后会出现一个非常关键的状态：当读入>时，你不知道下一个字符是=还是其它，必须保留一个「等待后缀」的中间状态。这就是后面实现中要处理的最长匹配问题。
2.2 NFA合并：为什么不能跳过去直接写DFA
从正则表达式到 NFA 的过程，理论课讲的是 Thompson 构造法，这里不展开。值得说的是合并这一步——实验要求把每个规则对应的 NFA 合并成一个大的 NFA。合并的方式是引入一个新的初始状态，用 ε 边连到所有子 NFA 的初态。
很多同学会觉得这步是形式主义，直接把正则表达式翻译成程序里的判断逻辑不就完了吗？这个想法在只有七八种词法的场景下确实能做，但一旦词法规则超过十五个、状态数超过三十个，手写判断逻辑就成了一团乱麻。DFA 的好处是：每次读一个字符，查一次状态转移表，复杂度是 O(n)，没有回溯，行为可预测。合并 NFA 再确定化，本质上是让程序的状态机结构从「人的直觉」变成「算法的产物」。
在本次实验里，由于运算符存在多字符情况，NFA 合并后需要特别小心那些可接受状态之间的 ε 闭包。以>和>=为例，单个>的 NFA 和>=的 NFA 合并后，初始状态经过>既能到达「运算符接受态」，又能到达一个中间状态继续等待=。如果不做确定化，直接用 NFA 去匹配，就必须处理回溯；确定化后，这个不确定性被消解为两个不同的 DFA 状态。
合并后 NFA 确定化的产物是一个真实存在的大表。例如，合并后初始状态S0在读到字符i时，既可能进入标识符 NFA 的路径，也可能进入保留字if的路径——因为if也是以i开头。确定化时要把这两个 NFA 状态做子集合并，形成一个新的 DFA 状态。这个状态内部同时包含「标识符进行中」和「保留字进行中」两个 NFA 状态，所以后续读到f时，状态会继续分裂或汇合。这也是if和int这类保留字与普通标识符共享前缀的理论原因。
2.3 DFA最小化：状态等价性判断的实际操作
确定化得到的 DFA 不是最小的，接下来要按可区分性做最小化。常见的算法是把状态分成接受态集合和非接受态集合，然后反复分裂不可区分的状态组。
以本次实验为例，确定化后的 DFA 中有这么几个状态值得关注：
| 状态 | 含义 | 是否为接受态 |
|---|---|---|
| S1 | 正在读标识符 | 是（但当读到运算符/分界符时需输出） |
| S2 | 正在读整数 | 是 |
| S3 | 刚读到/，可能是除号或注释起始 | 否 |
| S4 | 刚读到>，可能是大于号或>= | 否 |
最小化的执行步骤是：初始把状态分成接受组和非接受组，然后看每个组里的状态在相同输入字符类别下，跳转到的目标组是否一致。比如 S1 在读字母时跳到自身，S2 在读字母时跳到错误态，两者不等价，分开；S3 和 S4 都不是接受态，但 S3 读/进入注释状态，S4 读=进入运算符接受态，行为完全不同，也要分开。
最小化做完后，一个很实用的习惯是把状态重新编号，并顺手把等价状态合并的收敛过程画一遍。很多同学直接拿未最小化的 DFA 写程序，功能上也没错，但状态表里会有冗余行。对于这个只有十几个状态的实验来说，冗余状态对最终程序的影响不大，但如果后面要做完整的编译前端，状态表膨胀会直接影响内存占用和查表速度，所以最小化这个步骤最好还是认真走一遍。
2.4 状态转移表构造的代码落点
最小 DFA 完成后，把它落成程序里的状态转移表，最常见的做法是用二维字典。Python 里可以写成：
# DFA状态转移表：行是状态，列是输入字符类别 dfa = { 'START': {'ALPHABET': 'ID', 'DIGIT': 'NUM'}, 'ID': {'ALPHABET': 'ID', 'DIGIT': 'ID'}, 'NUM': {'ALPHABET': 'ERROR', 'DIGIT': 'NUM'}, }这里有一个关键的工程决策：状态转移表里存的是状态名还是状态编号。存状态名的好处是调试时打印信息可读性强，坏处是比较字符串有额外开销；存编号（整数）则相反。对于课程实验几十个状态来说，可读性优先，存字符串完全没问题。真正重要的是表的结构要跟最小化后的 DFA 一一对应——每一行都必须覆盖所有可能的输入类别，否则运行时访问不存在的键就会抛 KeyError。
3. 单词分类与输出方案：Token规格表的边界设计
3.1 保留字与标识符的区分：查表还是走状态
实验的单词分类方案列出了七类：关键字、标识符、无符号整数、分界符、运算符、注释符、保留字。眼睛尖的读者已经发现了，里面既有关键字又有保留字，而且把int单独拿出来列了一次。这是实验报告里一个常见的语义重叠现象：有的资料把int归为关键字，有的归为保留字，实际含义相近。代码实现时应该以「关键字」表为准，把七个小词全部放进一个集合。
# 关键字/保留字表 KEYWORDS = {'int', 'if', 'else', 'for', 'while', 'read', 'write'}识别策略上，业界有两种主流做法。第一种是 DFA 状态区分法：为每个保留字单独建 NFA 状态，合并后再确定化，让 DFA 自己天然区分if和普通标识符。第二种是回调查表法：先用统一的标识符规则识别出字符串，然后查 KEYWORDS 表，命中就标记为 Keyword，否则就是 Identifier。实验原方案用了后者，这也是大多数生产级词法分析器（例如各类工具生成的词法器）采取的方式。原因是保留字列表经常变动，把表独立出来便于维护，不必改 DFA 结构。
3.2 Token输出格式设计：面向语法分析的接口约定
单词输出方案在整个编译前端中扮演接口角色——语法分析器消费它的输出，所以格式必须稳定。原实验方案给出的输出是：
Keyword: int Identifier: x Delimiter: ;这种「类型: 值」的平铺输出适合人工查看，但词法分析器返回给语法分析器的通常不是文本，而是一个个 Token 对象或元组。本次实验用 Python 元组实现也够用：(类型, 值, 行号, 列号)。行号和列号一定要加，虽然这个实验的要求里没有强制，但后续做语法分析报错时，没有位置信息根本没法定位问题。我在这个实验里吃过亏：一开始没记行号，测试一个几十行的程序时报错只能靠肉眼数，浪费了大量时间。
对于分界符和运算符，一个实用建议是每个符号单独领一个类型名，而不是笼统地全标成 Operator。例如(可以细分为LPAREN，{细分为LBRACE。这样语法分析阶段判断结构就非常直接，不用去比较运算符的值。但实验原方案把(归为分界符（Delimiter），把>归为运算符（Operator），这也在合理范围内——语法分析器拿到 Delimiter 之后再看具体值来区分左右括号也是常见的。关键是输出形式定义之后不要中途变动，否则后面语法分析器的代码跟着返工。
3.3 注释丢弃还是保留：词法分析层的一个决定
注释符//被识别后，最终不应该出现在 Token 流里，这个原方案没有明说，但属于默认行为——注释是给程序员看的，不是给编译器消费的。实现时需要在识别到完整注释后把状态重置到 START，并丢弃当前累积的 token 文本。这个决定会在第 5 章的避坑部分再次出现，因为它是本实验调试记录里明确写出的两个问题之一。
4. 基于DFA的Python词法分析程序：状态转移表驱动
4.1 字符分类函数的实现：五类输入的边界
原实验的程序里有一个get_char_category函数，它把输入字符分成几类：字母（ALPHABET）、数字（DIGIT）、运算符与分界符混合类（OPERATOR_DELIMITER）、空白（WHITESPACE）、斜杠（SLASH）和其它（OTHER）。这里有个值得注意的设计决策：运算符和分界符合并成一个类别。这样做的好处是状态转移表可以少几列，缺点是状态转移表里无法区分(和+——两者被视为同类输入。如果 DFA 已经最小化且确认这两个符号的转移路径完全一致，合并是安全且高效的。但如果后续要扩展语言，比如给括号增加单独的状态逻辑，就需要把它们拆开。
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'逻辑说明：isalpha()在 Python 里对 Unicode 字母也会返回 True，但 TEST 语言的源程序是 ASCII 字符集，所以不需要额外限制。如果源文件可能包含中文或其他非 ASCII 字符，建议改成'a' <= char <= 'z' or 'A' <= char <= 'Z'，避免把中文误判为标识符字符。
参数说明：该函数只接受单字符参数，调用前应确保传入的不是空串。char.isspace()覆盖空格、制表符、换行、回车，这些都是词法单元的分隔边界，不会被累积进 token。
这里有一个被我反复折腾过的点：/既是除号，又是注释前缀，所以不能简单地放进OPERATOR_DELIMITER集合里，要单独作为 SLASH 类别处理。这样 DFA 在遇到/时进入一个特殊状态，在该状态读取下一个字符来区分除号（后面跟空白或数字）与注释（后面跟/）。原实验报告的调试记录里专门写到了这个问题，后面第 5 章再细说。
4.2 DFA状态转移表：字典结构里的状态机
状态转移表用嵌套字典表示，这是 Python 里最直白的做法。外层键是当前状态，内层键是输入字符类别，内层值就是下一个状态。原实验的 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'}, }仔细看一下ID状态：当读到OPERATOR_DELIMITER时转移到ID本身？这在语义上是站不住脚的——标识符中混入(应该结束当前标识符并开始新 Token。实际上这行转移规则存在隐患。正确的做法有两层含义需要澄清。
第一层，状态转移表负责的是「当前正在扫描的 Token」的状态。当处于ID状态且读入OPERATOR_DELIMITER类的字符时，当前 Token（标识符）应该结束了，然后对这个字符重新开启一个新的 Token 扫描。但你没法在一个转移表里同时表达「结束上一个 Token」和「开始下一个 Token」两件事。所以常见工程做法是：主循环里检测到「进入终止或错误状态」时，先输出当前累积的 Token，再把当前字符交给 START 状态重新开始。
这也是原实验代码逻辑里比较含糊的部分。正确实现时，主循环不能只用一张转移表，还要负责 Token 的切分。原报告的代码没有单独处理这个边界，这其实为后续调试埋了雷。
4.3 主扫描循环与Token提取：别把状态转移和输出混在一起
主扫描循环的正确逻辑应该是四步：读一个字符 → 查表得下一个状态 → 判断状态变化是否意味着 Token 结束 → 决定是否输出。原实验代码用一个 for 循环直接驱动状态更新，遇到WHITESPACE或ERROR状态就重置，但仔细推敲会发现它没有显式处理「当前字符应该归属下一个 Token」的情况。
一个更清晰的写法是采用「当前累积 token + 状态 + 回退标记」的模式：
def lex_analysis(input_string): current_state = 'START' current_token = '' tokens = [] i = 0 while i < len(input_string): char = input_string[i] category = get_char_category(char) # 状态转移失败时,当前Token结束,该字符需要重新处理 if category not in dfa[current_state]: tokens.append((current_state, current_token)) current_token = '' current_state = 'START' # 不递增i,让当前字符从START重新走一次 continue current_state = dfa[current_state][category] current_token += char # 注释块识别后直接丢弃 if current_state == 'COMMENT_SLASH' and char == '/': # 已读到"//"的第一个斜杠,继续读 pass i += 1 if current_token: tokens.append((current_state, current_token)) return tokens逻辑说明：这段代码用while循环替代for循环，关键差别在于遇到转移失败时，continue不消费当前字符，让该字符从 START 状态重新开始扫描。这样才能做到「上一个 token 已经结束，当前字符是新 token 的开头」。for i循环做不到这件事，这也是很多词法分析器翻车的原因。
参数说明：input_string是待分析的源代码字符串；dfa是状态转移表；tokens列表存(状态, 值)元组。这个实现里没有考虑跨行处理与行号记录，实际实验报告中要求把错误位置报告出来，所以行号计数器是少不了的。建议改造为双指针时，同时维护line变量在一遇到\n就自增，并把(token_type, value, line, col)存成四元组，后面报错才有足够信息。
5. 调试记录与避坑指南：注释符与除号冲突的根因分析
5.1 翻车现场：除号/被吞掉还是被误判为注释
实验调试记录里明确写了一个现象：代码运行结果中不能处理除运算符号/。我在复现这个实验时也遇到了完全一样的问题——输入abc = abc / i;，结果输出里没有/运算符，程序要么把/误判成注释开头丢掉，要么整个卡住。这个现象在初学 DFA 实现时非常典型。
现象：输入表达式abc / i，词法分析结果中缺少 Operator 类型的/条目；或者把//之后的整行内容吞掉。
原因：/在字符分类时被单独标为 SLASH，但 DFA 状态转移表里 START 状态收到 SLASH 直接进入 COMMENT 状态。于是所有出现在表达式中的/都被当作注释起始符处理，后续字符全部被丢弃。这本质上是「SLASH 类别覆盖了除号」这一设计漏洞。正确处理方式是引入一个中间状态：START 收到/后进入 SLASH_SEEN 状态，再读一个字符判断——如果是/则进入 COMMENT，如果是数字、字母、空白等则回退并识别为除号运算符。
解决：使用一个专门的COMMENT_START状态桥接。代码如下：
# 新增"读到斜杠"的中间状态 if current_state == 'SLASH_SEEN': if char == '/': current_state = 'COMMENT' # 确认是注释 else: # 斜杠是除号,当前token结束,斜杠重新走START tokens.append(('OPERATOR', '/')) current_state = 'START' current_token = '' continue解决后要立刻补一组回归测试：/、//、/**（虽然不支持块注释）、a/b、a//b这五种输入都必须产出预期 Token。其中a//b应该产出标识符 a、注释//b丢弃，而不是运算符/加错误 Token。
5.2 收尾处理与多字符运算符：文件末尾的Token被漏掉
现象：源代码文件最后的一个 Token 经常不输出。例如输入int x（末尾没有分号），输出只剩Keyword: int，Identifier: x丢失。
原因：主循环处理完最后一个字符后，current_token里还残留着一个尚未输出的 Token，但循环已经结束，没有收尾代码把缓冲清空。原实验代码里虽然有「处理最后一个词法单元」的代码，但只在current_state不属于某些集合时才输出，判断条件写得稍微不对就会漏。
解决：统一在循环结束后写一段收尾逻辑，且收尾逻辑要与循环内的输出条件保持一致。比较好的做法是写一个flush_token()小函数，循环内用continue跳过输出时调用它，文件末尾也调用它，避免把同一逻辑复制两遍。
5.3 标识符误报与非 ASCII 字符：Unicode 字母带来的额外麻烦
现象：源代码里混入中文注释或被测试的标识符，程序没有报错，反而把中文字符当作标识符的一部分一起输出了。
原因：char.isalpha()在 Python 3 中默认返回 True 对所有 Unicode 字母成立，包括中文。这导致int 变量名;会被识别为一个完整标识符变量名。对于课程实验，这是不可接受的，因为 TEST 语言明确规定标识符只能是 ASCII 字母加数字。
解决：把isalpha()换成显式 ASCII 范围判断，或者先用char.encode('ascii', 'ignore')过滤。我在自己实现时用了'A' <= char <= 'Z' or 'a' <= char <= 'z'，宁可多写几行也不贪图isalpha()的简洁。这个坑属于那种「测试用例不覆盖就永远不会暴露」的类型，建议在测试集里显式加上中文注释和非法标识符用例。
5.4 状态转移表缺键的三类典型表现
现象：程序运行中抛出 KeyError，报错位置指向dfa[current_state][category]；或没有任何异常但结果 Token 类型错乱。
原因：三种典型情况——第一，状态转移表没有覆盖所有状态的所有输入类别；第二，字符分类函数返回了 DFA 表里未定义的类别；第三，转移表里对某个状态定义了输入类别，但切换来的状态初始值不在 START 且没有经过合法路径。最常见的是第一类，比如OPERATOR状态在读ALPHABET时表里写的是ERROR，但如果你顺手把SLASH项漏了，就会在执行时报 KeyError。
解决：写一个小测试脚本遍历所有状态与类别的笛卡尔积，确保每个组合都有对应值。就算目标是 ERROR，也不能缺失。
6. 把最长匹配落进代码：多读一个字符的代价与收益
最长匹配原则在实验报告里被反复强调，落到代码上，核心技巧其实就是一个「向前看一个字符」的回退机制。以>和>=为例，当 DFA 处于可接受状态且有继续读入的路径时，你不能立刻终止 Token，必须再读入一个字符尝试更长匹配；如果读入的字符不构成更长的合法 Token，就把这个字符「回退」——在代码里表现为不消费它，直接让状态输出当前 Token，然后把这个字符交给 START 状态重新扫描。
实现时不要尝试真的「放回」字符——字符串不像流式输入那样能 unread。正确做法是主循环里维护一个last_state判断逻辑：当从START读到>进入OPERATOR状态后，读下一个字符=时状态转移成功，Token 累积为>=；如果下一个字符是x，则当前 Token 应为>，且x不进入运算符累积串。
# 最长匹配示例:处理 ">=" 与 ">" 的区分 def scan_operator(source, pos): """从pos位置开始尝试匹配运算符, 返回(token, next_pos)""" if pos >= len(source): return None, pos char = source[pos] two_char = source[pos:pos+2] if two_char in {'>=', '<=', '!=', '=='}: return ('OPERATOR', two_char), pos + 2 if char in {'+', '-', '*', '/', '=', '<', '>', '!', '(', ')', '{', '}', ';'}: return ('OPERATOR' if char not in {'(', ')', '{', '}', ';'} else 'DELIMITER', char), pos + 1 return None, pos逻辑说明：这个函数先看两个字符能否匹配双字符运算符，再看单个字符。这实际上就是最长匹配在运算符场景下的两种实现方式之一——主动尝试两位匹配，匹配失败回退到一位。这种写法的收益是代码逻辑直白，不会出现「先匹配单字符再后悔」的问题；代价是需要保证双字符匹配集合的字符串长度都是 2，如果出现三字符运算符就要再往下扩展。
从那以后我每次写词法分析器都会强制走一遍「最长匹配检查」：把所有以相同前缀开头的 Token 对找出来，逐个确认代码里的两个分支有没有正确处理回退。这个检查清单不长，但每次都能抓出至少一个漏网之鱼。另外还有一条教训：字符分类函数的状态分支不要图省事合并运算符和分界符，除非你确定 DFA 两条路径的后续行为完全一致——为了省几行代码，后面排查时花了两个晚上，这笔账不划算。希望这份拆解能帮你少走这些弯路，祝实验顺利。
本文还有配套的精品资源，点击获取
