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

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

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

    中文 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
    leopku
        1
    leopku  
       2017-05-15 01:14:29 +08:00 via Android
    吱驰
    ynyounuo
        2
    ynyounuo  
       2017-05-15 05:02:11 +08:00 via iPhone
    故得!
    doskoi
        3
    doskoi  
       2017-05-15 10:51:50 +08:00
    http://www.regexper.com/
    在线版,试试输入第一个例子的 (a|b)cd*e?
    howlanderson
        4
    howlanderson  
    OP
       2017-05-16 14:56:25 +08:00
    @doskoi 看起来也不错
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2422 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 02:14 · PVG 10:14 · LAX 18:14 · JFK 21:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.