如何在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>

希望你能把剩下的部分补充完整，并找出如何将其转换为一个真正可以执行的解析器。