Newsgroup: it.comp.programmare
Titolo: Parser top-down (in python)

>> print parse('3 + 5 + 7')
('+', 3, ('+', 5, 7))
per la somma (e in generale gli operatori associativi) non ci sono 
problemi, ma se usiamo lo stesso codice per le sottrazioni sono dolori:
('-', 3, ('-', 5, 7)) verrebbe infatti valutato come 3 - (5 - 7), che 
ovviamente e` sbagliato.
Per risolvere ho pensato a questa grammatica:
        expr ::= number | expr + number
pero` il problema ora e` questo: come implementarla?
Forse sara` banale, ma proprio non ci riesco :-(
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 Forse sara` banale, ma proprio non ci riesco :-(
Secondo me bisogna gestire le parentesi e inserire quelle implicite.
A questo punto si può procedere al parsing.
Per esempio:
3 - 4 - 5
diventa
(3 - 4) - 5
e comunque io non costruirei alberi binari, ma alberi del tipo:
(+, 3, -4, -5)
Se per esempio abbiamo:
5 + 7*8 -7 + 4*9
creerei un albero del tipo:
(+, 5, 7*8, -7, 4*9) ==>
(+, 5, (*, 7, 8), -7, (*, 4, 9))
Kiuhnm

 Forse sara` banale, ma proprio non ci riesco :-(
Dimenticavo:
a + b + c        OK (IRRIL.)
a + b*c          OK
a - b - c         AMBIGUA
a * b * c        OK (IRRIL.)
a / b / c          AMBIGUA
ecc...
Il tuo problema mette soltanto in luce che alcune espressioni sono ambigue.
Comunemente si inseriscono quindi delle parentesi mancanti in modo però del
tutto arbitrario, infatti nessuno mi vieta di calcolare un'espressione in un
modo o nell'altro.
Di solito s'inseriscono le parentesi da sinistra verso destra.
Kiuhnm


La grammatica che hai scritto, IMHO, va bene; prova pero' a riscriverla
cosi':
        expr::= numer {+ number }       [1]
Questa grammatica perde l'informazione sull'associativa' dell'operatore + ma
e' molto semplice da implementare.
[1]le parentesi graffe stanno ad indicare la ripetizione di zero o piu'
volte del termine tra esse contenuto.
Ciao, Davide :)

 ha scritto nel messaggio
news:mjg1oa...@anto.cuni.lan...

E' un problema che ho riscontrato anch'io scrivendo un parser per
espressioni matematiche in C++ (purtroppo ho perso il sorgente, ma se ho
tempo lo ricostruisco). L'ho risolto adottando un albero ennario invece di
un semplice binario, basato su una grammatica tipo questa:
 expr ::= { +|- term }
Poi ovviamente c'era la definizione di term, factor, etc. In sostanza avevo
delle classi che rappresentavano i nodi dell'albero di parsing con un metodo
eval() per la valutazione. Il parser quando trovava una somma (o differenza)
creava l'albero ed aggiungeva tutti gli addendi tenendo traccia di quelli
positivi e quelli negativi, qualcosa come (so che il C++ lo conosci,
purtroppo per impegni universitari il python ancora non l'ho potuto
scaricare per dargli un'occhiata):
// we look for a term
Node* term = GetTerm();
token = Scanner.ScanNext();
// we have a sum
if( token == Token :: Plus )
  {
  SumNode* node = new SumNode( GetTerm() );
  token = Scanner.ScanNext();
  while( token == Token :: Plus || token == Token :: Minus )
    {
    Node* term = getTerm();
    node->AddChild( term );
    token = Scanner.ScanNext()
    }
  }
Il fatto che il primo if controlli solo il '+' č conseguenza che un fattore
poteca essere espresso come -expr e quindi il primo termine era da
considerare positivo in quanto veniva gestito da un nodo che nella
valutazione lo rendeva negativo, e considerarlo negativo l'avrebbe reso di
nuovo positivo.
D'altronde questa č solo una parte del parser (neanche sono sicuro che fosse
proprio cosě). L'idea comunque funziona.
Spero ti possa essere d'aiuto!
Ciao,
--
----------------------------
Fulvio Esposito
"La differenza tra teoria e pratica e', in pratica, un po' piu' che in
teoria"
----------------------------

 anziche` a sinistra:
Cuni, mi stupisci. Il tuo:
expr ::= number | expr "+" number
(i terminali li metto tra virgolette, giusto per non confondermi) altro 
non è che un banale:
expr ::= [ expr "+" ] number
che è praticamente la tua grammatica iniziale, ma con ricorsione a 
sinistra anzichè a destra. Come implementarlo non me lo chiedere :-))) 
probabilmente potresti continuare la ricorsione su expr() finchè non 
consiste di un solo token, e a quel punto controllare se è un numero. 
Da quel punto in poi dovrebbe essere abbastanza lineare
-- 
 < 
http://www.reactos.com/
 >  Open source clone of Windows NT. Current
     Don't stand, REACT!      version 0.0.20. C, C++ and ASM developers
                              and beta testers are welcome!

 (+, 3, -4, -5)
penso proprio che utilizzero` una variazione di questa idea. A livello 
implementativo probabilmente rappresentero` gli alberi con una coppia 
(nodo, lista-di-figli), quindi l'espressione in questione diventa:
('-', [3, 4, 5])
forse potrei anche dire al parser di sbattersi un po' di piu` e di 
trasformare le differenze in somme dell'opposto (come fai implicitamente 
tu nel tuo esempio), pero` non mi aggrada molto dover dotare il parser 
di semantica.


  expr ::= { +|- term }
[cut]
vedo che questa soluzione e` quella che va per la maggiore (in pratica la 
tua versione, quella di kiuhnm, quella di davide e quella di maya sono 
grosso modo tutte equivalenti). Tra l'altro python mi consente di 
implementare molto facilmente alberi n-ari utilizzando una lista per 
contenere i nodi, quindi dovrebbe essere facile.
Tra l'altro questa e` anche la tecnica che usa Stroustrup nel capitolo 6 
di TC++PL (anche se in quel caso lo scopo era di valutare le 
espressioni, non di generare l'albero).


 consiste di un solo token, e a quel punto controllare se è un numero.
il problema e` "ridurre" il numero di token fino a farli diventare un 
solo numero. Mi spiego: con questa grammatica:
        expr ::= number [ + expr ]
se proviamo a tradurla meccanicamente abbiamo, in pseudocodice:
expr():
        <cerca di ottenere un numero>
        if <abbiamo ottenuto il numero>
                if <prossimo token> == '+' then return (+, numero, expr())
Se invece la grammatica e`
        expr ::= [expr +] number
la traduzione meccanica inizierebbe con:
expr():
        <cerca di ottenere un expr>
        ...
causando una ricorsione infinita.


 contenere i nodi, quindi dovrebbe essere facile.
Non avevo inteso che il tuo scopo fosse quello di creare l'albero
dell'espressione.
L'espressione, comunque, in una BNF classica e':
Expr ::= Expr + Fatt | Expr - Fatt | Fatt
Fatt ::= Fatt * Term | Fatt / Term | Term
e Term e' l'elemento terminale.
In realta', potresti anche evitare l'uso di un albero n-ario e usare un
semplice albero binario.
Difatti, se hai 5 + 3 * (2 - 2 - 3) lo traduci in:
E = [['*', L1, L2]]
L1 = ['+', [5], [3]]
L2 = ['-', [2], L3]
L3 = ['-', [2], [3]]
In ogni caso, tradurre la notazione infissa in quella prefissa con
l'algoritmo di Dijkstra forse potrebbe aiutarti.
--------------------------------
Inviato via 
http://usenet.libero.it

 dotare il parser di semantica.
OK, felice di esserti stato utile :-)
Kiuhnm

Se ci tieni cosě tanto ti do una soluzione "binaria".
4 - 5 - 3 - 1 + 8
GetExpr()
{
    // Partendo da destra!!!
    b = GetNumber();
    t = GetTocken();
    if (t)
    {
       a = GetExpr();
       return (t, a, b);
    }
    else return b;
}
(4 - 5 - 3 - 1 + 8)
Eseguendolo si ottiene:
b = 8
t = +
a =
{
    b = 1
    t = -
    a =
    {
         b = 3
         t = -
         a =
         {
              b = 5
              t = -
              a =
              {
                   b = 4
              }
              a = 4
              (t, a, b) = (-, 4, 5)
         }
         a = (-, 4, 5)
         (-, (-, 4, 5), 3)
    }
    a = (-, (-, 4, 5), 3)
    (-, (-, (-, 4, 5), 3), 1)
}
a = (-, (-, (-, 4, 5), 3), 1)
(+, (-, (-, (-, 4, 5), 3), 1), b)
Insomma l'albero risultante č
(+, (-, (-, (-, 4, 5), 3), 1), b)
(come desideravi :-) )
OPPURE:
4 - 5 - 3 - 1 + 8
MakeTree(a)
{
    // Partendo da sinistra!!!
    t = GetTocken();
    b = GetNumber();
    MakeTree((t, a, b));
}
Si userebbe nel seguente modo:
MakeTree(GetNumber);
E si avrebbe:
MakeTree(4)
{
  t = -
  b = 5
  MakeTree((-, 4, 5))
  {
     t = -
     b = 3
     MakeTree((-, (-, 4, 5))
     {
        ecc....
        fino ad ottenere:
        MakeTree((+, (-, (-, (-, 4, 5), 3), 1), b))
     }
   }
}
Oppure in generale:
4 - ((5 - 3) - 1 - 7) + 8
BeginTree()
{
   if (GetOpened())   // trovata '('
     a = BeginTree();
   else
     a = GetNum();
   return MakeTree(a);
}
MakeTree(a)
{
    if (GetClosed())
      return 0;
    t = GetTocken();
    if (GetOpened())   // trovata '('
       b = BeginTree();
    else
       b = GetNum();
    return MakeTree((t, a, b));
}
E quindi con
4 - ((5 - 3) - 1 - 7) + 8
si avrebbe:
BeginTree()
{
    a = 4;
    b = BeginTree();   // trovata '('
    {
        a = BeginTree();    // trovata ancora '('
        {
            a = 5
            MakeTree(a);
            {
                t = -
                b = .....
}
Adesso sono un po' stanco, comunque il concetto dovrebbe essere chiaro.
Potrebbero esserci errori: non ho proprio voglia di rileggere tutto...
Kiuhnm

 L3 = ['-', [2], [3]]
Sei sicuro?
Secondo me l'albero che hai scritto e' equivalente a: (5+3)*(2-(2-3))
L'albero per 5+3*(2-2-3) dovrebbe essere:
E = ['+' , 5 , L1]
L1 = ['*' , 3 , L2]
L2 = ['-' , L3 , 3]
L3 = ['-' , 2 , 2]
Ciao, Davide :)

 beh, chiedevo proprio questo ;-))
eh, mi spiace, queste cose preferisco farle fare ad una macchina. Tipo 
yacc. Probabilmente al corso di Linguaggi ci spiegheranno anche come si 
affrontano questi casi, per il momento il mio cervello anestetizzato 
non riesce a produrre nulla. Almeno, niente di corretto


 Secondo me l'albero che hai scritto e' equivalente a: (5+3)*(2-(2-3))
E' vero.


 }
perfetto, era proprio quello che cercavo, grazie!
Solo una cosa: token si scrive senza 'c' ;-)


 In realtà non entri in un circolo vizioso...fidati!
allora come fai a inserire le parentesi al punto giusto?


 Solo una cosa: token si scrive senza 'c' ;-)
E' vero!
Token č un termine che uso poco...
Kiuhnm

 allora come fai a inserire le parentesi al punto giusto?
Si può fare (TUTTO) però non ho voglia di scrivere altro codice...
Kiuhnm

 }
così ovvio che fa male :-) non so perchè, ma pensavo a tutt'altro


 cosě ovvio che fa male :-) non so perchč, ma pensavo a tutt'altro
:-)
Ciao...perchč non mi "offendi" piů?
Ricordo ancora i bei tempi...
Kiuhnm

 Ricordo ancora i bei tempi...
'saggerato! "i bei tempi"! sarà stato, tipo, due mesi fa :-)


 permettono?)
perche` in un contesto piu` ampio (da leggersi come "grammatica piu` 
complessa") non puoi sapere da dove partire a leggere: pensa ad esempio 
al parser di un compilatore C: come fai a sapere il punto in cui finisce 
una espressione senza farne il parsing?
