正则表达式1.2(创建NFA)

图片 7

承接上一篇日志, 这一次实现的是创建NFA.

写在前面


从源代码到可执行文件要经历几个过程:

  1. 词法分析
  2. 语法分析
  3. 语义分析
  4. 中间代码生成
  5. 代码优化

词法分析有点像中文分词,是将输入结构化的第一步:从字符串序列变为词法单元序列,它的输出将作为语法分析的输入。在词法单元中主要涉及到的概念有:

  1. DFA:有穷确定状态机。
  2. NFA:有穷不确定状态机。

确定和不确定的区别在于:当遇到字符的时候状态的变化是不是确定的,下面是一个NFA的例子:

图片 1

NFA

对于这样一个状态机可以构造出一个转换表如下:

状态 a b
1 {1,2} {1}
2 {3}
3

对于DFA来说每个状态上的转换都是确定的,那么其对应的代码的样子如下:

s = s0;
c = nextChar();
while(c != eof){
    s = move(s, c); // 根据状态转换表
    c = nextChar();
}
return s in F ? "yes" : "no";

从代码上来看DFA要比NFA简单不少,那么下面接着来看。

输入是正则表达式对应的解析树(一个二叉树).

从NFA到DFA


既然DFA看起来要比NFA用起来简单很多,那么如果能将NFA转换为DFA的话问题不就变简单了?

子集构造法是一种比较简单、直观的转化方法,既然在NFA中状态1根据字符a可以到状态1,也可以到状态2,那么如果将状态{1,2}合并看做一个节点,那得到结果不就是DFA了~

图片 2

从NFA到DFA

在实际操作的时候需要用到三个集合:

  1. ε-closure(s):从NFA中状态s开始只通过ε得到的状态的集合。
  2. ε-closure(T):从T中的某个状态s开始只通过ε得到的状态的集合。
  3. move(T, a):从T中某个状态s开始通过a得到的状态集合。

在NFA上构造完成三个集合之后,那么可以通过如下流程进行转换:

// 在最开始Dstatus中只有ε-closure(s0)一种状态,并未未加标记
while(在Dstatus中有一个未标记的状态T){
    给T加上标记;
    for(每个输入符号a) {
        U = ε-closure(move(T, a));
        if(U 不在Dstates中)
            将U加入到Dstatus中// 不加标记
        Dtran[T, a] = U;// 转换表
    }
}

在实际上DFA和NFA的状态数都是差不多的,但是理论上转换后的DFA可能是原本的NFA状态数的指数级,(a|b)*a(a|b)^(n-1)就是这样一个例子:

图片 3

DFA状态数为NFA的指数倍

输出是对应的NFA(一个有向图).

从正则到NFA


很多的词法分析器都是用正则来描述规则,一般正则基本上能搞定所有的需求,而且足够简单。但是在识别输入的字符序列的时候需要用到自动机,那么就需要从正则到NFA
or DFA的转换。对于正则的每种行为都有对应的NFA中的转换可以代替:

  1. r=s|t:通过ε实现。
  2. r=st:将s的接受状态和t的初始状态进行合并。
  3. r=s*:将s的接受状态和初始状态相连,从而达到循环的效果。

达到的效果如下:

图片 4

从正则到NFA

对于(a|b)*a这样的正则按照上面的方法得到的NFA如下:

图片 5

(a|b)*a对应的NFA

有了这种方法,根据正则的AST就能很容易递归生成NFA。

思路也是递归实现, 对于一个树节点, 用两个子节点创建对应的NFA,
然后再根据树节点的类型将两个子NFA拼接起来.

从正则到DFA


DFA是比较简单的,那么在解析正则的一个思路是正则->NFA->DFA,但是这样做比较麻烦,我们肯定是希望能够直接转换。这里需要四个集合:

  1. nullable(n):节点n的子表达式中包含空字符串。
  2. firstpos(n):节点n为根的子表达式中某个串的第一个符号的位置的集合。
  3. lastpos(n):节点n为根的子表达式中某个串的末一个符号的位置的集合。
  4. followpos(p):如果L((r)#)中的某个串x=a1..an,使得我们在解释为什么x属于L((r)#)时,可以将x中的某个ai和AST中的位置p匹配,且位置ai+1和位置q匹配,那么q在该集合中。

这样看起来比较难理解,来看一个例子:

图片 6

集合例子

那么对于框中的根节点来说:

  1. nullable(n):false。
  2. firstpos(n):{1,2,3}。
  3. lastpos(n):{3}。
  4. followpos(1):{1,2,3}。

这些集合可以递归得到,比如较为麻烦的followpos的计算方法如下:

  1. 如果n是一个cat节点,其左右子节点分别为c1、c2,那么对于lastpos(c1)中的每个位置i,firstpos(c2)中的所有位置都在followpos(i)中。
  2. 如果n是一个star节点,并且i是lastpos(n)中的一个位置,那么firstpos(n)中所有的位置都在followpos(i)中。

其中关键的followpos其实就是NFA中的状态转换,那么下面的正则到DFA的过程就很容易理解了:

// 构造D的状态集Dstates和D的转换函数Dtran。
初始化Dstates,使之只包含未标记状态firstpos(n0),其中n0是(r)#的抽象语法树的根节点
while(Dstates中存在未标记状态S){
    标记S;
    for(每个输入符号a){
        令U为S中和a对应的所有位置p的followpos(p)的并集;
        if(U不在Dstates中)
            将U作为未标记的状态加入到Dstates中;
        Dtran[S,a] = U;
    }
}

在实际中DFA确实有优势,但是还有进一步优化的空间,接着往下看。

使用到的数据结构:

DFA状态最小化


在DFA中有一些状态是的等价的,等价的意思就是没有区别的,那有区别的意义在于:

从状态s、t出发,沿着标号为x的路径到达两个状态,分别为接受状态和非接受状态。

下面是一个简单的最小化的例子:

图片 7

状态最小化

那么最小化呢?上面的这个定义太抽象了,如果直接找路径的话估计会累死的。想到每条路径都是由字符一点一点拼接成的,那么对应的方法也就比较容易能想到了:

  1. 将所有状态根据接受、非接受分成两组。
  2. 遍历分组、字符,如果同一组内的状态根据该字符到达了不同的组,那么继续将当前的组进行分割。
  3. 重复执行2,直到没有变化。
  4. 每个组中选择一个代表状态,重新构造DFA,最小化完成。

最后给出一个结论:任何一个正则表达式都有唯一的状态数最少的DFA

struct State  {      int code; //状态码, 一般是自动机中边上的字符, 特殊情况是S(开始), T(结束), FAKE(伪节点,导出空转移的边)      State* out; //出边1      State* out1; //出边2      int lastList; //记录上一次所在的链表, 判重用的.  };    struct Frag  {      State* start; //子NFA的进入节点      State* end;   //子NFA的出节点  };

State表示状态机里面的状态, 但是这里的State是标记边的,
而实际状态机理论里面的状态在这里是out和out1.

其实无所谓, 怎样表达更方便就怎样使用(从Russ Cox代码里抄来的XD).

Frag表示一个子NFA, 这个NFA的进入节点是start, 出节点是end.

对于解析树里面的一个Node, 就会生成一个Frag.

但是一个子NFA不一定只有一个出节点的, 比如”|”符号, 就会有两个处节点才对,
这样我们需要用一个链表存出节点.

我增加了一个伪节点的概念, 就是会导出ε边的State.
这种状态节点的code设置成FAKE, 让每一个字NFA的出边都指向这个Fake节点,
然后Frag的形式就可以统一了, 即一个入节点, 一个出节点.

实际上Fake节点也是必不可少的, 因为Thompson发明的NFA本来就避免不了ε边.

发表评论

电子邮件地址不会被公开。 必填项已用*标注