首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  正则表达式

MicroRegEx: 一个微型的正则表达式引擎

  •  
  •   howlanderson · 2017-05-15 00:28:20 +08:00 · 667 次点击
    这是一个创建于 765 天前的主题,其中的信息可能已经有所发展或是发生改变。

    中文 readme 地址: https://github.com/howl-anderson/MicroRegEx/blob/master/README.zh-Hans.md

    项目自带的绘图功能是研究正则表达式和自动机原理的绝佳工具,可以将正则表达式转换成可视化的有穷状态机,还能借助于状态机的简化工具将状态机最小化。同时项目代码也是研究编译原理和正则表达式的一个优良的参考实现。

    什么是 MicroRegEx

    MicroRegEx 是一个微型的正则表达式引擎.

    所支持的 Operator 列表

    • * - 零次或者更多次重复
    • + - 一次或者更多次重复
    • ? - 可选(零次或者一次)
    • a|b - 匹配 a 或者 b
    • (expr) - 将expr作为原子
    • \ - 转义字符

    使用方法

    像 python 内建的 regex 一样使用

    import MicroRegEx
    
    regex = MicroRegEx.compile("(a|b)cd*e?")
    result = regex.match("abcde")
    print(result)
    
    result = regex.match("acde")
    print(result)
    

    将会输出:

    False
    True
    

    绘制 NFA(非确定性有穷状态机)

    import MicroRegEx
    
    regex = MicroRegEx.compile("(a|b)c?")
    regex.plot()
    

    绘制结果如下: NFA

    NFA 转换成 DFA(确定性有穷状态机)

    NFA to DFA

    原始的 DFA
    import MicroRegEx
    from MicroRegEx.Automaton.NFA2DFA import NFA2DFA
    
    nfa = MicroRegEx.compile("(a|b)c?")
    
    dfa = NFA2DFA(nfa).convert()
    dfa.plot()
    

    绘制结果如下: DFA_native

    简化的 DFA
    import MicroRegEx
    from MicroRegEx.Automaton.NFA2DFA import NFA2DFA
    
    nfa = MicroRegEx.compile("(a|b)c?")
    
    dfa = NFA2DFA(nfa).convert().simplify()
    dfa.plot()
    

    绘制结果如下: DFA_simplified

    DFA 最小化

    Brzozowski 方法
    import MicroRegEx
    from MicroRegEx.Automaton.NFA2DFA import NFA2DFA
    from MicroRegEx.Automaton.Minimal.Brzozowski import Brzozowski
    
    nfa = MicroRegEx.compile("(a|b)c?")
    
    dfa = NFA2DFA(nfa).convert().simplify()
    mini_dfa = Brzozowski(dfa).construct()
    mini_dfa.plot()
    

    绘制结果如下: DFA_mini


    中文 readme 地址: https://github.com/howl-anderson/MicroRegEx/blob/master/README.zh-Hans.md

    4 回复  |  直到 2017-05-16 14:56:25 +08:00
        1
    leopku   2017-05-15 01:14:29 +08:00 via Android
    吱驰
        2
    ynyounuo   2017-05-15 05:02:11 +08:00 via iPhone
    故得!
        3
    doskoi   2017-05-15 10:51:50 +08:00
    http://www.regexper.com/
    在线版,试试输入第一个例子的 (a|b)cd*e?
        4
    howlanderson   2017-05-16 14:56:25 +08:00
    @doskoi 看起来也不错
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2901 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 17ms · UTC 00:51 · PVG 08:51 · LAX 17:51 · JFK 20:51
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1