企业官网建设流程全解析

简介：面向编译原理课程学习者以及需要完成词法分析实验的学生，这份西南科技大学实验报告聚焦“设计词法分析程序”这一经典任务，可辅助理解编译器前端从词法规则到可运行程序的完整链路。报告围绕TEST语言展开，涵盖用正则表达式描述标识符、保留字、无符号整数、分界符、运算符与注释符，继而构造NFA、合并确定化并化简为最小DFA，同时给出单词分类与输出方案，并附Python状态机实现框架，便于对照实验步骤、梳理设计思路与排查状态转移问题。资源包共1个doc文件，约444KB，篇幅集中、结构完整，适合作为实验报告撰写与课程设计参考。目前已有479人学习，在该校编译原理实验场景中具有一定参考价值。

1. 编译原理实验报告：从 7 条正则到一台能跑的状态机

很多人拿到《编译系统综合设计》的第一份实验包，第一反应是把那几张 NFA 图照着描一遍交差。这份编译原理实验报告里真正值钱的东西不是图，而是一个能跑的词法分析程序：它以最小 DFA 状态转移表驱动，配一段故意埋了坑的 TEST 语言源程序，跑完能把合法单词写进 lex.txt，把非法字符连同行列号一起报出来。正则表达式怎么描述词法规则、NFA 怎么确定化并最小化、单词怎么分类输出，这三件事在报告里是分开写的，落到代码里其实是一条线。适合正在做编译器前端课程设计的人，也适合想拿一个几十行就能跑通的状态机当模板、往自己项目里塞词法层的人。

2. 正则在先、自动机在后：TEST 语言七类单词的规则怎么落地

2.1 七条词法规则的正则表达式，以及它们互相咬合的地方

词法分析的第一步不是写代码，是把自然语言描述的「单词长什么样」翻译成正则表达式。实验指导里给出的 TEST 语言是一个极小的子集，但它已经把词法层的所有典型冲突都摆出来了：标识符和关键字的前缀重合、>和>=的前缀重合、/和//的前缀重合。这三处重合决定了后面 DFA 能不能做对最长匹配。

按报告里的规则整理出来是这样一张表：

这张表里有两个地方需要提前警觉。第一个是关键字和标识符在正则层面完全重合——关键字集合是标识符集合的真子集，靠 DFA 是分不开的，必须扫完之后拿字符串去查表。这不是偷懒，是标准做法，后面 3.3 节会展开。

第二个是报告正文把int同时列进「关键字」和「保留字」两个分类，这是原始文档里的一处笔误，但如果你照着抄进代码，token 流里就会出现同一种单词被归到两个类型的情况，下游语法分析直接对不上号。写代码前先把这个分类表定死：int属于关键字，保留字这个分类在 TEST 语言里可以合并掉。

提示：正则表达式写到纸上之后，先别急着画 NFA，拿几个边界串在脑子里过一遍——a1、1a、>=、> =、//x、/x、0、01。这八个串能过，规则基本就写对了。

2.2 Thompson 构造到子集构造：NFA 合并、确定化、最小化三步走

报告要求把每条正则先转成 NFA，再合并、确定化、最小化。手算这套流程是实验的考核点，但落到工程上，真正需要你亲手把控的只有最后那张表。说说每一步在做什么。

单条规则转 NFA 用 Thompson 构造就够了。以标识符letter(letter|digit)*为例，状态只有两个：起始态q0收到字母跳q1，q1收到字母或数字自环，q1是终态。无符号整数同理，只是把字母换成数字，并且q0只接受1-9，数字0单独走一条到终态的边——这条单独的边就是「不允许前导零」在自动机层面的体现，你的状态表里必须有它，否则012345会被当成合法整数放过去。

合并是把所有子 NFA 的起始态并成一个START，从START出发按第一个字符的类别分岔。确定化就是子集构造：把「当前可能处于的状态集合」当成一个新状态，初始集合是{START}，然后对每个输入类别求 ε-闭包下的后继集合。手算的时候状态会膨胀得很快，因为{q_ID, q_NUM}这类混合集合会出现；但 TEST 语言的规则彼此首字符互斥（字母、数字、符号、空白各走各的），膨胀得并不严重。

最小化用划分法：先按「终态 / 非终态」划两个集合，再看每个集合里的状态对每个输入类别是否跳到同一个集合，跳得不一致就继续拆，直到划分不再变化。对这份实验来说，最小化的收益主要体现在运算符那一支——+、-、*、(、)、{、}、;、:全都是「收到即终态、没有后续」的形状，最小化之后它们在等价类上是同一类，可以合并成一个状态。

我最后收敛出来的最小 DFA 有 16 个状态：

把+ - * ( ) { } ; :全部塞进一个SINGLE状态是主动做的取舍：状态数从 25 个压到 16 个，代价是出 Token 的时候要回查一次字符集合才能确定它到底是分界符还是运算符。这个交换在状态机规模小的时候划算，规则涨到几十条的时候就得反过来做，5.x 节会讲什么时候该拆回去。

2.3 把最小 DFA 摊成转移表：用状态名换掉几百行 if

最小 DFA 画出来之后，下一步是选数据结构。实验报告里的做法是 Python 的 dict-of-dict：外层键是状态名，内层键是字符类别名，值是下一个状态名。这个结构的好处是直接对应纸上那张图，调试的时候打印出来一眼能对上；坏处是查表要走两次哈希，而且状态名写成字符串容易拼错。

如果后面要接真正的编译器，一般会换成二维数组：行是状态编号，列是字符类别编号，值是整数状态编号，-1表示无转移。桥接代码很短：

# 状态名 -> 行号，类别名 -> 列号，一次性建好索引 CATS = ['ALPHA', 'DIGIT', 'WS', 'SINGLE', 'SLASH', 'GT', 'LT', 'EQ', 'BANG', 'OTHER'] SID = {name: idx for idx, name in enumerate(DFA)} # dict 保序，编号稳定 CID = {name: idx for idx, name in enumerate(CATS)} # -1 等价于 dict 版里 .get() 返回 None：该状态下不接受这个类别 table = [[-1] * len(CATS) for _ in DFA] for sname, row in DFA.items(): for cname, tname in row.items(): table[SID[sname]][CID[cname]] = SID[tname]

SID和CID是把字符串映射成下标的字典，table就是压平后的二维表。-1是哨兵值，扫描时判断nxt == -1就等价于原来判断「这个类别不在当前状态的行里」。这样主循环里只剩两次整数下标访问，没有哈希、没有字符串比较。

参数上有一个坑值得提前说：enumerate(DFA)依赖 Python 3.7 之后 dict 的插入顺序保证，如果你的环境是更老的版本，SID的编号会和table的行序对不上，扫描出来的结果会莫名其妙地错乱。血泪经验是别省这一步，老老实实写sorted(DFA)或者显式给每个状态一个常量编号。

3. 扫描器主循环：DFA 驱动的词法分析器怎么写出最长匹配

3.1 字符分类函数：粗粒度类别是状态数能压下来的关键

DFA 的输入不是字符本身，是字符类别。这一步抽象做得好不好，直接决定状态表的宽度。实验报告里的get_char_category把字符分成ALPHABET、DIGIT、OPERATOR_DELIMITER、SLASH、WHITESPACE、OTHER六类，思路对，但OPERATOR_DELIMITER这一刀切得太粗——把>和+归成一类，状态机就没法区分「这里可能出现>=」和「这里绝不可能」。

我一般会按「是否可能作为双字符运算符的前缀」再切一刀：

DELIMS = set('(){};:') def category(ch): """把字符映射成 DFA 的输入类别，类别数直接决定状态表的列数""" if ch.isalpha(): return 'ALPHA' if ch.isdigit(): return 'DIGIT' if ch == '/': return 'SLASH' # 除号还是注释开头，靠下一跳区分 if ch == '>': return 'GT' if ch == '<': return 'LT' if ch == '=': return 'EQ' if ch == '!': return 'BANG' # 单独出现非法，必须跟 = if ch in '+-*' or ch in DELIMS: return 'SINGLE' # 收下即终态，不再有后继 if ch in ' \t\r\n': return 'WS' return 'OTHER'

这里每个分支对应状态表的一列，一共 10 列。GT、LT、EQ、BANG单独成列是必须的，因为它们在START状态下会跳到不同的中间状态，后续能不能接受=也各不相同。SINGLE合并了+ - *和全部分界符，因为这些字符后面不可能再接出更长的合法运算符。

BANG是一个特殊的存在：它自己不是终态，必须再吃一个=才能出 Token。这个设计的意义在于，!单独出现时程序会直接报「非法字符」，而不是把它当成一个运算符放行——这正是报告里那段调试记录想解决的问题的同类。

3.2 主循环的三个指针：start、j 和 last_accept

最长匹配这件事，落到代码里就是三个索引。start记住当前单词的起始位置，j是扫描游标一直往前跑，last_accept记住「最后一次落在终态时」的游标位置和类型。跑到跳不动了，就回退到last_accept，把start到last_accept之间的子串切出来当 Token，剩下的字符留给下一轮。

KEYWORDS = {'int', 'if', 'else', 'for', 'while', 'do', 'write', 'read'} def tokenize(src): tokens, errors = [], [] i, line, col = 0, 1, 1 n = len(src) while i < n: start, s_line, s_col = i, line, col state, j, last = 'START', i, None while j < n: nxt = DFA.get(state, {}).get(category(src[j])) if nxt is None: break # 跳不动了，退出内层循环 state = nxt j += 1 if state == 'COMMENT': while j < n and src[j] != '\n': # 单行注释吞到行尾 j += 1 last = (j, 'COMMENT', state) break if state in ACCEPT: last = (j, ACCEPT[state], state) # 记录最长的一次接受 # —— 内层循环结束，开始切 Token —— if last is None: if j == start: j = start + 1 # 一个字符都没吃进去，强制前进 errors.append({'line': s_line, 'col': s_col, 'text': src[start:j], 'msg': '非法字符或残缺运算符'}) else: end, ttype, st = last j = end # 关键：回退到最长匹配的位置 text = src[start:end] if ttype == 'WS' or ttype == 'COMMENT': pass # 空白和注释不产出 Token elif ttype == 'IDENT' and text in KEYWORDS: tokens.append(('KEYWORD', text, s_line, s_col)) elif ttype == 'IDENT': tokens.append(('IDENT', text, s_line, s_col)) elif text in DELIMS: tokens.append(('DELIM', text, s_line, s_col)) else: tokens.append(('OP', text, s_line, s_col)) # 位置信息按实际消费掉的字符推进，无论成功失败 line, col = step_pos(src[start:j], s_line, s_col) i = j return tokens, errors

逐段看这段代码的关键点。

DFA.get(state, {}).get(...)用两层get是为了让「当前状态没有这条转移」和「当前状态根本不在表里」两种情况统一返回None，内层循环遇到None就break，不会抛 KeyError。实验报告原始版本里直接写dfa[current_state][category]，跑到空白字符时会因为WHITESPACE不在任何一行里而炸掉，这是最常见的一处翻车。

last = (j, ...)的赋值位置很关键：必须在state = nxt和j += 1之后。此时j指向的是「下一个待读字符」，而src[start:j]恰好是已经确认属于当前单词的部分。如果写成j + 1，每个 Token 都会多带一个字符，int会变成int，x会变成x;。

j = end那一行是整个最长匹配的落点。以x >= 1为例：从START读到>进GT（终态，last = (pos, 'OP')），继续读到=进GE（终态，last更新），再读空格时GE行里没有WS这条转移，内层循环break，此时j已经指到空格了，但last记的是>之后的位置，j = end把游标拉回来，切出>=一个 Token。如果不回退，>=会被切成一个带空格的 Token，后面所有位置全错。

if j == start: j = start + 1这一行是防死循环的。比如输入里出现一个孤零零的!，START收到BANG跳到BANG状态，但BANG不在ACCEPT里，last一直是None；内层循环在下一个字符上跳不动，j停在start + 1。如果这里不强制推进，外层while的i就永远不涨，程序卡死。这是状态机类代码最典型的黑匣子式故障：没有报错，就是不返回。

3.3 关键字与标识符的二次判定，别在 DFA 里做

int和integer在状态机看来走的是同一条路，都是ALPHA打头、ALPHA和DIGIT自环。想让 DFA 自己区分，就得为 8 个关键字各建一条独立分支，状态数从 1 涨到 30 多，而且每加一个关键字就要重画整张图。

标准做法是把这一步推到 DFA 之外：DFA 只管认出「这是一个标识符形状的串」，扫完之后拿字符串去查关键字表，命中就改类型，不命中就是普通标识符。上面代码里的elif ttype == 'IDENT' and text in KEYWORDS就是这一步。

KEYWORDS用set而不是list，是因为这是每个标识符都要走一次的热路径，set的查找是 O(1)，list是 O(n)。8 个关键字看不出区别，等到语言有 50 个关键字、源文件有几万行的时候，这个差别会体现在编译耗时上。

注意：关键字表必须和 DFA 里的标识符规则保持一致。如果哪天把$加进标识符的允许字符集，别忘了KEYWORDS里不能出现带$的词——否则那条关键字分支永远走不到，排查起来很难想到是这个原因。

DELIMS的判定放在最后一步做，是因为SINGLE状态把运算符和分界符合并了，必须回查字符集合才能区分。这个回查代价很小（一次set查找），换来的是状态表少 9 行。

4. 错误报告与 lex.txt：行列号定位、非法字符和落盘格式

4.1 行列号跟踪：一次扫描、一个 step_pos

实验要求「报告词法错误及其位置」，位置至少要到行。最省事的做法是扫完整个文件后用src[:start].count('\n')反推，但那是 O(n²)，几万行就卡住了。正确做法是在主循环里维护line和col，每消费掉一段字符就推进一次。

def step_pos(chunk, line, col): """按消费掉的字符片段推进行列号，换行时列号归 1""" for ch in chunk: if ch == '\n': line, col = line + 1, 1 else: col += 1 return line, col

这个函数接收的是「本次实际消费的字符」，不是「本次识别出的 Token」。区别在于空白和注释也要推进位置——//开头的注释整行被吞掉，如果不用它推进，后面所有 Token 的行号都会少算。所以主循环里写的是step_pos(src[start:j], s_line, s_col)，j是最终游标，包含被丢弃的空白、注释，以及报错时吃掉的那一个非法字符。

col记录的是字符偏移，不是显示宽度。如果源文件里有制表符，报出来的列号和编辑器里看到的位置会对不上。要做得更细，就在\t分支里按 4 或 8 补齐，但\t在不同编辑器下宽度不同，报错位置本来就不可能处处精确，我一般选择直接在输出里标注「列号按字符计」，省掉这块玄学。

s_line和s_col是在每轮外层循环开头就存档的，不是用当前值。因为内层循环会把j推到很远，但错误要报在单词起始的位置——123@里的@应该报在第 5 列（123之后），而不是报在整个 Token 的起点。

4.2 lex.txt 的落盘格式：一行一个 Token 还是对齐三元组

报告要求「将合法单词存入 lex.txt」。格式没人管，但格式选得对不对，直接决定你后面调试语法分析时好不好受。三种常见选择：

第一种最实用。写出来只要十来行：

def dump(tokens, errors, path='lex.txt'): with open(path, 'w', encoding='utf-8') as f: for ttype, text, ln, col in tokens: # 用冒号分隔，文本里出现空格也不会串行 f.write(f'{ln}:{col}\t{ttype}\t{text}\n') if errors: f.write('\n-- 词法错误 --\n') for e in errors: f.write(f'{e["line"]}:{e["col"]}\t{e["msg"]}\t{e["text"]}\n')

\t做分隔符而不是空格，是因为 Token 的文本本身可能是空格以外的一切字符，用空格分隔时abc def这类输入一旦出现异常切分，读回来就分不清哪部分是值、哪部分是后续字段。encoding='utf-8'显式写死，是为了避免在 Windows 上默认走gbk导致中文注释行写不进去——这是个只在别人机器上复现的坑，本地跑一百遍都不会有事。

错误单独用一段写在同一份文件里，而不是另开一个error.txt。理由是词法错误和 Token 流有严格的先后关系，分两个文件之后你要靠行号手工关联，非常麻烦。分隔行-- 词法错误 --让下游解析可以按这行一刀切开。

4.3 最长匹配的四个自测用例

报告里有一段int x; if (x > 0) { write x + 1; }的示例输出，但这段输入太干净，覆盖不到最容易出问题的地方。我一般会自备一组用例，跑完对着输出逐条核：

CASES = [ 'a >= b;', # 必须是 OP '>=' 而不是 OP '>' 加 OP '=' 'a <= b;', # 同上，注意 < 和 <= 'a == b;', # 双等号不是两个赋值号 'a != b;', # ! 单独非法，!= 才合法 'x = y / 2;', # / 是除号 '// x = y / 2', # 整行是注释，一个 Token 都不出 'n 0123;', # 前导零，应该报错 'q 123@;', # @ 非法，位置要报在第 5 列 ]

a >= b;和a == b;这两条是检验最长匹配的唯一标准。如果输出里出现OP '>'紧跟OP '='，说明last_accept的回退没生效，或者GT状态没有EQ这条转移。

x = y / 2;和// x = y / 2这两条检验的是/的二义性。第一行必须切出OP '/'，第二行必须一个 Token 都不出。这两条放一起看，才能确认注释判定不是靠「第一个字符是/」这种粗暴条件。

n 0123;和q 123@;检验错误分支。前者的问题在规则层（正则里已经排除了前导零），后者的问题在状态层（@没有对应转移）。两种错误走的是完全不同的代码路径，必须分开验。

跑完这组用例，再把报告里那段带abc123$、123@、2a、012345的完整程序喂进去，看输出是否符合报告正文里给出的结论。对不上的地方，八成就是下面第 5 章那几个坑。

5. 避坑与排查：注释符、前导零和 2a 这几个坑不踩一遍不会懂

5.1 坑一：标识符状态自环太宽，吞掉运算符

现象：输入x+1输出一个 TokenIDENT 'x+1'，输入abc = ab c* i输出IDENT 'abc'、OP '='、IDENT 'ab'、IDENT 'c'、OP '*'、IDENT 'i'看起来还算正常，但只要运算符紧贴标识符没有空格，就会被并进前一个 Token。

原因：实验报告原始的转移表里，ID这一行写的是{'ALPHABET': 'ID', 'DIGIT': 'ID', 'OPERATOR_DELIMITER': 'ID', 'SLASH': 'ID', 'OTHER': 'ERROR'}。也就是说标识符状态收到运算符、斜杠、甚至未知字符都不会停下来，一直自环下去。这不是最长匹配做过头了，是这个状态压根没有「终态」的概念。

解决：ID状态只保留两条出边，ALPHA和DIGIT自环，其他类别一律无转移。同时把最长匹配交给last_accept回退机制去处理，而不是靠状态表本身去阻止。改完之后的ID行只有两个键，x+1会正确切成IDENT 'x'、OP '+'、NUM '1'。

顺带说一句：原始代码里OPERATOR和DELIMITER两个状态也是自环的，a+-*/b会被并成一个OPERATORToken。同理，这两个状态只该有「无后续」这一种可能。

5.2 坑二：/到底是除号还是单行注释

现象：x = a / b;里的/被当成注释开头，整行后半截被吞掉，Token 流从a直接跳到下一行；或者反过来，// comment被切成一个OP '/'加一个OP '/'。

原因：这两个词法单元共享第一个字符，只看一个字符无法判定。实验报告的调试记录里写的「在遇到符号 / 时无法判断是单行注释符还是除运算符号」，说的就是这个。

解决：/一定要走两步。第一步从START到SLASH，此时已经可以当成除号接受（SLASH是终态）；第二步再看下一个字符，如果是/就进COMMENT。代码上只需要在状态表里加两行：

'slash 分支：先接受成除号，再看能不能凑成注释' 'SLASH': {'SLASH': 'COMMENT'}, # 第二个 / 才进注释 'COMMENT': {}, # 行尾由扫描器直接跳到 \n

SLASH同时在ACCEPT里登记为OP，意味着a / b这种除号不用特殊处理，last_accept自然会在读到空格时回退到/。而//的情况，第二步进了COMMENT后会覆盖last并跳出，整行不产 Token。这样两种语义共用同一条入口，不需要在扫描前做「这行有没有//」的预判。

5.3 坑三：012345被当成合法整数

现象：源程序里写abc = 012345;，扫出来是NUM '012345'，报告里的错误列表却是空的。

原因：这条错误在规则层面就该被挡住，但代码里的NUM状态只有一个DIGIT自环，从0起步之后不管后面跟几个数字全都接受，等于把「允许前导零」写进了状态机。正则表达式写了(1|…|9)(0|…|9)*|0，状态机没跟上。

解决：两个选择。一是把NUM拆成两个状态，START收到0直接进终态ZERO，ZERO只允许后面跟非数字（跟数字就报错）；二是状态机不管，扫完之后做一次字符串检查。我倾向于后者，因为它不增加状态数，而且错误信息更好写：

if ttype == 'NUM' and len(text) > 1 and text[0] == '0': errors.append({'line': s_line, 'col': s_col, 'text': text, 'msg': '无符号整数不能有前导零'})

这行代码放在 Token 切出来之后、写进tokens之前。注意条件是len(text) > 1，单独的0是合法的。这条检查在状态机外面做，好处是错误消息能精确描述问题，而不是笼统报「非法单词」。

5.4 坑四：2a和123@该报在哪、报几次

现象：报告正文说「标识符2a不符合标识符的命名规则」，但程序跑出来是NUM '2'紧跟IDENT 'a'，一个错误都没有；123@报的是一条NUM '123'加一条@非法，位置也不对。

原因：词法层严格来说没有「标识符命名规则」这个概念，它只认最长匹配。2a在词法上是两个合法单词，语法分析阶段才会报「两个表达式之间缺少运算符」。123@里的@确实非法，但它和前面的123是两个独立 Token，报错位置应该是@所在的那一列，而不是123的起始列。

解决：如果实验要求必须把2a报成词法错误，就在NUM出 Token 之后加一条粘连检查——下一个字符如果是字母，说明数字和标识符粘在一起了：

已切出 NUM，且 j < n 且 src[j].isalpha() -> errors.append({'msg': '数字后直接跟字母，疑似非法标识符', ...})

123@的情况反过来，正确的输出是两条记录：NUM '123'进tokens，@进errors，位置取@自己的列号。这里容易翻车的点是「一个非法字符要不要跳过」——必须跳过并继续扫，否则后面的;、}全部连带丢光，你看到的错误列表会莫名其妙地少一大截。

5.5 坑五：!单独出现时状态机卡死

现象：源程序里写a ! b，程序不返回，或者直接抛 KeyError。

原因：BANG状态不是终态，last一直是None；内层循环在下一个字符（空格）上跳不动，j停在原地，外层while的i没有前进，死循环。

解决：last is None这个分支里必须有兜底前进。上面 3.2 节代码里的if j == start: j = start + 1就是干这个的——只要确认本轮一个字符都没被接受，就强行吃掉一个字符并记一条错误。这里不要用while去试着「再找找」，词法层遇到无法启动的字符就是错误，多试只会把后面的正确 Token 一起拖下水。

6. 二次开发：把实验代码改成表驱动、可扩展的扫描器

实验做完，代码能跑，但离能用还差一步：状态表硬编码在 Python 源码里。加一个+=运算符要改三处——category()加分支、DFA加行、ACCEPT加键，改漏一处就是运行时才发现的隐性 bug。我一般会把状态表抽成独立的 JSON，扫描器只认表不认规则：

抽表的做法很直接：把DFA、ACCEPT、KEYWORDS三个结构序列化成

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