词法分析——有限自动机进阶

有穷自动机的时间复杂度

我们设正则表达式为$r$，其大小为$\left| r \right|$。正则表达式的大小是其运算符和运算分量的长度的总和。输入串为$x$，其长度为$\left| x \right|$。那么NFA和DFA的时间复杂度如下表所示：

自动机	构造自动机	识别字符串
NFA	$\mathcal O ( \|r\| )$	$\mathcal O ( \|r\| \times \|x\| )$
DFA（平均）	$\mathcal O ( \|r\|^3 )$	$\mathcal O ( \| x \| )$
DFA（最坏）	$\mathcal O ( \|r\|^2 2^{\|r\|} )$	$\mathcal O ( \| x \| )$

不难发现，NFA的构造非常迅速，而DFA的识别更加快速。因此，对于有大规模输入的词法分析器，我们通常使用DFA而非NFA；而对于只使用一次的情况，如grep命令，则通常采用NFA。

还有一种方法可以实现NFA和DFA的折中：使用记忆化方法。我们先构造NFA，然后记录用到的状态集合和其转移。如果再遇到同样的状态集合，就不用重新计算了。

用于词法分析器的有穷自动机

我们此前介绍的NFA和DFA已经足以用来识别所有用于词法分析的模式。然而要用这些自动机来解决词法分析仍然需要一些补充。本节将解决这些问题。

基于NFA的词法分析

为了利用NFA进行词法分析，首先我们需要解决如何同时匹配多个正则表达式的问题。我们可以先把每个正则表达式的NFA构造出来，构造一个新的开始状态，然后用标号为空串的边把每个正则表达式的NFA的开始状态连接起来。

下图就是一个可识别a、abb和a*b+的NFA，注意a*b+的NFA不是用前一篇文章中的算法构造出来的。

现在我们还需要解决优先级的问题。对于字符串abbbbb，三个正则表达式都可以识别，此时应输出哪个词法单元呢？通常来说，我们优先识别前缀最长的，也就是a*b+。如果此时仍然存在多个可识别的表达式，那么我们按照给出的先后顺序识别。如果字符串为abb，那么识别abb而非a*b+。

现在我们给出一个算法用来处理这种情况。

在模拟NFA时，我们保存途径的所有状态和转移。模拟过程中，我们总是会到达一个状态，此时再输入一个符号就会导致当前状态集合为空（也就是前一个状态集合中所有状态都没有可用的转移）。这个时候，我们就沿着保存的状态向前查找，直到找到至少一个接受状态为止。

比如我们用上述NFA识别aaba这个字符串，其途径的状态分别为： $\{0,1,3,7\} \xrightarrow{a} \{2,4,7\} \xrightarrow{a} \{7\} \xrightarrow{b} \{8\} \xrightarrow{a}$ 到达8这个状态之后，对给定的输入已经没有可转移的状态了。此时我们沿着路径向前寻找，可以发现两个接受状态（2和8）。最靠近末尾的状态是8，对应识别a*b+。如果最后含有接受状态的状态集合中含有多个接受状态，那么我们按接受状态对应的表达式的先后顺序识别即可。

基于DFA的词法分析

我们已经知道，在词法分析中通常使用DFA而非NFA，现在我们考虑如何把上面的讨论应用到DFA上。实际上，我们只要把维护状态集合的路径变成维护状态的路径即可。严格地说，对DFA，不存在没有可用转移的情况，而是以一个特殊的状态取而代之（参见上一篇文章），我们把这个状态称为死状态，用空集符号表示。我们会在DFA的优化一节中详细讨论死状态的产生与消除。

除此之外，如果这个DFA是由NFA生成的，那么在构造DFA的接受状态时还要记录对应的正则表达式。回忆一下，从NFA生成DFA时，只要DFA的状态对应的NFA的状态集合中含有至少一个接受状态，那么对应DFA的状态也是接受状态。这个时候，我们需要把NFA的状态集合中的所有接受状态对应的正则表达式都记录到DFA对应状态中。可能会出现一个DFA接受状态对应多个正则表达式的情况，这个时候我们还是优先识别在正则定义中先出现的。比如在上述NFA生成DFA时，会产生一个状态，其对应状态集合为$\{6,8\}$，这个状态既能接受abb又能接受a*b+，因此在DFA中是一个接受状态。因为abb先出现，因此DFA中这个状态接受的模式为abb。

我们知道，如果按照上述算法执行直到没有转移（转移到死状态），那么一定会匹配最长的前缀。我们又保证了最长前缀对应多个表达式时优先匹配先出现的，因此这个算法的优先级和此前定义的一样。

我们用生成的DFA匹配相同的字符串，其状态路径为： $0137 \xrightarrow{a} 247 \xrightarrow{a} 7 \xrightarrow{b} 8 \xrightarrow{a} \emptyset$ 此处状态$0137$表示由NFA中状态集合$\{0,1,3,7\}$生成的DFA状态。到达空状态后我们沿着路径回溯，可以发现第一个接受状态为$8$，对应正则表达式为a*b+。

向前看运算符

有些时候，我们需要知道一个词素后面紧跟着的部分，才能判定这个词素的语法单元名，这种情况尤其容易出现在关键字不是保留字的语言中。比如在Fortran中，IF(I,J)=3表示对名为IF的数组赋值，而IF ( condition ) THEN才是条件判断语句。如果要识别这种词素，我们必须知道IF后面的部分。这个时候，我们需要引入向前看运算符，写作斜线（/）。

比如要识别IF，我们的正则表达式可以写为IF / ( .* ) letter，其中.*表示匹配任意字符任意多次，letter表示一个字母。这表示匹配到IF之后，再向前看几个字符，只有斜线前后都被匹配时才表明匹配了这个语法单元，但是斜线之后的部分不是这个词素的一部分。

在构造自动机时，我们直接把斜线当作空串处理。而在发生匹配时，我们必须仔细寻找满足以下四点的状态s：

在s上存在一个空串的转换；
对给定的输入，存在一个从开始状态到s的转换，匹配输入的一个前缀；
对给定的输入，存在一个从s到接受状态的转换，匹配输入的一个后缀；
如果存在多个满足以上条件的状态，选择前缀最长者。

此时我们把从开始状态到s状态所经过的边的标号连接起来，形成输入的一个前缀，这个前缀才是匹配的词素。

如果在这个s状态上只有一个代表/的空串转换，那么词素的末尾就是最后一次进入该状态的位置。如果存在多个这样的转换，则识别会相当复杂。

对DFA的实现，一个简单的思路就是把正则表达式分为r1/r2两个部分，分别为r1r2和r1构造自动机，只有识别到r1r2后再识别r1。但这种算法也有一些问题，尤其不能处理r1和r2有重合的情况，比如对a*/a这个模式，如果使用这个方法就会识别出额外的字符。

关于向前看（以及某些正则表达式引擎中支持的向后看）运算符的更多内容，可参考这篇讨论。

有穷自动机的优化

本章从三个方面介绍有穷自动机的优化：直接从正则表达式构建状态数更少的DFA；最小化DFA的状态数目；表示DFA的状态转换的更优方法。

在此之前，我们先介绍几个重要的概念。

重要状态与四个函数

首先让我们考虑一下从NFA构建DFA时的各种状态。我们注意到，只有在某一个状态$s$存在至少一条离开该状态的非空转换时，状态集合$move(s,a)$，即从该状态出发经过标号为$a$（非空）的边所指的状态集合，才可能是非空的。我们称这样的状态为重要状态。

基于同样的思想，在执行子集构造法时我们需要求状态集合的ε-闭包。当且仅当该状态集合中至少有一个重要状态时，这个闭包才是非空的。

在应用子集构造法时，两个NFA的状态集合可以认为是一致的，如果两个集合含有一样的重要状态，且它们要么都包含接受状态，要么都不包含。如果这个NFA是由前文所述的算法生成的，那么每个重要状态对应于正则表达式中的一个运算分量。

我们注意到，按前文所述算法构造生成的NFA的接受状态并不是重要状态，因为它没有出边。为解决这个问题，我们可以在正则表达式末尾附上一个唯一的符号，记为#，用来标记表达式的结束。这个符号不在原字母表中出现，因此不会干扰正则表达式的识别。这样的正则表达式，记为(r)#，称作原正则表达式r的增广正则表达式。

利用增广表达式，我们在处理NFA时就可以不再考虑接受状态的问题：任何有前往#状态的出边的状态都是原来的接受状态。

我们已经知道，每一个重要状态对应正则表达式中的一个运算分量，因此我们需要确定正则表达式的运算分量。以下是正则表达式(a|b)*abb#的抽象语法树（AST），注意cat表示字符串的拼接。

抽象语法树的叶子节点的标号可以为空$\epsilon$或任何字母表中的字母。对于每个非空的叶子节点，我们赋予其一个独特的整数，称为这个叶子节点的位置（position）。

四个由AST计算的函数

利用AST，我们可以计算增广表达式的以下四个函数，这些函数将用于直接从原正则表达式生成DFA。

$nullable(s)$对一个语法树结点$s$若为真，则其子表达式的语言中包含空串，也就是说这个子表达式可以匹配空串。
$firstpos(s)$表示对一个结点$s$，以其为根的子表达式的语言中的所有串的第一个符号所对应的位置的集合。
$lastpos(s)$表示对一个结点$s$，以其为根的子表达式的语言中的所有串的最后一个符号所对应的位置的集合。
$followpos(p)$的自变量是一个位置$p$，其值是位置的集合，由此定义： $followpos(p) = \left\{ q \in \text{Positions} \; \middle| \; \exists a_1 a_2 \dots a_n \in L(r\#), \text{such that} \; a_i \rightsquigarrow p, a_{i+1} \rightsquigarrow q \right\}$ 其中$a_i \rightsquigarrow p$表示符号$a_i$对应语法树中的$p$位置。这就是说，当串与增广表达式匹配时，可能跟随$p$位置的符号所在的位置的集合。

我们以上一节给出的AST为例说明这几个函数的计算。考虑对应表达式(a|b)*a的cat结点n，即3号位置的父结点。

$nullable(n)=\text{false}$，因为这个表达式不可能生成空串；相对地，其左子节点的值为真，因为(a|b)*可以匹配空串。
$firstpos(n)=\{1,2,3\}$，因为其对应的语言的开头可以是1号位置（形如aa），也可以是2号位置（形如ba），也可以是三号位置（a）。
$lastpos(n)=\{3\}$，因为其语言的结尾必须对应3号结点。

$followpos$的计算较为复杂，这里给出一个例子：$followpos(1)=\{1,2,3\}$。考虑一个匹配(a|b)*abb#的串...ac...，其中a来自1号位置。那么其紧跟着的字母可能来自子表达式(a|b)*，也可能来自表达式a。对于前者，其对应的位置为1，2；对于后者则为3。

计算这些函数

下表给出了递归计算前三个函数的方法。我们规定当前结点的位置（若有）为$i$，左子节点为$c_1$，右子节点为$c_2$。

结点类型	$nullable$	$firstpos$	$lastpos$
空叶子节点	$True$	$\emptyset$	$\emptyset$
=非空叶子节点	$False$	$\{i\}$	$\{i\}$
表示或`\|`的结点	$nullable(c_1)$ $\lor$ $nullable(c_2)$	$firstpos(c_1)$ $\cup$ $firstpos(c_2)$	$lastpos(c_1)$ $\cup$ $lastpos(c_2)$
表示连接的结点	$nullable(c_1)$ $\land$ $nullable(c_2)$	$\left\{\begin{aligned} &firstpos(c_1) \cup firstpos(c_2) \\& \quad , nullable(c_1) \\ &firstpos(c_1) \end{aligned}\right.$	$\left\{\begin{aligned} &lastpos(c_1) \cup lastpos(c_2) \\& \quad , nullable(c_2) \\ &lastpos(c_2) \end{aligned}\right.$
表示闭包`*`的结点	$True$	$firstpos(c_1)$	$lastpos(c_2)$

不难发现后两个函数的计算是高度对称的。

最后我们说明如何计算$followpos$。只有两种情况可能让表达式的某个位置跟在另一个位置之后：

连接：如果结点$n$是cat结点，那么 $\forall i \in lastpos(c_1), \; firstpos(c_2) \subset lastpos(i)$
闭包：如果结点$n$是*结点，那么 $\forall i \in lastpos(n), \; firstpos(n) \subset followpos(i)$

我们还知道a?和(ε|a)等价，a+和(a(a*))等价，因此也可以给出这两个运算的计算方法。

下图是根据AST计算的$firstpos$和$lastpos$的值。

接下来我们尝试计算$followpos$。首先，对所有cat结点，把右子节点的$firstpos$放到左子节点的$lastpos$的$followpos$中。对最低的cat结点，这说明3位置在1和2位置的$followpos$中。逐层向上，可以说明4在$followpos(3)$中，5在$followpos(4)$中，6在$followpos(5)$中。接下来，对所有的*结点，该节点的$firstpos$在其$lastpos$的$followpos$中。这说明1和2在1和2的$followpos$中。从而我们可以列出$followpos$的表格

n	followpos(n)
1	{1,2,3}
2	{1,2,3}
3	{4}
4	{5}
5	{6}
6	$\emptyset$

从正则表达式构建DFA

利用之前计算的函数，我们可以给出直接由正则表达式构造DFA的算法：

构造增广正则表达式(r)#的抽象语法树。
利用抽象语法树计算上面提到的四个函数。
执行以下算法，构造状态集合Dstates（每个状态表示为位置的集合）和转移函数Dtrans，记AST的根节点为n0：

start_state = firstpos[n0];
Dstates.insert(start_state);
while(!Dstates.unmarked().empty())
{
    // 标记状态避免重复
    const auto & S = Dstates.unmarked().begin();
    Dstates.mark(S);
    
    for(const auto & symb : alphabet)
    {
        auto U = empty_set();
        // U为S中和a对应的所有位置p的followpos的并集
        for(const auto & pos : S)
            if(pos.symb == symb)
                U.insert(followpos(pos));
        if(!Dstates.find(U))
            Dstates.insert(U);
        Dtrans[S][symb] = U;
    }
    
}
// 构造接受状态
fin_state = empty_set();
for(const auto & state : Dstates)
{
    for(const auto & pos : state)
    {
        if(pos.symb == '#') // 只要某个状态的位置中含有标记#，就是接受状态
            fin_state.insert(state);
    }
}

我们接着考虑上文的例子。这个增广表达式对应的根节点的$firstpos$为$\{1,2,3\}$，因此DFA的开始状态可记为123。接下来我们计算其状态转移。这个集合中对应a的位置为1、3，因此从该状态出发输入为a的转移状态为$followpos(1) \cup followpos(3) = \{1,2,3,4\}$。同理输入为b的转移为$followpos(2) =\{1,2,3\}$。注意最后会产生状态1236，这个状态是接受状态，因为位置6对应结束标记。

DFA的状态最小化

接下来我们介绍一个可以将DFA的状态数最小化的算法。首先说明一个定理：

如果忽略各个状态的名字不同，那么任何正则语言都有唯一的一个状态最小的DFA与之对应。

为了说明这个算法，我们首先引入区分的概念。

如果分别从状态s、t出发，沿着标号为x的边前进，到达的两个状态中只有一个状态是接受状态，那么我们称串x区分这两个状态。

比如空串$\epsilon$就可以区分任何接受状态和非接受状态。

这个算法的原理就是不停地用不同的串把DFA的所有状态划分成组，每个组内的状态用任意串都是不能区分的。把每个组合并成一个状态，就实现了状态的最小化。

我们设DFA的状态集合为S，其接受状态集合为F。

构造包含两个组$S-F$和$F$的分划$\Pi$。
构造新的分划$\Pi_{new}$：
1. 令$\Pi_{new} = \Pi$；
2. 对$\Pi$中的每个组$G$，将$G$划分成更小的组：状态$s$、$t$在同一小组中，当且仅当对所有字母，$s$和$t$都转移到同一小组；
3. 在$\Pi_{new}$中用新的$G$的分划代替$G$。
如果$\Pi_{new} = \Pi$，说明不能再产生新的分划，按下面的步骤构造新的DFA：
1. 新DFA的状态集合就是这个分划，分划中的每一组对应新DFA的一个状态，从这一组中选择一个作为代表状态；
2. 如果组中含有开始状态，那么新的状态也是开始状态；
3. 如果组中含有接受状态，那么新的状态也是接受状态；
4. 设$s$为某个组中的代表状态（任取一个状态即可），若其在某个字母输入后转移到的新状态在另一个组中，那么这两个组之间存在转移。

这个最小化算法可能会产生带有死状态的DFA。在原来的DFA中，可能存在一些状态，虽然不是死状态，但是一旦进入就不可能到达接受状态。这种状态在最小化时会被归纳到和死状态同组，因此会合并为一个状态。在最终的DFA中，我们可以省略掉到达死状态的转换，从而提前终止DFA。

词法分析器的状态最小化

在最小化DFA的状态数时，我们使用是否是接受状态进行初始分划。而在词法分析器中，这种分划是不足够的，因为我们需要识别不同的词法单元。这个时候，我们把识别同一词法单元的状态划分到一个组中，而不识别任何词法单元的状态单独成组。

结语

这篇文章，连同此前两篇，构成了构建基本的词法分析器的所有理论知识。我们以正则表达式为核心，介绍了识别它们的方式和如何利用它们构造词法分析器。关于正则表达式的更多内容，可参见这些博客。如果不想亲自编写一个用来识别词素的语法分析器，可以使用lex或flex工具，这些内容不在这篇文章的范围之内。想要构造一个编译器的前端，还有语法分析相关内容，这一部分就是下几篇文章的内容了。

Twitter Facebook LinkedIn

结点类型	$nullable$	$firstpos$	$lastpos$
空叶子节点	\(True\)	\(\emptyset\)	\(\emptyset\)
=非空叶子节点	\(False\)	\(\{i\}\)	\(\{i\}\)
表示或`\|`的结点	\(nullable(c_1)\) \(\lor\) \(nullable(c_2)\)	\(firstpos(c_1)\) \(\cup\) \(firstpos(c_2)\)	\(lastpos(c_1)\) \(\cup\) \(lastpos(c_2)\)
表示连接的结点	\(nullable(c_1)\) \(\land\) \(nullable(c_2)\)	\(\left\{\begin{aligned} &firstpos(c_1) \cup firstpos(c_2) \\& \quad , nullable(c_1) \\ &firstpos(c_1) \end{aligned}\right.\)	\(\left\{\begin{aligned} &lastpos(c_1) \cup lastpos(c_2) \\& \quad , nullable(c_2) \\ &lastpos(c_2) \end{aligned}\right.\)
表示闭包`*`的结点	\(True\)	\(firstpos(c_1)\)	\(lastpos(c_2)\)