howl-anderson/MicroRegEx

一个微型的正则表达式引擎 | A micro regular expression engine

README written in English

什么是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()

绘制结果如下:

深入理解 MicroRegEx 的原理

为了更好的理解 MicroRegEx 是如何工作的，我提供了一个 Jupyter Notebook，用户可以按照其中的指引，一步一步的探索 MicroRegEx 的底层原理。

测试

通过了包含 64 个测试样例的测试数据的测试。 运行测试请执行 python ./testing.py

License

本项目采用 MIT License - 具体细节见 LICENSE.md 文件

致谢与荣誉

1. 灵感来自xysun的regex项目
2. 少量部分文档来自lihao98722的regular_expression_engine项目
3. 测试数据来自Glenn Fowler项目的测试套装.
4. 测试脚本修改自regex项目.

参考资料

• Implementing Regular Expressions