简介西南科技大学编译原理实验报告围绕“设计词法分析程序”这一主题完整记录了从实验目的、实验设计到实验过程、程序实现的全部环节适合正在学习编译原理、准备期末课程设计或需要完成类似词法分析实验的学生参考。报告以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: intIdentifier: 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:pos2] 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 两条路径的后续行为完全一致——为了省几行代码后面排查时花了两个晚上这笔账不划算。希望这份拆解能帮你少走这些弯路祝实验顺利。本文还有配套的精品资源点击获取