技海无涯:正则表达式相关的知识和技术(2)——算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

技海无涯:正则表达式相关的知识和技术(2)——算法

简介:

 

 

转换算法

为了让正则表达式最终能够被机器识别,并且能够用其来匹配目标字符串,必须首先将正则表达式转换为NFA或者DFA(后面介绍)两种等价的自动机,一般的转换过程如下:

正则表达式—①—>NFA—②—>DFA

当然也可以直接这样转换,当然这个算法复杂度更高:

正则表达式—③—>DFA

上面的每个过程对应一个算法,下面我们分别简单的介绍三种算法。

 

①正则表达式——>NFAThompson 算法

算法本身是比较简单的,算法的关键如下:每个字符都构造一个NFA,然后用epsilon变化将每个NFA连接起来。

具体的算法描述请参考《编译原理(龙书)》第一版的3.7.1章节。

 

NFA—②—>DFA:子集构造算法

这个算法稍微复杂一些,算法关键如下:

1)区分状态和状态集:DFA中的状态,实际上对应NFA中的多个状态,也就是一个NFA状态集;这也是算法为什么叫子集算法的原因,因为DFA中的每一个状态实际上都是NFA状态集的一个子集

2)二次转换:对于已经构造的DFA状态(NFA状态集),拿字符集循环验证状态集中的状态能否转换到其它状态,有二次转换:(1)首先看原有状态集中哪些状态包含指定字符的转换,(2)一旦转换成功,则这些转换后的状态后续所有能够经过一个或者多个epsilon转换到达的状态都要包含进来;。

 

③正则表达式——>DFA

这个算法没有明确的名称,但其中用到了语法树的概念,因此我暂且称其为“语法树构造法”。

算法太复杂,我还没有时间来仔细研究,因此就不能详细介绍了:)有需要的大侠可以参考《编译原理(龙书)》第一版3.9.2章节。

 

Shunting-yard算法

在介绍表达式的时候提到了中缀表达式、后缀表达式,将中缀表达式转换为后缀表达式的算法就是Shunting-yard算法。

详情请参考:http://en.wikipedia.org/wiki/Shunting_yard_algorithm

 

 

========================未完待续==================================

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章