资源描述：
《正则表达式的dfa算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、正则表达式1正则表达式的定义正则表达式（RegularExpression）是一种强大的，便捷的，高效的文本处理工具，它可以表示比单字符、字符串集合等更加复杂的搜索模式。下面首先给出正则表达式和它所表达语言的形式化定义。一个正则表达式RE是符号集合Σ{ε,
2、,·,*,(,)}上的一个字符串，它可以递归定义如下：空字符ε是正则表达式。任意字符α∈Σ是正则表达式。如果RE1和RE2都是正则表达式，则（RE1），（RE1·RE2），（RE1
3、RE2）和（RE1*）亦是正则表达式。通常（RE1·RE2）可以简写为RE1RE2。符号“·
4、”，“*”，“
5、”称为操作符，可以通过为每个操作符赋予优先级来消除更多的括号。为了方便起见，这里使用了额外的后缀操作符“+”，它的含义是RE+=RE·RE*。其他所使用的操作符如”?”，字符组，”.”等实际上都可以用上面的方式来表达。下面定义正则表达式所表达的语言。正则表达式RE所表达的语言是Σ上的一个字符串集合。根据RE的结构，可以将它递归的定义如下：如果RE是ε，则L(RE)={ε}，即空串。如果RE是α∈Σ，则L(RE)={α}，即包含一个字符的单串。如果RE是（RE1）这种形式，则L(RE)=L(RE1)。如果RE是（
6、RE1RE2）这种形式，则L(RE)=L(RE1)L(RE2)，其中W1W2可以看成是字符串集w的集合，其中，w=w1w2并且w1∈W1，w2∈W2。操作符表示字符串的连接。如果RE是（RE1
7、RE2）这种形式，则L(RE)=L(RE1)∪L(RE2)，是这两种语言的并集，“
8、”称为并操作符。如果RE是（RE1*）这种形式，则L(RE)=L(RE)*=∪i≥0L(RE)i，其中L0={ε}并且Li=LLi-1，它表示字符串集合是由0个或者多个RE1表达的字符串连接而成。“*“称为星操作符。正则表达式RE的规模是指它所包含的属于
9、字母表Σ的字符的个数，在算法复杂性分析中，它是一个重要的度量。在文本T中搜索正则表达式RE的问题就是找到文本中所有属于语言L(RE)的字串。搜索的方法是首先将正则表达式解析成一颗表达式树，然后将表达式树转换成非确定性有限自动机（NFA）。直接使用NFA进行搜索是可行的，然而NFA算法处理速度通常比较慢，一般的，搜索过程最坏情况时间复杂度是O(mn)，但是所需存储空间并不多。另外一种策略是将NFA转变成确定性有限自动机（DFA），它的搜索时间是O(n)，但是构造这样的一个自动机所需的最坏情况时间和空间复杂度都是O(2m)。2构造
10、解析树通常来说，解析树并不是唯一的。在解析树中，每个叶节点都是使用Σ∪{ε}中的一个字符来标识的，而每个中间节点则使用操作符集合{
11、,·,*}中的一个进行标识。一种可能的解析树使用二叉树来表示，二叉树的父节点是一个操作符，两个子节点表示这个操作符作用的两个子表达式。如正则表达式(AT
12、GA)((AG
13、AAA)*)的解析树可以表示如下：。程序中使用这个二叉树的后序遍历序列来存储这个解析树，那么上面那个正则表达式的存储序列如下：AT·GA·
14、AG·AA·A·
15、*·。函数re2post就是将输入的正则表达式字符串转换成解析树的后序遍
16、历序列。解析过程中有两个重要的变量，natom和nalt，natom表示解析到这个字符为止，已经有多少个原子结构，而nalt表示解析到这个字符为止，已经有多少个分支结构。正则表达式中的括号表示一个子表达式，这个子表达式对于括号外面的表达式来说是一个原子结构，它内部的natom和nalt的值和外部的表达式的这些值没有关系。为了正确的处理这种括号及其嵌套，程序中使用堆栈来辅助解析，每当碰见“（“，将当前的natom和nalt压入栈中，新的natom和nalt从零开始；而解析到”）“时，则根据当前的natom和nalt值进行后续处理
17、，然后从栈中弹出上一层的natom和nalt。具体的处理算法如下：Parse(p=p1p2…pm,last)v=0；Whileplast≠$DoIfplast∈ΣThenIf(natom>1)Then--natom;v←v+'.';EndIfv←v+plast;natom++;ElseIf='
18、'v←v+(natom-1)×'.'nalt++;ElseIf='*'or'+'or'?'v←v+plast;ElseIf='('If(natom>1)Then--natom;v←v+'.';EndIfpush(natom,nalt);
19、nalt←0;natom←0;ElseIf=')'v←v+(natom-1)×'.'v←v+nalt×'
20、'pop(natom,nalt);natom++;EndIfEndwhilev←v+(natom-1)×'.'v←v+nalt×'
21、'Returnv;1构造NFA有多种方
