mmmhj2

Es kommt darauf an, sie zu verändern.

词法分析——有限自动机

本文中我们研究如何使用有限状态自动机进行词法分析。 有限状态机（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： 首先，当前状态不再是单个状态，而是状态集合； 其次，初始状态从单个状态变成初始状态的闭包； 然后，进行状态转移时，需要求所有当前状态的转移，并取闭包； 最后，结束时需要判定可接受状态是否在当前状态集合中，而不是判定等于。

这个算法中最大的时间花费为状态转移，我们将利用滚动的思想提出一种简捷快速的实现方法。 我们需要以下三个数据结构：

  1. 用于描述NFA的状态转移表trans，表示为一个含有指向链表的指针的二维数组，索引分别为当前状态序号和输入。 链表储存了所有可达状态的序号。
  2. 两个栈，用来表示状态集合。堆栈oldStack表示当前状态集合，newStack表示下一个状态集合。
  3. 以状态序号为下标的布尔数组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只有一个开始状态和一个接受状态，因此这种表示不会产生歧义。

  1. 对匹配空串或单个字母表中元素的正则表达式，直接构造开始状态和接受状态，并在两个状态之间用对应字母标号连边即可。
  2. 设$r = s|t$，则$N(r)$按以下方法构造：
    1. 构造两个新状态$I(N(r)) = i$,$F(N(r)) = f$；注意$N(s)$和$N(t)$中的开始和接受状态不再是$N(r)$中的开始和接受状态。
    2. 从$i$向$I(N(s))$和$F(N(t))$连边，标号为$\epsilon$。
    3. 从$F(N(s))$和$F(N(t))$向$f$连边，标号为$\epsilon$。
  3. 设$r = st$，即两个表达式的连接，则$N(r)$按以下方法构造：
    1. 令$I(N(r)) = I(N(s))$，$F(N(r)) = F(N(t))$。
    2. 合并$F(N(s))$和$I(N(t))$两个状态，保留两个状态的所有转换。 我们可以说明按此算法构造的自动机的开始状态没有入边（用来标记开始状态的START边不是实际意义上的转换），接受状态没有出边，因此这个合并不会产生问题。
  4. 设$r = s^*$，则$N(r)$按以下方法构造：
    1. 构造两个新状态$I(N(r)) = i$,$F(N(r)) = f$。
    2. 从$I(N(r))$向$I(N(s))$和$f$连接两条标号为$\epsilon$的边。
    3. 从$F(N(s))$向$i$和$I(N(s))$连接两条标号为$\epsilon$的边。
  5. 设$r = (s)$，则$N(r) = N(s)$。

为了执行这个算法，我们需要先把正则表达式拆分成子表达式，然后递归地应用上述算法。 我们可以借助语法分析实现这一目标：先构造正则表达式的语法分析树，然后自底向上地执行这个算法。

此前在介绍NFA向DFA的转换时使用过一个例子：

这个自动机就是用上述算法构造出来的，对应的正则表达式为(a|b)*abb。 可以注意到我们先生成了a|b的自动机，又生成了(a|b)*的自动机，最后把它们拼接在一起。

总结

本文已经详细介绍了正则表达式识别所用的自动机，利用这些内容，已经可以构造通用的正则表达式识别器。 然而，为了进行词法分析，我们还需要一些额外内容，比如同时识别多个表达式（就是识别不同语法单元），并确定其优先级。 此外，我们可能还需要让自动机识别向前看指针。 最后，我们还希望尽可能地优化自动机以降低所需的运算量。 这些主题都将包含在下一篇文章中。

  1. 准确地说，本文研究的是自动机的一个子集：识别器。参见有限状态机（维基百科）。 ↩

更新时间:

猜您还喜欢

能带理论

薛定谔函数的周期解 我们将在晶格产生的周期性势场中求解薛定谔函数，并得出方程的布洛赫函数(Bloch function)解。 利用波恩-奥本海默近似，我们研究的实际上仅是电子的薛定谔函数，而原子之间的互动由经典物理处理。 我们研究周期性势能的薛定谔方程，其哈密顿算符为 \(\hat H = \sum_{j=...

晶格动力学

本文研究晶格的动力学，即晶格中原子的运动。 在之前的模型中，我们总是假设晶格中的原子是静止的；然而，这与 X 射线衍射给出的结果不相符——X 射线衍射的结果说明其中的原子总是在振动的。 在研究固体物理时，我们通常使用波恩-冯·卡门边界条件，此时要注意晶体中的两种平移周期性： \(\mathbf u(x_j, t...