python - Pythonでプレフィックス正規表現から式ツリーを作成しますか?

Question

以下のようなプレフィックス表記の正規表現が与えられます。

(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*"

上記の正規表現を入力として与えられた式ツリーにこれを解析するにはどうすればよいですか? 一部の用語内に空白があるため、空白で分割することはできません。そのため、どこから始めればよいかわかりません。

Answer 1

括弧で囲まれた表現とアトミックな表現を分割することで、これを攻撃し始めます。この 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>

うまくいけば、残りを埋めて、それを実際の実行可能なパーサーに変換する方法を見つけてください。