是否有任何編譯器可以將regexp轉換爲fsm？或可以轉換爲人類的話？

的東西，可以轉換是否有任何編譯器可以將regexp轉換爲fsm？或可以轉換爲人類的話？

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

到

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

或類似

，並在2個或5

來源

2012-06-24 somethin

回到我們的理論CS類中，我們確實有一種將正則表達式轉換爲FSM的方法。畢竟這正是一個正則表達式引擎無論如何。 – Joey

我有一些代碼會這樣做。它沒有很好的文檔記錄，並且不被支持，但是如果你感興趣的話，歡迎來看看它。

庫被稱爲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這可以匹配「一個」去國家1。從那裏你可以匹配一個「b」到狀態2或「c」去狀態3。狀態2然後轉換回1，可能會消耗另一個「b」等等，手動讀取有點難看，但是當測試失敗時，您會在屏幕上顯示一個小圖。

該庫還具有各種「引擎」，它們會將字符串與此圖匹配（並且正則表達式匹配也如此）。但它比python庫慢得多（因爲它是純Python）。

這是不支持，可能不是很清楚 - 對不起 - 但我認爲它接近你想要的，如果有用的話，歡迎你使用它（MPL或LGPL許可證）。

來源

2012-06-24 12:46:14

接受你有一個debug flag東西，打印您的正則表達式更可讀形式：

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

來源

2012-06-24 10:43:34 kosii

是否有任何編譯器可以將regexp轉換爲fsm？或可以轉換爲人類的話？

回答

相關問題