貌似刚开学的时候装了个逼,和老师立了个flag说我要写个正则表达式引擎,然后学期末估计老师早就忘了这茬了,在历时３个月的懒癌发作下,终于在这学期末deadline的时候花了一个下午加晚上在没有网的房间写完了它,于是便有了这篇blog,本来想正儿八紧写篇论文,说不定毕业设计可以直接丢一篇这个走人,但第一觉得一个晚上写好的东西太low了,第二自己实在不适合写那种正经的论文,于是还是写从高中开始的一贯的乱七八糟体好了.
主要写自己写的时候遇到的一些瓶颈,例如茹何储存一个图,茹何遍历一个图,茹何表示一个集合之类基础的问题,等不再赘述.请自行查阅数据结构,Ｃ++ STL之类的相关书籍,首先介绍一些基础知识
1.DFA.NFA.正则表达式
DFA即有穷状态自动机,是一个有向图,其中每条边有有一个字母．这个图有唯一一个起始点 q0 ,有一些点是终止状态,现在有一个字符串str,当我们就从起点q0开始，根据下一个字符,在图中走到不同的点上,当整个字符串走完,我们必定停在某个点上,如果那个点是终止状态,那么我们称这个DFA接受这个字符串,反之不接受
/*************************************/
/*形式化定义DFA:
/* DEF:DFA是一个五元组(Q,∑,δ,q0,F)
/*其中Ｑ是一个有穷集合,叫做状态集
/*∑是一个有穷集合,叫做字母表
/*δ是一个映射 δ:Ｑ × ∑ －>Ｑ
/*q0属于Ｑ是起始状态
/*Ｆ是Ｑ的子集是终止状态
/*
/*这个定义前三个定义了一个图Ｇ,别忘了图的定义Ｇ<V,E,δ> 第四个定义了一个起始状态,第五个定义了终止状态的集合,所以这个定义和上面的说法是定价的
/*
/*************************************/
NFA即非确定有穷状态自动机,简单来说,对于DFA,在每个点,不同的字符走到下一个点是确定的,而NFA则是不确定的,也就是
----------------------to be continue----------------------------------------------------------------------
reference:
[1] Michael Sipser "计算理论导引" 机械工业出版社
[2] Alfred V.aho Monica S.Lam Ravi Sethi Jeffrey D Ullman "Compilers:Pinciples,Techniques,&Tools Second Edition" 人民有点出版社影印
[3] 陈梓瀚(vczh) http://www.cppblog.com/vczh/archive/2008/05/22/50763.html
[4] Andrew W. "现代编译原理 Ｃ语言描述" 人民邮电出版社