在Python中從前綴regex創建表達式樹？

我給出前綴符號正則表達式像下面這樣：在Python中從前綴regex創建表達式樹？

(r* (r. r| a (r. b b) (r. c (r* c))) a))

其中：

c (for any char c) means "regex accepting the single-character string c" 
r. means "regex accepting the empty string" 
r/ means "regex accepting nothing" 
(r| r1 r2 ...) means "r1 union r2 union ..." 
(r. r1 r2 ...) means "r1 concat r2 union ..." 
(r* r1) means "r1*"

我怎麼會去解析成一個表達式樹這給出了上述正則表達式作爲輸入？它不能在空白處被分割，因爲在某些術語中有空格，所以我不確定從哪裏開始。

來源

2013-02-13 Jakemmarsh

這聽起來像是功課。如果是這樣，那麼約束是什麼？你是否應該使用正則表達式來解析它，或者寫一個解析器？如果是後者，你可以使用像'pyparsing'這樣的庫嗎？或者你必須從頭開始做什麼，除了stdlib？ – abarnert 2013-02-13 22:39:43

@abarnert它是功課。我們應該編寫一個解析器，但如果我們願意，可以使用像pyparsing一樣的庫。我只是沒有經驗與該圖書館，並沒有發現它用於前綴（波蘭）符號的例子。 – Jakemmarsh 2013-02-13 22:42:58

另外，'（r。r1 r2）'看起來含糊不清。規則是否有優先權（嘗試從下到上貪婪地應用規則） - 或者，相當於'r.'實際上是指類似於「正則表達式接受空字符串，除非它是第一個元素括號表達「？ – abarnert 2013-02-13 22:44:37

我會開始攻擊這個通過分解圓括號和原子表達式。事情是這樣的BNF：

<expr> ::= "(" <paren-expr> ")" 
     | <atomic-expr> 

<exprs> ::= <expr> 
      | <expr> <space> <exprs> 

<atomic-expr> ::= <empty-expr> | <nothing-expr> | <char> 

<paren-expr> ::= <union-expr> | <concat-expr> | <star-expr> 

<union-expr> ::= "r|" <space> <exprs> 

<star-expr> ::= "r*" <space> <expr>

希望你可以在休息填寫，並找出如何把這種爲實際的可執行解析器。

來源

2013-02-13 22:54:41 abarnert

在Python中從前綴regex創建表達式樹？

回答

相關問題