是否有任何编译器可以将regexp转换为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
}"""

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

该库还有各种“引擎”，可以将字符串与该图进行匹配（正则表达式匹配也是如此）。但它比 python 库慢得多（因为它是纯 python）。

这不受支持，并且可能不是很清楚 - 抱歉 - 但我认为它接近您想要的，如果它有用，欢迎您使用它（MPL 或 LGPL 许可证）。