简介西南科技大学编译原理实验报告1聚焦词法分析程序的设计与实现面向正在学习编译原理、需要完成实验一或梳理编译器前端流程的高校学生。报告按实验目的、设计、过程与程序实现展开完整呈现正则表达式描述词法规则、构造NFA、合并并确定化为DFA、再化简为最小DFA的推导链条并给出TEST语言中标识符、保留字、无符号整数、分界符、运算符和注释符的分类及单词输出方案。文中还列出基于Python的DFA状态转移表与词法分析函数框架提示错误处理、缓冲区管理和回溯机制等可扩展细节便于对照复现和查漏补缺。资源包共1个doc文件约444KB篇幅紧凑适合作为实验报告参考与复习提纲目前已有479人学习具有一定参考热度。1. 词法分析为什么编译器前端第一件事是把字符流切成 Token很多人第一次翻开词法分析这一章会觉得它像个文字游戏拿正则表达式描述单词画几个圆圈箭头最后写个循环读字符能跑就行。真正反直觉的地方在于——词法分析器的正确性跟你会不会写 if-else 几乎无关它取决于你能不能把一组正则表达式“编译”成一张无回溯的有限状态转移表。某高校那份《编译系统综合设计》实验报告从写正则、造 NFA、确定化为 DFA、化简到最小 DFA再用 Python 落实成一个状态机走的正是这条完整的编译链。搞懂它你就明白为什么不会被拆成和为什么//和除号必须靠状态而不是靠字符判断也就知道自己手写的分词函数为什么总在边界上翻车。这份实验报告的价值不在“实验报告”四个字而在它把每一步都留了痕迹。2. 正则到 NFA为什么先造一台“会猜”的自动机正则表达式本身就是给人类读的机器读不了(a|b|...|z)*这种东西。要让机器执行得先把“模式”翻译成“状态”。这条翻译链的第一站是 NFA而 NFA 之所以叫“非确定”是因为它在任何一个时刻可以同时停在好几个状态上——它靠 ε 边“猜”。工程师的第一反应通常是直接跑 NFA 不行吗不行因为猜就要回溯回溯就要爆炸。2.1 把词法规则翻译成正则表达式时边界在哪实验报告列出了 TEST 语言的六类规则看起来很简单但每一条都埋着坑。标识符写成(a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*意思是首字符必须是字母后续可以是字母或数字。保留字写成if|else|for|while|do|int|write|read。这里立刻出现第一个矛盾if这个串同样能被标识符的正则匹配上。两条规则在语言层面是重叠的。工程上通行的做法不是把保留字从标识符里“减掉”而是反过来——先全部按标识符识别再拿这个串去查一张关键字表。查中了就改写 token 类型查不中就保持 Identifier。这样 DFA 只需要一套标识符规则关键字表是一张哈希表代价接近零。实验报告里单词分类把int同时列进了“关键字”和“保留字”说明作者已经隐约意识到这个重叠只是没讲透。第二个坑在无符号整数((1|...|9)(0|1|...|9)*)|0。为什么非要把0单独拎出来做一支因为要禁止前导零。如果不拆012345会被整个吞成一个整数而按严格规则它应该是0和12345两个 token或者直接被判为非法。报告里的源程序恰好有abc 012345;这一句实验者把它当成合法单词处理了——这是一处真正的语义分歧点取决于语言规范怎么定义而不取决于代码能不能跑。第三个坑更隐蔽。运算符写成|-|*|/||||||!|这个顺序是错的。如果用一个从左到右、匹配到第一个成功分支就停的正则引擎去跑读到时第一个分支不匹配、匹配直接成功返回这一支永远走不到。正确写法必须是长串在前||!||||||...。这是“最长匹配”在正则层面的第一次现身也解释了为什么后面 DFA 必须带接受态和回退。第四个坑是分界符那行(|)|;|{|}。(和)在正则里是分组符号直接这么写会被当成语法结构而不是字面量必须转义成\(\)或者干脆在实现里放弃正则、用字符集合判断。报告里的注释符写成了/|/从上下文看本意是//排版把两个斜杠弄丢了——这类文本失真在抄实验报告时极常见但一旦照抄进代码就是灾难。提示写词法规则时凡是“一个串是另一个串前缀”的情况与、与、/与//正则的书写顺序和后续状态机的接受态设计必须一起考虑不能分开拍脑袋。2.2 Thompson 构造一个正则算子对应一小块子图把正则变成 NFA 有一套机械的、可以照着敲的算法叫 Thompson 构造。它的核心思想是归纳先给最小单元画图再给每种组合算子规定“怎么把已有的图拼起来”。一共就三条拼接规则加两条变体。基本单元是单个字符a新建两个状态i和f画一条从i到f、标号a的边。连接rs把r的终态和s的初态用一条 ε 边接起来整体初态取r的初态终态取s的终态。图不用改只加一条空边。选择r|s新建初态i和终态f从i各拉一条 ε 边到r的初态和s的初态r的终态、s的终态各拉一条 ε 边到f。这样从i出发两条路都能走。闭包r*新建初态i和终态fi用 ε 连到r的初态同时也用 ε 直连f表示匹配零次r的终态用 ε 连回r的初态表示再来一次同时用 ε 连到f表示收工。正闭包r只是去掉“i直连f”那一条边。拿无符号整数((1|...|9)(0|...|9)*)|0走一遍把字母表按区间简写成[1-9]和[0-9]得到的转移关系大致是状态输入后继状态N0εN1, N7N1[1-9]N2N2εN3, N6N3εN4, N6N4[0-9]N5N5εN3, N6N70N8N8εN6N0 是初态N6 是唯一的终态。这张表就是“正则被翻译成状态”的第一形态。注意 N3 和 N5 之间那条回边——那就是*的“再来一次”。整个构造过程不需要任何创造性纯粹是照着算子套模板这正是它适合被写成程序的原因。2.3 ε-闭包NFA 的“猜”到底是什么NFA 的“非确定”听上去玄落到实现上其实是一个集合运算。给定一个状态集合T它的 ε-闭包ε-closure(T)定义为从T中任意状态出发只走 ε 边能到达的所有状态的集合包含T本身。这个操作是幂等的再做一次不会变大。有了闭包NFA 的“同时处在多个状态”就有了严格定义当前配置不是“一个状态”而是“一个状态集合”。读入字符a时先对集合里每个状态找所有标号a的出边把后继收集起来再对这个后继集合求一次 ε-闭包。整个过程是一次集合到集合的映射。问题来了这个映射是多对一的不同输入串可能落到同一个集合但同一个集合读同一个字符可能分叉出多条路。如果用程序直接模拟就得维护一个“待探索路径栈”一旦某条路走死就要回退到上一个分叉点换一条。最坏情况下路径数随输入长度指数增长。词法分析器要处理的是几十万行源码这种代价不可接受。所以 NFA 在工程上从来不是“运行”的目标它只是一个中间表示。真正的运行形态必须是确定的一个状态、一个字符、唯一后继。把 NFA 变成这个形态的过程叫确定化也就是下一章的子集构造。3. 子集构造NFA 确定化到底在做什么数学操作一句话概括子集构造把“NFA 的状态集合”整体打包当成 DFA 的一个状态。听起来像变魔术其实是把 NFA 运行时那个“集合”直接固化成了状态机的节点于是运行期不再需要维护集合也不需要回溯。3.1 一个 DFA 状态 一个 NFA 状态集合算法骨架是这样的从ε-closure({s0})出发把它记作 DFA 的初态D0。对每个尚未处理的 DFA 状态D和每个输入字符a计算U ε-closure(move(D, a))其中move(D, a)是D里所有状态沿标号a的出边到达的后继集合。如果U非空且没出现过就新建一个 DFA 状态最后把D --a-- U记进转移表。反复直到没有新状态产生。关键在于“非空”这个判断。move(D, a)为空意味着当前集合里没有任何状态能吃下a这条边在 DFA 里就不画——这正是词法分析器“读到一个不该读的字符就停下来”的来源也是错误检测的天然入口。用伪代码写出来大概是这样def subset_construction(nfa_start, nfa_trans, alphabet): # nfa_trans: dict[state][char] - set[state]ε 边用 作键 start frozenset(epsilon_closure({nfa_start}, nfa_trans)) dfa_states [start] dfa_trans {} queue [start] while queue: cur queue.pop(0) dfa_trans[cur] {} for ch in alphabet: # 先沿 ch 走一步再求 ε 闭包得到一个 NFA 状态集合 moved set() for s in cur: moved | nfa_trans.get(s, {}).get(ch, set()) if not moved: continue # 空集不建边留作死路 nxt frozenset(epsilon_closure(moved, nfa_trans)) dfa_trans[cur][ch] nxt if nxt not in dfa_states: dfa_states.append(nxt) queue.append(nxt) return dfa_states, dfa_trans def epsilon_closure(states, nfa_trans): # 反复扩展 ε 边直到不再增长典型的定点迭代 stack, closure list(states), set(states) while stack: s stack.pop() for t in nfa_trans.get(s, {}).get(, set()): if t not in closure: closure.add(t) stack.append(t) return closure这段代码里frozenset不是随手写的。DFA 状态需要作为字典的键可哈希是硬性要求而普通set不可哈希一旦用列表存集合再比较每次查重都是 O(n) 的线性扫描状态一多就直接拖垮。frozenset把“集合相等”变成哈希比较整个构造从平方级降到接近线性。这是实现层面一个很容易被忽略但影响巨大的选择。另一个细节是epsilon_closure用了显式栈而不是递归。NFA 的 ε 链可能很长尤其是a*嵌套b*这种递归深度一旦上去就是栈溢出编译器前端在这种地方崩掉非常难看。3.2 合并 NFA为什么必须新建一个唯一初态词法分析器要同时识别标识符、整数、运算符、注释等好几类规则。自然的做法是给每条规则各造一个 NFA然后合并成一个大的。合并方式不是把初态直接连起来而是新建一个全局初态S用 ε 边分别指向每个子 NFA 的初态。这一步不能省。如果图省事让标识符的初态兼任全局初态那么从标识符初态出发就只能走标识符那条路其他规则永远进不去。反过来如果让所有子 NFA 的初态直接合并成一个去掉 ε 边共享节点那状态转移的语义就被破坏了——本来“读字母”应该只进标识符分支合并后可能同时进整数分支虽然子集构造能把这种混乱重新整理成合法 DFA但初态的接受性质会变得难以判断。新建S之后S本身的 ε-闭包天然包含了所有子规则的入口状态于是 DFA 的初态就自动是“所有可能规则的起点的集合”。这一步的收益在确定化之后才显现从D0读一个字母move会同时走到标识符分支和保留字分支的对应位置闭包一求得到的集合同时携带了“可能是标识符”和“可能是关键字”两种身份。等到整个串读完再看这个终态集合里有没有包含某条规则的终态就知道该归到哪一类。注意合并后的终态通常不止一个。一个 DFA 状态可能同时是“标识符的终态”和“某个关键字的终态”这时候必须靠规则优先级来裁决——一般是关键字优先于标识符长规则优先于短规则。优先级不写在状态机里写在“终态到 token 类型”的映射表里。3.3 字符等价类让转移表从 70 列缩到 6 列理论上字母表有多大转移表就有多少列。TEST 语言涉及大小写字母 52 个、数字 10 个、各种符号十几个加起来七十多列。但实际构造出来的 DFA 里大量列的转移是完全一样的——所有小写字母在任何状态下的后继都相同所有数字也相同。于是有一步必做的优化把行为一致的字符归成一个等价类。实验报告的 Python 实现里get_char_category函数干的就是这件事它把字符映射到ALPHABET、DIGIT、OPERATOR_DELIMITER、WHITESPACE、SLASH、OTHER六个类别。转移表的列数从七十多降到六状态数不变内存直接降一个数量级。这个函数看着简单却是整个程序里最容易出错的地方原因在于判断顺序即优先级。看它的实现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/同时满足第三个分支的集合和第五个分支的等值判断而if-elif是短路求值第三个分支先命中SLASH那一行永远不可达。这就是实验报告里“遇到/时无法判断是单行注释符还是除运算符号”这个 bug 的真正根因——不是 DFA 设计错了是字符分类函数的判定顺序把信息提前吃掉了。后面第 5 章会专门拆这个坑。4. DFA 最小化为什么等价状态必须合并确定化得到的 DFA 能跑但通常臃肿。子集构造会把 NFA 的状态集合原样搬过来很多集合其实行为完全一致只是包含的元素不同。最小化做的就是把这些“看起来不同、用起来一样”的状态压成一个。4.1 等价状态区分与不可区分两个状态p和q称为等价当且仅当对任意输入串w从p出发读完w后停在终态与从q出发读完w后停在终态这两件事同时成立或同时不成立。换句话说从外部观察者的角度看你根本分不出当前处在p还是q。这个定义直接给出了判定方法如果存在一个串能把p和q区分开一个到终态一个不到那它们就不等价。最小化的目标就是找到等价类的最大划分——每个类内部所有状态互相等价类与类之间至少有一个串能区分。有一个经典结论叫 Myhill-Nerode 定理它说一个正则语言对应的最小 DFA 在忽略状态命名的情况下是唯一的。这句话的工程含义很实在不管你用哪种最小化算法只要做对了最后得到的自动机大小和结构必然一致。所以不同的实现之间可以直接对比状态数多一个少一个都说明有 bug。4.2 划分法手推从终态分组到稳定划分最直观的算法是 Moore 划分法。步骤只有三步但手工推的时候容易乱得拿纸记。第一步把所有状态分成两组终态一组非终态一组。理由是终态和非终态天然可区分——空串ε就能区分它们终态读完空串还在终态非终态不在。第二步对每个组检查组内状态在每个输入符号下的后继落在哪个组。如果某两个状态读同一个符号后落到了不同的组就把它们拆开。这一步等价于“用长度为 1 的串做区分”。第三步重复第二步直到某一轮没有任何组被拆开。此时的划分就是最终的等价类划分每个类合并成一个状态。举个具体的小例子。假设某个 DFA 有状态{A, B, C, D, E}终态是{C, E}转移如下状态输入 0输入 1ABCBADCEADEBECD第一轮划分P0 {A, B, D}非终态P1 {C, E}终态。检查P0A 读 0 到 B在 P0B 读 0 到 A在 P0D 读 0 到 E在 P1。D 和 A、B 行为不同拆出。P0变成{A, B}和{D}。再检查{A, B}A 读 1 到 CP1B 读 1 到 D现在单独成组拆开。P0最终碎成{A}、{B}、{D}。检查P1 {C, E}C 读 0 到 EP1E 读 0 到 CP1一致C 读 1 到 AP0E 读 1 到 DP0一致。P1不拆。这一轮结束后划分是{A}, {B}, {D}, {C, E}。下一轮再扫一遍发现没有新的拆分发生算法终止。最终C和E合并状态数从 5 降到 4。手推的时候有个习惯很值得养成每轮都重新扫全部组不要只扫刚被拆过的。因为一个组被拆开后它原来的“邻居组”在后继归属上可能跟着变化漏扫一轮就会提前宣布收敛得到的是一个假的最小化结果。这个错误在实验报告里不会暴露因为报告只给了最终 DFA 的图没给中间过程但对拍测试时状态数对不上八成就是这里少扫了一轮。4.3 最小化真正省下的是什么很多人以为最小化是为了省内存其实对一门课设语言来说状态数从三十降到二十转移表也就省几百个字节实在算不上优化。它真正的价值在另外三个地方。第一是可读性。最小化之后一个状态往往精确对应一条词法规则的一个阶段比如“已读入标识符首字母”“已读入等待”“已读入/等待第二个/”。状态名可以直接写成人能看懂的东西调试时看一眼状态就知道程序走到哪了。没最小化的 DFA 里状态是 NFA 状态集合的哈希frozenset({3, 7, 12})这种名字对排查毫无帮助。第二是错误检测的清晰度。最小化会合并掉大量“死路”状态剩下的每个非终态基本都有明确语义。读到一个不属于任何合法转移的字符时当前状态本身就能告诉你“读者期望的是什么”报错信息可以写得非常具体而不是笼统的一句“非法字符”。第三是对拍验证的锚点。Myhill-Nerode 的唯一性意味着最小 DFA 是一个规范形式。两个不同的实现只要词法规则一致最小化后的状态数必须一样。这给自动化测试提供了一个硬指标改完代码跑一遍状态数变了就是引入 bug 了比人工 review 靠谱得多。5. 常见问题与排查斜杠歧义、最长匹配失效和错误定位这一章不从理论出发从实验报告里真实出现的调试记录出发。报告的自评部分提到“遇到了许多问题但通过一次次代码调试最终解决”但只写了“增加判断语句”这种结论没有留下路径。下面把典型翻车点按“现象 → 原因 → 解决”拆开这些坑在写任何词法分析器时都会反复遇到。5.1 斜杠歧义/永远进不了注释状态现象输入里有//This a test program这样的单行注释程序却把它当成一串运算符和标识符输出注释内容被当成代码分析This、a、test全部变成了 Identifier。原因问题不在 DFA 的转移表而在字符分类函数。get_char_category里/被写进了OPERATOR_DELIMITER的字符集合而elif char /: return SLASH排在它后面。if-elif短路求值/一旦被前面的分支截获SLASH这个类别就永远返回不了。于是 DFA 里那条从START出发、标号SLASH、指向COMMENT的边成了死边注释状态不可达。解决把/从OPERATOR_DELIMITER的集合里移除或者把char /的判断提到最前面。两种改法等价但前者更干净——字符集合应该表达“这一类字符共享同一种转移行为”而/恰恰是那个行为特殊的异类把它混进去本身就是分类错误。改完之后还要补一条COMMENT状态读到换行符必须退回START否则单行注释会把下一行也吃掉。5.2 最长匹配失效 被吞成一个 token现象源码里写x a b两个加号中间有空格输出的 token 序列里只有一个Operator: 空格被无视了。更极端的例子是ab直接被解析成a、、b。原因实验报告里的那版程序状态在转移时只做了“能转就转”没有区分“接受态”和“中间态”。OPERATOR状态的转移表里OPERATOR_DELIMITER的后继还是OPERATOR意思是“只要是运算符字符就一直吃”。于是连续的同类别字符会被无脑拼进同一个 token中间的空格因为WHITESPACE不在转移表里才勉强切断一旦没有空格就彻底粘连。这不是最长匹配这是“最长吞并”。解决真正的词法分析器必须给每个状态标记is_accept并且维护一个“最近一次接受位置”的指针。扫描时每读一个字符就尝试转移转移成功且新状态是接受态就把last_accept_pos更新到当前位置一旦转移失败不是简单地把当前缓冲整个吐出去而是回退到last_accept_pos吐出那一段作为 token然后从last_accept_pos重新开始扫描。这套机制叫“带回溯的最长匹配”也是flex这类工具生成代码时的标准做法。用代码表达核心循环长这样def scan_one_token(src, pos, dfa, accept_states): state, cur, last_accept START, pos, None while cur len(src): ch src[cur] nxt dfa.get(state, {}).get(get_char_category(ch)) if nxt is None: break # 转移失败准备回退 state nxt cur 1 if state in accept_states: # 只有接受态才值得记住 last_accept cur if last_accept is None: return None, pos # 一个字符都认不出报错 return src[pos:last_accept], last_acceptlast_accept这个变量是整个函数里最关键的没有它最长匹配就退化成贪心吞并。注意返回的是last_accept而不是cur这两个值在多字符运算符场景下会分叉比如读到后又读到一个字母cur已经越过了字母但last_accept还停在之后——正确做法是吐出让字母留给下一轮。实验报告声称“满足最长匹配原则”从代码看是靠字符类别恰好不同才蒙对的换成ab立刻原形毕露。5.3 运算符状态没有细分被当成合法运算符现象源码里手滑写了a b程序没有报错输出了一个Operator: 的 token。原因转移表里所有运算符共享一个OPERATOR状态这个状态读到任何运算符字符都继续停在OPERATOR。进来是OPERATOR进来还是OPERATOR两个字符拼成一个谁都不认识的 token而且因为它是接受态还不触发错误。解决把OPERATOR拆成细粒度状态。至少要区分“单个字符就能成词”的 - * / 和“必须再看一个字符才能定”的 、 、! 、 。前者读入即接受后者读完第一个字符处于“中间态”只有读到才进入接受态读到别的就回退到只有第一个字符的那个接受态。拆完之后会在读时发现的中间态没有对应转移回退吐出然后单独成词——虽然仍然是两个运算符但至少不会拼出一个不存在的符号。如果语言规范要求更严可以在语法分析阶段再报后面不该跟。5.4 错误定位只有 token没有行列号现象报告里能报出“第三行标识符123中包含非法字符”“第四行2a不符合标识符命名规则”但这是人工看源码数出来的行号程序本身输出的 token 流里没有任何位置信息。原因词法分析函数只维护了current_state和current_token两个变量没维护行号和列号。\n在字符分类里被归到WHITESPACE直接丢弃行号信息就此丢失。解决扫描循环里加两个计数器line和col每读一个字符col 1读到\n时line 1、col 0。每个 token 记录起始位置报错时输出(line, col)和出错字符。这一步成本极低但收益极高——后面语法分析报错时能直接指到源码的具体位置不需要再靠人工数。另外123这种串的正确处理方式是先按整数规则识别出123接受态停在3之后然后不属于任何合法转移触发回退吐出123紧接着从位置重新扫描连START都进不去这才报“非法字符位于第 3 行第 X 列”。报告里把它笼统归为“标识符123包含非法字符”其实是把两个 token 的错误合并成一个了定位精度会下降。提示还有一条容易被漏掉的边界——输入读完时缓冲区里可能还剩最后一个 token。循环正常退出后必须再 flush 一次否则最后一行没有换行符时最后一个单词会凭空消失。这个 bug 在测试用例恰好以换行结尾时完全不暴露上线后遇到真实文件才炸。6. 表驱动还是硬编码把 DFA 落成程序时的三个取舍理论走到这里已经完整了正则 → NFA → 子集构造 → 最小化 → 转移表。剩下的是工程决策而工程决策没有标准答案只有代价权衡。第一个取舍是表驱动还是硬编码。表驱动把转移关系塞进字典或二维数组主循环只有一个while加规则只改数据不改代码硬编码则是给每个状态写一个case分支性能略好、调试时能打断点但规则一多就是几百行嵌套if改一条规则要动三处。教学实验里表驱动明显更合适因为它的结构和 DFA 的数学定义一一对应出错时能直接对着转移表核对。第二个取舍是要不要真的做最小化。最小化的收益在状态数上是线性的但在可维护性上是非线性的——合并后的状态语义清晰报错信息能写得很具体。代价是要多写一个划分算法而且一旦词法规则变更最小化结果会整体重排之前基于状态编号写的测试用例全部失效。实际项目里常见的折中是构造阶段做最小化但对外暴露的接口只用 token 类型和位置不暴露状态编号这样规则变更不会击穿测试。第三个取舍是错误恢复策略。最激进的做法是遇到非法字符直接终止最简单也最不友好温和一点的是跳过该字符继续扫描但会掩盖后续的连锁错误工程上常用的是“panic mode”——报错后丢弃字符直到遇到一个明确的分界符分号、换行、右花括号再从那里恢复。词法层能做到的恢复很有限但至少可以保证一次编译报出多个错误而不是只报第一个。方案改规则成本运行性能调试友好度适用场景纯表驱动低改数据即可中多一次哈希查找中需打印状态规则多、频繁变更硬编码 switch高要改多处高直接跳转高可下断点规则稳定、追求极致性能表驱动 生成器最低改正则重生成中低生成代码不可读工业级编译器前端那份实验报告最后停在“程序能跑通示例”这一步没有做回退指针、没有做状态接受标记、也没有做位置跟踪。这不奇怪课程设计的验收标准本来就是“能识别出正确 token”而不是“能扛住真实源码”。但如果想把这份实验报告当成真正理解词法分析的入口我建议至少把 5.2 里那个last_accept的回退逻辑自己实现一遍再把 5.1 的字符分类顺序调对然后拿一段故意写错的代码去跑看它能不能同时报出多个错误位置。这三步做完DFA 就不再是纸上的圆圈箭头而是一台你能拆开、能修、能预测行为的机器。从那以后我每次写任何形式的字符串解析都会先把状态和接受态画出来再动手这个习惯救过我很多次。希望帮到你。本文还有配套的精品资源点击获取
简介西南科技大学编译原理实验报告1聚焦词法分析程序的设计与实现面向正在学习编译原理、需要完成实验一或梳理编译器前端流程的高校学生。报告按实验目的、设计、过程与程序实现展开完整呈现正则表达式描述词法规则、构造NFA、合并并确定化为DFA、再化简为最小DFA的推导链条并给出TEST语言中标识符、保留字、无符号整数、分界符、运算符和注释符的分类及单词输出方案。文中还列出基于Python的DFA状态转移表与词法分析函数框架提示错误处理、缓冲区管理和回溯机制等可扩展细节便于对照复现和查漏补缺。资源包共1个doc文件约444KB篇幅紧凑适合作为实验报告参考与复习提纲目前已有479人学习具有一定参考热度。1. 词法分析为什么编译器前端第一件事是把字符流切成 Token很多人第一次翻开词法分析这一章会觉得它像个文字游戏拿正则表达式描述单词画几个圆圈箭头最后写个循环读字符能跑就行。真正反直觉的地方在于——词法分析器的正确性跟你会不会写 if-else 几乎无关它取决于你能不能把一组正则表达式“编译”成一张无回溯的有限状态转移表。某高校那份《编译系统综合设计》实验报告从写正则、造 NFA、确定化为 DFA、化简到最小 DFA再用 Python 落实成一个状态机走的正是这条完整的编译链。搞懂它你就明白为什么不会被拆成和为什么//和除号必须靠状态而不是靠字符判断也就知道自己手写的分词函数为什么总在边界上翻车。这份实验报告的价值不在“实验报告”四个字而在它把每一步都留了痕迹。2. 正则到 NFA为什么先造一台“会猜”的自动机正则表达式本身就是给人类读的机器读不了(a|b|...|z)*这种东西。要让机器执行得先把“模式”翻译成“状态”。这条翻译链的第一站是 NFA而 NFA 之所以叫“非确定”是因为它在任何一个时刻可以同时停在好几个状态上——它靠 ε 边“猜”。工程师的第一反应通常是直接跑 NFA 不行吗不行因为猜就要回溯回溯就要爆炸。2.1 把词法规则翻译成正则表达式时边界在哪实验报告列出了 TEST 语言的六类规则看起来很简单但每一条都埋着坑。标识符写成(a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*意思是首字符必须是字母后续可以是字母或数字。保留字写成if|else|for|while|do|int|write|read。这里立刻出现第一个矛盾if这个串同样能被标识符的正则匹配上。两条规则在语言层面是重叠的。工程上通行的做法不是把保留字从标识符里“减掉”而是反过来——先全部按标识符识别再拿这个串去查一张关键字表。查中了就改写 token 类型查不中就保持 Identifier。这样 DFA 只需要一套标识符规则关键字表是一张哈希表代价接近零。实验报告里单词分类把int同时列进了“关键字”和“保留字”说明作者已经隐约意识到这个重叠只是没讲透。第二个坑在无符号整数((1|...|9)(0|1|...|9)*)|0。为什么非要把0单独拎出来做一支因为要禁止前导零。如果不拆012345会被整个吞成一个整数而按严格规则它应该是0和12345两个 token或者直接被判为非法。报告里的源程序恰好有abc 012345;这一句实验者把它当成合法单词处理了——这是一处真正的语义分歧点取决于语言规范怎么定义而不取决于代码能不能跑。第三个坑更隐蔽。运算符写成|-|*|/||||||!|这个顺序是错的。如果用一个从左到右、匹配到第一个成功分支就停的正则引擎去跑读到时第一个分支不匹配、匹配直接成功返回这一支永远走不到。正确写法必须是长串在前||!||||||...。这是“最长匹配”在正则层面的第一次现身也解释了为什么后面 DFA 必须带接受态和回退。第四个坑是分界符那行(|)|;|{|}。(和)在正则里是分组符号直接这么写会被当成语法结构而不是字面量必须转义成\(\)或者干脆在实现里放弃正则、用字符集合判断。报告里的注释符写成了/|/从上下文看本意是//排版把两个斜杠弄丢了——这类文本失真在抄实验报告时极常见但一旦照抄进代码就是灾难。提示写词法规则时凡是“一个串是另一个串前缀”的情况与、与、/与//正则的书写顺序和后续状态机的接受态设计必须一起考虑不能分开拍脑袋。2.2 Thompson 构造一个正则算子对应一小块子图把正则变成 NFA 有一套机械的、可以照着敲的算法叫 Thompson 构造。它的核心思想是归纳先给最小单元画图再给每种组合算子规定“怎么把已有的图拼起来”。一共就三条拼接规则加两条变体。基本单元是单个字符a新建两个状态i和f画一条从i到f、标号a的边。连接rs把r的终态和s的初态用一条 ε 边接起来整体初态取r的初态终态取s的终态。图不用改只加一条空边。选择r|s新建初态i和终态f从i各拉一条 ε 边到r的初态和s的初态r的终态、s的终态各拉一条 ε 边到f。这样从i出发两条路都能走。闭包r*新建初态i和终态fi用 ε 连到r的初态同时也用 ε 直连f表示匹配零次r的终态用 ε 连回r的初态表示再来一次同时用 ε 连到f表示收工。正闭包r只是去掉“i直连f”那一条边。拿无符号整数((1|...|9)(0|...|9)*)|0走一遍把字母表按区间简写成[1-9]和[0-9]得到的转移关系大致是状态输入后继状态N0εN1, N7N1[1-9]N2N2εN3, N6N3εN4, N6N4[0-9]N5N5εN3, N6N70N8N8εN6N0 是初态N6 是唯一的终态。这张表就是“正则被翻译成状态”的第一形态。注意 N3 和 N5 之间那条回边——那就是*的“再来一次”。整个构造过程不需要任何创造性纯粹是照着算子套模板这正是它适合被写成程序的原因。2.3 ε-闭包NFA 的“猜”到底是什么NFA 的“非确定”听上去玄落到实现上其实是一个集合运算。给定一个状态集合T它的 ε-闭包ε-closure(T)定义为从T中任意状态出发只走 ε 边能到达的所有状态的集合包含T本身。这个操作是幂等的再做一次不会变大。有了闭包NFA 的“同时处在多个状态”就有了严格定义当前配置不是“一个状态”而是“一个状态集合”。读入字符a时先对集合里每个状态找所有标号a的出边把后继收集起来再对这个后继集合求一次 ε-闭包。整个过程是一次集合到集合的映射。问题来了这个映射是多对一的不同输入串可能落到同一个集合但同一个集合读同一个字符可能分叉出多条路。如果用程序直接模拟就得维护一个“待探索路径栈”一旦某条路走死就要回退到上一个分叉点换一条。最坏情况下路径数随输入长度指数增长。词法分析器要处理的是几十万行源码这种代价不可接受。所以 NFA 在工程上从来不是“运行”的目标它只是一个中间表示。真正的运行形态必须是确定的一个状态、一个字符、唯一后继。把 NFA 变成这个形态的过程叫确定化也就是下一章的子集构造。3. 子集构造NFA 确定化到底在做什么数学操作一句话概括子集构造把“NFA 的状态集合”整体打包当成 DFA 的一个状态。听起来像变魔术其实是把 NFA 运行时那个“集合”直接固化成了状态机的节点于是运行期不再需要维护集合也不需要回溯。3.1 一个 DFA 状态 一个 NFA 状态集合算法骨架是这样的从ε-closure({s0})出发把它记作 DFA 的初态D0。对每个尚未处理的 DFA 状态D和每个输入字符a计算U ε-closure(move(D, a))其中move(D, a)是D里所有状态沿标号a的出边到达的后继集合。如果U非空且没出现过就新建一个 DFA 状态最后把D --a-- U记进转移表。反复直到没有新状态产生。关键在于“非空”这个判断。move(D, a)为空意味着当前集合里没有任何状态能吃下a这条边在 DFA 里就不画——这正是词法分析器“读到一个不该读的字符就停下来”的来源也是错误检测的天然入口。用伪代码写出来大概是这样def subset_construction(nfa_start, nfa_trans, alphabet): # nfa_trans: dict[state][char] - set[state]ε 边用 作键 start frozenset(epsilon_closure({nfa_start}, nfa_trans)) dfa_states [start] dfa_trans {} queue [start] while queue: cur queue.pop(0) dfa_trans[cur] {} for ch in alphabet: # 先沿 ch 走一步再求 ε 闭包得到一个 NFA 状态集合 moved set() for s in cur: moved | nfa_trans.get(s, {}).get(ch, set()) if not moved: continue # 空集不建边留作死路 nxt frozenset(epsilon_closure(moved, nfa_trans)) dfa_trans[cur][ch] nxt if nxt not in dfa_states: dfa_states.append(nxt) queue.append(nxt) return dfa_states, dfa_trans def epsilon_closure(states, nfa_trans): # 反复扩展 ε 边直到不再增长典型的定点迭代 stack, closure list(states), set(states) while stack: s stack.pop() for t in nfa_trans.get(s, {}).get(, set()): if t not in closure: closure.add(t) stack.append(t) return closure这段代码里frozenset不是随手写的。DFA 状态需要作为字典的键可哈希是硬性要求而普通set不可哈希一旦用列表存集合再比较每次查重都是 O(n) 的线性扫描状态一多就直接拖垮。frozenset把“集合相等”变成哈希比较整个构造从平方级降到接近线性。这是实现层面一个很容易被忽略但影响巨大的选择。另一个细节是epsilon_closure用了显式栈而不是递归。NFA 的 ε 链可能很长尤其是a*嵌套b*这种递归深度一旦上去就是栈溢出编译器前端在这种地方崩掉非常难看。3.2 合并 NFA为什么必须新建一个唯一初态词法分析器要同时识别标识符、整数、运算符、注释等好几类规则。自然的做法是给每条规则各造一个 NFA然后合并成一个大的。合并方式不是把初态直接连起来而是新建一个全局初态S用 ε 边分别指向每个子 NFA 的初态。这一步不能省。如果图省事让标识符的初态兼任全局初态那么从标识符初态出发就只能走标识符那条路其他规则永远进不去。反过来如果让所有子 NFA 的初态直接合并成一个去掉 ε 边共享节点那状态转移的语义就被破坏了——本来“读字母”应该只进标识符分支合并后可能同时进整数分支虽然子集构造能把这种混乱重新整理成合法 DFA但初态的接受性质会变得难以判断。新建S之后S本身的 ε-闭包天然包含了所有子规则的入口状态于是 DFA 的初态就自动是“所有可能规则的起点的集合”。这一步的收益在确定化之后才显现从D0读一个字母move会同时走到标识符分支和保留字分支的对应位置闭包一求得到的集合同时携带了“可能是标识符”和“可能是关键字”两种身份。等到整个串读完再看这个终态集合里有没有包含某条规则的终态就知道该归到哪一类。注意合并后的终态通常不止一个。一个 DFA 状态可能同时是“标识符的终态”和“某个关键字的终态”这时候必须靠规则优先级来裁决——一般是关键字优先于标识符长规则优先于短规则。优先级不写在状态机里写在“终态到 token 类型”的映射表里。3.3 字符等价类让转移表从 70 列缩到 6 列理论上字母表有多大转移表就有多少列。TEST 语言涉及大小写字母 52 个、数字 10 个、各种符号十几个加起来七十多列。但实际构造出来的 DFA 里大量列的转移是完全一样的——所有小写字母在任何状态下的后继都相同所有数字也相同。于是有一步必做的优化把行为一致的字符归成一个等价类。实验报告的 Python 实现里get_char_category函数干的就是这件事它把字符映射到ALPHABET、DIGIT、OPERATOR_DELIMITER、WHITESPACE、SLASH、OTHER六个类别。转移表的列数从七十多降到六状态数不变内存直接降一个数量级。这个函数看着简单却是整个程序里最容易出错的地方原因在于判断顺序即优先级。看它的实现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/同时满足第三个分支的集合和第五个分支的等值判断而if-elif是短路求值第三个分支先命中SLASH那一行永远不可达。这就是实验报告里“遇到/时无法判断是单行注释符还是除运算符号”这个 bug 的真正根因——不是 DFA 设计错了是字符分类函数的判定顺序把信息提前吃掉了。后面第 5 章会专门拆这个坑。4. DFA 最小化为什么等价状态必须合并确定化得到的 DFA 能跑但通常臃肿。子集构造会把 NFA 的状态集合原样搬过来很多集合其实行为完全一致只是包含的元素不同。最小化做的就是把这些“看起来不同、用起来一样”的状态压成一个。4.1 等价状态区分与不可区分两个状态p和q称为等价当且仅当对任意输入串w从p出发读完w后停在终态与从q出发读完w后停在终态这两件事同时成立或同时不成立。换句话说从外部观察者的角度看你根本分不出当前处在p还是q。这个定义直接给出了判定方法如果存在一个串能把p和q区分开一个到终态一个不到那它们就不等价。最小化的目标就是找到等价类的最大划分——每个类内部所有状态互相等价类与类之间至少有一个串能区分。有一个经典结论叫 Myhill-Nerode 定理它说一个正则语言对应的最小 DFA 在忽略状态命名的情况下是唯一的。这句话的工程含义很实在不管你用哪种最小化算法只要做对了最后得到的自动机大小和结构必然一致。所以不同的实现之间可以直接对比状态数多一个少一个都说明有 bug。4.2 划分法手推从终态分组到稳定划分最直观的算法是 Moore 划分法。步骤只有三步但手工推的时候容易乱得拿纸记。第一步把所有状态分成两组终态一组非终态一组。理由是终态和非终态天然可区分——空串ε就能区分它们终态读完空串还在终态非终态不在。第二步对每个组检查组内状态在每个输入符号下的后继落在哪个组。如果某两个状态读同一个符号后落到了不同的组就把它们拆开。这一步等价于“用长度为 1 的串做区分”。第三步重复第二步直到某一轮没有任何组被拆开。此时的划分就是最终的等价类划分每个类合并成一个状态。举个具体的小例子。假设某个 DFA 有状态{A, B, C, D, E}终态是{C, E}转移如下状态输入 0输入 1ABCBADCEADEBECD第一轮划分P0 {A, B, D}非终态P1 {C, E}终态。检查P0A 读 0 到 B在 P0B 读 0 到 A在 P0D 读 0 到 E在 P1。D 和 A、B 行为不同拆出。P0变成{A, B}和{D}。再检查{A, B}A 读 1 到 CP1B 读 1 到 D现在单独成组拆开。P0最终碎成{A}、{B}、{D}。检查P1 {C, E}C 读 0 到 EP1E 读 0 到 CP1一致C 读 1 到 AP0E 读 1 到 DP0一致。P1不拆。这一轮结束后划分是{A}, {B}, {D}, {C, E}。下一轮再扫一遍发现没有新的拆分发生算法终止。最终C和E合并状态数从 5 降到 4。手推的时候有个习惯很值得养成每轮都重新扫全部组不要只扫刚被拆过的。因为一个组被拆开后它原来的“邻居组”在后继归属上可能跟着变化漏扫一轮就会提前宣布收敛得到的是一个假的最小化结果。这个错误在实验报告里不会暴露因为报告只给了最终 DFA 的图没给中间过程但对拍测试时状态数对不上八成就是这里少扫了一轮。4.3 最小化真正省下的是什么很多人以为最小化是为了省内存其实对一门课设语言来说状态数从三十降到二十转移表也就省几百个字节实在算不上优化。它真正的价值在另外三个地方。第一是可读性。最小化之后一个状态往往精确对应一条词法规则的一个阶段比如“已读入标识符首字母”“已读入等待”“已读入/等待第二个/”。状态名可以直接写成人能看懂的东西调试时看一眼状态就知道程序走到哪了。没最小化的 DFA 里状态是 NFA 状态集合的哈希frozenset({3, 7, 12})这种名字对排查毫无帮助。第二是错误检测的清晰度。最小化会合并掉大量“死路”状态剩下的每个非终态基本都有明确语义。读到一个不属于任何合法转移的字符时当前状态本身就能告诉你“读者期望的是什么”报错信息可以写得非常具体而不是笼统的一句“非法字符”。第三是对拍验证的锚点。Myhill-Nerode 的唯一性意味着最小 DFA 是一个规范形式。两个不同的实现只要词法规则一致最小化后的状态数必须一样。这给自动化测试提供了一个硬指标改完代码跑一遍状态数变了就是引入 bug 了比人工 review 靠谱得多。5. 常见问题与排查斜杠歧义、最长匹配失效和错误定位这一章不从理论出发从实验报告里真实出现的调试记录出发。报告的自评部分提到“遇到了许多问题但通过一次次代码调试最终解决”但只写了“增加判断语句”这种结论没有留下路径。下面把典型翻车点按“现象 → 原因 → 解决”拆开这些坑在写任何词法分析器时都会反复遇到。5.1 斜杠歧义/永远进不了注释状态现象输入里有//This a test program这样的单行注释程序却把它当成一串运算符和标识符输出注释内容被当成代码分析This、a、test全部变成了 Identifier。原因问题不在 DFA 的转移表而在字符分类函数。get_char_category里/被写进了OPERATOR_DELIMITER的字符集合而elif char /: return SLASH排在它后面。if-elif短路求值/一旦被前面的分支截获SLASH这个类别就永远返回不了。于是 DFA 里那条从START出发、标号SLASH、指向COMMENT的边成了死边注释状态不可达。解决把/从OPERATOR_DELIMITER的集合里移除或者把char /的判断提到最前面。两种改法等价但前者更干净——字符集合应该表达“这一类字符共享同一种转移行为”而/恰恰是那个行为特殊的异类把它混进去本身就是分类错误。改完之后还要补一条COMMENT状态读到换行符必须退回START否则单行注释会把下一行也吃掉。5.2 最长匹配失效 被吞成一个 token现象源码里写x a b两个加号中间有空格输出的 token 序列里只有一个Operator: 空格被无视了。更极端的例子是ab直接被解析成a、、b。原因实验报告里的那版程序状态在转移时只做了“能转就转”没有区分“接受态”和“中间态”。OPERATOR状态的转移表里OPERATOR_DELIMITER的后继还是OPERATOR意思是“只要是运算符字符就一直吃”。于是连续的同类别字符会被无脑拼进同一个 token中间的空格因为WHITESPACE不在转移表里才勉强切断一旦没有空格就彻底粘连。这不是最长匹配这是“最长吞并”。解决真正的词法分析器必须给每个状态标记is_accept并且维护一个“最近一次接受位置”的指针。扫描时每读一个字符就尝试转移转移成功且新状态是接受态就把last_accept_pos更新到当前位置一旦转移失败不是简单地把当前缓冲整个吐出去而是回退到last_accept_pos吐出那一段作为 token然后从last_accept_pos重新开始扫描。这套机制叫“带回溯的最长匹配”也是flex这类工具生成代码时的标准做法。用代码表达核心循环长这样def scan_one_token(src, pos, dfa, accept_states): state, cur, last_accept START, pos, None while cur len(src): ch src[cur] nxt dfa.get(state, {}).get(get_char_category(ch)) if nxt is None: break # 转移失败准备回退 state nxt cur 1 if state in accept_states: # 只有接受态才值得记住 last_accept cur if last_accept is None: return None, pos # 一个字符都认不出报错 return src[pos:last_accept], last_acceptlast_accept这个变量是整个函数里最关键的没有它最长匹配就退化成贪心吞并。注意返回的是last_accept而不是cur这两个值在多字符运算符场景下会分叉比如读到后又读到一个字母cur已经越过了字母但last_accept还停在之后——正确做法是吐出让字母留给下一轮。实验报告声称“满足最长匹配原则”从代码看是靠字符类别恰好不同才蒙对的换成ab立刻原形毕露。5.3 运算符状态没有细分被当成合法运算符现象源码里手滑写了a b程序没有报错输出了一个Operator: 的 token。原因转移表里所有运算符共享一个OPERATOR状态这个状态读到任何运算符字符都继续停在OPERATOR。进来是OPERATOR进来还是OPERATOR两个字符拼成一个谁都不认识的 token而且因为它是接受态还不触发错误。解决把OPERATOR拆成细粒度状态。至少要区分“单个字符就能成词”的 - * / 和“必须再看一个字符才能定”的 、 、! 、 。前者读入即接受后者读完第一个字符处于“中间态”只有读到才进入接受态读到别的就回退到只有第一个字符的那个接受态。拆完之后会在读时发现的中间态没有对应转移回退吐出然后单独成词——虽然仍然是两个运算符但至少不会拼出一个不存在的符号。如果语言规范要求更严可以在语法分析阶段再报后面不该跟。5.4 错误定位只有 token没有行列号现象报告里能报出“第三行标识符123中包含非法字符”“第四行2a不符合标识符命名规则”但这是人工看源码数出来的行号程序本身输出的 token 流里没有任何位置信息。原因词法分析函数只维护了current_state和current_token两个变量没维护行号和列号。\n在字符分类里被归到WHITESPACE直接丢弃行号信息就此丢失。解决扫描循环里加两个计数器line和col每读一个字符col 1读到\n时line 1、col 0。每个 token 记录起始位置报错时输出(line, col)和出错字符。这一步成本极低但收益极高——后面语法分析报错时能直接指到源码的具体位置不需要再靠人工数。另外123这种串的正确处理方式是先按整数规则识别出123接受态停在3之后然后不属于任何合法转移触发回退吐出123紧接着从位置重新扫描连START都进不去这才报“非法字符位于第 3 行第 X 列”。报告里把它笼统归为“标识符123包含非法字符”其实是把两个 token 的错误合并成一个了定位精度会下降。提示还有一条容易被漏掉的边界——输入读完时缓冲区里可能还剩最后一个 token。循环正常退出后必须再 flush 一次否则最后一行没有换行符时最后一个单词会凭空消失。这个 bug 在测试用例恰好以换行结尾时完全不暴露上线后遇到真实文件才炸。6. 表驱动还是硬编码把 DFA 落成程序时的三个取舍理论走到这里已经完整了正则 → NFA → 子集构造 → 最小化 → 转移表。剩下的是工程决策而工程决策没有标准答案只有代价权衡。第一个取舍是表驱动还是硬编码。表驱动把转移关系塞进字典或二维数组主循环只有一个while加规则只改数据不改代码硬编码则是给每个状态写一个case分支性能略好、调试时能打断点但规则一多就是几百行嵌套if改一条规则要动三处。教学实验里表驱动明显更合适因为它的结构和 DFA 的数学定义一一对应出错时能直接对着转移表核对。第二个取舍是要不要真的做最小化。最小化的收益在状态数上是线性的但在可维护性上是非线性的——合并后的状态语义清晰报错信息能写得很具体。代价是要多写一个划分算法而且一旦词法规则变更最小化结果会整体重排之前基于状态编号写的测试用例全部失效。实际项目里常见的折中是构造阶段做最小化但对外暴露的接口只用 token 类型和位置不暴露状态编号这样规则变更不会击穿测试。第三个取舍是错误恢复策略。最激进的做法是遇到非法字符直接终止最简单也最不友好温和一点的是跳过该字符继续扫描但会掩盖后续的连锁错误工程上常用的是“panic mode”——报错后丢弃字符直到遇到一个明确的分界符分号、换行、右花括号再从那里恢复。词法层能做到的恢复很有限但至少可以保证一次编译报出多个错误而不是只报第一个。方案改规则成本运行性能调试友好度适用场景纯表驱动低改数据即可中多一次哈希查找中需打印状态规则多、频繁变更硬编码 switch高要改多处高直接跳转高可下断点规则稳定、追求极致性能表驱动 生成器最低改正则重生成中低生成代码不可读工业级编译器前端那份实验报告最后停在“程序能跑通示例”这一步没有做回退指针、没有做状态接受标记、也没有做位置跟踪。这不奇怪课程设计的验收标准本来就是“能识别出正确 token”而不是“能扛住真实源码”。但如果想把这份实验报告当成真正理解词法分析的入口我建议至少把 5.2 里那个last_accept的回退逻辑自己实现一遍再把 5.1 的字符分类顺序调对然后拿一段故意写错的代码去跑看它能不能同时报出多个错误位置。这三步做完DFA 就不再是纸上的圆圈箭头而是一台你能拆开、能修、能预测行为的机器。从那以后我每次写任何形式的字符串解析都会先把状态和接受态画出来再动手这个习惯救过我很多次。希望帮到你。本文还有配套的精品资源点击获取
