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

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #15 il: Ottobre 11, 2015, 23:14 »
Ciao ragazzi, grazie per le risposte!

Citazione da: riko
Io direi che non implementa correttamente la precedenza degli operatori.
Si a quello non avevo pensato, ma è giusto implementarlo.

Citazione da: GlennHK
Io direi che float matcha anche ".", o sbaglio?
Hai ragione Glenn. Per matchare correttamente un float ho trovato una porzione di EBNF di python:
[codice]floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+[/codice]
anche se è una EBNF "mista" di due stili diversi.. usa + e [] insieme (anziché ?)

comunque una EBNF per espressioni così semplici non è difficile:

E = T (+|- T)*
T = F (*|/ F)*
F = "(" E ")" | number | string "(" E ")"
wow... me la devo studiare fuori bene questa..



Scusatemi se sono così niubbo, ma non ho l'esperienza dalla mia. Ho invece molta voglia di imparare!  :) :)
ho provato anche a parlarne con un mio prof, che mi ha detto che lui userebbe ... eval  :O (ha perso molti punti fiducia in un colpo solo)


PS: adesso mi guardo fuori anche la grammatica di python che ho trovato qui.
« Ultima modifica: Ottobre 11, 2015, 23:16 da bebo »

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #16 il: Ottobre 12, 2015, 00:16 »
Da quell'esempio trovato su internet ho provato a riflettere un po' e penso di essere arrivato alla EBNF corretta per un float à la C:
[codice]unsigned_int := digit+
signed_int := plus_or_minus unsigned_int
opt_signed_int := plus_or_minus? unsigned_int
point := "."
float_num := signed_int point unsigned_int? | point unsigned_int | opt_signed_int point? unsigned_int? ("e" | "E") opt_signed_int[/codice]
così dovrebbe fare match su tutti i casi più disparati di float che potrei trovare (questi ad esempio: 32.094   0.12   .935   -1e+13   84.102e-25 ). Ne ho saltato qualcuno secondo voi?


Adesso cerco di capire meglio la grammatica usata in fourFn.py.

Ogni commento o aiuto è benvenuto :)

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.651
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #17 il: Ottobre 12, 2015, 04:59 »
Eval buttalo giustamente nel cesso.

Float::= (+|-)? (. (0|...|9)+) | (0|...|9)(.(0|...|9)+) ( (e|E) (+|-) (0|...|9)+ )?

Vado ad intuito, ma mi sembra abbastanza coerente con la tua.

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.651
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #18 il: Ottobre 12, 2015, 05:04 »
Puoi anche dare un'occhiata a questo mio vecchio progetto, ci trovi anche una ebnf e la semantica statica.

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #19 il: Ottobre 12, 2015, 12:08 »
Float::= (+|-)? (. (0|...|9)+) | (0|...|9)(.(0|...|9)+) ( (e|E) (+|-) (0|...|9)+ )?

Vado ad intuito, ma mi sembra abbastanza coerente con la tua.
più che altro così non faresti match su float del tipo -1e+13. e se aggiungi le condizioni per fare anche questi match ti "dovresti" ritrovare con una ebnf come la mia.

Puoi anche dare un'occhiata a questo mio vecchio progetto, ci trovi anche una ebnf e la semantica statica.
wow perfetto! sto guardando ora le grammatiche dei tuoi progetti.

Grazie dell'aiuto intanto, padre maronno  ;) :D

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.651
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #20 il: Ottobre 12, 2015, 12:56 »
Eval buttalo giustamente nel cesso.

Float::= (+|-)? (. (0|...|9)+) | (0|...|9)(.(0|...|9)+) ( (e|E) (+|-) (0|...|9)+ )?

Vado ad intuito, ma mi sembra abbastanza coerente con la tua.

Pardon, ho commesso un leggero errore
Float::= (+|-)? (. (0|...|9)+ | (0|...|9)(.(0|...|9)+))? ( (e|E) (+|-) (0|...|9)+ )?

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #21 il: Ottobre 12, 2015, 13:55 »
Float::= (+|-)? (. (0|...|9)+ | (0|...|9)(.(0|...|9)+))? ( (e|E) (+|-) (0|...|9)+ )?

sbaglio o così prenderebbe anche un semplice + o - ? e anche un +e12.


Mi sto studiando la precedenza degli operatori da wiki.
Avete qualche altro link che la spieghi, con un esempio magari?


edit: dopo il tuo esempio ho ripensato anche alla mia ebnf per i float, e l'ho modificata da così:
[codice]unsigned_int := digit+
signed_int := plus_or_minus unsigned_int
opt_signed_int := plus_or_minus? unsigned_int
point := "."
float_num := signed_int point unsigned_int? | point unsigned_int | opt_signed_int point? unsigned_int? ("e" | "E") opt_signed_int[/codice]

a così
[codice]unsigned_int := digit+
signed_int := plus_or_minus unsigned_int
opt_signed_int := plus_or_minus? unsigned_int
point := "."
float_num := signed_int point unsigned_int? | point unsigned_int | opt_signed_int (point | unsigned_int | point unsigned_int) ("e" | "E") opt_signed_int[/codice]
« Ultima modifica: Ottobre 12, 2015, 14:11 da bebo »

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.651
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #22 il: Ottobre 12, 2015, 14:18 »
argh mi sono imbrogliato con le parentesi!

Ultimo tentativo:

Float::= (+|-)? (. (0|...|9)+ | (0|...|9)(.(0|...|9)+)?) ( (e|E) (+|-) (0|...|9)+ )?

Per quanto riguarda la precedenza, è semplice, è tutta una questione di come la grammatica è espansa.

Prendiamo la mia EBNF di prima come esempio:

E = T (+|- T)*
T = F (*|/ F)*
F = "(" E ")" | number | string "(" E ")"

e applichiamola all'espressione 2 + 3 * 4

mi trovo in E (albero vuoto)
incontro 2 -> T
incontro 2 -> F
2 matcha number, ok, avanza a + (costruisco una foglia (2) )
torno a T, + non matcha *|/, vado su
torno ad E, + matcha +|- quindi passo a 3 (costruisco un nodo (+), attacco (2) come figlio sinistro )
incontro 3 -> T
incontro 3 -> F
3 matcha number, ok, avanza a * ( costruisco un nodo (3) )
torno a T, * matcha * | /, quindi passo a 4 (costruisco un nodo (*), attacco (3) come figlio sinistro )
incontro 4 -> T
incontro 4 -> F
4 matcha number, ok (costruisco (4) )
risalgo a F ( attacco (4) come figlio destro di (*) )
risalgo a T ( attacco (*) come figlio destro di (+) )

l'albero sintattico che ne viene fuori è
                  ( 4 )
         ( * )
( + )           ( 3 )
        ( 2 )

Come puoi vedere, gli operatori con maggiore precedenza devono stare ai livelli più bassi della grammatica, poiché risalendo li incontreresti prima e quindi genereresti i corrispondenti nodi prima.

Ad esempio, ti lascio come esercizio di estendere la mia piccola EBNF con l'operazione di elevamento a potenza, che deve avere priorità maggiore di moltiplicazione e divisione. Dove la metteresti?

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #23 il: Ottobre 12, 2015, 22:26 »
Grazie della spiegazione passo passo Glenn, mi è veramente servita.

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]


Provando a rivedere la mia ebnf alla luce del problema dei float e della precedenza degli operatori, sono arrivato a questo:
[codice]digit := "0"|...|"9"
letter := "a"|...|"z"
plus_or_minus := "+"|"-"
mul_or_div := "*"|"/"

unsigned_int := digit+
signed_int := plus_or_minus unsigned_int
opt_signed_int := plus_or_minus? unsigned_int
point := "."
float_num := signed_int point unsigned_int? | point unsigned_int | opt_signed_int (point | unsigned_int | point unsigned_int) ("e" | "E") opt_signed_int
real_num := opt_signed_int | float _num| "pi()"

add_op := mul_op (plus_or_minus mul_op)*
mul_op := expr (mul_or_div expr)*
function := letter (letter|digit)* "(" add_op ")"
expr := "(" add_op ")" | real_num | function
[/codice]

A questo punto mi sembra corretta, di sicuro più di quanto avessi fatto prima. Avete altri suggerimenti?

Provo a implementare il lexer in pyparsing?


Ho una domandona, un dubbio che ancora mi sfugge, e che magari sembrerà stupido: il parsing vero e proprio in che momento dell'esecuzione si fa? Mentre ancora sto facendo il lexing, o dopo aver finito il lexing?
Cioè: si invoca subito una funzione con un algoritmo tipo lo shunting-yard che cominci a mettere gli oggetti in uno stack, ecc ecc
oppure
si analizza tutta la stringa e si ritorna un "oggetto pyparsing" da calcolare effettivamente dopo?
La mia è proprio una domanda strutturale.

Grazie ancora per le preziosissime indicazioni. Nel tempo libero continuerò a studiare.
« Ultima modifica: Ottobre 12, 2015, 22:42 da bebo »

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #24 il: Ottobre 13, 2015, 12:53 »
Ho provato a scrivere la ebnf in pyparsing, questa è la mia prova:
[codice]digit = Word(nums)
letter = Word(alphas)
plus_or_minus = Word("+-")
mul_or_div = Word("*/")

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

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(")") | real_num | function )[/codice]

provando a testarlo con add_op.parseString("sqrt(pow({d}/2,2)+{d}*{c}/pi()/8.854/4*1000)-{d}/2") esplode sul primo carattere con questo output:
[codice]Traceback (most recent call last):                                                                                                                                                     
....                                                                                                                                               
  File "/usr/lib/python2.7/dist-packages/pyparsing.py", line 1041, in parseString                                                                                                     
    raise exc                                                                                                                                                                         
pyparsing.ParseException:  (at char 0), (line:1, col:1)  [/codice]

cosa sbaglio?

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 #25 il: Ottobre 13, 2015, 22:21 »
Non dovrebbe essere expr.parseString? Esplode lo stesso, ma sul carattere 4. Esperimenti più semplici quantomeno danno un risultato, anche se non mi sembra corretto:
[codice]In [1]: expr.parseString('1 + 2')
Out[1]: (['1'], {})

In [2]: expr.parseString('1 + 2 * 3')
Out[2]: (['1'], {})

In [3]: expr.parseString('1 + (2 * 3)')
Out[3]: (['1'], {})[/codice]

EDIT: Riguardando il tuo codice, dove è la parte in cui descrivi le variabili (parentesi graffe)?
« Ultima modifica: Ottobre 13, 2015, 23:55 da Python »

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #26 il: Ottobre 14, 2015, 21:05 »
Ciao python!
Grazie dell'interessamento!
E grazie per avermi fatto notare di essermi dimenticato delle variabili di moodle, quelle racchiuse tra le graffe.
Ho sistemato spero per l'ultima volta l'EBNF: (mi sono anche accorto che il float prima faceva match anche con opt_signed_int + unsigned_int + E.... quindi l'ho sistemato)
[codice]digit := "0"|..|"9"
letter := "a"|..|"z"
plus_or_minus := "+"|"-"
mul_or_div := "*"|"/"

unsigned_int := digit+
signed_int := plus_or_minus unsigned_int
opt_signed_int := plus_or_minus? unsigned_int
point := "."
float_num := plus_or_minus? (unsigned_int point unsigned_int? | point unsigned_int) (("e"|"E") opt_signed_int)?
moodle_var := "{" letter (letter|digit)* "}"
real_num := opt_signed_int | float_num | "pi()" | moodle_var

add_op := mul_op (plus_or_minus mul_op)*
mul_op := expr (mul_or_div expr)*
function := letter (letter|digit)* "(" add_op ")"
expr := "(" add_op ")" | real_num | function[/codice]

Cosa ne dite?


Ho riscritto anche il codice in pyparsing:
[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(")")) ^ real_num ^ function )[/codice]

Invece @Python, il metodo parseString dev'essere proprio richiamato su add_op, che a cascata può (o meglio, *dovrebbe*) arrivare fino a expr al bisogno.
Questo è l'unico modo per fare match di espressioni come nel caso di 3+2, perché giustamente dopo che ha fatto match con 3, è finita la grammatica e pyparsing termina, mentre partendo da add_op e ritornandoci, come ha mostrato Glenn un paio di messaggi fa, c'è la ZeroOrMore che può far continuare la grammatica.

Nonostante questo, quando chiamo add_op.parseString("9 + 3"), pyparsing esplode:
[codice]$ python parserprova.py
Traceback (most recent call last):
  File "parserprova.py", line 52, in <module>
    print add_op.parseString("9 + 3")
  File "/usr/lib/python2.7/site-packages/pyparsing.py", line 1125, in parseString
    raise exc
pyparsing.ParseException:  (at char 0), (line:1, col:1)[/codice]


Idee??  :(


Edit: spostato riga function dopo add_op, come era in origine (errore mio a trascrivere sul forum facendo pulizia), vedi mess di python qua sotto.
« Ultima modifica: Ottobre 14, 2015, 23:30 da bebo »

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 #27 il: Ottobre 14, 2015, 23:09 »
C'è qualcosa che non quadra, perché alla linea 14 usi add_op che non esiste. Tuttavia anche aggiungendo Forward non cambia nulla.
Sinceramente non saprei come aiutarti, gli errori di PyParsing sono praticamente inutili (nessun messaggio?!) e io non l'ho mai usato...

Offline bebo

  • python erectus
  • ***
  • Post: 231
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #28 il: Ottobre 14, 2015, 23:28 »
Si hai ragione per quanto riguarda function sopra, colpa mia che ho invertito la riga.

Ho editato e commentato il post prcedente per evitare di scrivere sempre lo stesso codice.


Gli errori che genera pyparsing sono completamente inutili, sono d'accordo. Non capisco proprio perché dovrebbe dare errori sul primo carattere, visto che è un numero.
Se faccio semplicemente real_num.parseString("3") o anche real_num.parseString("-.23E+0213") funziona perfettamente.
L'errore *dovrebbe* essere nel paragrafo seguente.

Ogni idea o aiuto è benvenuto!!

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.651
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: pyparsing - come impostare la grammatica e poi visitare la lista?
« Risposta #29 il: Ottobre 15, 2015, 10:48 »
Devi mettere "<<" anche a mul_op in quanto dichiarato come Forward.

Dalla wiki di pyparsing: "Forward - placeholder token used to define recursive token patterns; when defining the actual expression later in the program, insert it into the Forward object using the << operator (see fourFn.py for an example)."