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