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

我怎么会去解析成一个表达式树这给出了上述正则表达式作为输入？它不能在空白处被分割，因为在某些术语中有空格，所以我不确定从哪里开始。

这听起来像是功课。如果是这样，那么约束是什么？你是否应该使用正则表达式来解析它，或者写一个解析器？如果是后者，你可以使用像'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>

希望你可以在休息填写，并找出如何把这种为实际的可执行解析器。

在Python中从前缀regex创建表达式树？

相关推荐