一个微型的正则表达式引擎 | A micro regular expression engine
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
MicroRegEx
demo
img
.gitignore
LICENSE.md
Makefile
README.en-US.md
README.md
TODO.txt
grammar.md
requirements.txt
requirements_dev.txt
setup.py
test_suite.dat
testing.py

README.md

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

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

测试

通过了包含 64 个测试样例的测试数据的测试

License

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

致谢与荣誉

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