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

揰掵佲

标 题: 【原创】C++正则表达式引擎设计与实现(core)
作 者: 红绡枫叶
时 间: 2016-10-19,22:50:13
链 接: http://bbs.pediy.com/showthread.php?t=213353

此正则引擎主要目的还是让更多的人了解自动机理论的一些实际应用.
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状态机图文件:
[/url]

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

dot -T png -O NFA.dot DFA.dot min_DFA.dot
NFA:
[url=http://m.pediy.com/attachment.php?attachmentid=107854&d=1476888441]
DFA:
[url=http://m.pediy.com/attachment.php?attachmentid=107852&d=1476888441][/url]
最小化DFA:


源代码:


https://github.com/yufengzjj/ERE

冯古屋

不明觉厉！