我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 栈自动机 >

如何将正则表达式转换为NFA

归档日期:07-02       文本归类:栈自动机      文章编辑:爱尚语录

  1.符号栈,即运算的符号,其存储的为wchar_t类型,为连接,左括号,选择3种运算符。

  2.NFA栈,即保存的NFA,这里因为整个计算过程都是更新一个Graph结构,所以这里的NFA栈保留的其实是当前NFA的开始和结束信息,即start和end。

  1.遍历输入的正则表达式,这里正则表达式的保存在CString变量中,可以通过下标访问;

  2.首先初始化一张保存NFA的Graph结构,算法过程中的节点的数量不会超过正则表达式长度的2倍,所以这里直接开辟一个大小为正则表达式长度为2倍的Graph结构;

  3.遇到非运算符,及正则表达式里面的转移符号的时候,这里就需要构造一个基本的NFA, 一个初始状态,一个终止状态,然后由初始状态至终止状态有一条为该转移符号的边,此时仍然需要检查正则表达式的下一个符号,如果不是运算符或者为左括号,此时应该运算栈中添加一个连接运算符,然后将构造的基本NFA添加入NFA栈中,方便以后将基本的NFA进行其他选择,重复,连接运算;

  5.如果是运算符“)”,即右括号,此符号属于运算级最高的符号了,所以它要在符号栈中弹出所有符号运算,直到遇到“)”匹配,运算过程中根据符号栈中弹出的符号计算;

  6.如果是运算符“(”,即左括号,此符号只是用来和右括号结合的,所以直接将该运算符压入符号栈中即可;

  7.如果是运算符“*”,即重复符号,这个在正则表达式中运算级最高,直接进行计算,计算方法就是从NFA栈中弹出一张图,然后得到两个未分配的新节点,添加4条上面图表示的那样的边,然后重新设定NFA的start和end之后将新的NFA压入NFA栈中即可,运算后检查其后跟随的元素,如果是转移符号或者左括号,则必须要向符号栈中添加连接符号;

  8.如果是运算符“+”,即选择符号,由于此符号的优先级没有连接符号高,所以此时应该弹出符号栈中优先级高于它的符号,但是“(”不参与弹出,所以这里只是弹出连接符号和自身“+”符号运算,然后将该符号压入符号栈等候计算;

  9.正则表达式遍历完毕之后,需要弹出所有的符号栈进行计算,最后NFA栈中的唯一NFA就是所求的NFA;

  接下来就是具体的运算的算法,这里点与点的连接通过更新Graph中相应的点的邻接链表即可;

  10.连接运算,此时需要弹出NFA栈中的两个NFA,然后将其中一个的end连接至另一个的start,然后更新新的NFA的start和end,压入NFA栈中。

  11.选择运算,此时需要弹出NFA栈中的两个NFA,然后Graph重新分配两个节点,作为新的NFA的start和end,然后新的start分别连接弹出的两个NFA的start,弹出的两个NFA的end分别连接新的end即构成新的NFA,压入NFA栈中。

  12.闭包运算,此时需要弹出NFA栈中的一个NFA,然后Graph重新分配两个节点,作为新的NFA的start和end,然后新的start连接弹出NFA的start,弹出NFA的end连接新的end,然后添加一条新的start到新的end的一条空边和一条旧的end到旧的start的一条空边,将新的NFA压入NFA栈中。

  最近得做一些跟自动机有关的东东,其中一部分可以简要地看作是由一套正则文法生成状态自动机的过程。什么是正则表达式?首先我们看看什么是正则表达式。这个东东呢,一般用于描述一个字符串的集合——直接说就是一个正则表达式可能可以匹配一大堆字符串,而这一大堆字符串可以形成一个集合,它们的共同特征就是可以被这个正则表达式匹配。就像去死去死团,但是不同的是去死去死团的团员的共同特征是不被任何异性所匹配——但是这没关系,我们不妨取去死去死团的补集就行了。反正正则表达是很好啦,因为你只要用一点点在脏话里,就可以骂好多好多人,比如:Mar(ykcus) is son of bitch.真是非常de省力,唯一的缺点是可能对方不知道你在说什么。好了,从上面我们可以看出正则表达式中的两个基本结构:连结(Concatenation),比如 bitch,由b, i, t, c, h连接而成 联合(Union),比如 ykcus,可以认为是y或k或者cus 下面是第三个基本结构,被称为Kleene star (或者 Kleene 闭包)的。因为这个操作是Stephen Cole Kleene发明的。啊啊,其实正则表达式这个东西就是Kleene发明的。这个同学真是非常的牛B,因为他是更加牛B的 阿隆佐 - 丘奇 ( Alonzo Church )——历史上和阿兰 - 图灵 ( Alan Turing ) 并称的人物——的学生。有多牛B呢,这个Kleene还和他的老师,还有图灵,就递归论发表了论文,奠定了可计算理论的根基。啊哈哈哈,真是牛B啊。嗯,所谓Kleene Star的例子就是这样的。Kleene Star,比如a*,可以接受空串和若干个a连结组成的串 当然咯,还有一些别的操作,比如我们知道的+,?,集合[]等等,但是这些操作都可以通过上面三个基本操作的组合来完成。比如+,a+可以认为是aa*什么是NFA?要说NFA嘛,我得先说说DFA。所谓DFA,就是Deterministic Finite state Automata的简称。是状态机的一种。通俗的说,就是一大堆状态的集合,里面有一个初始状态和若干终止状态,每个状态可以有若干个输出边前往别的状态。但是要求每个状态的同一种输出边至多只有一个,所以自动机被称为是”Deterministic”的。比如下面这个例子:表述的是一个电灯de开关,这个开关每按一下就从’开’状态转换到’关’状态,或者从’关’状态转换到’开’状态。而为了从环保角度出发,在’关’状态才被认为是终止态。上面的自动机呢,就可以描述这个灯泡的行为模式,或者说可以描述电灯的状态转换过程。输出边就是’开’或者’关’的动作,或者说这个灯泡的开关,只接受这两种动作:“Trun On”,“Trun Off”。而”Trun On”动作只会导致灯的状态变成“On”,“Trun Off”动作只会导致灯的状态变成“Off”,这是确定的,你的外婆都可以预料到的。所以说DFA是确定有限状态自动机。现在可以说NFA了。这个NFA嘛,全称是Non-deterministic Finite state Automata。也是状态自动机的一种。确切地说,刚才的DFA是NFA的一个子集。和DFA唯一的区别就是他是”Non-deterministic”的,哈,非确定的,每个状态的同一种输出边可以不止一个。还是用刚才的例子。现在假设我们的电灯有一种新的状态咯~:坏掉了。灯丝被过大的电流烧断了,听上去遭透了,因为一”Trun On”就得准备换灯泡了:但是我们没法确定的知道哪一次Trun On会导致灯泡坏掉,使得灯泡进入”Down”状态的那次“开”操作看上去跟你昨天开灯的那次操作一模一样(严格的说,每一次点亮灯泡都会导致灯丝的状态发生变化,但是在此简化了)所以从状态”Off”出来的输出边中,”Trun On”有两条,这就导致没法根据当前状态和输出边确定下一状态,这就是为什么称为非确定性有限自动机的原因。如何转换?刚才Shellex说了,正则表达式有三种基本结构。如果能先将这三种基本结构转换成对应的NFA,然后在用这三种基本结构去拼装成完整的NFA是不是很省力呢?下面就是三种基本正则表达式的NFAab:a*:ab:里面出现了一种叫“None”的边。这个不代表这个边是字面上的“None”,而是指这个边是个空边。也就是说任何“动作”都可以从这个边进入下一个状态。它的学名叫 epsilon 边,一般表示成’ε’,Shellex这里表示成“None”了。下面我们来考虑正则表达式到NFA转换。给出一个正则串的输入,得到一个NFA的输出。被广泛采用的是Thompson Algorithm,也就是所谓的子集算法。该算法的发明人应该就是写ed编辑器的那个Thompson大牛。该算法的实现和算术表达式的求值非常的类似,需要一个符号栈存放操作符,一个自动机栈存放生成的自动机。算法结束后,可以从自动机栈中Pop一个最终的结果。比如对于正则表达式(ab)*cd,求值过程如下:PUSH a To automaton stackPUSH b To automaton stackUNION STAR PUSHc To automaton stack CONCAT PUSH d To automaton stack CONCAT POP result里面的UNION,STAR 和 CONCAT就是三种基本结构的生成操作了。

本文链接:http://mezzomagazine.com/zhanzidongji/130.html