正则表达式的dfa算法

正则表达式的dfa算法

ID:18635381

大小:3.48 MB

页数:17页

时间:2018-09-20

正则表达式的dfa算法_第1页
正则表达式的dfa算法_第2页
正则表达式的dfa算法_第3页
正则表达式的dfa算法_第4页
正则表达式的dfa算法_第5页
资源描述:

《正则表达式的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是(RE1RE2)这种形式,则L(RE)=L(RE1)L(R

6、E2),其中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的规模是指它所包含的属于字母表Σ的字符的个数,在算法复杂性分析中,它是一个重要的度量。在文本T中搜索正则表达

9、式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就是将输入的正则表达式字符串转换成解析树的后序遍历序列。解析过程中有两个重要的变量,natom和nalt,natom表示解析到这个字符为止,已经有多少个原子结构,而nalt表示解析到这个字

16、符为止,已经有多少个分支结构。正则表达式中的括号表示一个子表达式,这个子表达式对于括号外面的表达式来说是一个原子结构,它内部的natom和nalt的值和外部的表达式的这些值没有关系。为了正确的处理这种括号及其嵌套,程序中使用堆栈来辅助解析,每当碰见“(“,将当前的natom和nalt压入栈中,新的natom和nalt从零开始;而解析到”)“时,则根据当前的natom和nalt值进行后续处理,然后从栈中弹出上一层的natom和nalt。具体的处理算法如下:Parse(p=p1p2…pm,last)v=0;Whileplast≠$DoIfplast∈ΣThe

17、nIf(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);nalt←0;natom←0;ElseIf=')'v←v+(natom-1)×'.'v←v+nalt×'

19、'pop(natom,nalt);natom++;EndIfEndwhilev←v+(na

20、tom-1)×'.'v←v+nalt×'

21、'Returnv;1构造NFA有多种方

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。