易语言实地培训长期招生 QQ1615457736

乐易论坛

 找回密码
 立即注册

微信登录

微信扫码,快速开始

QQ登录

用QQ账号登陆

导航
导航
培训
培训
产品
产品
易歪歪客服聊天助手——永久免费阿里云服务器最高¥1888云产品通用代金券我要租广告
易歪歪客服聊天助手——永久免费阿里云服务器低至10元/月我要租广告
易歪歪客服聊天助手——永久免费最高2000云产品通用代金券我要租广告
查看: 3673|回复: 1
收起左侧

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

[复制链接]
  • TA的每日心情
    奋斗
    昨天 08:56
  • 签到天数: 724 天

    [LV.9]以坛为家II

    发表于 2017-3-19 14:03:57 | 显示全部楼层 |阅读模式

    乐易编程网免费注册!抓住机会哦!

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    标 题: 【原创】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状态机图文件:
    attachment.jpg

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

    dot -T png -O NFA.dot DFA.dot min_DFA.dot
    NFA:
    attachment.jpg
    DFA:
    attachment.jpg
    最小化DFA:
    attachment.jpg

    源代码:


    https://github.com/yufengzjj/ERE
    易语言实地培训,报名联系QQ 1615457736
    [超强]《易语言软件加密(防破解)技术特训》
    回复

    使用道具 举报

  • TA的每日心情
    无聊
    2018-11-13 20:12
  • 签到天数: 32 天

    [LV.5]常住居民I

    发表于 2017-3-19 22:54:05 | 显示全部楼层
    不明觉厉!
    易语言实地培训,报名联系QQ 1615457736
    [超强]《易语言软件加密(防破解)技术特训》
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    乐易推荐上一条 /6 下一条

    QQ|网站地图|Archiver|手机版|小黑屋|乐易论坛 ( 湘ICP备19007035号-2 )

    GMT+8, 2019-10-20 20:15 , Processed in 0.093560 second(s), 83 queries .

    Powered by Discuz! X3.4 Licensed

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表