简介：这份西南科技大学编译原理实验报告1面向计算机专业学生及刚接触编译器前端的学习者，聚焦“设计词法分析程序”实验任务，帮助读者理解从正则表达式到NFA、DFA确定化与最小化的完整流程，并完成TEST语言单词分类与输出方案设计。包内为1个doc文档，约444KB，涵盖实验目的、实验设计、实验过程与程序实现，结合Python状态机框架展示词法分析程序的组织方式，也提示错误处理、缓冲区管理与回溯等工程细节。已有477人学习，适合用于实验报告撰写参考、编译原理课程复习及词法分析模块对照实现，可据此梳理DFA状态转移表与单词输出格式，为后续语法分析打下基础。

1. 一份词法分析实验报告：从正则到 lex.txt 的完整链路

某高校《编译系统综合设计》的实验报告一，题目是设计词法分析程序，把正则表达式 → NFA → 确定化 → 最小化 DFA → Python 扫描器 → lex.txt 输出这条链路完整走了一遍，还附了调试记录和两道讨论题。它解决的是一个很具体的尴尬：编译原理课讲了三周自动机理论，实验课却要求交一份能跑的扫描器，中间那段落差没人补。适合赶编译原理实验报告的学生、想把书里那张手画状态图变成可执行代码的自学者，以及要手写一个配置式 lexer 的工程师。陷阱也很明确——报告里贴的 Python 代码，状态转移表和前面画的 DFA 根本不是同一台机器，直接抄会翻车。下面按理论到实现的顺序拆。

2. 正则表达式与 NFA：TEST 语言七类词怎么表达成自动机

这一章解决的是"规则怎么写"和"规则怎么变成状态机"两件事。很多人卡在第一步，不是因为不会写正则，而是没想清楚正则和自动机之间那条通道——Thompson 构造法就是这条通道，它保证任何正则表达式都能机械地翻译成 NFA，不需要灵感。

2.1 七条词法规则的正则写法与冲突处理

TEST 语言在报告里定义了七类词：标识符、关键字（保留字）、无符号整数、分界符、运算符、注释符，加上被跳过的空白。把它们写成正则不难，难的是这些正则之间存在大量重叠，必须先定好切分顺序。

表里有四处冲突，必须在设计阶段就拍板，否则后面全是补丁。

第一处是关键字和标识符。教科书做法是给if、while各建一条独立分支，结果是 NFA 里凭空多出几十个状态，最小化之后还是几十个。主流编译器的做法是根本不区分：int在词法层就是一个合法标识符，扫完之后拿字符串去哈希表里查一次，命中就改类型。这样 DFA 里只需要一条ID状态，工程量和可维护性差一个数量级。

第二处是/和//。单个/是除号，两个连着是注释开头。这不是靠优先级声明能解决的，只能靠最长匹配——读到第一个/时先接受为除号候选，再看下一个字符，是/就继续走注释分支。

第三处是>和>=、=和==、!和!=。同样是最长匹配，>单独出现时是合法运算符，后面跟=时才升格成>=。这意味着>对应的状态既是接受态，又有出边——这是整个 DFA 里最容易写错的结构，后面第 5 章会专门讲。

第四处是注释。从词法角度看注释不是单词，但它必须被正确吞掉，而且吞的时候要维护行列号，否则报错位置全错。

提示：报告里int同时被列进"关键字"和"保留字"两个分类，这是原始材料的口径含混，不是两种不同的东西。实现时统一按关键字处理即可，不用为它单独建类别。

2.2 Thompson 构造：从正则到 NFA 的四条拼装规则

正则表达式到 NFA 的转换是纯机械的，只有四条规则，任何复杂的正则都是这四条规则递归拼出来的。

单字符c：新开两个状态 s、e，s 上加一条读c到 e 的边。

连接RS：R 的所有接受态加 ε 边指向 S 的初态，R 的初态成为新初态，S 的接受态成为新接受态。

选择R|S：新开一个初态，用两条 ε 边分别指向 R 和 S 的初态；再新开一个接受态，R 和 S 的所有接受态用 ε 边指向它。

闭包R*：新开初态，ε 边一条指向 R 初态、一条直接指向新接受态；R 的每个接受态用 ε 边回指 R 初态，同时指向新接受态。

把这四条规则写成代码，数据结构只需要两个字段：转移表和接受态集合。转移表的键是(状态, 字符)，字符用None表示 ε 边。

# NFA 的最小表示：转移表 + 初态 + 接受态（接受态带 token 类型，便于后续合并） class NFA: def __init__(self): self.trans = {} # (state, ch) -> set(state)，ch=None 表示 ε 边 self.start = None self.accept = {} # state -> token 类型字符串 def add(self, src, ch, dst): self.trans.setdefault((src, ch), set()).add(dst) _seq = [0] def new_state(prefix='s'): _seq[0] += 1 return f'{prefix}{_seq[0]}' def frag_char(c): """单字符片段：s --c--> e""" n = NFA() s, e = new_state(), new_state() n.start = s n.accept = {e: None} n.add(s, c, e) return n def _union_env(*frags): """把多个 NFA 的状态和边并到一个新对象里，供下面三条规则复用""" n = NFA() for f in frags: for k, v in f.trans.items(): n.trans.setdefault(k, set()).update(v) n.accept.update(f.accept) return n def frag_concat(a, b): """连接 RS：a 的每个接受态打 ε 边指向 b 的初态""" n = _union_env(a, b) n.start = a.start n.accept = dict(b.accept) # 连接后只有 b 的接受态有效 for s in a.accept: n.add(s, None, b.start) return n def frag_alt(a, b): """选择 R|S：新初态分两路，两路接受态汇到新终态""" n = _union_env(a, b) s0, e0 = new_state('s'), new_state('s') n.start = s0 n.add(s0, None, a.start) n.add(s0, None, b.start) n.accept = {e0: None} for s in list(a.accept) + list(b.accept): n.add(s, None, e0) return n def frag_star(a): """闭包 R*：接受态回指初态，同时 ε 跳过整个片段""" n = _union_env(a) s0, e0 = new_state('s'), new_state('s') n.start = s0 n.add(s0, None, a.start) n.add(s0, None, e0) for s in a.accept: n.add(s, None, a.start) n.add(s, None, e0) n.accept = {e0: None} return n

这段代码的逻辑很直白，但有三个参数含义需要说清楚，否则抄完改不动。

self.trans用(状态, 字符)元组做键，而不是嵌套字典，是因为 ε 边没法用字符索引，用None当字符是最省事的做法，后面求 ε-闭包时直接取trans.get((s, None), set())就行。

self.accept从set改成了dict，值存 token 类型。原因在后面合并阶段：多条规则拼成一台机器后，必须知道停在哪个接受态对应哪种词，否则还得反过来查状态编号。用None占位表示"这是接受态但还没定类型"，合并时统一填充。

_seq是全局计数器，保证两条并行构造的片段不会撞状态名。工程实现里一般会换成带前缀的命名空间或者直接给每个 NFA 分配独立编号段，这里用全局自增是为了代码短。

用这四条规则拼一条标识符的正则[A-Za-z][A-Za-z0-9]*，写法是：

# 26 个小写 + 26 个大写，用选择串起来 letter = frag_char('a') for c in 'bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ': letter = frag_alt(letter, frag_char(c)) digit = frag_char('0') for d in '123456789': digit = frag_alt(digit, frag_char(d)) ident = frag_concat(letter, frag_star(frag_alt(letter, digit)))

手工拼 60 多条|显然不现实，实际项目里这一段一定是先用正则解析器把字符串解析成语法树再递归下降，或者干脆直接手写状态机跳过 NFA 阶段。做实验报告时手工拼一遍是有意义的，因为拼完你会发现frag_star里那两条 ε 边到底指向哪里，这件事画图容易画错。

2.3 合并 NFA：一个新初态把七条规则接成一台机器

每条规则单独构造出来的 NFA 是七台互不相干的机器，它们各自有初态、各自有接受态。要变成一台能同时识别所有词的扫描器，需要做一次合并：新建一个总初态 S，用 ε 边分别指向七个子片段的初态；把所有子片段的接受态保留，并标注上各自的 token 类型。

def build_combined_nfa(rules): """rules: [(token_type, 子NFA), ...]，返回一台合并后的 NFA""" n = NFA() n.start = new_state('S') for ttype, frag in rules: for k, v in frag.trans.items(): n.trans.setdefault(k, set()).update(v) n.add(n.start, None, frag.start) # 总初态 ε 边分叉 for s in frag.accept: n.accept[s] = ttype # 接受态打上 token 类型 return n RULES = [ ('ID', ident), ('NUM', frag_concat(frag_char('0'), frag_star(digit))), # 简化版：允许前导零 ('OP', frag_alt(frag_char('>'), frag_char('<'))), # 其余运算符同理拼接 ('DELIM', frag_char(';')), ('COMMENT', frag_concat(frag_char('/'), frag_char('/'))), # 注释体在扫描阶段吞掉 ] combined = build_combined_nfa(RULES)

合并这一步有两个容易忽略的细节。

第一个是总初态必须新建，不能拿某条规则的初态顶替。因为int这条规则和标识符规则的初态是不同的，如果复用其中任何一个，另外六条规则的入口就断了，扫出来的结果会漏词。

第二个是接受态的标注时机。合并前每个子片段都是{e: None}，合并时统一填ttype。如果某条规则内部用了frag_alt，它的接受态经过_union_env之后还是None，会被build_combined_nfa补上，顺序不能反——先并转移、再打标签，否则标签会被覆盖。

合并后的 NFA 状态数通常在 100 到 300 之间，取决于正则的展开程度。这个数字本身没意义，因为它马上就要被确定化成 DFA，状态数会变，边数也会变。但它决定了确定化阶段的表有多大——子集构造的复杂度是 O(2^n)，所以 NFA 设计得越紧凑，后面越省事。这也是为什么前面强调不要把关键字单独建成 8 条分支：那会让 NFA 的初始状态直接多出 8 个分支点，子集构造时状态爆炸的概率显著上升。

还有一点值得说：注释符//在合并 NFA 里只构造了两个字符的片段，完整的注释体[^\n]*没进去。这是有意为之。注释体是任意长度、任意字符，把它塞进 DFA 只会让状态转移表多出一大堆"到行尾"的自环，而它对 token 输出没有任何贡献。工程上的通行做法是：DFA 只负责识别//这个开头，识别到之后立刻切换到"行注释模式"，用一段简单循环吞到换行符为止。报告里的代码在这一点上是混着处理的，后面第 5 章会展开。

3. 确定化与最小化：子集构造和 Hopcroft 划分的手算过程

NFA 是不能直接跑的，因为同一个状态读同一个字符可能有多条出边，程序无法决定走哪条。确定化的任务就是把它变成一台"每个状态每个字符最多一条出边"的机器，代价是状态数可能指数膨胀。最小化再把膨胀出来的冗余状态合并回去。

3.1 子集构造：ε-闭包和 move 两个原语

子集构造的核心思想是：DFA 的每一个状态，对应 NFA 状态集合的一个子集。读一个字符，就把当前子集能到达的所有状态收集起来，再求一次 ε-闭包，得到下一个子集。

需要两个原语。ε-闭包：从一个状态集合出发，沿着所有 ε 边能走到的全部状态（含起点自身）。move：从一个状态集合出发，读一个具体字符能到达的全部状态（不含 ε 展开）。

def eps_closure(states, trans): """沿 ε 边做可达性扩展，返回闭包后的 frozenset""" stack = list(states) seen = set(states) while stack: s = stack.pop() for t in trans.get((s, None), ()): if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def move(states, ch, trans): """读一个字符后能到达的状态集合，不展开 ε""" out = set() for s in states: out |= trans.get((s, ch), set()) return out def determinize(nfa): """子集构造：NFA -> (状态编号表, 转移表, 接受类型表)""" alphabet = sorted({c for (_, c) in nfa.trans if c is not None}) start = eps_closure({nfa.start}, nfa.trans) id_of = {start: 0} order = [start] trans = {} # (dfa_state_id, ch) -> dfa_state_id accept = {} # dfa_state_id -> token 类型 queue = [start] while queue: cur = queue.pop(0) cid = id_of[cur] for ch in alphabet: nxt = eps_closure(move(cur, ch, nfa.trans), nfa.trans) if not nxt: continue if nxt not in id_of: id_of[nxt] = len(order) order.append(nxt) queue.append(nxt) trans[(cid, ch)] = id_of[nxt] # 该子集里只要含 NFA 接受态，DFA 状态就是接受态 types = {nfa.accept[s] for s in cur if nfa.accept.get(s)} if types: accept[cid] = sorted(types)[0] # 冲突时按优先级取，见下方说明 return order, trans, accept

代码里queue是待处理的子集队列，用列表 pop(0) 实现广度优先。生产代码会换成collections.deque，因为 list 的 pop(0) 是 O(n)，几千个状态时会有明显感知。

types取集合而不是单个值，是因为一个子集里可能同时含有两个不同 token 类型的 NFA 接受态。这种情况说明词法规则本身有歧义，比如int如果单独建了分支，扫到i的时候那个子集里既有 ID 的接受态路径也有 int 的接受态路径。处理办法有两种：一是靠最长匹配在扫描阶段自然消解（in不是int，长度不够），二是给sorted(types)[0]定一个明确的优先顺序。我一般会显式写一个TYPE_PRIORITY = ['KEYWORD', 'ID', 'NUM', 'OP', 'DELIM']的字典，用min(types, key=TYPE_PRIORITY.index)取，比sorted靠谱，因为字符串排序是字典序，跟业务优先级无关。

手算的时候会画一张表，行是 DFA 状态（也就是 NFA 子集），列是字母表里的每个字符，格子里填 ε-闭包后的新子集。这张表要一直填到没有新子集产生为止。闭包符号用ε-closure({...})表示，子集直接写状态编号集合，比如{1,2,5}。填表时有个技巧：先把含初态的子集ε-closure({S})写在第一行，然后逐个字符展开，新出现的子集编号往后排，这样不会漏。

3.2 最小化：按 token 类型做初始划分

确定化得到的 DFA 通常有一半状态是冗余的，最小化的目标是在保持语言不变的前提下把状态数压到最少。Hopcroft 划分法的思路是：先把状态分成"接受态"和"非接受态"两组，然后反复检查每组内部能不能再按"读同一个字符后落到哪一组"细分，直到划分不再变化。

def minimize(n_states, alphabet, trans, accept, start): def group_of(part, s): for i, g in enumerate(part): if s in g: return i return -1 # 初始划分：相同 token 类型的接受态一组，非接受态单独一组 buckets = {} for s in range(n_states): buckets.setdefault(accept.get(s), set()).add(s) part = list(buckets.values()) while True: new_part = [] for g in part: sig = {} for s in g: # 签名：读每个字符后落到哪个组 key = tuple(group_of(part, trans.get((s, ch), -1)) for ch in alphabet) sig.setdefault(key, set()).add(s) new_part.extend(sig.values()) if len(new_part) == len(part): break part = new_part # 重新编号，输出最小 DFA new_trans, new_accept = {}, {} for i, g in enumerate(part): rep = next(iter(g)) if rep in accept: new_accept[i] = accept[rep] for ch in alphabet: t = trans.get((rep, ch)) if t is not None: new_trans[(i, ch)] = group_of(part, t) return len(part), new_trans, new_accept, group_of(part, start)

初始划分用accept.get(s)做键，意味着"接受态按 token 类型分组、非接受态归为一组"。如果用传统的二划分（接受态一组、非接受态一组），最小化出来的状态数会多一些，因为不同 token 类型的接受态在后续迭代中还是会被拆开，只是多绕几轮。直接按类型分更省事，也更贴近词法分析的实际需求。

trans.get((s, ch), -1)里的-1是"死亡状态"的占位。DFA 里没有显式死亡状态时，缺边就是死亡，用-1表示，group_of会返回-1，所有缺边的状态在这个字符上签名相同，自然归到一起。

代码里part是列表的列表，group_of用线性扫描找组号。状态数上千时这会变成瓶颈，实际实现会用dict维护state -> group_id的映射，每轮重建一次。实验报告规模下，几十个状态无所谓。

最小化之后，状态数通常能压到 10 到 20 之间。这个量级刚好可以画在一张 A4 纸上，也刚好可以手写进制表里。

3.3 把结果落成状态转移表

最小化得到的new_trans是以整数状态编号为键的，直接塞进扫描器可读性很差。落地时要做一次重命名，把状态改成有意义的字符串，把字符按类别归并，最终得到一张人能看懂的转移表。

字符归并有讲究。字母有 52 个，如果每个都单独一列，转移表会有 52 列冗余，而且每一列的走向完全相同。归并成类别L（字母）、D（数字）、其余字符保持原样，表就从 70 列压到 20 列左右。

def to_class(ch): if ch.isalpha(): return 'L' if ch.isdigit(): return 'D' return ch def rebuild_table(new_trans, alphabet, rename): """把整数编号的 DFA 表转成人能读的字符串表""" table = {} for (s, ch), t in new_trans.items(): cls = to_class(ch) table.setdefault(rename[s], {})[cls] = rename[t] # 同一状态同一类别必须映射到同一目标，否则归并失败 for s, row in table.items(): for cls, t in row.items(): pass return table

这段代码的重点不是实现，而是那个注释——归并字符类别时有一个隐含前提：同一状态下，所有被归到同一类的字符，转移目标必须相同。字母归成L是安全的，因为标识符状态读任何字母都还在标识符状态；但如果把>和>=混着归并就会出错。落地前建议加一句断言：先用原表逐字符展开，检查同类字符的目标是否一致，不一致就不归并，单独留一列。

最终得到的那张表就是第 4 章扫描器的输入。手工整理出来的版本大致长这样：S是初态，ID、NUM、GT、GE等是状态名，L/D是归并后的字符类，其余字符原样作为键。这张表同时包含了接受信息——哪些状态是接受态、接受成什么 token，单独用一张字典维护。这两张表加起来不到 40 行，比一个几百行的if-elif链好维护得多。

4. 从 DFA 表到 Python 扫描器：最长匹配、回退和词法错误定位

理论部分到这里就结束了。这一章是整份资源的实操核心：把第 3 章那张表喂给一个循环，让它吐出 token 序列、写进lex.txt，同时把非法字符的行列号报出来。

4.1 表驱动主循环：最长匹配靠一个 last 指针兜底

扫描器的骨架非常固定：从当前位置出发，尽可能多地读字符，每读一个就查表跳状态；记录最后一次停在接受态的位置；读不下去时回退到那个位置，切出一个 token。

关键在于那个"最后一次接受态"的记录。以>=为例，读到>时状态是GT，这是个接受态，记下位置；再读=，状态变成GE，也是接受态，更新记录；如果后面是字母，读不动了，回退到GE的位置，切出>=。如果只读到>就读不动了，回退到GT的位置，切出>。

# DFA 状态转移表（等价于第 3 章最小化后的结果，状态名做了可读化处理） TRANS = { 'S': {'L': 'ID', 'D': 'NUM', '>': 'GT', '<': 'LT', '=': 'ASSIGN','!': 'NOT', '/': 'DIV', '+': 'PLUS', '-': 'MINUS', '*': 'STAR', '(': 'LPAREN',')': 'RPAREN', '{': 'LBRACE','}': 'RBRACE',';': 'SEMI', ',': 'COMMA', ':': 'COLON'}, 'ID': {'L': 'ID', 'D': 'ID'}, 'NUM': {'D': 'NUM'}, 'GT': {'=': 'GE'}, # > 本身是接受态，且还能继续吃 = 'LT': {'=': 'LE'}, 'ASSIGN': {'=': 'EQ'}, 'NOT': {'=': 'NE'}, # 单独的 ! 不是合法 token 'DIV': {'/': 'COMMENT'}, # 除号状态吃到一个 / 就转注释 } ACCEPT = { 'ID': 'ID', 'NUM': 'NUM', 'GT': 'OP', 'GE': 'OP', 'LT': 'OP', 'LE': 'OP', 'EQ': 'OP', 'NE': 'OP', 'ASSIGN': 'OP', 'PLUS': 'OP', 'MINUS': 'OP', 'STAR': 'OP', 'DIV': 'OP', 'LPAR <p> <a href="https://download.csdn.net/download/m0_65436422/88754609" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>