词法分析——有限自动机
本文中我们研究如何使用有限状态自动机进行词法分析。 有限状态机（Finite State Machine, FSM）、有限状态自动机（Finite State Automaton，FSA）和有限（有穷）自动机（Finite Automaton）的所指基本相同1，本文不加以区分。
有限状态自动机
有穷自动机和状态转移图类似，只是有以下一点不同： 自动机是识别器，它们对每个输入串只能回答“是”（到达接受状态）或“否”（不能到达接受状态）。 不同于转移图，它们不能在到达某个状态后执行操作。
形式化地说，有穷自动机是一个五元组$(\Sigma, S, s_0, \delta , F)$。 $\Sigma$是一个有限非空集合，称为字母表； $S$是一个有限非空集合，称为状态集； $s_0 \in S$称为开始状态； $\delta$是一个从$S \times \Sigma$到$S$的一个元素（值域为$S$）或一个子集（值域为$S$的幂集，记为$2^S$）的映射，称为状态转移函数； $F$为接受状态的集合，可以为空。 特别地，如果$\delta$的像是状态（即$S$的元素）且字母表中不含空串，那么称这个自动机是确定的； 如果$\delta$的像是状态的集合（即$S$的子集）或字母表中含有空串$\epsilon$，那么称这个自动机是非确定的。
所谓确定有穷自动机（Deterministic FA，DFA），就是给出目前状态和输入，可以确定下一个状态； 所谓非确定有穷自动机（Non-deterministic FA，NFA），就是给出目前状态和输入，不能确定下一个状态，只能确定可能的下一个状态（即状态的集合）。 由于空串可能在边的标号上存在，所以即使状态转移函数的像都是单个状态，依然不能唯一确定下一个状态。 含有空串的NFA也叫NFA-ε。
虽然如此分类，实际上确定和非确定的有穷自动机能识别的语言是相同的，且通常我们希望将NFA转化为DFA，因为模拟DFA远比模拟NFA方便。 本文后面会介绍将转化的方法。
如果对于输入字符串，存在至少一条到达接受状态的路径，使得路径上的标号连接起来和输入字符串相同，那么称该自动机可以接受这个字符串。 注意路径上可以存在空串$\epsilon$，空串在连接时会消失。 对于同一个自动机和输入串，可能存在多条到达接受状态的路径，也可能同时存在到达非接受状态的路径，但是只要存在可以到达接受状态的路径就可以接受。
通常我们认为函数$\delta$是一个偏映射，这就是说对某些输入$(s,a)$，$\delta(s,a)$可能没有定义。 此时自动机不进行状态转换而是直接拒绝这个串。 我们可以引入一个特殊的状态来表示“直接拒绝”，并把所有未定义的$\delta(s,a)$指向这个状态，然后让这个状态的所有出边都指向自己。 出于简单考虑，我们特别规定，对DFA$\delta$应该是全映射，即对所有状态和输入都有定义。
转换图与转换表
接下来我们介绍两种表示自动机的方式：转换图和转换表。
不难发现，自动机和状态转移图非常相似，因此我们可以用类似状态转移图的方式来表示一个自动机。
沿用之前的规定，我们把接受状态用两层圆表示。
从状态s到状态t之间存在一条标号为a的边，当且仅当$t = \delta (s, a)$或$t \in \delta (s, a)$。
自动机的转换图和状态转移图之间的区别就是对同一输入和状态，可以有多条出边，同时空串$\epsilon$也可以出现在标号上。
上图就是一个NFA的转换图。
可以注意到对于状态0，输入a，有两条不同的出边。
这个NFA可以接受所有满足正则表达式(a|b)*abb的输入。
我们将在下一章如何从正则表达式产生NFA。
不难发现，自动机的关键在于其状态转移函数$\delta$。 对于所有可能的状态和输入，我们可以以列表的方式展示这个函数。 我们规定这张表的行对应状态，列对应输入符号（和$\epsilon$），把它称作转换表。 假设字母表为$\{a,b,c\}$， 上图所示自动机可表示为下面这张表：
| 状态 | a | b | c |
|---|---|---|---|
| 0 | 0,1 | 0 | $\emptyset$ |
| 1 | $\emptyset$ | 2 | $\emptyset$ |
| 2 | $\emptyset$ | 3 | $\emptyset$ |
| 3 | $\emptyset$ | $\emptyset$ | $\emptyset$ |
$\emptyset$表示目标状态没有定义，从而如果出现这种情况就直接拒绝。 如果字母表很大，那么状态表也会很大； 如果同时还有大量的转换没有定义，那么会浪费大量的空间。
模拟DFA
我们知道，DFA是一种特殊的有穷自动机，其边上不含空串，且对每个状态和每个符号至多只有一条出边。 我们又规定了对DFA其状态转移应是全映射，因此这样的出边有且仅有一条。 这些性质表明当前状态有且仅有一个，因此称为确定的有穷自动机。 如果用转换表来书写DFA，那么每一格中有且只有一个状态，因此其模拟非常简单。
下面这个算法可以用来模拟DFA：
s = s0;
c = nextchar();
while( c != '\0')
{
s = delta(s,c);
c = nextchar();
}
return isaccepted(s);
从正则表达式到自动机
虽然模拟DFA相较于模拟NFA更加简单且快速，NFA的构造却比DFA简捷且更加直观。 因此我们先以NFA为桥梁研究，先考察NFA到DFA的转化，在考察NFA的模拟，最后给出从正则表达式构造NFA的方式。
从NFA到DFA
从NFA到DFA转换的基本思想就是，如果在NFA中，当前状态是所有状态的子集，那么为所有状态的子集构造一个新的状态，当前状态就被确定了。 这种构造的思路称为子集构造法。 原则上讲，通过这种方式构造的DFA的状态数是关于NFA状态数的指数函数，然而对大部分现实语言而言，其构造的DFA和NFA的状态数基本相同。
为了计算可能的状态子集，我们不得不仔细考察空串对状态转移的影响。 为此，我们需要定义ε-闭包：
我们称所有能从状态$s$只经过标号为$\epsilon$的边到达的状态的集合为状态$s$的ε-闭包，记为$\epsilon{\text -}closure(s)$. 设$T$是状态的集合，则$\epsilon{\text -}closure(T) = \cup_{s \in T} \epsilon{\text -}closure(s)$。
我们用以下算法从NFA构造DFA，返回DFA的状态转移表。
Dstates = empty_set();
Dstates.insert(eps_closure(s0));
while(!Dstates.unmarked().empty())
{
T = Dstates.unmarked().begin(); // 只选择未标记的状态集合，防止重复计算
Dstates.mark(T);
for(const auto & symb : alphabet)
{
// 计算从T用symb可转移到的所有状态
_U = empty_set();
for(const auto & state : T)
_U.insert(move(state, symb));
U = eps_closure(_U); // 计算闭包
if(!Dstates.find(U))
Dstates.insert(U); // 此时U应该是未标记的
Dtrans[T][a] = U;
}
}
return Dtrans;
接下来我们给出计算闭包的方法：
for(const auto & state : T)
stack.push(state);
closure = T;
while(!stack.empty())
{
t = stack.top();
stack.pop();
// 对每个可从t经过空串到达的状态...
for(const auto & state : Trans[t]['\0'])
{
closure.insert(state);
stack.push(state);
}
}
return closure;
我们知道，在NFA中只要存在一条到达接受状态的路径就可以接受此串，因此对应NFA的状态集合中只要含有接受状态，新产生的DFA的状态就是接受状态。
现在我们以下述NFA为例计算其对应的DFA。
这个NFA对应正则表达式(a|b)*abb。
首先我们计算初始状态的闭包：$A=\{0,1,2,4,7\}$。
然后我们计算这个状态的转移函数。
如果输入为a，那么可达的状态为$B^\prime=\{3,8\}$，其闭包为$B=\{1,2,3,4,6,7,8\}$。
如果输入为b，那么可达的状态为$C^\prime=\{4\}$，其闭包为$C=\{1,2,4,5,6,7\}$。
现在设当前状态为$B$，如果输入为a，那么可达的状态仍为$B^\prime$，其闭包仍为$B$。
如果输入为b，那么可达状态为$D^\prime=\{5,9\}$，其闭包为$D=\{1,2,3,4,5,6,7,9\}$。
重复以上步骤，即可得到DFA的转移表：
| NFA状态 | DFA状态 | a |
b |
|---|---|---|---|
| 0,1,2,4,7 | A | B | C |
| 1,2,3,4,6,7,8 | B | B | D |
| 1,2,4,5,6,7 | C | B | C |
| 1,2,4,5,6,7,9 | D | B | E |
| 1,2,4,5,6,7,10 | E | B | C |
注意NFA状态10在DFA状态E中，因此状态E是新DFA的接受状态。
模拟NFA
借助子集构造法的思想，我们可以直接模拟NFA： 首先，当前状态不再是单个状态，而是状态集合； 其次，初始状态从单个状态变成初始状态的闭包； 然后，进行状态转移时，需要求所有当前状态的转移，并取闭包； 最后，结束时需要判定可接受状态是否在当前状态集合中，而不是判定等于。
这个算法中最大的时间花费为状态转移，我们将利用滚动的思想提出一种简捷快速的实现方法。 我们需要以下三个数据结构：
- 用于描述NFA的状态转移表
trans，表示为一个含有指向链表的指针的二维数组，索引分别为当前状态序号和输入。 链表储存了所有可达状态的序号。 - 两个栈，用来表示状态集合。堆栈
oldStack表示当前状态集合，newStack表示下一个状态集合。 - 以状态序号为下标的布尔数组
inStack，表示某个状态是否在newStack中。 维护这个数组可以避免反复遍历堆栈以确定某个状态是否在栈中。
接下来我们提出一个函数，用来递归地向newStack中添加状态：
void addState(s)
{
newStack.push(s);
inStack[s] = true;
for(const auto & ns : trans[s]['\0'])
{
if(!inStack[ns])
addState(ns);
}
}
然后我们用以下代码替换状态转移：
while(!oldStack.empty())
{
s = oldStack.top();
for(const auto & ns : trans[s][c])
{
if(!inStack[ns])
addState(ns);
}
oldStack.pop();
}
while(!newStack.empty())
{
s = newStack.top();
oldStack.push(s);
inStack[s] = false;
newStack.pop();
}
设转移图上的点集为$V$，边集为$E$，那么进行单次状态转移的时间复杂度为$\mathcal O \left(\left| V \right|+\left| E \right|\right)$。 从而总的时间复杂度为$\mathcal O \left(k \left( \left| V \right|+\left| E \right|\right)\right)$，其中$k$为输入的长度。
由正则表达式构造NFA
接下来我们介绍一个归纳地从正则表达式构造NFA的算法，称为McMaughton-Yamada-Thompson算法。 我们设正则表达式$r$所对应的语言为$L(r)$，对应的NFA为$N(r)$。 设$N$为一NFA，则其开始状态表示为$I(N)$，结束状态表示为$F(N)$。 用此算法构造的NFA只有一个开始状态和一个接受状态，因此这种表示不会产生歧义。
- 对匹配空串或单个字母表中元素的正则表达式，直接构造开始状态和接受状态，并在两个状态之间用对应字母标号连边即可。
- 设$r = s|t$，则$N(r)$按以下方法构造：
- 构造两个新状态$I(N(r)) = i$,$F(N(r)) = f$；注意$N(s)$和$N(t)$中的开始和接受状态不再是$N(r)$中的开始和接受状态。
- 从$i$向$I(N(s))$和$F(N(t))$连边，标号为$\epsilon$。
- 从$F(N(s))$和$F(N(t))$向$f$连边，标号为$\epsilon$。
- 设$r = st$，即两个表达式的连接，则$N(r)$按以下方法构造：
- 令$I(N(r)) = I(N(s))$，$F(N(r)) = F(N(t))$。
- 合并$F(N(s))$和$I(N(t))$两个状态，保留两个状态的所有转换。
我们可以说明按此算法构造的自动机的开始状态没有入边（用来标记开始状态的
START边不是实际意义上的转换），接受状态没有出边，因此这个合并不会产生问题。
- 设$r = s^*$，则$N(r)$按以下方法构造：
- 构造两个新状态$I(N(r)) = i$,$F(N(r)) = f$。
- 从$I(N(r))$向$I(N(s))$和$f$连接两条标号为$\epsilon$的边。
- 从$F(N(s))$向$i$和$I(N(s))$连接两条标号为$\epsilon$的边。
- 设$r = (s)$，则$N(r) = N(s)$。
为了执行这个算法，我们需要先把正则表达式拆分成子表达式，然后递归地应用上述算法。 我们可以借助语法分析实现这一目标：先构造正则表达式的语法分析树，然后自底向上地执行这个算法。
此前在介绍NFA向DFA的转换时使用过一个例子：
这个自动机就是用上述算法构造出来的，对应的正则表达式为(a|b)*abb。
可以注意到我们先生成了a|b的自动机，又生成了(a|b)*的自动机，最后把它们拼接在一起。
总结
本文已经详细介绍了正则表达式识别所用的自动机，利用这些内容，已经可以构造通用的正则表达式识别器。 然而，为了进行词法分析，我们还需要一些额外内容，比如同时识别多个表达式（就是识别不同语法单元），并确定其优先级。 此外，我们可能还需要让自动机识别向前看指针。 最后，我们还希望尽可能地优化自动机以降低所需的运算量。 这些主题都将包含在下一篇文章中。
-
准确地说，本文研究的是自动机的一个子集：识别器。参见有限状态机（维基百科）。 ↩