python - Descenso recursivo simple en PyParsing

recursive-descent

Question

He intentado tomar este código y convertirlo en algo para un proyecto en el que estoy trabajando para el procesamiento del lenguaje de programación, pero tengo 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 varias modificaciones diferentes de esta configuración simple. Por lo general, intentando algo como:

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

Volverá [''1''] . Mientras estoy atrapado en una profunda recursión con algo como:

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

¿Qué me falta con respecto a la recursión simple de que no puedo analizar expresiones aritméticas arbitrarias, como 1+(2 * 3-(4*(5+6)-(7))... ?

Answer 1

¿Esto es 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)" )

emitiendo

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

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

Answer 2

Una gramática como:

expr :: expr op expr

Es difícil trabajar con él porque la recursión sigue sumergiéndose en la izquierda.

Una gramática aritmética normal se vería algo así como:

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

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

Answer 3

Usa operatorPrecedence para construir expresiones. Construirá las expresiones correctas y se ocupará de la precedencia del operador mientras esté 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'']]]]

Answer 4

Wow, supongo 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 déjame añadir un comentario o dos:

1. Si suprimimos los símbolos de paréntesis de apertura y cierre, y agrupamos la expresión en paréntesis utilizando Grupo, el establecimiento de un resultado estructurado será más cercano a 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 + atom)
       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)" )

   Dando:

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

   De lo contrario, el establecimiento de parámetros es solo tokenización, y usted tiene que recorrer la lista de tokens analizados para encontrar las expresiones anidadas.

2. Dado que op se define como solo oneOf ("+ - * /"), no hay precedencia de operaciones. Hay ejemplos en el repositorio de pyparsing en https://github.com/pyparsing/pyparsing/tree/master/examples de la forma manual de definir esto (fourFn.py), o el enfoque más reciente utilizando el ayudante de anotación de infijo (simpleArith). py). De nuevo, esto tiene que agregar más valor que solo tokenización.

Para el OP, por favor revisa esos ejemplos, creo que te ayudarán a avanzar en tu proyecto.

-- Pablo