python - 将自上而下的文法规则转换为 BNF

Question

我继承了一个 ANTLR 语法，现在我需要编写一个很好的、古老的、类似 YACC/BISON 的解析器(具体来说，我使用 PLY for python)。有许多奇怪的规则，我现在正在努力解决以下问题:

factor : ('(' expr ')' | procedure | variable) ('.' variable | call)* '!'?

目前，我只有第一部分的规则，它们是

factor :  '(' expr ')' 
       | procedure 
       | variable

以及 PLY 规则:

def p_factor_1(self, p):                                                                                                                                                                                       
    """ factor : LPAREN expr RPAREN """                                                                                                                                                                        
    p[0] = p[2]                                                                                                                                                                                                

def p_factor_2(self, p):                                                                                                                                                                                       
    """ factor : variable                                                                                                                                                                                      
               | procedure_definition                                                                                                                                                                          
    """                                                                                                                                                                                                        
    p[0] = p[1]  

我怎样才能把最上面的部分变成真正适合 PLY 的东西？我需要合理的规则，以便我可以为单个 expr、过程、变量构造一个 AST 节点，然后还可以为变量访问和链式调用的链接构造一些节点。更糟糕的是还有'!' .原始语法的创建者这样做是为了给予最高优先级的因式分解，但对于转换来说，这是一个彻头彻尾的痛苦。

Answer 1

有条不紊地做:)

           V → ω X             V → V X                V → ω 
V → ω X? ⇒            V → X* ⇒            V → ω | ζ ⇒ 
           V → ω               V →                    V → ζ

当然，如果您必须在单个产品中执行上述多个操作，则需要引入新的非终端。

所以:

factor : ('(' expr ')' | procedure | variable) ('.' variable | call)* '!'?

一个。引入新的非终端:

factor          : factor-prefix factor-suffix '!'?
factor-prefix   : '(' expr ')' | procedure | variable
factor-suffix   : factor-continue*
factor-continue : '.' variable | call

B.按以上规则替换

  factor          : factor-prefix factor-suffix '!'?
⇒
  factor          : factor-prefix factor-suffix '!'
  factor          : factor-prefix factor-suffix

  factor-prefix   : '(' expr ')' | procedure | variable
⇒
  factor-prefix   : '(' expr ')'
  factor-prefix   : procedure
  factor-prefix   : variable

  factor-suffix   : factor-continue*
⇒
  factor-suffix   : factor-suffix factor-continue
  factor-suffix   :

  factor-continue : '.' variable | call
⇒
  factor-continue : '.' variable
  factor-continue : call