2010-12-31 18 views
5

Estoy tratando de averiguar cómo hacer una expresión de asociación de la izquierda donde son posibles las expresiones recursivas (no incluidas en nada). Por ejemplo, me gustaría hacer:Expresiones recursivas con pyparsing

expr + OP + expr 

que analiza 2 operaciones como 1 x 2 x 3 en (expr OP expr) OP expr resultado.

Si intento para evitar expr análisis de recursividad infinita, lo que puedo hacer algo como:

expr -> Group(simple_expr + OP + expr) 
     | simple_expr 

pero entonces tendría obtener el resultado expr OP (expr OR expr).

¿Cómo fuerzo el encuadernado del lado izquierdo?

Editar: Sé acerca de operatorPrecedence pero cuando el operador es "IS" + Optional("NOT") o similar, no parece coincidir correctamente.

Respuesta

8

Aquí es una acción de análisis ejemplo que se llevará a las listas planas de tokens y nido de ellos como si analizado izquierda recursiva:

from pyparsing import * 

# parse action -maker 
def makeLRlike(numterms): 
    if numterms is None: 
     # None operator can only by binary op 
     initlen = 2 
     incr = 1 
    else: 
     initlen = {0:1,1:2,2:3,3:5}[numterms] 
     incr = {0:1,1:1,2:2,3:4}[numterms] 

    # define parse action for this number of terms, 
    # to convert flat list of tokens into nested list 
    def pa(s,l,t): 
     t = t[0] 
     if len(t) > initlen: 
      ret = ParseResults(t[:initlen]) 
      i = initlen 
      while i < len(t): 
       ret = ParseResults([ret] + t[i:i+incr]) 
       i += incr 
      return ParseResults([ret]) 
    return pa 


# setup a simple grammar for 4-function arithmetic 
varname = oneOf(list(alphas)) 
integer = Word(nums) 
operand = integer | varname 

# ordinary opPrec definition 
arith1 = operatorPrecedence(operand, 
    [ 
    (None, 2, opAssoc.LEFT), 
    (oneOf("* /"), 2, opAssoc.LEFT), 
    (oneOf("+ -"), 2, opAssoc.LEFT), 
    ]) 

# opPrec definition with parseAction makeLRlike 
arith2 = operatorPrecedence(operand, 
    [ 
    (None, 2, opAssoc.LEFT, makeLRlike(None)), 
    (oneOf("* /"), 2, opAssoc.LEFT, makeLRlike(2)), 
    (oneOf("+ -"), 2, opAssoc.LEFT, makeLRlike(2)), 
    ]) 

# parse a few test strings, using both parsers 
for arith in (arith1, arith2): 
    print arith.parseString("A+B+C+D+E")[0] 
    print arith.parseString("A+B+C*D+E")[0] 
    print arith.parseString("12AX+34BY+C*5DZ+E")[0] 

Lienzo:

(normales)

['A', '+', 'B', '+', 'C', '+', 'D', '+', 'E'] 
['A', '+', 'B', '+', ['C', '*', 'D'], '+', 'E'] 
[['12', 'A', 'X'], '+', ['34', 'B', 'Y'], '+', ['C', '*', ['5', 'D', 'Z']], '+', 'E'] 

(similar a LR)

[[[['A', '+', 'B'], '+', 'C'], '+', 'D'], '+', 'E'] 
[[['A', '+', 'B'], '+', ['C', '*', 'D']], '+', 'E'] 
[[[[['12', 'A'], 'X'], '+', [['34', 'B'], 'Y']], '+', ['C', '*', [['5', 'D'], 'Z']]], '+', 'E'] 
1

Pyparsing produce árboles de análisis izquierdo. Agregue una acción semántica para editar el árbol de análisis justo después de que se haya analizado expr.