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

中文 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 转换成 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

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

绘制结果如下:

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() 

绘制结果如下:

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