Skip to main content
 首页 » 编程设计

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

2024年11月01日10小虾米

我继承了一个 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 节点,然后还可以为变量访问和链式调用的链接构造一些节点。更糟糕的是还有'!' .原始语法的创建者这样做是为了给予最高优先级的因式分解,但对于转换来说,这是一个彻头彻尾的痛苦。

请您参考如下方法:

有条不紊地做:)

           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