词法分析基础：正则表达式与有限自动机

各位同学，今天我们来聊聊编译器里最基础、也最容易被忽视的一环——词法分析。说白了，就是把源代码那串长长的字符，拆成一个个有意义的“词”，也就是Token流。

我刚开始做编译器的时候，觉得这步太简单了，不就是字符串切割吗？后来踩了坑才发现，这里面的门道比想象中深得多。你想想看，一个if关键字和一个变量名if_else，怎么区分？嵌套注释怎么处理？这些都得靠正则表达式和有限自动机来解决。

从字符串到Token：第一道工序

编译器拿到源代码，第一件事就是词法分析。它把字符流变成Token流，就像把一堆乐高零件按颜色分类。

Token通常包含这几类：

• 关键字：if、else、while、return等
• 标识符：变量名、函数名，比如myVar、calculate
• 字面量：数字42、字符串"hello"
• 运算符：+、-、*、==
• 分隔符：;、{、}、(、)

每个Token还附带位置信息（行号、列号），方便报错时定位。嗯，这个细节很多初学者会忽略，但实际项目中调试时特别有用。

正则表达式：描述词法的语言

正则表达式是描述字符串模式的利器。比如标识符的规则：以字母或下划线开头，后面跟字母、数字或下划线。用正则写就是[a-zA-Z_][a-zA-Z0-9_]*。

我个人习惯把词法规则先写成一组正则表达式，然后逐个匹配。比如：

关键字：   if|else|while|return|int|float
标识符：   [a-zA-Z_][a-zA-Z0-9_]*
数字：     [0-9]+(\.[0-9]+)?
运算符：   \+|-|\*|/|==|!=|<|>|<=|>=
分隔符：   ;|,|\(|\)|\{|\}

这里有个坑：正则匹配的顺序很重要。比如if既是关键字，也符合标识符的规则。所以必须先匹配关键字，再匹配标识符。我曾经在项目里因为顺序搞反，导致所有if都被当成变量名，编译出来的程序逻辑全乱了。

有限自动机：正则的底层实现

正则表达式虽然方便，但计算机不能直接理解它。我们需要把正则转换成有限自动机（Finite Automaton）。

有限自动机分两种：

• NFA（非确定有限自动机）：同一个状态，读入同一个字符，可能跳到多个状态。或者可以不读字符就跳转（ε转移）。
• DFA（确定有限自动机）：每个状态对每个输入字符，只有唯一的下一个状态。没有ε转移。

DFA执行效率高，但构造起来复杂。NFA构造简单，但执行时可能有多个分支，需要回溯。实际编译器里，通常先把正则转成NFA，再把NFA转成DFA。

从正则到NFA：Thompson构造法

Thompson构造法是一种经典算法。它把每个正则表达式片段，都对应一个小的NFA子图，然后通过ε转移把它们拼起来。

举个例子，正则a|b对应的NFA是这样的：

开始状态 --ε--> 状态A --a--> 接受状态
         --ε--> 状态B --b--> 接受状态

而ab（连接）则是：

开始状态 --a--> 中间状态 --b--> 接受状态

闭包a*更巧妙：

开始状态 --ε--> 状态A --a--> 状态A
         --ε--> 接受状态
状态A --ε--> 接受状态

我在项目中实现词法分析器时，就是用Thompson构造法生成NFA。虽然代码量不大，但调试起来挺费劲的——NFA的状态图一复杂，肉眼根本看不清楚。后来我写了个小工具，把NFA可视化出来，这才好多了。

从NFA到DFA：子集构造法

NFA执行时，同一时刻可能处于多个状态。子集构造法的思路是：把NFA的状态集合，映射成DFA的单个状态。

比如NFA在状态{1, 2, 3}，读入字符'a'后，能到达的状态是{2, 4, 5}。那么DFA中，{1,2,3}就是一个状态，{2,4,5}是另一个状态。

这个过程需要计算ε闭包——从某个状态出发，通过ε转移能到达的所有状态。嗯，这里要注意，ε闭包包含状态本身。

DFA构造完成后，每个状态对每个输入字符都有唯一转移。执行时只需要顺着状态图走一遍，效率极高。

实际词法分析器的设计

一个实用的词法分析器，通常不是只用一个DFA。我建议的做法是：

1. 为每种Token类型（关键字、标识符、数字等）分别构造DFA
2. 用一个主循环，逐个字符读取，尝试匹配所有DFA
3. 匹配到最长前缀后，生成一个Token，然后重置状态继续

这里有个关键点：最长匹配原则。比如intVar，应该匹配成标识符intVar，而不是先匹配关键字int再匹配Var。所以词法分析器要“贪心”地读入尽可能多的字符，直到无法继续匹配为止。

知识体系总览

下面这张图展示了词法分析的核心流程，从源代码到Token流的完整路径：

这张图把整个流程串起来了：源代码经过正则表达式描述，转成NFA，再转成DFA，最后词法分析器执行DFA，输出Token流给语法分析器。

避坑指南

最后分享几个我踩过的坑：

• 状态爆炸：NFA转DFA时，如果正则写得不好，DFA状态数可能指数级增长。我曾经处理一个复杂的字符串字面量正则，结果DFA有上千个状态，内存直接爆了。后来把正则拆成多个小正则，逐个匹配，问题就解决了。
• 回溯陷阱：直接用NFA匹配时，如果遇到歧义，可能需要回溯。比如a*a匹配aaa，NFA会尝试各种组合。DFA没有这个问题，因为它每个状态只有唯一转移。
• 错误恢复：词法错误（比如非法字符）怎么处理？我建议的做法是：跳过当前字符，记录错误，然后继续分析。这样一次编译能发现多个错误，用户体验更好。

好了，词法分析的基础就讲到这里。记住，写词法分析器时，先想清楚Token的种类和规则，再动手实现。别像我当年一样，上来就写代码，结果改来改去，浪费了好多时间。

可可精品资料库