python - 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'ab*c' : //code.google.com/p/rxpy/source/browse/rxpy/src/rxpy/parser/_test/parser.py#234のテストを見てみましょう。

"""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
}"""

that で始まる0which は、「a」に一致して state に移動できます1。そこから、「b」に一致して状態に移動する2か、「c」に一致して状態に移動できます3。状態2は、別の「b」などを消費できる状態に戻る遷移1があります。手で読むのは少し見にくいですが、テストが失敗すると、画面に小さなグラフが表示されます。

ライブラリには、このグラフに対して文字列を照合するさまざまな「エンジン」もあります (正規表現の照合も同様です)。ただし、python ライブラリよりもはるかに低速です (純粋な python であるため)。

これはサポートされておらず、あまり明確ではないかもしれません - 申し訳ありません - しかし、私はそれがあなたが望むものに近いと思います.