简介：这是一份西南科技大学《编译系统综合设计》课程的编译原理实验报告，主题为“设计词法分析程序”，适合计算机专业本科生在编译原理实验、期末设计或考研复习时参考。报告完整记录了实验目的、词法规则设计、NFA构造、NFA确定化与最小化DFA的推导过程，并给出了标识符、关键字、无符号整数、分界符、运算符、注释符等单词分类及输出方案，配有Python词法分析程序的状态转移表和关键代码，便于对照理解词法分析器的核心流程与实现细节。压缩包内仅包含1个doc格式实验报告文档，文件量小、结构清晰，整体大小约444KB，可满足快速预览与学习需求；资源上线后已有477人浏览学习，是编译原理入门阶段较为实用的实验参考资料。

1. 编译原理第一个实验就翻车：斜杠被当成注释，除法直接消失

做编译原理词法分析实验的人，十有八九会在第一次跑测试用例时遇到这个现象：丢进去一段a / b * c，出来的 token 只有a、b、c，中间的除号不见了；再放一段//开头的单行注释，注释里的内容反而被当成标识符吐出来。整个结果看起来就像「除法被吃掉了，注释被放出来了」。

这类问题最折腾人的地方在于：它不是崩溃、不是抛异常，而是静默地多 token、少 token。程序能跑通，输出也有模有样，只有最后跟预期结果逐行核对时才发现对不上。源码里三种写法会让问题无限放大——a / b、a // b、a >= b，它们共享同一个坑：前缀相同，后缀决定身份。这篇笔记从一次词法分析程序实验的完整排错过程出发，把斜杠歧义、注释识别、多字符运算符、非法字符定位这几个点逐个拆开，给出能直接照做的解决顺序。

2. 词法规则先写对：从正则到最小 DFA 的完整落地

2.1 TEST 语言的词法规则：每一条都要能写成正则表达式

词法分析的第一步不是写代码，而是把语言里每一类单词用正则表达式描述清楚。报告里给出的 TEST 语言规则一共六类，我整理成下面这张表：

这条正则清单看着简单，实际每个选择都有讲究。以无符号整数为例，((1|...|9)(0|1|...|9)*)|0把 0 单独剥出来，意味着0123这种前导零写法不在「单个整数」的规则里。后面测试程序里出现了abc = 012345;，如果严格按这条正则跑，它会先识别出0，再识别出12345，而不是整体一个整数。实验报告最终把它当合法单词存入了 lex.txt，说明当时的实现选择了容忍这种写法，但这恰恰是词法设计里需要提前拍板的问题：前导零到底是报错、拆分还是作为一个合法整数，必须在正则阶段定清楚。

注释符在正则里只有一条//，但实现时它是最容易翻车的地方，因为单个/同时也是运算符。这就是第 3 章要重点展开的歧义来源：正则可以并列写出/和//，DFA 状态却只有一个入口。谁先抢到状态，谁就决定了程序行为。

2.2 正则转 NFA、合并、确定化、最小化：最终 DFA 状态表从哪来

有了正则表达式之后，下一步是构造 NFA。每个正则表达式都可以用最基本的 Thompson 构造法拼出一个 NFA：单个字符是「起始状态 → 接受状态」的一条边，串联用 ε 边连接，并联用 ε 分支汇合，闭包则加回环。标识符的正则 a-zA-Z 开头后跟字母数字，它的 NFA 就是开头一条字母边，接受状态上挂一个字母或数字的自循环。

六类规则分别构造出六棵 NFA 之后，需要把它们合并成一个大 NFA。常见的做法是新建一个全局起始状态，从这个状态分别拉 ε 边到六个子 NFA 的起始状态。这一步的目的是让所有词法规则共享同一个识别入口，之后的确定化才有意义。

合并后的 NFA 是带 ε 边的非确定自动机，直接写程序没法逐字符查表，所以要用子集构造法把它确定化成 DFA。子集构造法的本质是按字符看「NFA 从当前状态集合能到达哪些状态集合」，把状态集合当作新状态，消除 ε 边和分支。最后是最小化：把那些「接受性相同、对所有输入字符到达的状态也相同」的等价状态合并。报告里的 DFA 最后落在 START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR 这几个状态上，就是从这一串手工推导里提炼出来的。

我一般会让学生在画完最小 DFA 之后，把每个状态的职责写在一行注释里，比如ID状态的含义是「当前累积的是一个标识符前缀，后面还能跟字母或数字」。这个习惯后面写代码时非常有用——DFA 转移表里的每一行，对应着你脑子里对这类单词的完整认知，任何一个转移填错，都会直接体现为识别结果错乱。

2.3 单词分类与输出方案：和后续语法分析怎么衔接

TEST 语言的单词分类方案是七类：关键字（keyword）、标识符（Identifier）、无符号整数（Unsigned Integer）、分界符（Delimiter）、运算符（Operator）、注释符（Comment）、保留字（Reserved Word）。这里有个细节值得注意：int既出现在关键字列表里，又出现在保留字列表里。实验里它们实际指向同一个集合，所谓保留字就是语言保留了用途的单词，实现上把int、if、else、while、for、read、write放进同一张表即可，查表命中就是关键字，没命中就是普通标识符。

输出方案决定了词法分析程序跟语法分析程序之间的接口长什么样。报告给的示例输出是按源程序顺序打印每一行的类型和值，比如int x;输出Keyword: int、Identifier: x、Delimiter: ;。但继续往下看会发现输出名不统一：(输出成Parenthesis，{输出成Curly Brace，;输出成Delimiter。同一个分界符类别用了三种叫法，这对后面的语法分析很不友好。我的建议是输出类型统一用单词分类里的类别名，比如全部输出Delimiter: (、Delimiter: {，这样下游要按类型做映射时只需要查一个固定集合，不会出现同一种符号有三种标签的情况。

单词分类还有一个容易被忽略的价值：它直接决定了语法分析阶段的工作量。运算符里>=、<=、==、!=是多字符运算符，如果词法阶段把它们拆成两个单字符运算符，语法分析器就得自己重新拼装，等于把词法的责任推给了语法。所以词法分析程序必须保证这些运算符以整体形式出现在 token 流里，这也是后面第三、第五两章反复提到的「最长匹配原则」的实际意义。

3. 除号消失与注释错乱：根因是「/」的双重身份和缺失的预读

3.1 报错现场：除法算不出、注释全乱码

实验调试记录里写了两个问题表现：程序不能处理除运算符号/，处理注释符时出现错误。先还原一下报错现场。用初版程序分析x = a / b;，收集 token 时从a后面读到空格，token 结束输出标识符a；接着遇到/，字符分类函数把它归成SLASH，DFA 从 START 状态直接跳进 COMMENT 状态，然后把这个/累加进 current_token。下一个字符是空格，COMMENT 状态对 WHITESPACE 没有定义转移，token 收集提前中断，COMMENT 状态的 token 又被过滤掉不输出。一次循环下来，除号没了，后面b被当成独立标识符输出。

再看//注释的情况。源程序里写了{ //This a test program.，初版程序读到第一个/进 COMMENT，第二个/也进 COMMENT，理论上注释开始得还行，但 next 字符T是 ALPHABET，COMMENT 状态的转移表里 ALPHABET 指向 ERROR。于是注释内容This a test program.要么被报成错误，要么被当前状态判成非法字符——注释内的正常文本反而触发了词法错误，这就是「处理注释符时会出现错误」的直接来源。

这两个现象本质上是一个问题：初版 DFA 把斜杠单列成SLASH类别，START 状态遇到斜杠无条件进 COMMENT，等于默认「所有斜杠都是注释开头」。但语言里/还是除运算符。一个字符两种身份，转移表却只给了它一条路，于是总有一边的程序是错的。

3.2 根因分析：SLASH 类别抢走了运算符的位置，更缺最长匹配

深挖根因要回到 DFA 状态设计本身。字符分类函数里先判断char in {'+', '-', '*', '/', '>', '<', '=', '!', ...}返回OPERATOR_DELIMITER，后面又单独判断char == '/'返回SLASH。Python 的 if-elif 顺序里，/会先命中OPERATOR_DELIMITER分支还是SLASH分支，取决于代码排列——初版把 SLASH 分支放在后面，但 DFA 转移表 START 状态里又写了'SLASH': 'COMMENT'，两个定义互相打架。识别/时到底走哪条转移，全靠巧合和运气，这就是典型的黑匣子式翻车：你能跑出一个结果，但说不清它为什么是这个结果。

更本质的缺陷是缺失了「向前看一个字符」的机制。词法分析里的最长匹配原则说的是：识别出的单词有混淆时，按长度最长的确定。>和>=共享>前缀，!和!=共享!前缀，/和//共享/前缀。这类规则光靠逐字符读入无法区分：读到第一个/时，必须再看一眼下一个字符是不是/，才能决定是除号还是注释。原文 DFA 没有预读能力，遇到/就做出决定，自然无法满足最长匹配。

同样的缺陷也影响多字符运算符。>=如果按初版逻辑从 START 进 OPERATOR，读到>后下一个字符=仍是 OPERATOR_DELIMITER 类别，OPERATOR 状态继续累积，理论上碰巧能把>=拼成一个 token。但!=里的!在字符分类里也属于 OPERATOR_DELIMITER，逻辑上也是通的。问题在于这套状态表对「该在哪里停下」没有约束：=>这种语言里根本不存在的组合也会被拼出来，然后当作合法运算符输出。状态机只负责吞字符，不负责校验「吞出来的东西在不在单词表里」。

3.3 修复方案：预读一个字符，把「//」和「/」分开处理

修复的思路不复杂：对/做一次预读。读到/时先不急着决定类别，看下一个字符——如果是/，进入行注释处理，一直读到换行符为止；如果不是/，按除运算符输出。这样a / b里的/后面跟着空格，走正常运算符分支；//This里的第一个/后面是另一个/，走注释分支。两者从根源上被分开。

# 修复前：一个斜杠直接进 COMMENT 状态，除号被吞 if c == '/': state = 'COMMENT' # 修复后：预读一个字符，是 / 才进注释，否则是除号 if c == '/': if i + 1 < n and input_code[i + 1] == '/': # 行注释：一直读到行尾，不产生 token while i < n and input_code[i] != '\n': i += 1 continue else: tokens.append(('Operator', '/', line)) i += 1 continue

这段代码的逻辑说明：i是当前扫描下标，n是源程序总长度。i + 1 < n保证预读不会越界，也就是源程序最后恰好以/结尾时，不会误判成注释开头。进入注释分支后用一个 while 循环吃掉整行，直到遇到换行符\n停止，continue让外层循环继续处理下一行。除号分支直接把/登记为 Operator token，然后下标后移一位继续扫描。

这里要特别注意一点：预读只是帮助「分类」，不负责「吃掉」注释内容。注释内容应该在注释分支里直接跳过，而不是继续走 DFA 的字符累积逻辑。很多实现改到一半，注释是识别出来了，但注释里的字母数字又顺着 COMMENT 状态进入 ERROR，报一堆莫名其妙的非法字符错误。正确处理方式是注释判断永远放在主扫描逻辑最前面，斜杠一旦确认是注释开头，后续字符全部跳过，不参与任何 token 累积。这样的预读机制推广到多字符运算符上也成立：>预读=得到>=，!预读=得到!=，=预读=得到==，都遵循同一套「先看后决定」的逻辑。

4. 实跑 TEST 源程序：输出 lex.txt 并定位 123@ 与 2a 的词法错误

4.1 完整可运行的词法分析程序

基于修复思路，我重写了一个可以直接跑通的完整版本。它保留 DFA 状态转移表的骨架，加入了注释预读、关键字查表、非法字符定位三类能力，代码里关键位置都加了注释。

import sys # 关键字集合：标识符识别完后查这张表，区分 Keyword 与 Identifier KEYWORDS = {'int', 'if', 'else', 'while', 'for', 'read', 'write'} # 合法运算符集合：状态机拼出候选后，必须在这里校验 OPERATORS = {'+', '-', '*', '/', '>', '<', '=', '>=', '<=', '==', '!='} DELIMITERS = {'(', ')', '{', '}', ';'} def char_cat(c): """字符分类：决定 DFA 用哪条转移边""" if ('a' <= c <= 'z') or ('A' <= c <= 'Z'): return 'ALPHABET' if '0' <= c <= '9': return 'DIGIT' if c in '+-*/<>=!': return 'OPERATOR' if c in DELIMITERS: return 'DELIMITER' if c.isspace(): return 'WHITESPACE' return 'OTHER' # DFA 状态转移表：每个状态只保留自己关心的输入类别 dfa = { 'START': {'ALPHABET': 'ID', 'DIGIT': 'NUM', 'OPERATOR': 'OPERATOR', 'DELIMITER': 'DELIMITER'}, 'ID': {'ALPHABET': 'ID', 'DIGIT': 'ID'}, 'NUM': {'DIGIT': 'NUM'}, 'OPERATOR': {'OPERATOR': 'OPERATOR'}, 'DELIMITER': {}, } def lex(source): tokens, errors = [], [] i, line = 0, 1 n = len(source) while i < n: c = source[i] # 换行计数，保证错误和 token 都带行号 if c == '\n': line += 1 i += 1 continue # 空白字符直接跳过 if c.isspace(): i += 1 continue # 斜杠预读：// 是注释，/ 是运算符 if c == '/': if i + 1 < n and source[i + 1] == '/': while i < n and source[i] != '\n': i += 1 continue tokens.append(('Operator', '/', line)) i += 1 continue start_line, col = line, i + 1 # 记录 token 起点的行号和列号 state, token = 'START', '' while i < n: cc = char_cat(source[i]) if state == 'START': # 起始状态按首字符决定进入哪个子状态 nxt = {'ALPHABET': 'ID', 'DIGIT': 'NUM', 'OPERATOR': 'OPERATOR', 'DELIMITER': 'DELIMITER'}.get(cc) if nxt is None: break state = nxt else: nxt = dfa[state].get(cc) if nxt is None: break state = nxt token += source[i] i += 1 # 一个字符都没积累起来，说明是非法字符 if not token: errors.append(f'第{line}行第{col}列：非法字符 {c!r}') i += 1 continue # 数字后紧跟字母，典型错误：2a if state == 'NUM' and i < n and char_cat(source[i]) == 'ALPHABET': while i < n and char_cat(source[i]) in ('ALPHABET', 'DIGIT'): token += source[i] i += 1 errors.append(f'第{start_line}行第{col}列：{token!r} 不能以数字开头') continue # token 定级 if state == 'ID': kind = 'Keyword' if token in KEYWORDS else 'Identifier' elif state == 'NUM': kind = 'Unsigned Integer' elif state == 'OPERATOR': # 运算符候选必须出现在合法集合里，防止吞出 => 这种组合 if token not in OPERATORS: errors.append(f'第{start_line}行第{col}列：无法识别的运算符 {token!r}') continue kind = 'Operator' else: kind = 'Delimiter' tokens.append((kind, token, start_line)) return tokens, errors def main(): # test.txt 放 TEST 语言源程序，lex.txt 放合法单词 with open('test.txt', 'r', encoding='utf-8') as f: source = f.read() tokens, errors = lex(source) with open('lex.txt', 'w', encoding='utf-8') as f: for kind, val, line in tokens: f.write(f'{line}: {kind} {val}\n') for err in errors: print(err) if __name__ == '__main__': main()

参数说明：source是整个源程序字符串，tokens列表存(类型, 单词, 行号)，errors列表存错误描述。i是全局扫描下标，line是当前行号，每遇到\n加一。col在每次 token 开始时记录列号，用于准确定位非法字符。dfa转移表里DELIMITER和ERROR状态留空字典，表示这些状态一旦到达就结束当前 token，不再继续吞字符。OPERATOR状态吞到合法运算符集合之外时会被token not in OPERATORS拦截并报错，避免=>、=<这类组合悄悄混过去。

这个版本里最值得关注的设计是「先按 DFA 累积、再按集合校验」的两步走。DFA 负责把连续同类字符拼成一个候选，运算符白名单负责判断这个候选在不在语言里。前者解决识别问题，后者解决合法性问题，两者凑齐才叫完整的词法分析。

4.2 词法错误怎么报告：行号、列号、非法字符一个都不能少

实验要求里明确写了一句「报告词法错误及其位置」，这意味着错误信息至少要包含三样东西：出错的行号、出错的列号、非法字符本身。初版程序只输出ERROR状态和累积的 token，没有行号列号，等于告诉你有错但不告诉你在哪，排查起来要从头逐行数。

报告里给出的两个错误来自这段测试源程序：

{ //This a test program. int abc123$; int 123@; int 2a; abc = 012345; for (i = 1; i <= n; i = I + 1) { if(i != n) abc = ab c* i else abc = abc / i; } }

一个在第 3 行：123@以数字开头，后面跟了非法字符@；另一个在第 4 行：2a以数字开头跟字母，不符合标识符「字母开头」的命名规则。这两个位置的共同点是：错误都不发生在 token 的第一个字符，而是发生在 token 累积到中途时遇到了不该出现的字符。所以错误定位必须在 token 累积的循环里记录起点行号和列号，等到 break 跳出时，用起点信息去描述整个失败的 token。

int 2a这行值得单独说。按 DFA 逻辑，2先进 NUM 状态，接着a是字母，NUM 状态转移表里没有 ALPHABET 的转移边，循环 break。此时 token 是2，下一个字符是a。修复版代码检测到「NUM 状态 + 下一个字符是字母」的组合，就把连续字母数字都并进来，输出一条专门错误。这样不会出现「先输出一个合法的整数 2，再把 a 当独立标识符输出」的误导性结果。词法错误的处理原则本来就是：一旦发现一个单词不合法，尽量把它整体报出来，而不是拆成半截合法半截非法来掩盖问题。

4.3 输出结果核对：合法单词入库，非法单词留下精确位置

用修复版程序跑上面那段测试源程序，lex.txt里会得到按行组织的结果。开头几行长这样：

5: Identifier abc 5: Operator = 5: Unsigned Integer 012345 6: Keyword for 6: Delimiter ( 6: Identifier i 6: Operator = 6: Unsigned Integer 1 6: Delimiter ; ...

注释行//This a test program.整体被跳过，不在 lex.txt 里，也没有报错。abc123$里的abc123作为合法标识符入库，$在下一个扫描位置被单独报为非法字符——这里有一个实现差异值得说明：报告只列了123@和2a两个错误，但测试程序里$同样不属于任何合法类别。严谨的词法分析器应该把它也报出来，报告没列可能是因为当时只检查了用例里明示的两个点。实际工程里，所有不在字符分类表里的符号都必须走非法分支，漏掉任何一个都意味着后面语法分析会拿到脏 token。

对照实验预期逐项核验：int全部输出为 Keyword，普通变量名输出为 Identifier，数字输出为 Unsigned Integer，<=、!=、/都作为完整 Operator 输出，没有拆成单字符，//注释没有污染 token 流。三个最初的问题——除号消失、注释错乱、错误无定位——在这个版本里全部消失。输出文件里每个合法单词都带行号，错误信息也带行号和列号，拿它去跟语法分析器对接或人工核对，都能直接定位到源程序对应位置。

5. 词法分析常见问题避坑清单：五种翻车现场与对应修法

5.1 注释内容被当成合法单词输出

现象：//后面的注释文本出现在 token 输出里，比如注释里的test被识别成 Identifier。原因：注释分支没有把后续字符完全跳过，COMMENT 状态在转移表里只覆盖了少数类别，遇到字母数字就中断并把已经累积的内容当作 token 返回。解决：注释判断放在扫描主逻辑最前，确认进入注释后直接循环到行尾，全程不参与 token 累积。判断的标准是：一个词法分析器如果输出的 token 里出现了注释里的单词，就说明注释处理没有真正生效。

5.2 除号被当成注释开头吞掉

现象：a / b输出里没有/，b直接跟在a后面。原因：DFA 把/无条件指向 COMMENT 状态，所有斜杠都被当作注释入口。解决：读/时预读下一个字符，//才进注释，否则输出 Operator。最容易踩的坑是预读越界——源程序最后一个字符是/时，i + 1 < n必须先判断再取字符，否则直接访问会越界。

5.3>=、==、!=被拆成两个运算符

现象：x >= 0输出三个 token：x、>、=、0。原因：OPERATOR 状态每遇到一个运算符字符就收尾，没有做最长匹配。解决：OPERATOR 状态持续吞运算符字符，吞完后用 OPERATORS 白名单校验，>=在白名单里就以整体输出。OBS 里还要留意=单独作为赋值运算符的存在，赋值和多字符比较靠预读就能区分，但前提是预读逻辑写在对的层级——判断=下一个是不是=或>或<，决定它是赋值还是比较的一部分。

5.4 关键字和标识符没区分，int 被输出成 Identifier

现象：int x;输出Identifier: int而不是Keyword: int。原因：DFA 只负责把连续的字母数字拼成一个 token，它本身不具备语义判断能力，关键字表没有接入。解决：ID 状态的 token 收集完整后，先去 KEYWORDS 集合查一轮，命中输出 Keyword，未命中输出 Identifier。这个查表动作必须在 token 完整识别之后做，不能在读到i时就判断是不是if，否则int的前两个字符会误命中。

5.5 非法字符只报 ERROR，不报行号和列号

现象：程序输出Token: @, Type: ERROR，但不知道 @ 在源文件哪一行哪一列。原因：token 累积循环没有记录起点位置，错误分支也没有把(行号, 列号)带进错误信息。解决：每个 token 开始扫描前记录start_line和col，token 积累失败时用这两个值拼错误描述。判断一个词法分析器定位能力是否合格，直接看错误信息里有没有「第几行第几列」就够了。实验要求明确要报告词法错误及其位置，行号列号是硬性指标，不是可选项。

6. 快速定位词法分析问题：三组测试用例就够了

6.1 第一组：单字符与多字符运算符

词法分析的大多数 bug 集中在多字符运算符和单字符运算符的边界上。我每次拿到一个词法分析器，第一件事就是跑三行输入：

a >= b a != b a == b

预期输出分别是Identifier a、Operator >=、Identifier b；Identifier a、Operator !=、Identifier b；Identifier a、Operator ==、Identifier b。如果输出里出现单独的>、=、!，说明最长匹配没生效。确认办法是给三个用例各加一行对照：a > b、a = b、a !b。能同时正确处理这两组，运算符部分的边界才算稳。

6.2 第二组：注释与除号的边界

第二组专门测/的双重身份，输入三行：

x / y x // y x // y + z

第一行必须输出Operator /，第二行注释整体跳过不产生 token，第三行注释从//开始到行尾全部跳过，+和z如果出现在注释后面就不该出现。最容易迷惑的情况是第三行——如果实现只在读到//时跳过两个字符而不是跳过整行，y + z就会漏出来。

6.3 第三组：非法字符与数字开头标识符

第三组测错误定位能力：

int 2a; int 123@;

预期结果不是「程序崩溃」，而是给出类似「第 1 行第 5 列：'2a' 不能以数字开头」「第 2 行第 5 列：非法字符 '@'」的错误信息。如果错误信息里没有行号列号，或者2a被拆成合法整数2加标识符a，说明错误处理策略有问题。

定位问题的方法说来也简单：先看字符分类函数char_cat是否把目标字符归对了类，再看对应状态在转移表里有没有需要的边，最后用「逐字符走表」的方式把出错输入在纸上过一遍。输入不长的时候，这种方法十分钟内就能把问题范围缩小到一两行代码。遇到复杂点的输入，就按行二分：先在中间行加打印，看错误出现在前半还是后半，再继续缩小。

从那以后，我每写完一个词法分析器，都会强制自己先跑这三组用例再跑完整测试程序，三组全过才敢说代码能交。三组用例背后的三个问题——最长匹配、注释跳过、错误定位——正是报告里那几次调试记录的根源所在。希望帮到你。

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