descendente recursivo simple en PyParsing

Question

he intentado tomar this code y convirtiéndolo en algo para un proyecto que estoy trabajando para el procesamiento de lenguaje de programación, pero estoy corriendo en un problema con una versión simplificada:

op = oneOf('+ -/*') 
lparen, rparen = Literal('('), Literal(')') 

expr = Forward() 
expr << (Word(nums) | (expr + op + expr) | (lparen + expr + rparen)) 

He jugado con una serie de modificaciones diferentes de esta configuración simple. Por lo general, tratando algo como:

print(expr.parseString('1+2')) 

Will volver ['1']. Mientras me pillan en profundidad de recursión con algo como:

print(expr.parseString('(1+2)')) 

¿Qué me falta con respecto a la recursividad sencilla que no puedo analizar arbitrariamente expresiones aritméticas, tales como 1+(2 * 3-(4*(5+6)-(7))...?

Answer 1

Una gramática como:

expr :: expr op expr 

es difícil de trabajar debido a la recursividad sólo mantiene el buceo en la izquierda.

Una gramática aritmética normal, sería algo como:

expr :: mulxp | mulxp '+' expr 
mulxp :: atom | atom '*' expr 
atom :: Word(nums) | '(' + expr + ')' 

Básicamente, nunca se tiene S :: S; cada vez que aparece un no terminal en los lados izquierdo y derecho de una línea en la gramática, debe haber un literal en el medio para que el analizador consuma.

Answer 2

¿Es esto más o menos lo que quieres ...?

from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf 

def Syntax(): 
    op = oneOf('+ -/*') 
    lpar = Literal('(') 
    rpar = Literal(')') 
    num = Word(nums) 

    expr = Forward() 
    atom = num | (lpar + expr + rpar) 
    expr << atom + ZeroOrMore(op + expr) 
    return expr 


if __name__ == "__main__": 

    expr = Syntax() 

    def test(s): 
     results = expr.parseString(s) 
     print s,'->', results 

    test("(9 + 3)") 
    test("(9 + 3) * (4/5)") 

emisor

(9 + 3) -> ['(', '9', '+', '3', ')'] 
(9 + 3) * (4/5) -> ['(', '9', '+', '3', ')', '*', '(', '4', '/', '5', ')'] 

? Esto "ancla" la recursión separando un "átomo" (número o expresión entre paréntesis) de una "expresión" (uno o más "átomos" con operadores intermedios).

Answer 3

¡Guau, creo que pyparsing está realmente en el mapa! Gracias Alex y John por intervenir en esta pregunta. Ambos están en la marca con sus respuestas. Pero permítanme añadir un comentario o dos:

1. Si suprimimos la apertura y cierre de paréntesis símbolos, y el grupo de la expresión entre paréntesis utilizando Group, pyparsing hará resultado estructurado que está más cerca de un AST.

   from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf,Group 
   
   def Syntax(): 
       op = oneOf('+ -/*') 
       lpar = Literal('(').suppress() 
       rpar = Literal(')').suppress() 
       num = Word(nums) 
       expr = Forward() 
       atom = num | Group(lpar + expr + rpar) 
       expr << atom + ZeroOrMore(op + expr) 
       return expr 
   
   if __name__ == "__main__": 
       expr = Syntax() 
       def test(s): 
        results = expr.parseString(s) 
        print s,'->', results 
   
       test("(9 + 3)") 
       test("(9 + 3) * (4/5)") 
   

   Dar:

   (9 + 3) -> [['9', '+', '3']] 
   (9 + 3) * (4/5) -> [['9', '+', '3'], '*', ['4', '/', '5']] 
   

   De lo contrario, es sólo pyparsing tokenizing, y tienes que caminar por la lista de tokens analiza para encontrar las expresiones anidadas.

2. Como op se define como solo oneOf ("+ - * /"), no hay precedencia de operaciones. Hay ejemplos en la wiki de pyparsing de la forma manual para definir esto (fourFn.py), o el enfoque más reciente utilizando el operadorPrecedence helper (simpleArith.py). Nuevamente, esto tiene pyparsing agregando más valor que solo tokenizing.

Para el OP, consulte estos ejemplos, creo que lo ayudarán a avanzar en su proyecto.

- Paul

Answer 4

Uso operatorPrecedence para construir expresiones, por ejemplo, como en el ejemplo de http://pyparsing.wikispaces.com/file/view/simpleArith.py/30268305/simpleArith.py. Se va a construir las expresiones correctas, y cuidar de precedencia de los operadores, mientras que en ello:

num = Word(nums) 
plusop = oneOf('+ -') 
multop = oneOf('/ *') 
expr = operatorPrecedence(num, 
          [(multop, 2, opAssoc.LEFT),(plusop, 2, opAssoc.LEFT)]) 

ejemplo:

>> print parsetime.expr.parseString("1+(2 * 3-(4*(5+6)-(7)))") 
[['1', '+', [['2', '*', '3'], '-', [['4', '*', ['5', '+', '6']], '-', '7']]]]