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>

希望您可以填写其余部分，并弄清楚如何将其转换为实际的可执行解析器。