Topic: pyparsing - come impostare la grammatica e poi visitare la lista?  (Letto 2810 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.652
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #30 il: Ottobre 15, 2015, 10:53 »
Occhio anche a come usi Word, perchè ad esempio "letter = Word(alphas)" non vuol dire che letter è un elemento di alphas, ma una sequenza qualsiasi di elementi di alphas. Devi usare "letter = Word(alphas, max=1)" per indicare che vuoi un elemento solo.

Offline Python

  • python sapiens sapiens
  • ******
  • Post: 2.045
  • Punti reputazione: 2
  • Radon - Cyclomatic Complexity of your Python code
    • Mostra profilo
    • Radon - Cyclomatic Complexity of your Python code
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #31 il: Ottobre 15, 2015, 20:26 »
Ho provato con i cambiamenti di Glenn, che hanno perfettamente senso, ma purtroppo non funziona ancora. E i messaggi di PyParsing sono quasi inutili. Non è che forse conviene cercare un'altra libreria di parsing? Alla fine la parte più difficile probabilmente è progettare la grammatica, poi l'implementazione dovrebbe prendere meno tempo.
« Ultima modifica: Ottobre 15, 2015, 20:45 da Python »

Offline bebo

  • python erectus
  • ***
  • Post: 238
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #32 il: Ottobre 15, 2015, 21:06 »
Citazione da: GlennHK
Devi mettere "<<" anche a mul_op in quanto dichiarato come Forward.

Eurekaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa  :D :D :D

dopo aver sistemato anche questa mia svista dell'uguale con i doppi apici finalmente non esplode più, e fa addrittura il parsing per benino :D

Il codice ora è questo:
[codice]
digit = Word(nums)
letter = Word(alphas)
plus_or_minus = oneOf("+ -")
mul_or_div = oneOf("* /")

unsigned_int = OneOrMore(digit)
signed_int = plus_or_minus + unsigned_int
opt_signed_int = Optional(plus_or_minus) + unsigned_int
point = Word(".")
float_num = Combine( Optional(plus_or_minus) + ( unsigned_int + point + Optional(unsigned_int) | point + unsigned_int ) + Optional(CaselessLiteral("e") + opt_signed_int))
moodle_var = Suppress("{") + Word(alphas, alphas+nums) + Suppress("}")
# here I use the ^ operator to match the longest grammar.
real_num = (float_num ^ opt_signed_int ^ "pi()" ^ moodle_var)

mul_op = Forward()
expr = Forward()
add_op = mul_op + ZeroOrMore(plus_or_minus + mul_op)
mul_op << expr + ZeroOrMore(mul_or_div + expr)
function = Word(alphas, alphas+nums) + Suppress("(") + add_op + Suppress(")")
expr << ( (Suppress("(") + add_op + Suppress(")")) | function | real_num )
[/codice]

ecco alcune prove:
[codice]{Q}*log({b}/{a})/log({c}/{a}) -> ['Q', '*', 'log', 'b', '/', 'a', '/', 'log', 'c', '/', 'a']
sqrt({q1}*{sigma}*(sqrt({a1}*{a1}+{b1}*{b1})-{b1})/{m1}/8.854) -> ['sqrt', 'q1', '*', 'sigma', '*', 'sqrt', 'a1', '*', 'a1', '+', 'b1', '*', 'b1', '-', 'b1', '/', 'm1', '/', '8.854']
round({V1}*{R1}/({R1}+{R2})*100)/100 -> ['round', 'V1', '*', 'R1', '/', 'R1', '+', 'R2', '*', '100', '/', '100']
round({C}*{V1}*{R2}/({R1}+{R2})*100)/100 -> ['round', 'C', '*', 'V1', '*', 'R2', '/', 'R1', '+', 'R2', '*', '100', '/', '100']
round(100*{C}*({R2}+{R3})*log(10))/100 -> ['round', '100', '*', 'C', '*', 'R2', '+', 'R3', '*', 'log', '10', '/', '100'][/codice]

Incredibile come quell'uguale rompesse tutto però...


Invece mi sono accorto di essermi dimenticato che una funzione può avere dei parametri separati da virgola, tipo pow(2,3).
Sistemerò la EBNF e vedrò di prevedere anche quello.
Devo inoltre fare in modo di raggruppare con la classe Group() i valori all'interno delle parentesi tonde, e sostituire le variabili di moodle del tipo {var} con il rispettivo valore che gestisco con una classe apposita.

Il fatto di essere riuscito a far andare una versione "base" mi da fiducia di non essere io l'unico scemo al mondo a non riuscire a far andare pyparsing :P


Volevo chiedere: ora come devo fare? Implemento una funzione da chiamare in coda al match, tipo questa create_node nel link segnalatomi da riko?
Inoltre, voi come creereste l'ast? e come fareste a visitarlo poi? Con l'algoritmo shunting-yard?


Grazie mille ragazzi per la pazienza di avermi sopportato ;)
buona serata intanto!

Offline Python

  • python sapiens sapiens
  • ******
  • Post: 2.045
  • Punti reputazione: 2
  • Radon - Cyclomatic Complexity of your Python code
    • Mostra profilo
    • Radon - Cyclomatic Complexity of your Python code
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #33 il: Ottobre 15, 2015, 21:45 »
L'algoritmo Shunting-yard mi sembra proprio fatto apposta. Tuttavia in questo modo devi reimplementare le precedenze e le associatività (se ho capito bene), quando invece questo lavoro può essere svolto dal parser (come dicevi prima quando parlavi di add_op).

Per spiegarmi meglio faccio un esempio. L'espressione "3 + 4 * 2" potrebbe essere parsata direttamente in un albero: Add(3, Mul(4, 2)), invece che in ['3', '+', '4', '*', '2'] dove bisogna ricominciare da capo. Add e Mul potrebbero essere degli oggetti.

Poiché non conosco PyParsing e poiché volevo esercitarmi in Haskell, ho scritto un piccolo programma che illustrasse quanto detto sopra. Esempio:
[codice]> 2 + 4
Op "+" (Number 2.0) (Number 4.0)
> 2*pi() - sqrt(234, 4) + 4 - 2*4
Op "-" (Op "+" (Op "-"
  (Op "*" (Number 2.0) (Function "pi" [])) (Function "sqrt" [Number 234.0,Number 4.0])) (Number 4.0)) (Op "*" (Number 2.0) (Number 4.0))
[/codice]

In questo caso Op, Number, Function, etc. sono costruttori di tipi (e sono dello stesso tipo). In Python come dicevo prima potresti usare degli oggetti (come fa, tra l'altro, il modulo ast di Python).
Qui il codice (se interessasse a qualcuno):
https://github.com/rubik/moodle-to-latex

Preciso comunque che non me ne intendo di parsing e sto imparando qualcosa adesso.

Offline bebo

  • python erectus
  • ***
  • Post: 238
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #34 il: Ottobre 16, 2015, 00:20 »
Aggiungendo un Group() attorno all' add_op dentro a expr e all' add_op dentro a function ho ottenuto una lista annidata con liste al posto degli elementi delle parentesi.
Esempio:
[codice]round(100*{C}*({R2}+{R3})*log(10))/100 -> ['round', ['100', '*', 'C', '*', ['R2', '+', 'R3'], '*', 'log', ['10']], '/', '100'][/codice]


Per quanto riguarda lo shunting-yard
Citazione da: Python
L'algoritmo Shunting-yard mi sembra proprio fatto apposta. Tuttavia in questo modo devi reimplementare le precedenze e le associatività (se ho capito bene)
No le precedenze dovrebbero essere giuste così come mi ha spiegato Glenn nel post del 12 ottobre delle 14. C'è una cascata alla rovescia applicando la grammatica: praticamente si torna indietro verso l'alto dopo essere scesi fino ad expr.

Non c'è bisogno di "rivisitare" la stringa/ricominciare da capo il parsing dopo aver fatto il lexing.
A qualsiasi riga di grammatica pyparsing si può appendere una funzione, e quando l'espressione fa matching, vengono passati i token trovati a questa funzione. Ad esempio per i float e gli int ho fatto una funzione lambda da aggiungere alla grammatica float_num fatta così:
[codice]float_num = Combine( Optional(plus_or_minus) + ( unsigned_int + point + Optional(unsigned_int) | point + unsigned_int ) + Optional(CaselessLiteral("e") + opt_signed_int)).setParseAction(lambda el: float(el[0]))[/codice]
All'interno di una funzione del genere potrei gestire il riconoscimento dell'operatore ed effettuare già il calcolo.

Questa è una bozza, scritta qua nel forum, non testata, ed ispirata dal FourFn.py di Paul McGuire, l'autore di PyParsing.

[codice]import operator

def Syntax():
    digit = Word(nums)
    letter = Word(alphas)
    plus_or_minus = oneOf("+ -")
    mul_or_div = oneOf("* /")

    unsigned_int = OneOrMore(digit)
    signed_int = Combine(plus_or_minus + unsigned_int)
    opt_signed_int = Combine(Optional(plus_or_minus) + unsigned_int).setParseAction(lambda el: int(el[0]))
    point = Word(".")
    float_num = Combine( Optional(plus_or_minus) + ( unsigned_int + point + Optional(unsigned_int) | point + unsigned_int ) + Optional(CaselessLiteral("e") + opt_signed_int)).setParseAction(lambda el: float(el[0]))
    moodle_var = (Suppress("{") + Word(alphas, alphas+nums) + Suppress("}")).setParseAction(return_el)
    # here I use the ^ operator to match the longest grammar.
    real_num = (float_num ^ opt_signed_int ^ "pi()" ^ moodle_var)

    mul_op = Forward()
    expr = Forward()
    add_op = (mul_op + ZeroOrMore(plus_or_minus + mul_op)).setParseAction(calc)
    mul_op << (expr + ZeroOrMore(mul_or_div + expr)).setParseAction(calc)
    function = Word(alphas, alphas+nums) + Suppress("(") + Group(add_op) + Suppress(")")
    expr << ( Suppress("(") + Group(add_op) + Suppress(")") | function | real_num )

    return add_op

math_ops = {'+': operator.add,
                       '-': operator.sub,
                       '*': operator.mul,
                       # ecc...
                      }

def calc(stringa_che_matcha, posizione_primo_carattere_match, lista_tokens):
    # i primi due elementi che il metodo setParseAction passa alla funzione non mi servono.
    # non so ancora bene perché setParseAction a volte restituisce una lista con solo un elemento
    #  (vedi sopra es con float) e a volte tre argomenti. Investighero'.
    math_symbol = lista_tokens[1]
    num1, num2 = float(lista_tokens[0]), float(lista_tokens[2])
    if lista_tokens[1] in math_ops:
        return math_ops[math_symbol](num1, num2)
[/codice]

ritornando il numero già calcolato tramite questa funzione, questo dovrebbe andare a sostituirsi a tutto il blocco dove prima c'erano i tre elementi, diventando un solo numero.
Se il processo continua a calcolare, l'espressione si risolve da sè senza utilizzare nemmeno lo shunting yard, ma "riducendosi" sempre più.

Può essere un'idea, o sto ragionando nel modo sbagliato?

Buona notte!

Offline Python

  • python sapiens sapiens
  • ******
  • Post: 2.045
  • Punti reputazione: 2
  • Radon - Cyclomatic Complexity of your Python code
    • Mostra profilo
    • Radon - Cyclomatic Complexity of your Python code
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #35 il: Ottobre 16, 2015, 00:36 »
Citazione da: Python
L'algoritmo Shunting-yard mi sembra proprio fatto apposta. Tuttavia in questo modo devi reimplementare le precedenze e le associatività (se ho capito bene)
No le precedenze dovrebbero essere giuste così come mi ha spiegato Glenn nel post del 12 ottobre delle 14. C'è una cascata alla rovescia applicando la grammatica: praticamente si torna indietro verso l'alto dopo essere scesi fino ad expr.

Non c'è bisogno di "rivisitare" la stringa/ricominciare da capo il parsing dopo aver fatto il lexing.
A qualsiasi riga di grammatica pyparsing si può appendere una funzione, e quando l'espressione fa matching, vengono passati i token trovati a questa funzione. Ad esempio per i float e gli int ho fatto una funzione lambda da aggiungere alla grammatica float_num fatta così:
[codice]float_num = Combine( Optional(plus_or_minus) + ( unsigned_int + point + Optional(unsigned_int) | point + unsigned_int ) + Optional(CaselessLiteral("e") + opt_signed_int)).setParseAction(lambda el: float(el[0]))[/codice]
All'interno di una funzione del genere potrei gestire il riconoscimento dell'operatore ed effettuare già il calcolo.

Beh allora mi pare stiamo dicendo cose molto simili. Da quel che leggo sullo shunting-yard l'input è lineare (come una lista per intenderci) e bisogna davvero conoscere le precedenze e le associatività. Usando Group() invece stai già costruendo un albero, che alla fine è quello che dicevo.

Offline Python

  • python sapiens sapiens
  • ******
  • Post: 2.045
  • Punti reputazione: 2
  • Radon - Cyclomatic Complexity of your Python code
    • Mostra profilo
    • Radon - Cyclomatic Complexity of your Python code
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #36 il: Ottobre 16, 2015, 09:12 »
Per le potenze come fai? Io ho dovuto correggere la mia implementazione perché consentivo l'uso dell'operatore ^ e l'esponenziale è associativo a destra, non a sinistra.
Mi par di capire però che in Moodle si usa solo la funzione pow(), quindi non mi sembra ci siano problemi.

Offline bebo

  • python erectus
  • ***
  • Post: 238
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #37 il: Ottobre 17, 2015, 13:21 »
Non conosco bene le grammatiche neppure io, ma da come mi aveva fatto ragionare Glenn direi:
Per ampliare la mini grammatica alle potenze (anche se non è il mio caso in quanto c'è una funzione pow apposita) dovrebbe bastare questo:
[codice]E = T (+|- T)*
T = P (*|/ P)*
P = F (^ F)*
F = "(" E ")" | number | string "(" E ")"[/codice]


Per quanto riguarda l'implementazione in pyparsing, nel FourFn.py è implementato anche l'operatore ^. Riporto le righe salienti:
[codice]        ...
        expr = Forward()
        atom = (Optional("-") + ( pi | e | fnumber | ident + lpar + expr + rpar ).setParseAction( pushFirst ) | ( lpar + expr.suppress() + rpar )).setParseAction(pushUMinus)
       
        # by defining exponentiation as "atom [ ^ factor ]..." instead of "atom [ ^ atom ]...", we get right-to-left exponents, instead of left-to-righ
        # that is, 2^3^2 = 2^(3^2), not (2^3)^2.
        factor = Forward()
        factor << atom + ZeroOrMore( ( expop + factor ).setParseAction( pushFirst ) )
       
        term = factor + ZeroOrMore( ( multop + factor ).setParseAction( pushFirst ) )
        expr << term + ZeroOrMore( ( addop + term ).setParseAction( pushFirst ) )
        bnf = expr[/codice]

Una pagina di wikipedia da leggere sull'argomento è questa (it) e questa (en).

Sono argomenti molto interessanti, ma di "difficile" apprendimento.

...
Beh allora mi pare stiamo dicendo cose molto simili. Da quel che leggo sullo shunting-yard l'input è lineare (come una lista per intenderci) e bisogna davvero conoscere le precedenze e le associatività. Usando Group() invece stai già costruendo un albero, che alla fine è quello che dicevo.
si in effetti Group forse non mi serve neanche, se riesco ad implementare una calcolatrice che risolva un "atomo" di espressione.

More news soon, stay tuned ;)