简介这份面向高校编译原理课程学习者的实验报告聚焦词法分析程序的设计与实现适合正在完成课程实验、复习自动机理论或需要参考实验报告写法的学生。包内共1个doc文档约444KB围绕TEST语言完整梳理从正则表达式描述词法规则、构造NFA、合并确定化并最小化为DFA到单词分类与输出方案的设计流程。内容包含实验目的、设计思路、实验过程与程序实现并给出词法分析程序框架、DFA状态转移表及示例代码涉及标识符、保留字、无符号整数、分界符、运算符和注释符等单词类型的识别同时提示错误处理、缓冲区管理与回溯机制等实现细节。已有477人学习可作为实验报告结构、规则整理、状态机设计和程序实现思路的对照参考并帮助理解编译前端处理流程。1. 词法分析器不是切字符串为什么先要有自动机再写代码翻完这份词法分析实验报告最容易被忽略的不是正则表达式写得多漂亮而是真正跑起来的那个东西——状态转移表。很多人以为词法分析就是拿几条正则去匹配源码匹配到就输出 token可一旦遇到和、//和/、123abc这种边界简单正则拼接就会翻车。词法分析器底层是一台确定有限自动机它一个字符一个字符地读靠状态转移决定下一步靠接受态和回退实现最长匹配。搞懂这台自动机怎么从正则表达式一步步构造出来比背几条语法规则有用得多。这份实验报告的价值也正在于它把正则、NFA、DFA、最小化和代码实现串成了一条能验证的链。2. 正则到 NFAThompson 构造为什么能把模式变成状态图词法规则先写成正则表达式这是最接近人直觉的一步。标识符是字母开头、后跟零个或多个字母数字无符号整数要么是0要么是1到9开头再接任意数字运算符里有也有有也有注释以//开头一直延伸到行尾。正则表达式只声明“什么样的字符串合法”它没有告诉计算机怎么高效识别。NFA 是中间模型允许 ε 转移也允许同一个字符有多条出边直觉上像“猜”。Thompson 构造把每个正则运算符翻译成固定形状的小片段再用 ε 边拼起来。它的价值不是让机器直接跑而是保证任何正则表达式都能机械地变成一个 NFA不需要人想破头。2.1 六类词法规则怎么落成正则表达式实验报告里列了标识符、保留字、无符号整数、分界符、运算符、注释符。写成简化正则大致是下面这张表。表里的字符类是一种压缩写法实验报告里展开成(a|b|...|z|A|B|...|Z)也完全等价。词法类别正则表达式简化写法说明标识符[A-Za-z][A-Za-z0-9]*字母开头后跟字母数字无符号整数[1-9][0-9]*0保留字ifelse分界符()运算符-注释//[^\n]*到行尾结束写正则时有两个坑。第一保留字和标识符的正则重叠if既能被标识符匹配也能被保留字匹配。第二运算符有前缀关系是的前缀是的前缀。正则本身不解决优先级最终要靠 DFA 接受态里的类别标记和最长匹配策略。常见的实现思路是先给每条规则一个类别编号合并 NFA 时把接受态标上类别确定化后如果一个 DFA 状态包含多个接受态就按“保留字优先于标识符、长运算符优先于短运算符”的规则选类别。这个优先级不是正则语法的一部分而是词法分析器的设计决策。2.2 Thompson 构造每个运算符对应一个状态片段Thompson 构造的核心是“每个正则子表达式都有一个入口和一个出口”。字符c的片段是一条边连接ab是把a的出口用 ε 边接到b的入口选择a|b是新建初态用 ε 边分叉到两个片段的入口两个片段的出口再用 ε 边汇到新接受态闭包a*是新建初态和接受态初态既能进片段也能直接到接受态片段出口既能回片段入口也能到新接受态。下面是一个可运行的骨架省略了状态编号分配和字符类展开。class NFA: def __init__(self): self.trans {} # state - {char: set(states)} self.eps {} # state - set(states) self.start None self.accept None self.accept_tag None # 该接受态对应的词法类别 def char_nfa(c): 原子片段s --c-- f n NFA() s, f new_state(), new_state() n.start, n.accept s, f n.trans.setdefault(s, {}).setdefault(c, set()).add(f) return n def concat(a, b): 连接a 的出口用 ε 接到 b 的入口 n NFA() n.start, n.accept a.start, b.accept merge(n, a) merge(n, b) n.eps.setdefault(a.accept, set()).add(b.start) return n def union(a, b): 选择新初态 ε 分叉两个出口 ε 汇合 n NFA() s, f new_state(), new_state() n.start, n.accept s, f merge(n, a) merge(n, b) n.eps[s] {a.start, b.start} n.eps[a.accept] {f} n.eps[b.accept] {f} return n def star(a): 闭包初态可跳过片段片段出口可回入口或直接结束 n NFA() s, f new_state(), new_state() n.start, n.accept s, f merge(n, a) n.eps[s] {a.start, f} n.eps[a.accept] {a.start, f} return nchar_nfa(c)里的c是单个输入字符返回的是一个最小片段。concat(a, b)的a、b是子 NFA它不新建状态只把a.accept用 ε 边接到b.start所以整个片段的入口还是a.start出口变成b.accept。union(a, b)和star(a)会新建初态与接受态因为分叉和回边需要新的“汇合点”。merge(n, a)不是重点它只是把子片段的状态和转移合进当前对象实际实现里可以用全局自增编号避免状态冲突。这个构造的状态数和正则长度线性相关形状规整正好喂给确定化算法。2.3 ε 闭包NFA 同时处在多个状态时到底在算什么NFA 的“非确定”体现在 ε 边不读字符也能跳。计算ε-closure(T)就是从集合T出发沿 ε 边能到达的所有状态。它表示“在当前位置机器可能同时处在这些状态”。子集构造法就是把这种“可能集合”打包成一个 DFA 状态。要注意 ε 闭包必须迭代到不动点不能只走一层因为 ε 边可能连续跳好几次。def eps_closure(nfa, states): 从 states 出发沿 ε 边求闭包返回 frozenset 便于做字典键 stack list(states) closure set(states) while stack: s stack.pop() for t in nfa.eps.get(s, ()): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure)states是起始状态集合stack做深度优先遍历closure存放结果。用frozenset是为了后面能把它当 DFA 状态放进字典。这个函数不读输入字符只走 ε 边真正读字符的是move。两者组合起来就是子集构造法的全部核心。NFA 直接执行需要回溯最坏情况下会指数级尝试DFA 每个状态对一个输入字符只有一条出边扫描是线性的。Thompson 构造是“先放大再收拢”用 ε 边把结构写清楚再确定化消掉不确定性。3. NFA 确定化子集构造法如何消掉 ε 转移的“猜测”子集构造法的输入是 NFA输出是 DFA。DFA 的每个状态是 NFA 状态的一个集合。初始 DFA 状态是ε-closure({nfa.start})对每个 DFA 状态T和每个输入字符a计算U ε-closure(move(T, a))如果U没出现过就新建状态转移T --a-- U。重复到没有新状态。接受态是那些包含 NFA 接受态的集合。这里的关键是NFA 的“同时处在多个状态”被压缩成 DFA 的一个状态读一个字符后可能到达的集合是确定的。虽然状态数最坏可能到2^n但词法规则通常有限实际规模可接受。3.1 子集构造的输入输出从状态集合到 DFA 状态把算法拆成步骤更清楚。第一步收集 NFA 的所有输入字符形成字母表第二步把初始 ε 闭包入队第三步每次取出一个状态集合对字母表中每个字符求move再求ε-closure第四步如果得到的新集合没出现过就分配一个新的 DFA 状态编号并入队第五步记录转移第六步如果集合里包含 NFA 接受态就记录该 DFA 状态的接受类别。整个过程像一个广度优先搜索搜的是“状态集合的可达图”。这里有一个容易忽略的细节DFA 状态不是 NFA 状态的简单编号而是一个集合。两个不同的 NFA 状态集合可能包含相同的接受态但它们的后续转移不同所以不能合并。最小化阶段才会判断它们是否等价。子集构造阶段只负责“确定化”不负责“最小化”这两步分开做逻辑才清楚。3.2 合并 NFA 时初态、接受态与词法类别的处理多条词法规则不能各自跑一遍 DFA那样效率太低。常见的做法是新建一个总初态S用 ε 边连到每条规则 NFA 的初态每条规则的接受态保留自己的类别标签。确定化后一个 DFA 状态可能包含多个接受态比如if的接受态和标识符的接受态可能落在同一个集合里。这时要按优先级选类别。优先级表可以这样定保留字高于标识符、、!、高于对应的单字符运算符注释高于除号。这个优先级不是拍脑袋它对应语言规范里的词法规则顺序。还有一个细节合并后的 NFA 初态只有S但S本身不是接受态。确定化后的初始 DFA 状态是ε-closure({S})它会包含各规则片段的入口。如果某条规则允许空串初始状态就可能是接受态但词法规则一般不允许空 token所以这里通常不会出问题。接受态标记要跟着 NFA 状态走确定化时把集合内所有接受态的标签收集起来再按优先级选一个。3.3 用 Python 实现 move 与 ε-closuremove只走字符边不走 ε 边ε-closure再补上 ε 可达的状态。两个函数分开写逻辑不容易乱。def move(nfa, states, ch): 从 states 出发读入字符 ch返回直接到达的状态集合 result set() for s in states: for t in nfa.trans.get(s, {}).get(ch, ()): result.add(t) return result def subset_construction(nfa, alphabet): start eps_closure(nfa, {nfa.start}) dfa_states [start] dfa_trans {} dfa_accept {} queue [start] while queue: T queue.pop(0) # 一个 DFA 状态可能包含多个 NFA 接受态按优先级选类别 tags [nfa.accept_tag[s] for s in T if s in nfa.accept_tag] if tags: dfa_accept[T] pick_tag(tags) for ch in alphabet: U eps_closure(nfa, move(nfa, T, ch)) if not U: continue if U not in dfa_states: dfa_states.append(U) queue.append(U) dfa_trans[(T, ch)] U return dfa_states, dfa_trans, dfa_acceptmove(nfa, states, ch)的参数states是当前 NFA 状态集合ch是输入字符返回值不含 ε 闭包。subset_construction(nfa, alphabet)的alphabet是收集好的输入字符集合返回值里dfa_states是状态集合列表dfa_trans用(状态, 字符)做键dfa_accept记录接受类别。pick_tag(tags)按优先级从候选标签里选一个比如保留字优先于标识符。这里省略了死状态如果某个字符没有转移就当作不能继续词法分析器会回退到最近接受态。4. DFA 最小化Hopcroft 分割凭什么合并等价状态最小化解决两个问题状态表太大、代码里状态分支太多。两个状态等价是指对任何输入串从它们出发要么都接受同类 token要么都不接受。最小化把等价状态合并成一个。常用 Hopcroft 分割先按接受类别分初始组非接受态一组每个接受类别一组然后反复检查每个组如果组内状态对某个输入字符的转移落在不同组就分裂直到所有组稳定。最后每个组代表一个状态。4.1 等价状态的定义与初始划分等价状态的定义里“接受同类 token”这一点很关键。如果两个状态都接受但一个输出关键字if另一个输出标识符它们不能合并因为后续词法分析器要按类别生成 token。初始划分不能只分“接受”和“非接受”而要按接受类别分组。非接受态单独一组每个接受类别一组。这样最小化后的每个组内部类别一致不会把关键字和标识符混在一起。还有一点死状态和错误状态也要考虑。如果某个状态对任何输入都没有转移它和另一个同样没有转移的非接受态可能等价可以合并。但错误处理需要记录位置所以实际实现里常常把错误状态单独保留不参与最小化。实验级代码可以简化工业级词法器一般会把错误恢复路径单独设计。4.2 分割细化为什么按输入字符分组就能逼近最小分割细化的逻辑是如果组内两个状态对某个输入字符分别跳到不同的组那么它们可区分必须分开。反复分裂直到稳定剩下的每个组就是等价类。下面是一个朴素实现复杂度比 Hopcroft 高但逻辑直白适合对照实验报告理解。def find_group(groups, state): for i, g in enumerate(groups): if state in g: return i return -1 def minimize(dfa_states, dfa_trans, dfa_accept, alphabet): # 初始划分非接受态一组每个接受类别一组 groups [] non_accept [s for s in dfa_states if s not in dfa_accept] if non_accept: groups.append(set(non_accept)) by_tag {} for s, tag in dfa_accept.items(): by_tag.setdefault(tag, set()).add(s) groups.extend(by_tag.values()) changed True while changed: changed False new_groups [] for g in groups: split {} for s in g: # 对每个输入字符记录目标状态所属组编号 key tuple( find_group(groups, dfa_trans[(s, ch)]) if (s, ch) in dfa_trans else -1 for ch in alphabet ) split.setdefault(key, set()).add(s) if len(split) 1: changed True new_groups.extend(split.values()) groups new_groups return groupsfind_group(groups, state)返回状态所属组编号找不到返回-1。minimize的参数dfa_states是状态列表dfa_trans是转移表dfa_accept是接受类别表alphabet是输入字符集合。核心在key它把组内状态对每个输入字符的目标组编号拼成元组元组不同就说明这些状态可区分需要分裂。循环直到changed为假分组稳定。这个实现没有做 Hopcroft 的“按小集合分裂”优化但结果一致。4.3 最小化后的状态表如何映射回词法类别最小化后每个组取一个代表状态组内所有状态的接受类别必须相同转移表重写为组到组。最后生成二维表行是状态列是字符类别值是下一状态。词法分析器就用这张表跑。要保留每个组的接受类别用于输出 token 类型。还要把死状态去掉或标记为错误。字符类别可以压缩比如把所有字母归为ALPHA所有数字归为DIGIT把运算符和分界符按字符细分。表驱动的好处是新增规则时只改表不改扫描循环。5. 词法分析器避坑排查五个让状态机悄悄翻车的实现细节实验代码里最容易出问题的地方不是 DFA 构造而是状态转移表和字符分类的细节。下面几条是血泪经验里最常见的翻车点每条按现象、原因、解决写。对照着看能省不少调试时间。5.1 除号被当成注释开头字符分类顺序写反了现象输入a / b词法分析器把/识别成注释开始后面的b被吞掉或者直接报错。有时候a / b能过a // b又过不了表现很玄学。原因get_char_category先把/归入运算符集合又写了一个SLASH分支但if char in {, -, *, /, ...}在前elif char /永远到不了同时 DFA 的START状态把SLASH直接转到COMMENT没有先判断下一个字符是不是/。这两个问题叠在一起除号和注释就分不开了。解决把/单独分类START看到/先进入一个中间状态SLASH_OR_COMMENT再读下一个字符是/进注释否则回退并接受为除号。代码里字符分类顺序要保证/不被运算符集合提前截走。注意回退时字符位置要一起回退否则下一个 token 会从错误的位置开始。5.2 标识符状态遇到分号不退出接受态没有回退现象int x;被识别成一个 tokenx;或者状态卡在ID出不来。调试输出里能看到 token 长度越来越长最后把整行都吞了。原因DFA 表里ID状态遇到OPERATOR_DELIMITER还转到ID把分号吞进标识符词法分析器只在“不能转移”时才输出 token没有在“到达接受态后遇到非法字符”时回退。简单说状态机没有“最近接受态”的概念它把接受当成了终点而不是一个可以回退的检查点。解决ID状态遇非字母数字应该停止不消耗当前字符回退到最近接受态把当前字符重新交给START处理。实现上用last_accept记录最近接受位置和类别读超一个字符后回退。扫描循环里维护pos、last_accept_pos、last_accept_tag回退时把pos设回last_accept_pos当前字符留给下一轮。5.3 数字后面跟字母直接报错缺少“接受后重新扫描”现象123abc报错实验里2a也报错。但有时候123后面跟一个空格再跟abc又正常边界很迷惑。原因NUM状态遇到字母直接进ERROR没有区分“数字常量后跟字母”和“数字正常结束”。如果语言允许123后跟标识符中间有空格则不能把字母一律当错误如果紧邻应该报错。实验要求2a报错是因为标识符不能以数字开头2a不是一个合法 token 序列。解决NUM接受后看下一个字符如果是字母或下划线记录错误起点并跳过整个非法单词否则回退到接受位置输出数字。实验里按错误处理就应在NUM状态遇字母时进入ERROR而不是接受2再识别a。如果要支持“最长匹配切分”则接受2再把a当标识符但这不符合实验的词法规则。两种策略要明确选一种不能一半一半。5.4 注释状态出不来结束条件没有回到 START现象// comment\nint x;注释后面的代码全被吞掉或者注释 token 被当成普通 token 输出。原因COMMENT状态只处理字符不识别换行遇到\n没有回到START或者把换行也吞了。还有一种情况是注释到文件尾没有结束条件循环退出后状态还停在COMMENT最后一个 token 处理逻辑又把它当普通 token 输出。解决COMMENT状态遇到\n时结束注释回到START并且不输出注释 token如果注释到文件尾也要正常结束。注释内容不参与 token 输出但行号要正常递增。实验报告里注释符写成//代码里却把/同时当运算符和注释开头这就是 5.1 和 5.4 的叠加问题。5.5 错误位置只记行号不记列号报错定位漂移现象报错说第 3 行有非法字符但用户在第 3 行找不到具体位置或者回退之后报错位置偏后几个字符。原因只维护line没有维护column回退时列号没有恢复。扫描时每读一个字符就递增列号回退时只改了pos没改column后面所有错误位置都漂了。解决扫描时维护line和column每读一个字符更新回退时同时恢复位置token 记录起始行列。错误信息输出line:column。这个细节在实验报告里容易被忽略但工业级词法器的错误信息全靠它。调试时可以先只打印line:column和当前字符确认位置对了再继续。6. 设计取舍实验级 DFA 与工业级词法器之间差的那一层实验里把正则、NFA、DFA、最小化、代码跑通已经能说明词法分析的核心机制。但工业级词法分析器还会在几个地方做取舍。字符集上实验通常只处理 ASCII工业级要面对 Unicode 标识符和多种编码驱动方式上实验适合表驱动工业级有时用手写switch换吞吐错误恢复上实验报错就停工业级往往跳过非法字符继续扫描尽量多报几个错缓冲区上实验一次读入字符串工业级用双缓冲和哨兵减少边界判断关键字识别上实验可以把关键字直接做进 DFA工业级更常见的是先按标识符扫出来再查关键字哈希表这样 DFA 状态数少很多。维度实验级词法器工业级词法器字符集ASCII 为主Unicode、编码处理驱动方式状态转移表表驱动或手写分支错误恢复报错停止跳过非法字符继续关键字识别做进 DFA标识符扫描后查表缓冲整串读入双缓冲、哨兵这些不是“更高级”而是场景不同。实验级追求把自动机链路讲清楚工业级追求吞吐、内存和错误信息。我的习惯是先把接受态、回退路径和错误位置这三件事在纸上画清楚再写代码。从那以后我每次写状态机都先跑一遍、//、123abc这三个用例再谈优化。希望帮到你。本文还有配套的精品资源点击获取