python - 有没有可以将正则表达式转换为 fsm 的编译器？或者可以转换成人类的话？

Question

可以转换的东西

r"a+|(?:ab+c)"

到

{
    (1, 'a') : [2, 3],
    (2, 'a') : [2],
    (3, 'b') : [4, 3],
    (4, 'c') : [5]
}

或类似的东西

并接受 2 或 5

Answer 1

您有一个调试标志，可以以更易读的形式打印您的正则表达式：

>>> import re
>>> re.compile(r"a+|(?:ab+c)", flags=re.DEBUG)
branch
  max_repeat 1 65535
    literal 97
or
  subpattern None
    literal 97
    max_repeat 1 65535
      literal 98
    literal 99
<_sre.SRE_Pattern object at 0x0000000002325328>

Answer 2

我有一些代码可以做到这一点。它没有很好的文档记录并且不受支持，但是如果您有兴趣，欢迎您查看它。

该库称为 rxpy，存储库是http://code.google.com/p/rxpy

进行解析的例程是http://code.google.com/p/rxpy/source/browse/rxpy/src/rxpy/parser/pattern.py#871上的 parse_pattern

如果你调用repr(...)结果，你会得到一个“点语言”的图表 - https://en.wikipedia.org/wiki/DOT_language

例如，将测试视为http://code.google.com/p/rxpy/source/browse/rxpy/src/rxpy/parser/_test/parser.py#47

为了说明我的意思，让我们看看http://code.google.com/p/rxpy/source/browse/rxpy/src/rxpy/parser/_test/parser.py#234上的测试'ab*c'：

"""digraph {
 0 [label="a"]
 1 [label="...*"]
 2 [label="b"]
 3 [label="c"]
 4 [label="Match"]
 0 -> 1
 1 -> 2
 1 -> 3
 3 -> 4
 2 -> 1
}"""

从0which 开始可以匹配“a”以进入 state 1。从那里你可以匹配一个“b”去状态2或一个“c”去状态3。状态2然后有一个转换回1可以消耗另一个“b”等等等。手动阅读有点难看，但是当测试失败时，你会在屏幕上显示一个小图表。

the library also has various "engines" which will match strings against this graph (and so do regular expression matching). but it is much slower than the python library (because it is pure python).

this is not supported and may not be very clear - sorry - but i think it's close to what you want and you're welcome to use it if it's useful (MPL or LGPL licence).