Semplice discesa ricorsiva nel PyParsing

Question

ho cercato di prendere this code e convertirlo in qualcosa per un progetto su cui sto lavorando per l'elaborazione del linguaggio di programmazione, ma sto correndo in un problema con una versione semplificata:

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

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

Ho giocato con una serie di diverse modifiche a questa semplice installazione. Di solito, provare qualcosa di simile:

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

torneranno ['1']. Mentre mi beccano in profonda ricorsione con qualcosa di simile:

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

Che cosa mi manca rispetto alla semplice ricorsione che non posso analizzare le espressioni aritmetiche arbitrariamente, come ad esempio 1+(2 * 3-(4*(5+6)-(7))...?

Answer 1

Una grammatica come:

expr :: expr op expr 

è difficile da lavorare perché la ricorsione continua a tuffarsi nel sinistro.

Una grammatica aritmetica normale sarebbe simile:

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

In sostanza, non si ha mai S :: S; ogni volta che una grammatica non terminale appare sui lati sinistro e destro di una linea nella grammatica, ci deve essere un letterale nel mezzo affinché il parser consumi.

Answer 2

Questo è più o meno quello che vuoi ...?

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)") 

emettono

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

? Questo "fissa" la ricorsione separando un "atomo" (numero o espressione tra parentesi) da una "espressione" (uno o più "atomi" con operatori intermedi).

Answer 3

Wow, immagino che il pyparsing sia davvero sulla mappa! Grazie Alex e John per intervenire su questa domanda. Siete entrambi sul marchio con le vostre risposte. Ma permettetemi di aggiungere un commento o due:

1. Se si sopprime l'apertura e la chiusura dei simboli parentesi, e il gruppo l'espressione tra parentesi usando Group, pyparsing sarà il risultato strutturato che è più vicino 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 + 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)") 
   

   Dare:

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

   In caso contrario, pyparsing è solo creazione di token, e bisogna camminare l'elenco di token analizzato per trovare le espressioni nidificate.

2. Poiché op è definito come solo unOf ("+ - * /"), non esiste la precedenza delle operazioni. Ci sono esempi sul wiki di pyparsing del modo manuale per definire questo (fourFn.py), o l'approccio più recente che usa l'helper operatorePrecedence (simpleArith.py). Ancora una volta, questo ha il pyparsing aggiungendo più valore della semplice tokenizzazione.

Per l'OP, si prega di consultare quegli esempi, penso che ti aiuteranno a far progredire il tuo progetto.

- Paul

Answer 4

Usa operatorPrecedence per costruire espressioni, ad esempio, come nell'esempio a http://pyparsing.wikispaces.com/file/view/simpleArith.py/30268305/simpleArith.py. Sarà costruire le espressioni corrette, e prendersi cura di precedenza degli operatori, mentre a esso:

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

esempio:

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