简介：这份西南科技大学编译原理实验报告一，围绕「设计词法分析程序」展开，面向正在学习编译原理、需要完成课程实验的高校学生与自学者，重点解决从正则表达式到词法分析程序落地的完整链路问题。报告按实验目的、实验设计、实验过程、程序实现四部分组织：先用正则表达式描述 TEST 语言的标识符、保留字、无符号整数、分界符、运算符与注释符规则，再依次构造 NFA，合并、确定化并化简为最小 DFA；随后给出单词分类与输出方案，并以 Python 状态机（含字符分类函数与 DFA 状态转移表）演示扫描流程，同时点出错误处理、缓冲区管理与回溯等后续要点。整包为 1 个 doc 文档，约 444KB，保留了实验名称、指导教师、日期等完整实验报告格式，可直接参照撰写或对照自查。已有 479 人学习下载，适合作为课程实验的参考范本与期末复习材料。

1. 一段二十行样例里的三处硬伤

导师把一段不到二十行的 TEST 语言源程序放在桌上，里面塞了int abc123$;、int 2a;、abc = abc / i;三行，要求输出完整 token 序列，同时指出每个问题出现在哪一行、哪一列。多数人第一次做编译原理的词法分析实验报告，就卡在这三行：$没人管，2a被拆成2和a两个合法单词糊弄过去，/到底是除号还是单行注释的开头全凭运气。这套方案要把正则表达式、NFA、确定化与最小化、DFA 状态表、表驱动扫描器、错误队列串成一条能跑的链路，最终产出一份带lex.txt和错误清单的实验交付物。适合正在做编译原理实验一「设计词法分析程序」的同学，也适合需要一份可改的扫描器骨架的从业者。

2. 词法规则建模：把七类单词写成能对着画图的正则

2.1 先把单词表钉死，正则才有落笔的地方

上手就写正则，是这类实验里最常见的时间浪费。七类单词里只要有一类的边界没定清楚，后面 NFA 合并时就会返工。我一般的顺序是：先列一张单词分类表，把「输出标记」这一列一并定下来，因为扫描器最终吐给语法分析器的就是这一列，不是中文名。

表里刻意没把「保留字」单列成第七类。原始素材的关键字列表里有int，保留字列表里又是int，两套机制同时存在，最后输出时必然打架：同一个int既可能被标成KEYWORD，也可能被标成保留字，测试用例一多就露馅。工程上的做法只有一种——关键字表唯一，用字典查，查中即改标，这件事放到 2.3 讲。

无符号整数这条正则也要盯一眼。写成(0|…|9)+当然更省事，但abc = 012345;这行会被整段吃成合法整数，而实验样例里它是故意埋的一个点。把首位限制成1-9、单独给0开一条分支，012345就会在扫描到0之后把12345留成下一个 token，错误处理阶段才有机会报出来。这种「正则写法直接决定程序能不能报错」的细节，实验报告里最好明写一句，答辩时是加分项。

2.2 正则到 NFA：Thompjson 构造只需要三种拼装

把正则变成 NFA，不用背一整套形式化定义，只要会三种基本拼装，剩下的都是嵌套。第一种是连接：ab就是两个子图首尾接上，中间加一条 ε 边。第二种是选择：a|b新建一个入口状态，用两条 ε 边分别跳到 a 和 b 的子图，再各用一条 ε 边汇到一个新出口。第三种是闭包：a*在子图入口和出口之间加一条回边，同时加一条从入口直通出口的 ε 边，保证零次匹配也能过。

按这个套路，标识符的 NFA 大致长这样：入口 ε 分叉出一条到「字母」边的路径，字母边指向一个中间状态，这个中间状态既接受字母也接受数字并自环，同时 ε 连到出口。读起来有点绕，但只要在纸上画过一次，就会发现它跟正则表达式是逐字符对应的。

无符号整数要单独说一句，因为它是本实验里唯一带优先级的规则。0单独一条边直达接受状态；1-9走另一条边，再自环吃0-9。两条分支的接受状态不同，但都标成NUM，这正是后面最小化时要合并的那类状态。

运算符的 NFA 是整个图里最容易被画糊的部分。>=、<=、==、!=这四个双字符运算符，必须在读完第二个字符之后才允许进入接受状态。也就是说>后面接一个中间状态，这个中间状态本身可以作为「大于号」的接受状态，同时有一条=边通向另一个「大于等于」的接受状态。这个中间状态是后面的关键：扫描器读到>时先记下这里可以结束，再看下一个字符，是=就继续走，不是就退回来。最长匹配的全部原理就藏在这个中间状态里。

还有一条容易被忽略：!本身不是 TEST 语言的合法运算符，只有!=是。所以!后面那个中间状态不能标成接受状态。如果偷懒直接把所有单字符都设成接受，遇到孤零零一个!时会静默通过，测试用例里的i != n写错成i ! n就查不出来了。

2.3 关键字不做进 DFA，识别完再查表

为什么不让 DFA 直接识别while？因为把八个关键字和标识符一起做进状态图，状态数会从十几个膨胀到几十个，图没法画，表也没法看，而且每加一个关键字就要重画整张图。教科书的通行做法是：DFA 只认标识符，扫描器拿到词素之后查一次哈希表，命中就改类型。

# 关键字表只有一份，不放第二条「保留字」通道 KEYWORDS = {'int', 'if', 'else', 'for', 'while', 'do', 'read', 'write'} def classify(lexeme, base_type): """base_type 来自 DFA 的接受状态，这里只做一次回填。""" if base_type == 'ID' and lexeme in KEYWORDS: return 'KEYWORD' return base_type

这段逻辑的价值不在于代码短，而在于它把「词法形态」和「语义归类」拆开了。DFA 负责判断这串字符长得像不像一个标识符，字典负责判断它在语言里是不是有特殊身份。好处很直接：加关键字只改字典，不动状态图；答辩时被问到「新增一个关键字要改几处」，答案是改一行，这个问题基本就稳了。

需要提醒的是回填的时机。必须等一个标识符完整识别完、确认它结束于非字母数字字符之后，才能查表。中途查表会把intx误判成关键字int加x，这是初学者最常犯的一个错。查表发生在「一个 token 已经确定边界」之后，这个顺序不能反。

2.4 注释符不是普通单词，它得单独定义处理规则

//这条规则有个尴尬之处：按实验要求它属于七类单词之一，要写正则、要进 NFA；但按编译器的实际行为，注释在词法阶段就被丢弃，根本不进 token 流。这两件事并不冲突，处理方式是把注释也纳入状态机，但主循环拿到COMMENT类型的 token 后直接扔掉，只更新行号和列号。

正则写成//[^\n]*而不是//.*，原因很实在：.在很多实现里默认不匹配换行符，但一旦有人开了 dotall 模式，.*就会把整个文件吞成一条注释。写[^\n]*是显式声明「注释到行尾为止」，这个习惯我保留了很长时间，因为它不依赖任何引擎的默认开关。

另一处细节是注释内部允许出现任意字符，包括$、@这些在外面属于非法字符的东西。样例程序第一行是{ //This a test program.，如果状态机在注释里还老老实实做字符集校验，$之类的东西就会被误报成词法错误。注释状态应该对所有非换行字符一律放行，这是一条硬规则。

3. 从 NFA 到最小 DFA：状态表才是能写进代码的东西

3.1 合并与子集构造：把 ε 闭包算清楚就行

把六张 NFA 合并成一张，最省事的办法是加一个新的总入口状态，用 ε 边分别连到六张子图的入口。合并之后它仍然是个 NFA：一个状态遇到一个字符可能跳到多个次态，还带一堆 ε 边。

确定化（子集构造）要做的就是把「状态集合」当成新状态。流程是三步循环：从初始状态的 ε 闭包开始，对每个输入字符算一次 move 得到新集合，再对新集合求 ε 闭包，如果这个集合没出现过就给它编号入队，直到队列空。

def epsilon_closure(states, eps_edges): """eps_edges: state -> set(states)，求传递闭包""" stack = list(states) closure = set(states) while stack: s = stack.pop() for t in eps_edges.get(s, ()): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construct(start, trans, eps_edges, alphabet): """trans: (state, char) -> set(states)""" start_set = epsilon_closure({start}, eps_edges) dfa = {start_set: 0} # 子集 -> DFA 状态编号 order = [start_set] table = {} i = 0 while i < len(order): cur = order[i] for ch in alphabet: moved = set() for s in cur: moved |= trans.get((s, ch), set()) if not moved: continue nxt = epsilon_closure(moved, eps_edges) if nxt not in dfa: dfa[nxt] = len(order) order.append(nxt) table[(i, ch)] = dfa[nxt] i += 1 return order, table

这三个函数的关系是：epsilon_closure是工具，subset_construct是主循环，外层驱动按字母表逐字符推进。字母表不需要真的列 52 个字母，用「字母类 / 数字类 / 具体符号」做等价类就够了，表能小一个数量级。这段代码写进实验报告时，注释里最好标明「此处对应实验步骤三的确定化」。

确定化之后要标接受状态。一个子集只要含有任意一个原子图的接受状态，它就是接受状态，接受类型取那个原子图对应的类型。如果一个子集同时含两种接受状态，说明正则之间有重叠，这是设计错误，必须回去改正则，而不是在代码里随便挑一个。

3.2 最小化：划分时接受类型必须分桶

最小化的标准做法是划分法：初始把状态分成「非接受」和「接受」两组，然后反复检查同组内两个状态遇到同一字符是否跳到同一组，不同就拆开，直到不再变化。

这里有一个必须强调的细节。初始划分不能只分「接受 / 非接受」两桶，必须按接受类型分桶，也就是ID一桶、NUM一桶、OPERATOR一桶、DELIMITER一桶，其余为非接受桶。如果只按接受与否分，>的接受状态和=的接受状态会被判成等价合并掉，最后>输出成=，样例程序里i <= n那一行立刻崩。这个坑我在第一次做的时候就踩过，症状是运算符全变成同一个符号，查了半天状态图，问题其实在划分的初始条件。

最小化的收益也要说清楚，不要为了流程完整而做。合并前的 DFA 可能有三十来个状态，合并后通常能压到二十个以内，对程序性能影响不大，对实验报告的意义在于「证明你理解了等价状态」。答辩被问到「最小化省了多少状态」，能报出具体数字和合并掉的是哪几个状态，比背定义有用得多。

3.3 状态表落地：用字符直接做键的字典

最小化后的 DFA 最终要变成代码里的数据结构。我倾向用嵌套字典，外层是状态名，内层是输入，值是次态。字母和数字用两个伪键表示，其余字符直接用它本身做键，这样表可以照着状态图一行一行抄下来，不容易抄错。

# 最小化后的 DFA 转移表（节选，覆盖标识符、整数、运算符、分界符、注释） DFA = { 'S': {'ALPHA': 'ID', 'DIGIT': 'NUM', '/': 'SLASH', '+': 'OP', '-': 'OP', '*': 'OP', '=': 'EQ', '<': 'LT', '>': 'GT', '!': 'BANG', '(': 'LP', ')': 'RP', '{': 'LB', '}': 'RB', ';': 'SEMI', ':': 'COLON'}, 'ID': {'ALPHA': 'ID', 'DIGIT': 'ID'}, 'NUM': {'DIGIT': 'NUM'}, 'SLASH': {'/': 'COMMENT'}, # 只有第二个 / 才进注释 'EQ': {'=': 'OP2'}, # == 'LT': {'=': 'OP2'}, # <= 'GT': {'=': 'OP2'}, # >= 'BANG': {'=': 'OP2'}, # != ，单独的 ! 不是合法 token } # 接受状态 -> 输出类型 ACCEPT = { 'ID': 'ID', 'NUM': 'NUM', 'OP': 'OPERATOR', 'SLASH': 'OPERATOR', 'EQ': 'OPERATOR', 'LT': 'OPERATOR', 'GT': 'OPERATOR', 'OP2': 'OPERATOR', 'LP': 'DELIMITER', 'RP': 'DELIMITER', 'LB': 'DELIMITER', 'RB': 'DELIMITER', 'SEMI': 'DELIMITER', 'COLON': 'DELIMITER', 'COMMENT': 'COMMENT', }

表里有两个地方值得单独解释。第一，SLASH同时是接受状态（除号）和有出边的状态（注释开头），这种「可接受但未终结」的状态正是最长匹配的载体。第二，BANG不在ACCEPT里，孤立的!会走到一个既不能接受也没有出边的位置，扫描器返回失败，报「非法运算符」，这是有意留的。

3.4 手工验证：拿三个字符串走一遍表

在写扫描器之前，最好先手工跑三个串，确认表是对的。这是整个实验里最省时间的一步，很多人跳过它，结果在代码里找了一晚上 bug。

abc123从S出发，a走ALPHA到ID，b、c自环，1、2、3走DIGIT自环，仍然在ID。字符串结束，ID是接受状态，输出标识符。

>=从S出发，>到GT，GT是接受状态，先记下「这里可以结束」；接着读=，到OP2，OP2也是接受状态，更新记录；再往后没有字符，返回OP2的接受结果，得到>=。这就是最长匹配。

>单独出现时，读到>到GT，记下可结束；下一个字符是空格，GT对空格没有出边，循环终止，回退到上次记录的结束位置，只吃掉>。如果没有这个「记录 + 回退」，扫描器会把空格也吞进来，或者在读>时就急急忙忙返回。

4. 扫描器实现：表驱动主循环加最长匹配回退

4.1 逐字符迁移的写法有三个硬伤

原始素材里那份参考程序，把状态迁移写成了「当前状态 + 当前字符类别」的二维查表，看上去挺规整，但有三处会直接导致结果错。

第一，标识符状态的转移行里，遇到OPERATOR_DELIMITER还留在ID。也就是说x;会整段被当成一个标识符，分号丢失。第二，注释状态遇到/还是留在COMMENT，遇到其他字符也进ERROR，完全没有「吃到行尾」的概念。第三，整个循环没有「回退」这个概念，读到>之后如果下一个是=，没法把>单独作为一个 token 吐出去。

这三个问题的共性是把「状态」和「token 边界」混为一谈了。修正思路很简单：状态机只负责往前探，什么时候结束由「最后一次见到的接受状态」决定，探不动了就退回来。

4.2 核心：一个带回退的匹配函数

把匹配拆成两层，一层负责单步转移，一层负责在一个位置上尽可能往前吃并记录最后一个可接受点。

def key_of(ch): """把字符归成转移表里的键：字母、数字、或字符本身""" if ch.isalpha(): return 'ALPHA' if ch.isdigit(): return 'DIGIT' return ch def step(state, ch): """单步转移，处理不了返回 None；注释状态单独吃整行""" if state == 'COMMENT': return 'COMMENT' if ch != '\n' else None return DFA.get(state, {}).get(key_of(ch)) def match_token(src, start): """ 从 start 开始做最长匹配。 返回 (token_type, end_index)，识别失败返回 None。 """ state = 'S' j = start best = None # (type, end) 最后一次可接受的位置 n = len(src) while j < n: nxt = step(state, src[j]) if nxt is None: break state = nxt j += 1 if state in ACCEPT: best = (ACCEPT[state], j) # 只记录，不返回 return best

match_token的关键在于「不提前返回」。每走到一个接受状态就把(类型, 结束位置)存进best，一直走到走不动为止，最后返回best。这样>后面跟=时，GT会被记一次，OP2会被再记一次并覆盖前者，最终按OP2返回；>后面跟空格时，GT被记一次，再往下走不动，返回GT。同一个函数同时覆盖了单字符和双字符运算符，不需要为>=写任何特判。

step里对注释的处理是实用主义的：注释状态不看字符集，只要不是换行就继续吃。这相当于把「注释内部允许任意字符」这条规则写在了转移逻辑里，代价是注释状态不像其他状态那样由表驱动，收益是不用给几十个非法字符一个个建转移。这种小妥协在实验报告里写一句「注释状态的处理从简」就够了。

4.3 主循环：跳过空白、丢弃注释、同步行列号

有了match_token，主循环就只剩下调度和记账。这里最容易出错的不是识别，是行号和列号的维护。

def scan(src): tokens, errors = [], [] i, line, col = 0, 1, 1 n = len(src) while i < n: ch = src[i] if ch == '\n': i += 1; line += 1; col = 1 continue if ch in ' \t\r': i += 1; col += 1 continue best = match_token(src, i) if best is None: errors.append((line, col, 'illegal character %r' % ch)) i += 1; col += 1 continue ttype, end = best lexeme = src[i:end] # 数字后面紧跟字母：词法上能拆开，语义上没有意义，单独报错 if ttype == 'NUM' and end < n and (src[end].isalpha() or src[end] == '_'): k = end while k < n and (src[k].isalnum() or src[k] == '_'): k += 1 errors.append((line, col, 'illegal number %r' % src[i:k])) col += k - i i = k continue if ttype == 'COMMENT': for c in lexeme: # 注释丢弃，但行列要跟着走 if c == '\n': line += 1; col = 1 else: col += 1 i = end continue if ttype == 'ID' and lexeme in KEYWORDS: ttype = 'KEYWORD' tokens.append((ttype, lexeme, line, col)) col += end - i i = end return tokens, errors

四个分支的顺序不能换。换行和空白必须最先处理，否则match_token会在空白处返回None，整个文件到处都是「非法字符」错误。注释必须在标识符前面判，因为/已经被SLASH状态接走了，走到COMMENT时不会再回到运算符分支。数字后跟字母的检查放在最后、token 入列之前，它不改识别结果，只额外记一条错误。

那个for c in lexeme的小循环看着笨，其实是在还债：注释可能是整行，里面有且仅有一个换行，但注释本身不产生 token，如果直接把i推到end而不更新行列号，下一行所有 token 的行号都会少 1。这类错误在短样例里看不出来，样例一长就全乱。同样的账在col += end - i那一行也记了一次，两次记账的规则统一成「谁推进了 i，谁负责更新 line 和 col」，是我后来强制自己遵守的规矩。

4.4 输出 lex.txt 与错误清单

结果落盘分两个文件，一个存合法单词，一个存错误。格式不用花哨，每行一条，字段之间用固定分隔符，方便后面写脚本比对。

def dump(tokens, errors, token_path='lex.txt', err_path='lex_err.txt'): with open(token_path, 'w', encoding='utf-8') as f: for ttype, lexeme, line, col in tokens: f.write('%s\t%s\t%d\t%d\n' % (ttype, lexeme, line, col)) with open(err_path, 'w', encoding='utf-8') as f: for line, col, msg in errors: f.write('%d:%d\t%s\n' % (line, col, msg))

拿样例程序跑一遍，期望的输出大致是这样：第一行的{是分界符，随后整段//This a test program.被当注释丢弃，不占 token；int abc123$;会先输出KEYWORD int、ID abc123，然后在$处报一个「illegal character '$'」；int 123@;输出KEYWORD int、NUM 123，在@处报错；int 2a;会先输出KEYWORD int，然后在2a处报「illegal number '2a'」，而不是把2和a分两条默默放过去。

最后这条需要说明一下立场。严格按词法规则，2a完全可以拆成NUM 2和ID a两个合法 token，编译器没有义务报错；但实验要求明确把2a列为错误，那就得加一条语法层面的启发式检查。写报告时把这一层说明白，比硬说「词法规则规定数字后不能跟字母」要可信得多，答辩时被追问也不至于卡住。

5. 排查清单：五个最容易翻车的点

5.1 除号被当成注释开头，整行消失

现象：abc = abc / i;这一行后面的 token 全部丢失，lex.txt里只剩到abc为止。

原因：状态机里SLASH状态读到/之后直接跳到注释状态，但代码在SLASH这一层就判断「这是注释」，把后面的内容一直吃到行尾。实际上第一个/是除号，只有连续两个/才是注释。

解决：SLASH必须是接受状态，且类型是OPERATOR；只有在它继续读到第二个/时才转入COMMENT。依靠 4.2 里的最长匹配机制，/会停在SLASH并按除号输出，//会走到COMMENT并按注释丢弃。改完之后拿abc = abc / i;和// test两行分别验一遍，两类都能过才算修好。

5.2 最长匹配丢失，>=被拆成两个符号

现象：i <= n输出成OPERATOR <加OPERATOR =，token 数比预期多一倍。

原因：match_token里一进接受状态就return，读到<的时候LT恰好是接受状态，函数立刻返回，根本没机会看后面的=。

解决：接受状态只记录不返回，用一个best变量保存「目前最长的可接受结果」，循环跑到走不动为止再返回best。改完用>=、>、!=、!四个串各测一次，前三个应该有输出，最后一个应该报错。

5.3 标识符状态吞掉后面的分号

现象：int x;只输出两个 token，x;被合成一个标识符。

原因：DFA 表里ID状态的转移行写得太宽，把运算符、分界符的字符类也留在了ID上。这多半是从 NFA 直接抄表时把「状态可以接受任意字符」误解成了「状态对所有字符都有出边」。

解决：ID状态只保留ALPHA和DIGIT两条自环，其余字符一律无出边，靠回退结束 token。这条规则对所有接受状态都适用——接受状态意味着「可以在这里停」，不意味着「可以继续吃任何字符」。改完后拿abc123$验一遍，期望得到ID abc123加一个非法字符错误。

5.4 错误位置漂移，行号列号对不上

现象：报错指向第 3 行，实际错误在第 4 行；或者同一行里第二个错误的位置总是比实际靠前几位。

原因：跳过一个非法字符时只写了i += 1，忘了col += 1；或者注释里含换行，直接i = end跳过去，line没有跟着加。两种漏记都会让后面的计数整体偏移，而且偏移量会累积。

解决：所有推进i的地方都成对更新line和col，包括跳过空白、跳过非法字符、跳过注释、正常吐出 token 四条路径。写完拿一段每行都埋一个错误的程序跑一遍，逐个核对报错坐标，比读代码快得多。

5.5 前导零整数一路绿灯

现象：abc = 012345;输出成OPERATOR =加NUM 012345，没有任何报错。

原因：无符号整数的正则写成了(0|…|9)+，首位是0也合法，整串自然被吃成一个数字。样例里这一行是故意放的，不报错就等于漏了一个测试点。

解决：正则改成((1|…|9)(0|…|9)*)|0，DFA 里0单独一条边直达接受状态，1-9走另一条边再自环。这样扫描到012345时会先吃下0作为一个整数，剩下的12345作为下一个整数，中间没有分隔符，再叠一条「数字后紧跟数字但已被前一个 token 截断」的检查，就能把这一行报出来。

6. 验收与答辩：用三张表讲完整个设计

验收这一步，多数人栽在「程序跑通了但讲不清」。导师不会盯着代码看，他会问三个问题：规则是怎么变成状态图的、状态图是怎么变成代码的、错了怎么定位。把这三件事各准备一张表，演示就能顺着走完。

答辩时我最常用的开场是拿出 DFA 状态表，指着SLASH那一行说：「这个状态既是接受状态又有出边，它是整个设计里唯一需要回退的地方，也是我调试时间最长的地方。」这句话一出，后面的问题基本都会围绕最长匹配展开，而这块恰好是我准备最充分的。反过来，如果一上来就讲正则表达式怎么推导，很容易被追问 NFA 的 ε 闭包细节，那些东西在纸上画得清、嘴上说不清。

演示顺序建议固定成：先跑一遍正确程序，展示lex.txt；再跑一遍错误程序，展示报错坐标；最后打开状态表，说明错误是怎么被这张表定位的。三步走完大概五分钟，剩下的时间留给提问。提前把lex.txt的内容打印一份带在身上，比当场翻文件稳。

有件事我吃过亏：第一次验收时程序在样例上跑得挺好，导师随手加了一行while (i <= n) do，结果do被识别成了标识符，因为关键字表里漏了它。从那以后我每次交这类实验，都会把关键字表里的每个词单独丢进扫描器跑一遍，八个词八行输出，全对才敢往下走。

一个具体的提问套路也提前准备好：「你这个 DFA 有多少个状态，最小化省了几个，省掉的是哪几个？」标准答案要能说出具体数字和合并掉的类型，比如「合并前三十一个，合并后十九个，合掉的是几个只认单个分界符的终态」。答得出数字，说明你真的跑过最小化算法，而不是抄了一张图。

希望帮到你。

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