首页
社区
课程
招聘
[原创]C++正则表达式引擎设计与实现(core)
发表于: 2016-10-19 22:50 10996

[原创]C++正则表达式引擎设计与实现(core)

2016-10-19 22:50
10996

此正则引擎主要目的还是让更多的人了解自动机理论的一些实际应用.
C++11实现.

1.核心文法设计

正则表达式有三种最基本的操作:
(1)选择 取并集.符号:|. 比如两个字符串集合R和S的选择操作,记作R|S.

(2)连接 字符串之间的拼接.两个字符串集合R和S的连接为RS.

(3)闭包 符号:* 字符串集合R的闭包R*是指把R与自身连接零次或者多次形成的所有集合的并集.

由这几个简单的操作可以得到我们平常接触的正则表达式的所有扩展.

所以设计最核心的正则文法G[RE]:

<RE>--><expr>

<expr>--><term>'|'<expr>|<term>

<term>--><factory><term>|<factory>

<factory>--><item>'*'|<item>

<item>-->'('expr')'|<sym>

<sym>-->a|b|c|....

文法已经把优先级写进去了,优先级分别是'('=')'>'*'>连接>'|'.
2.正则表达式引擎架构设计

文法解析用递归下降分析.分析完之后生成有限状态自动机.因此正则引擎主要两部分是正则分析器与状态机.

3.正则表达式引擎实现

在C++11标准库上实现了核心引擎,代码在github.

主要算法是将非确定性有限状态自动机(Non-deterministic Finite Automaton,NFA)转化到确定性有限状态自动机(Deterministic Finite Automaton,DFA)以及简化DFA的算法.两个算法本质上都是对等价状态集合的计算来简化状态机.现引用一段算法的介绍:

NFA到DFA

NFA到DFA的子集构造算法(The Subset Construction):从将初始状态划分为一个初始状态子集开始,构造状态子集(经过零个或多个空字符串ε转移到的状态和已在子集中的状态都是构造的新的状态子集),存在c属于字母表Σ,经过一个c的转移(必须有c的转移),能够使得从状态子集ni转移到状态子集nj,则在DFA中有在c的输入下从状态子集ni转移到状态子集nj的转移.最后不再有新的状态子集出现.根据状态子集的转移依次构造DFA.

DFA到最小DFA

最小化DFA用到的是等价状态集合的划分来构建.一开始只有两个状态集,一个接受状态集合,一个非接受状态集合.对于每一个状态集合Sp,如果存在c属于字母表Σ,使得Sp中的状态转移到不同的状态集合(包括没有转移的空状态集合),则拆分Sp,使得拆分后的状态集合中的每一个状态不可能转移到不同的状态集合.其中状态集合之间的转移构成最小化DFA中的转移.
更多的介绍:从正则表达式(RE)到最小确定性有限状态自动机(DFA)

我在核心引擎基础上上写了一个小工具方便查看状态机的构造过程.可以直接生成DOT语言描述的状态机图.

ERE.exe --help

Allowed options:

-h [ --help ] produce help message

-e [ --expr ] arg set regular expression

-s [ --string ] arg string to check by regular expression

-a [ --alphabet ] arg set regular expression alphabet

输入:ERE.exe -e "a(b|cd)*e" -s abbbcdcde,表示在正则表达式"a(b|cd)*e"下读入abbbcdcde字符串.输出匹配结果,并生成DOT状态机图文件:


利用Graphviz的dot工具生成png图片:

dot -T png -O NFA.dot DFA.dot min_DFA.dot
NFA:

DFA:

最小化DFA:


源代码:Educational Regular expression Engine


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

上传的附件:
收藏
免费 3
支持
分享
最新回复 (9)
雪    币: 135
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
看不懂系列~
2016-10-20 01:54
0
雪    币: 4751
活跃值: (1783)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
正则表达式 然而还有更简单的办法  vc6  就有实现
2016-10-20 07:17
0
雪    币: 5562
活跃值: (2143)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
当年编译原理看不懂,现在还是看不懂
膜拜
2016-10-21 08:20
0
雪    币: 43
活跃值: (388)
能力值: ( LV9,RANK:140 )
在线值:
发帖
回帖
粉丝
5
看到这个我又想起了心酸往事。最初我想做一个安全的密码本,然后发现密码本需要一个通用的文本编辑控件(ncurses),然后又写控件去了,写着又发现控件需要一个富文本引擎,然后又写引擎去了,写引擎的时候又发现需要一个正则引擎,然后又写正则引擎去了~~ 写完这堆东西,感觉身体被掏空~~
2016-10-21 12:20
0
雪    币: 9941
活跃值: (2143)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
6
深有同感...
2016-10-21 19:08
0
雪    币: 1
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
楼主功底不错啊
2016-10-21 20:39
0
雪    币: 35
活跃值: (1909)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
要在产品中实际应用还是推荐大家使用intel的牛逼正则引擎:hyperscan
https://github.com/01org/hyperscan
还有google的RE2也不错
这两个都是成熟的DFA的正则引擎,有内存优化和多线程优化
2016-10-21 21:40
0
雪    币: 39
活跃值: (158)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
正则表达式?我一直都是用boost库的.
2016-10-22 17:46
0
雪    币: 325
活跃值: (171)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
10
大牛,入门晚了
2016-10-24 21:12
0
游客
登录 | 注册 方可回帖
返回
//