从正则表达式到自动机

直接模拟NFA的算法可以用于那些将NFA转换到DFA比直接模拟NFA更加耗时的情形。

Copilot:在实际转化中，通常先将正则表达式转成 NFA，然后再由 NFA 转成 DFA。以便更好地实现词法分析。

从NFA到DFA的转换

DFA的状态数可能是NFA状态数的指数。但是实践中，对于一个真实的语言，它的NFA和DFA的状态数量会大致相同。

• 有NFA构造DFA的子集构造法

操作	描述
ε-closure(s)	能够从NFA的状态s开始只通过ε转换到达的NFA状态集合
ε-closure(T)	能够从T中某个NFA状态s开始只通过ε转换到达的NFA状态集合
move(T,a)	能够从T中某个状态s出发通过标号为a的转换到达的NFA状态的集合

• 子集构造法伪代码

while(在Dstates中有一个未标记状态T)
{
    给T加上标记;
    for(每个输入符号a)
    {
        U = ε-closure(move(T,a));
        if(U不在Dstates中)
            将U加入DStates中，且不加标记;
        Dtran[T, a] = U;
    }
}

NFA模拟

许多文本编辑程序使用的策略是根据一个正则表达式构造出相应的NFA，然后使用类似on-the-fly(即边构造边使用的)子集构造法来模拟这个NFA的执行。

S = ε-closure(s0);
c = nextChar();
while(c != eof)
{
    S = ε-closure(move(S,c));
    c = nextChar();
}
if(S∪F != Φ)
    return "yes";
else
    return "no";

从正则表达式构造NFA

将正则表达式转换为一个NFA的McMaughton-Yamada-Thompson算法。详见《编译原理》p101-算法3.23。

（END）