[Java] Creazione di un COMPILATORE in TurboPascal [Archivio]

Vincenzo1968

30-09-2008, 14:42

...
Anzi, i recursive descent parser generati da grammatiche LL(k) si sono sempre distinti per velocità in passato.
...

I parser a discesa ricorsiva sono(e lo sono sempre stati, anche in passato), tra tutte le tecniche disponibili, quelli meno efficienti perché richiedono il backtracking.

Tratto da Compilers Principles, Tecniques and Tools (http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=pd_cp_b_0/103-4878654-5305440?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-41&pf_rd_r=0NFD5YSKHFP3NQC86NRA&pf_rd_t=201&pf_rd_p=413864201&pf_rd_i=0201100886) di Aho, Lam, Sethi, Ullman(2006):

LR parsers can be constructed to recognize virtually all programminglanguage
constructs for which context-free grammars can be written. Non-
LR context-free grammars exist, but these can generally be avoided for
typical programming-language constructs.

The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other,
more primitive shift-reduce methods (see the bibliographic notes).

An LR parser can detect a syntactic error as soon as it is possible to do
so on a left-to-right scan of the input.

The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or
LL methods. For a grammar to be LR(k), we must be able to recognize
the occurrence of the right side of a production in a right-sentential form,
with k input symbols of lookahead. This requirement is far less stringent
than that for LL(k) grammars where we must be able to recognize the
use of a production seeing only the first k symbols of what its right side
derives. Thus, it should not be surprising that LR grammars can describe
more languages than LL grammars.

Il rovescio della medaglia è che sono più difficili da costruire(per questo sono nati tool come Yacc/Bison e compagnia bella)

Vincenzo1968

30-09-2008, 15:26

Ciao ragazzi!
...
Partendo dai molti manuali trovati in rete, voi avete qualche consiglio da darci? Attendo vostre risposte, grazie...

Puoi postare i link di questi manuali?

Ciao

Vincenzo1968

30-09-2008, 19:38

Il lavoro originale, del 1965, di colui che ha sviluppato le tecniche LR(k), il grande Knuth (http://www-cs-faculty.stanford.edu/~knuth/):

http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR607.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR608.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR609.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR610.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR611.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR612.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR613.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR614.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR615.pdf
http://www.cs.dartmouth.edu/~mckeeman/references/LR/LR616.pdf

:)

cdimauro

30-09-2008, 19:55

I parser a discesa ricorsiva sono(e lo sono sempre stati, anche in passato), tra tutte le tecniche disponibili, quelli meno efficienti perché richiedono il backtracking.
Dipende anche dalla complessità del linguaggio.

Ricordo che i compilatori Borland di Turbo Pascal & affini erano realizzati usando parser recursive descent (quindi LL(k)) e non hanno avuto rivali quanto a velocità di compilazione. ;)
Tratto da Compilers Principles, Tecniques and Tools (http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=pd_cp_b_0/103-4878654-5305440?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-41&pf_rd_r=0NFD5YSKHFP3NQC86NRA&pf_rd_t=201&pf_rd_p=413864201&pf_rd_i=0201100886) di Aho, Lam, Sethi, Ullman(2006):
[...]
Il rovescio della medaglia è che sono più difficili da costruire(per questo sono nati tool come Yacc/Bison e compagnia bella)
Certamente, ma un parser LL(k) non solo è molto più facile da realizzare, ma con tool come ANTLR è diventato pure molto più divertente. :cool:

Vincenzo1968

30-09-2008, 20:21

Dipende anche dalla complessità del linguaggio.

Ricordo che i compilatori Borland di Turbo Pascal & affini erano realizzati usando parser recursive descent (quindi LL(k)) e non hanno avuto rivali quanto a velocità di compilazione. ;)

Certamente, ma un parser LL(k) non solo è molto più facile da realizzare, ma con tool come ANTLR è diventato pure molto più divertente. :cool:

Si, l'importante è questo. Si produce codice inefficiente(e non mi riferisco solo alla velocità di esecuzione), ma divertendosi :cool:

cdimauro

30-09-2008, 21:02

Quando l'efficienza diventerà un requisito di cui tener conto, ne riparleremo. :O

Intanto ANTLR col tempo è come il vino: migliora, anche sotto l'aspetto dell'efficienza. :read: :Prrr: :D

Vincenzo1968

01-10-2008, 15:34

Quando l'efficienza diventerà un requisito di cui tener conto, ne riparleremo. :O

Intanto ANTLR col tempo è come il vino: migliora, anche sotto l'aspetto dell'efficienza. :read: :Prrr: :D

Si si e magari fammi un fischio quando nei libri che trattano l'argomento metteranno, come criterio principale, il divertimento al posto dell'efficienza. ;)

Ho appena scaricato i sorgenti di Python e questo è il commento che si trova alla fine del file parser.c:

/*

Description
-----------

The parser's interface is different than usual: the function addtoken()
must be called for each token in the input. This makes it possible to
turn it into an incremental parsing system later. The parsing system
constructs a parse tree as it goes.

A parsing rule is represented as a Deterministic Finite-state Automaton
(DFA). A node in a DFA represents a state of the parser; an arc represents
a transition. Transitions are either labeled with terminal symbols or
with non-terminals. When the parser decides to follow an arc labeled
with a non-terminal, it is invoked recursively with the DFA representing
the parsing rule for that as its initial state; when that DFA accepts,
the parser that invoked it continues. The parse tree constructed by the
recursively called parser is inserted as a child in the current parse tree.

The DFA's can be constructed automatically from a more conventional
language description. An extended LL(1) grammar (ELL(1)) is suitable.
Certain restrictions make the parser's life easier: rules that can produce
the empty string should be outlawed (there are other ways to put loops
or optional parts in the language). To avoid the need to construct
FIRST sets, we can require that all but the last alternative of a rule
(really: arc going out of a DFA's state) must begin with a terminal
symbol.

As an example, consider this grammar:

expr: term (OP term)*
term: CONSTANT | '(' expr ')'

The DFA corresponding to the rule for expr is:

------->.---term-->.------->
^ |
| |
\----OP----/

The parse tree generated for the input a+b is:

(expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))

*/

Python è un gran bel linguaggio ma non può certo annoverare la velocità di esecuzione tra i suoi punti di forza.
Se avessero scelto, per l'implementazione del parser, la meno facile via delle grammatiche di tipo LALR(1), sarebbe stato meglio, non credi?
E ci sarebbe da chiedersi perchè, tra le facili vie, non abbiano scelto ANTLR. È forse gente che non ama il divertimento? :cool:

cdimauro

02-10-2008, 07:29

Si si e magari fammi un fischio quando nei libri che trattano l'argomento metteranno, come criterio principale, il divertimento al posto dell'efficienza. ;)
In tal caso non si capisce perché si "ostinino" a trattare le grammatiche LL: basterebbe parlare esclusivamente di quelle LR, SLR, LALR, ecc., no?

Evidentemente chi lavora in questo campo non è fissato soltanto con l'efficienza... :O
Ho appena scaricato i sorgenti di Python e questo è il commento che si trova alla fine del file parser.c:

Python è un gran bel linguaggio ma non può certo annoverare la velocità di esecuzione tra i suoi punti di forza.
Vero. Trovami UNA sola volta in cui ho affermato il contrario.
Se avessero scelto, per l'implementazione del parser, la meno facile via delle grammatiche di tipo LALR(1), sarebbe stato meglio, non credi?
Se l'obiettivo fosse stata la velocità e, in generale, l'efficienza a tutti i costi, la tua domanda sarebbe stata legittima.

Peccato che tu non conosca né la storia di Python né segui la mailing list degli sviluppatori che ci lavorano: sapresti che quella di mantenere il linguaggio LL(k) è una precisa scelta per mantenere semplice la sua implementazione e manutenzione.

Per maggiori informazioni, direttamente dall'interprete Python:
>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
:cool:
E ci sarebbe da chiedersi perchè, tra le facili vie, non abbiano scelto ANTLR. È forse gente che non ama il divertimento? :cool:
Forse perché non si possono permettere il lusso di riscrivere l'interprete ogni volta che arriva un nuovo strumento di lavoro?

Immagino che tu, fissato come sei con l'efficienza, passerai il tuo tempo a riscriverti le applicazioni non appena avrai trovato qualche strumento e/o algoritmo che ti permetta di risparmiare mezzo ciclo di clock o byte.

Ti meraviglierà sapere che c'è tanta gente che non bada a queste cose. Perché un buon informatico sa valutare se per un determinato problema l'efficienza è un requisito che bisogna rispettare.

Comunque per la tua gioia ti passo questo http://codespeak.net/pypy/dist/pypy/doc/home.html link: si tratta di un compilatore Python... scritto in Python. Il massimo dell'efficienza, dirai tu. Beh, dai primi risultati sembra che sia mediamente più veloce di CPython (da cui hai tratto quel frammento di codice), che è scritto per una buona parte in C.

Saranno stati dei folli. Eh, sì, l'efficienza... l'efficienza... :p

Vincenzo1968

02-10-2008, 12:55

In tal caso non si capisce perché si "ostinino" a trattare le grammatiche LL: basterebbe parlare esclusivamente di quelle LR, SLR, LALR, ecc., no?

Evidentemente chi lavora in questo campo non è fissato soltanto con l'efficienza... :O

Vero. Trovami UNA sola volta in cui ho affermato il contrario.

Se l'obiettivo fosse stata la velocità e, in generale, l'efficienza a tutti i costi, la tua domanda sarebbe stata legittima.

Peccato che tu non conosca né la storia di Python né segui la mailing list degli sviluppatori che ci lavorano: sapresti che quella di mantenere il linguaggio LL(k) è una precisa scelta per mantenere semplice la sua implementazione e manutenzione.

Per maggiori informazioni, direttamente dall'interprete Python:
>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
:cool:

Forse perché non si possono permettere il lusso di riscrivere l'interprete ogni volta che arriva un nuovo strumento di lavoro?

Immagino che tu, fissato come sei con l'efficienza, passerai il tuo tempo a riscriverti le applicazioni non appena avrai trovato qualche strumento e/o algoritmo che ti permetta di risparmiare mezzo ciclo di clock o byte.

Ti meraviglierà sapere che c'è tanta gente che non bada a queste cose. Perché un buon informatico sa valutare se per un determinato problema l'efficienza è un requisito che bisogna rispettare.

Comunque per la tua gioia ti passo questo http://codespeak.net/pypy/dist/pypy/doc/home.html link: si tratta di un compilatore Python... scritto in Python. Il massimo dell'efficienza, dirai tu. Beh, dai primi risultati sembra che sia mediamente più veloce di CPython (da cui hai tratto quel frammento di codice), che è scritto per una buona parte in C.

Saranno stati dei folli. Eh, sì, l'efficienza... l'efficienza... :p

CPython, da quanto si legge nel sito (http://www.python.org/dev/implementations/), è la versione, almeno fino ad oggi, maggiormente usata:

The first implementation, and the one in widest use...

Ecco perchè ho scelto questa versione.
Sarò anche fissato con l'efficienza ma quando si tratta di scegliere un'implementazione che facilita la vita dello sviluppatore e una che avvantaggia invece l'utente finale, preferisco quest'ultima.

No, non mi meraviglia affatto che c'è tanta gente che non bada a queste cose, ma io non sono un buon informatico ;)

P.S.
Fammi capire una cosa: ogni volta che esce una nuova versione di ANTLR bisogna riscrivere tutto il codice? :eekk:

Vincenzo1968

02-10-2008, 13:35

Guarda che bell'esempio di algoritmo di parsing, con tanto di backtracking:

tratto dalla documentazione del parser PyPy (http://codespeak.net/pypy/dist/pypy/doc/parser.html):

Building the Python grammar
The python grammar is built at startup from the pristine CPython grammar file. The grammar framework is first used to build a simple grammar to parse the grammar itself. The builder provided to the parser generates another grammar which is the Python grammar itself. The grammar file should represent an LL(1) grammar. LL(k) should still work since the parser supports backtracking through the use of source and builder contexts (The memento patterns for those who like Design Patterns)

The match function for a sequence is pretty simple:

for each rule in the sequence:
save the source and builder context
if the rule doesn't match:
restore the source and builder context
return false
call the builder method to build the sequence
return true

C'è qualche autore, da Knuth a Ullman e a tutti gli altri, che prediliga il backtracking tra le caratteriche che un buon parser deve avere? Puoi farmi qualche esempio? Hai qualche link da postare?
È forse gente fissata con l'efficienza? (certamente non si può dire che non siano dei buoni informatici) :cool:

.:N3XV5:.

02-10-2008, 17:07

Non è una cattiva idea realizzare a mano un piccolo compilatore. Serve per familiarizzare con i concetti che stanno alla base(e che i tools automatici nascondono).

Esatto, hai centrato in pieno!... Quello è lo scopo, anche perchè in output voglio un bel codice asm.. Usando un qualche algoritmo che si fa già il grosso del lavoro, ma non è stato scritto da me... Vi immaginate che sorgente salterebbe fuori?.. Fosse un linguaggio ad alto livello anche si, le istruzioni inutili anche si vedono... Ma io voglio un bel codice, formattato ed indentato, con tanto di commenti sulle operazioni più comuni... Non è quello che cerco... Preferisco fare una cosa bruttina ed obsoleta, ma di cui conosco ogni ingranaggio, piuttosto che una cosa nuova e fiammante ma a me completamente (od in gran parte) sconosciuta...

P.S.
Prima ti avevo consigliato il corso della Stanford University:

http://www.stanford.edu/class/cs143/

Purtroppo, la versione corrente, non contiene il corso completo. Dovrei avere da qualche parte i pdf scaricati qualche tempo fa. Ti spiega passo passo le varie fasi per la creazione di un compilatore.
Grazie, ora parto da questo per cominciare...

WarDuck

02-10-2008, 18:35

Ragazzi in ingegneria non esiste parlare di assoluto, esistono dei compromessi. Poi questi possono essere buoni o meno, ma sempre di compromessi si tratta.

Ci sono algoritmi che vanno bene in un caso e male in un altro, e algoritmi che si comportano "mediamente" (dove per mediamente si intende nel caso medio) meglio rispetto ad altri.

Risparmiare cicli di clock su una funzione che verrà chiamata si e no 1 volta su 1 milione, non apporta benefici al livello macroscopico.

Tant'è che ad esempio all'interno della cpu alcuni circuiti nn sono minimizzati (anche se in quel caso è anche una questione di costi presumo).

Vincenzo1968

02-10-2008, 19:44

Ciao WarDuck,

qui non si tratta di risparmiare cicli di clock.
Parliamo di un algoritmo che, a causa del backtracking, deve ritornare spesso sui suoi passi e rileggere l'input se le previsione non era azzeccata. L'altro algoritmo esegue il parsing senza nessuna necessità di tornare indietro. Da un punto di vista della complessità computazionale, secondo te qual è il migliore?

L'argomento è, come si suol dire, well studied. Sin dal 1965.

cdimauro

03-10-2008, 07:36

CPython, da quanto si legge nel sito (http://www.python.org/dev/implementations/), è la versione, almeno fino ad oggi, maggiormente usata:

Ecco perchè ho scelto questa versione.
Certamente: CPython al momento è il più usato. PyPy comunque viene visto di buon occhio anche dagli sviluppatori CPython, e probabilmente ne prenderà il posto se riuscirà a maturare abbastanza.
Sarò anche fissato con l'efficienza ma quando si tratta di scegliere un'implementazione che facilita la vita dello sviluppatore e una che avvantaggia invece l'utente finale, preferisco quest'ultima.

No, non mi meraviglia affatto che c'è tanta gente che non bada a queste cose, ma io non sono un buon informatico ;)
Dipende sempre dagli obiettivi del progetto.

Python, pur usando una gramatica LL(k) (mi sembra, però, che sia LL(1) finora), è il più veloce dei linguaggi "di scripting" (PHP, Perl, Ruby) che sono molto più complessi e per i quali molto probabilmente un parser LL(k) non è sufficiente a coprire l'intera grammatica.

E' ovvio che anche gli sviluppatori di Python si pongono il problema dell'efficienza: se frequenti la mailing list te ne accorgerai anche tu. Ma al momento l'uso di una grammatica (e relativo parser) LL(k) rappresenta un buon compromesso fra velocità di parsing e scrittura e mantenimento dello stesso parser.
P.S.
Fammi capire una cosa: ogni volta che esce una nuova versione di ANTLR bisogna riscrivere tutto il codice? :eekk:
Non mi risulta. Io sono passato da ANTLR 3.0 a 3.1 praticamente a costo zero.

Il passaggio dalla versione 2.x alla 3.0 invece ha richiesto la modifica del codice, ma si tratta di una major version.

Un po' come il passaggio da Python 2.x a 3.0: richiederà non poche modifiche al codice (per fortuna è stato sviluppato un tool che aiuta, 2to3).
Guarda che bell'esempio di algoritmo di parsing, con tanto di backtracking:

tratto dalla documentazione del parser PyPy (http://codespeak.net/pypy/dist/pypy/doc/parser.html):
Leggi meglio:

The builder provided to the parser generates another grammar which is the Python grammar itself. The grammar file should represent an LL(1) grammar.

E comunque: sarebbe un problema per te avere a che fare con un parser LL(k)?
C'è qualche autore, da Knuth a Ullman e a tutti gli altri, che prediliga il backtracking tra le caratteriche che un buon parser deve avere? Puoi farmi qualche esempio? Hai qualche link da postare?
Intanto dovresti darmi la definizione di "buon" parser. Io ti do la mia: lo è quello che permette di risolvere il mio problema con un buon rapporto costi / benefici.
È forse gente fissata con l'efficienza? (certamente non si può dire che non siano dei buoni informatici) :cool:
No, e infatti non è un caso che ne parlino, altrimenti non ne avrebbero né fatto menzione né tanto meno parlato in maniera così estesa, se hai letto "The Dragon Book".

Il motivo è sempre il solito: un "buon" informatico sceglie lo strumento che gli permette di risolvere un problema trovando una "buona" soluzione (con "buona" = miglior rapporto costi / benefici).

Sia chiaro: l'efficienza è soltanto UNA variabile in gioco nelle scelte che si fanno.
Esatto, hai centrato in pieno!... Quello è lo scopo, anche perchè in output voglio un bel codice asm.. Usando un qualche algoritmo che si fa già il grosso del lavoro, ma non è stato scritto da me... Vi immaginate che sorgente salterebbe fuori?.. Fosse un linguaggio ad alto livello anche si, le istruzioni inutili anche si vedono... Ma io voglio un bel codice, formattato ed indentato, con tanto di commenti sulle operazioni più comuni... Non è quello che cerco... Preferisco fare una cosa bruttina ed obsoleta, ma di cui conosco ogni ingranaggio, piuttosto che una cosa nuova e fiammante ma a me completamente (od in gran parte) sconosciuta...

Grazie, ora parto da questo per cominciare...
Non vedo cosa ci sia di "sconosciuto" nell'usare parser LL(k) né tanto meno nell'usare linguaggi di alto livello.
Ragazzi in ingegneria non esiste parlare di assoluto, esistono dei compromessi. Poi questi possono essere buoni o meno, ma sempre di compromessi si tratta.

Ci sono algoritmi che vanno bene in un caso e male in un altro, e algoritmi che si comportano "mediamente" (dove per mediamente si intende nel caso medio) meglio rispetto ad altri.

Risparmiare cicli di clock su una funzione che verrà chiamata si e no 1 volta su 1 milione, non apporta benefici al livello macroscopico.

Tant'è che ad esempio all'interno della cpu alcuni circuiti nn sono minimizzati (anche se in quel caso è anche una questione di costi presumo).
Perfettamente d'accordo.
Ciao WarDuck,

qui non si tratta di risparmiare cicli di clock.
Parliamo di un algoritmo che, a causa del backtracking, deve ritornare spesso sui suoi passi e rileggere l'input se le previsione non era azzeccata. L'altro algoritmo esegue il parsing senza nessuna necessità di tornare indietro. Da un punto di vista della complessità computazionale, secondo te qual è il migliore?

L'argomento è, come si suol dire, well studied. Sin dal 1965.
Non si tratta di risparmiare cicli di clock, ma parli di backtracing che... necessariamente li fa perdere. Insomma, alla fine parli e t'interessa soltanto della variabile "efficienza".

Ma ti rileggi quando scrivi?

Vincenzo1968

03-10-2008, 14:38

...
Ma ti rileggi quando scrivi?

che belle queste battutine :)

No, e infatti non è un caso che ne parlino, altrimenti non ne avrebbero né fatto menzione né tanto meno parlato in maniera così estesa, se hai letto "The Dragon Book".

Parlare ne parlano. Iniziano, nei primi capitoli, con le tecniche meno efficienti, come i parser a discesa ricorsiva, e finiscono con quelle più efficienti.
Mi sembra un buon metodo. Sarebbe stupido parlare solo dell'ultima tecnica senza accennare alle precedenti, non credi?
Nei libri sugli algoritmi si parla del bubble sort. Questo non vuol dire che sia una buona idea utilizzarlo.

Del dragon book ho letto entrambe le edizioni(1986 e 2006).
E anche in tanti altri libri che ho letto(e che ti invito a leggere), per esempio:

http://www.cs.princeton.edu/~appel/modern/c/

http://www.cs.princeton.edu/~appel/modern/java/

l'efficienza è il criterio fondamentale per la progettazione dei compilatori(nota lo strumento consigliato dall'ultimo libro, CUP (http://www.cs.princeton.edu/~appel/modern/java/CUP/)).

La fissazione per l'efficienza mi viene proprio dalla lettura di tutti questi libri. E parlo non solo di parsing, ma di algoritmi in generale.

Non mi risulta. Io sono passato da ANTLR 3.0 a 3.1 praticamente a costo zero.

E come si spiega questa tua affermazione?:

Forse perché non si possono permettere il lusso di riscrivere l'interprete ogni volta che arriva un nuovo strumento di lavoro?

E qui ti giro la tua domanda: ma ti rileggi quando scrivi?

Leggi meglio:

The builder provided to the parser generates another grammar which is the Python grammar itself. The grammar file should represent an LL(1) grammar.
E comunque: sarebbe un problema per te avere a che fare con un parser LL(k)?

Nessun problema, ma leggi meglio tu, studiati l'algoritmo:

for each rule in the sequence:
save the source and builder context
if the rule doesn't match:
restore the source and builder context
return false
call the builder method to build the sequence
return true

Mi fa piacere notare che anche tra gli sviluppatori Python c'è chi è fissato con l'efficienza.
Io ho solo espresso una critica(è possibile?) e la riassumo:

Secondo me è stata una scelta sbagliata quella di utilizzare una grammatica di tipo LL(k). Hanno reso la vita più facile per lo sviluppatore ma non hanno reso un gran servizio all'utente finale.

Vincenzo1968

03-10-2008, 14:52

Esatto, hai centrato in pieno!... Quello è lo scopo, anche perchè in output voglio un bel codice asm.. Usando un qualche algoritmo che si fa già il grosso del lavoro, ma non è stato scritto da me... Vi immaginate che sorgente salterebbe fuori?.. Fosse un linguaggio ad alto livello anche si, le istruzioni inutili anche si vedono... Ma io voglio un bel codice, formattato ed indentato, con tanto di commenti sulle operazioni più comuni... Non è quello che cerco... Preferisco fare una cosa bruttina ed obsoleta, ma di cui conosco ogni ingranaggio, piuttosto che una cosa nuova e fiammante ma a me completamente (od in gran parte) sconosciuta...

Grazie, ora parto da questo per cominciare...

Secondo me stai seguendo la strada giusta. Una volta apprese le tecniche di base potrai utilizzare al meglio i tools automatici(puoi anche costruirtene uno tuo ;) )

Ho trovato i pdf del corso della Stanford. Se vuoi te li invio.

cdimauro

03-10-2008, 20:55

che belle queste battutine :)
Non era una battuta, ma una constatazione: prima hai affermato che non si tratta di risparmiare cicli di clock, e subito dopo mi parli dell'inefficienza del backtracking. E a meno che col backtracking non si guadagnino cicli di clock anziché perderli, direi che le due cose sono in contraddizione...
Parlare ne parlano. Iniziano, nei primi capitoli, con le tecniche meno efficienti, come i parser a discesa ricorsiva, e finiscono con quelle più efficienti.
Mi sembra un buon metodo. Sarebbe stupido parlare solo dell'ultima tecnica senza accennare alle precedenti, non credi?
Nei libri sugli algoritmi si parla del bubble sort. Questo non vuol dire che sia una buona idea utilizzarlo.

Del dragon book ho letto entrambe le edizioni(1986 e 2006).
Io ho soltanto la prima (tra l'altro dovrei andare cercarlo, perché non ricordo nemmeno dove l'ho infilato), e ricordo che il libro si soffermava molto sull'insieme di grammatiche riconoscibili dai vari tipi di parser. Poi trattava anche dell'efficienza.
E anche in tanti altri libri che ho letto(e che ti invito a leggere), per esempio:

http://www.cs.princeton.edu/~appel/modern/c/

http://www.cs.princeton.edu/~appel/modern/java/

l'efficienza è il criterio fondamentale per la progettazione dei compilatori(nota lo strumento consigliato dall'ultimo libro, CUP (http://www.cs.princeton.edu/~appel/modern/java/CUP/)).

La fissazione per l'efficienza mi viene proprio dalla lettura di tutti questi libri. E parlo non solo di parsing, ma di algoritmi in generale.
De gustibus, e mi ripeto: quando l'efficienza diventerà un REQUISITO per i problemi da risolvere, ne terrò conto.
E come si spiega questa tua affermazione?:

E qui ti giro la tua domanda: ma ti rileggi quando scrivi?
Certamente, e si tratta di due risposte a due cose dette in contesti diversi. Non vedo in che modo tu le abbia messe assieme.

Ti faccio notare che la frase su ANTLR e l'eventuale cambio di codice paventato l'hai pure messa come P.S.

Cerca almeno di non estrapolare singole frasi dai loro contesti, anche perché... Python non usa ANTLR. Lo sforzo di passare a una code base che facesse uso di AST e generatori di codice a partire da AST l'hanno fatto già una volta, e non avrebbe senso ripeterlo nuovamente.
Nessun problema, ma leggi meglio tu, studiati l'algoritmo:

for each rule in the sequence:
save the source and builder context
if the rule doesn't match:
restore the source and builder context
return false
call the builder method to build the sequence
return true

Lo conosco già da un pezzo, grazie.

Dove vorresti arrivare con ciò?
Mi fa piacere notare che anche tra gli sviluppatori Python c'è chi è fissato con l'efficienza.
Io ho solo espresso una critica(è possibile?) e la riassumo:

Secondo me è stata una scelta sbagliata quella di utilizzare una grammatica di tipo LL(k). Hanno reso la vita più facile per lo sviluppatore ma non hanno reso un gran servizio all'utente finale.
Purtroppo continuando a fissarti sull'efficienza a ogni costo e in ogni circostanza, perdi di vista qual è il servizio che l'utente finale deve ricevere: che il codice giri (decentemente).

Ora, non so tu, ma dalle mie parti (Python) un parser lo si usa per generare il bytecode che verrà POI eseguito, e... ti sembrerà strano, ma questo si verifica la PRIMA volta che viene eseguito un file / modulo, oppure se gli è stata apportata qualche modifica.

Quindi il processo di compilazione viene invocato una tantum, non sempre. Certo, a meno che uno non si diverta a forzare la compilazione del bytecode ogni volta, ma immagino che tu, prima di lanciare un eseguibile C/C++, non ricorrerai sempre alla compilazione dei sorgenti...

Detto ciò, Python è un linguaggio talmente semplice come grammatica da richiedere veramente poche risorse per il parsing. Infatti è sufficiente un parser LL(1), e... tanti saluti al backtracking che ti sta indigesto.

Ecco qui (http://mail.python.org/pipermail/python-dev/2000-July/005675.html):

The disadvantage is that you have to change the code generator to work
withthis mess -- that's why people like LALR(1) and other parsers.
But LL(1) was all I could create myself (Python uses a homegrown
parser generator).
Secondo me stai seguendo la strada giusta. Una volta apprese le tecniche di base potrai utilizzare al meglio i tools automatici(puoi anche costruirtene uno tuo ;) )

Ho trovato i pdf del corso della Stanford. Se vuoi te li invio.
Casualmente alla Stanford trovi pure questo (http://www.stanford.edu/class/cs242/slides/2006/python-vanRossum.pdf): Python: Design and Implementation :D

Vincenzo1968

03-10-2008, 22:27

Se invece di usare un Simple & stupid LL(1) parsing engine(è di van Rossum la definizione; l'ho presa dal link che hai indicato tu ;) ) ne avessero usato uno di tipo LR, forse, non ci sarebbe stato questo proliferare di versioni per cercarne di migliorare l'efficienza: IronPython, PyPy, Psycho...

E forse non avresti sentito il bisogno di difendere con con tanta energia un algoritmo che, e l'argomento, non lo dico io ma have been well studied, si è dimostrato nettamente inferiore.

In quanto alle frasi estrapolate ho sempre indicato il link al documento originale.

cdimauro

03-10-2008, 22:46

Non capisco se non hai capito o non vuoi proprio capire.

La ricerca dell'efficienza con le varie implementazioni di Python che hai citato (specialmente Psyco, che è l'esempio lampante di ciò che dico, ma anche con CPython stesso) verte sostanzialmente su un punto: MIGLIORARE LA VELOCITA' DI ESECUZIONE. Quindi virtual machine e codice (C e/o Python) vario.

La compilazione avviene UNA SOLA VOLTA (generalmente; a meno che non si sviluppi) ed è di scarsa importanza, anche perché, e te lo dice lo stesso Guido, il linguaggio è LL(1) e realizzare un parser (pure abbastanza efficiente, visto che non richiede nemmeno il backtracking) è semplice & stupido, appunto.

Spero sia chiaro una buona volta.

marco.r

03-10-2008, 23:33

Ma perche' vi scannate per un parser ? Non e' la parte piu' impegnativa e secondo me neanche quella piu' interessante di un compilatore...

Vincenzo1968

03-10-2008, 23:35

Che vuoi fare, sono duro di comprendonio, porta pazienza.
Chi l'ha detto che non è vero che i compilatori LL(k) sono sempre più inefficienti di quelli LR(k) o LALR?

Vincenzo, devono realizzare una tesina, non un compilatore HPF.

ANTLR va benissimo e con ANTLRWork "writing compilers was never been so much fun" (vediamo chi azzecca la citazione :D).

Poi non è vero che i compilatori LL(k) sono sempre più inefficienti di quelli LR(k) o LALR: dipende da come vengono scritti e dal linguaggio di programmazione di cui implementare il parser. Anzi, i recursive descent parser generati da grammatiche LL(k) si sono sempre distinti per velocità in passato.

Vero è che le vecchie versioni di ANTLR erano molto più lente di YACC/Bison et similia, ma col tempo il codice generato sta migliorando nettamente. In ANTRL 3.1 sono stati introdotti i DFA e dall'analisi del codice prodotto noto enormi miglioramenti rispetto alla 3.0; e t'assicuro che ci sono comunque ottimi margini di miglioramento per il futuro. ;)

Vincenzo1968

03-10-2008, 23:43

Ma perche' vi scannate per un parser ? Non e' la parte piu' impegnativa e secondo me neanche quella piu' interessante di un compilatore...

Ohé Marco, ciao.

E chi si scanna? Stiamo semplicemente discutendo(un po' animatamente, è vero, ma non mi sembra uno scannarsi ;) )

cdimauro

03-10-2008, 23:52

Ma perche' vi scannate per un parser ? Non e' la parte piu' impegnativa e secondo me neanche quella piu' interessante di un compilatore...
Personalmente trovo molto attraente la definizione della grammatica di un linguaggio, ma la parte più interessante è la valutazione dell'AST e la generazione del codice, IMHO.
Che vuoi fare, sono duro di comprendonio, porta pazienza.
Chi l'ha detto che non è vero che i compilatori LL(k) sono sempre più inefficienti di quelli LR(k) o LALR?
http://en.wikipedia.org/wiki/Pascal_programming_language#Compilers_and_interpreters

Turbo Pascal was the dominant Pascal compiler for PCs during the 80s and early 90s, popular both because of its powerful extensions and extremely short compilation times. Turbo Pascal was compactly written and could compile, run, and debug all from memory without accessing disk. Slow floppy disk drives were common for programmers at the time, further magnifying Turbo Pascal's speed advantage. Currently, older versions of Turbo Pascal (up to 5.5) are available for free download from Borland's site.

http://info.borland.com/pascal/tp7fact.html

The world's fastest compiler (more than 85,000 lines per minute)

http://www.pcengines.ch/tp3.htm

The following is documentation I created after reverse engineering the Turbo Pascal 3.01A compiler.
[...]
Like most Pascal compilers, TURBO uses a recursive descent parser.

Visto che, come dici, sei duro di comprendonio, spero ti basteranno come esempi. Sei abbastanza "stagionato", per cui dovresti conoscere la fama, ma anche la velocità sul campo che avevano i compilatori Turbo Pascal di Borland. Che NON usavano parser LR(k) o LALR.

Vincenzo1968

04-10-2008, 01:01

Allora dovrò buttare tutti quei libri visto che i parser a discesa ricorsiva sono descritti tra i peggiori dal punto di vista dell'efficienza(ma bisognerebbe vedere che tipo di algoritmo, all'epoca, utilizzavano gli altri compilatori).

Turbo Pascal was compactly written and could compile, run, and debug all from memory without accessing disk

Beh certo, se carica tutto quanto in memoria, allora sarà velocissimo, anche con il meno efficiente degli algoritmi.

Vogliamo fare una prova? Costruiamo un compilatore per il linguaggio Pascal. Io utilizzo un parser di tipo LALR e tu uno a discesa ricorsiva. So che sai programmare in C, per cui ti chiedo la cortesia di utilizzare questo linguaggio(altrimenti devi darmi un po' di tempo per imparare Python).
:)

cdimauro

04-10-2008, 06:15

Allora dovrò buttare tutti quei libri visto che i parser a discesa ricorsiva sono descritti tra i peggiori dal punto di vista dell'efficienza(ma bisognerebbe vedere che tipo di algoritmo, all'epoca, utilizzavano gli altri compilatori).
Come t'avevo già scritto, bisogna anche vedere il tipo di linguaggio da implementare.

Tra l'altro molto del tempo d'esecuzione di un compilatore viene consumato dal lexer.
Beh certo, se carica tutto quanto in memoria, allora sarà velocissimo, anche con il meno efficiente degli algoritmi.
Il Turbo Pascal 7 non caricava tutto in memoria.
Vogliamo fare una prova? Costruiamo un compilatore per il linguaggio Pascal. Io utilizzo un parser di tipo LALR e tu uno a discesa ricorsiva. So che sai programmare in C, per cui ti chiedo la cortesia di utilizzare questo linguaggio(altrimenti devi darmi un po' di tempo per imparare Python).
:)
Python l'ho imparato in mezz'ora (parlo della sintassi e della conoscenza dei tipi built-in). :cool:

A prescindere da tutto, ciò non toglie che i compilatori Turbo Pascal sono sempre stati i più veloci, sia che caricassero tutto in memoria, sia che compilassero leggendo da disco. E' un dato di fatto storico.

cdimauro

04-10-2008, 06:49

Sempre sull'argomento: http://www.tectonic.co.za/wordpress/?p=768

According to the Free Pascal development team, the compiler is well suited to compile very large software projects consisting of millions lines of code. Developers of those projects will be very pleased with the speed of the compiler, which is many times faster than GCC. The Free Pascal compiler is the most advanced open source compiler engine besides GCC.

Ed è più veloce anche di GPC (http://en.wikipedia.org/wiki/GNU_Pascal)

GCC e GPC sono scritti in C usando Flex e Bison (quindi parser LALR).

FreePascal è scritto in FreePascal e utilizza un tradizionale parser recursive descent.

Tutti e tre utilizzano alcuni tool GNU (make, assemblatore, e linker).

Vincenzo1968

04-10-2008, 14:19

Io come riferimenti, a wikipedia e tectonic preferisco i libri di autori come Knuth, Ullman e Sethi(per citarne solo alcuni).

I parser a discesa ricorsiva sono i migliori? Vediamolo in pratica.
Se non ti va bene il Pascal, proponi tu un linguaggio. Possiamo, e forse è meglio, inventarcene uno nostro.
Invece di creare un compilatore possiamo limitarci, se preferisci, a un semplice interprete.

P.S.
Tu ci hai messo mezz'ora a imparere Python; io, essendo duro di comprendonio, avrei bisogno di molto più tempo ;)

^TiGeRShArK^

04-10-2008, 19:21

Ecco perchè ho scelto questa versione.
Sarò anche fissato con l'efficienza ma quando si tratta di scegliere un'implementazione che facilita la vita dello sviluppatore e una che avvantaggia invece l'utente finale, preferisco quest'ultima.

:mbe:
Veramente l'utente finale è avvantaggiato quando vengono rispettati tutti i requisiti, e il programma funziona correttamente, con il minimo numero di bug.
Inoltre ogni istante di tempo risparmiato nello scrivere il codice utilizzando un linguaggio + semplice può essere utilizzato per trovare i bug e per aggiungere feature.
E, tanto per restare in tema di efficenza, nei vari contest gli interminabili sorgenti che scrivevi, con somma e ammirabile pazienza, non mi pare fossero tutti privi di bug ;)
E stavamo parlando di programini del cavolo che in alcuni casi in C# si riducevano ad una decina di righe di codice...
Non so se hai mai lavorato su progetti dell'ordine delle MLOC, perchè in quel caso credo che ADORERESTI linguaggi + semplici ;)

cdimauro

04-10-2008, 19:58

Io come riferimenti, a wikipedia e tectonic preferisco i libri di autori come Knuth, Ullman e Sethi(per citarne solo alcuni).
Bene, e cosa dicono di preciso?
I parser a discesa ricorsiva sono i migliori?
Mai detto questo. Mi riquoto:

Poi non è vero che i compilatori LL(k) sono sempre più inefficienti di quelli LR(k) o LALR: dipende da come vengono scritti e dal linguaggio di programmazione di cui implementare il parser. Anzi, i recursive descent parser generati da grammatiche LL(k) si sono sempre distinti per velocità in passato.

Adesso spiegami dov'è che ho sbagliato a scrivere, e soprattutto il perché.

In particolare, puoi dimostrare la seguente:

sia g una grammatica (per un qualunque linguaggio), Efficienza(LL(k)) < Efficienza(LR(k)) per ogni k naturale > 0.

?

Dove per Efficienza possiamo prendere il tempo di parsing e/o la memoria consumata.
Vediamolo in pratica.
Se non ti va bene il Pascal, proponi tu un linguaggio. Possiamo, e forse è meglio, inventarcene uno nostro.
Invece di creare un compilatore possiamo limitarci, se preferisci, a un semplice interprete.
Stiamo parlando di parsing, non di interpretazione né di compilazione: mi sembra che siano tre cose molto diverse, no?

Quindi la variabile in gioco è il parser. Dovremmo tenere fissi sia il linguaggio (e la sua grammatica) che il lexer.
Ovviamente il linguaggio dev'essere scelto fra quelli che permettono di realizzare per esso un parser LL(1).

Inventare un nuovo linguaggio non ha senso: per fare dei test che abbiano un qualche significato, servirebbe eseguire il parsing dei file di un qualche grosso progetto scritto in un certo linguaggio.
P.S.
Tu ci hai messo mezz'ora a imparere Python; io, essendo duro di comprendonio, avrei bisogno di molto più tempo ;)
Ti do una mano io, non ti preoccupare. :D

x Tiger: quoto proprio tutto. :cool:

Vincenzo1968

04-10-2008, 20:46

cdimauro

04-10-2008, 21:17

Ohé Tiger,

così racconti solo la mezza messa. Vogliamo raccontarla tutta?
Vero è che ci ho messo un sacco di tempo in più, rispetto agli altri, ed è verissimo che le mie prime versioni erano piene di bug.
Ma è anche vero che, alla fine, sono riuscito a spuntarla(tranne nel terzo contest ma lì è intervenuta una grande repne scasb).
Non ho mai detto di essere un programmatore C in gamba(anzi, in altre discussioni, ho sempre sostenuto il contrario). Altri avrebbero fatto meglio di me e molto più in fretta(e la soluzione di repne, al terzo contest, ne è la conferma).

Nell'ultimo contest, il quinto, la versione C impiega un decimo del tempo(e molta meno memoria) rispetto a quella in C# di Gugo(e mi dispiace, nei confronti di Gugo che ha fatto un gran bel lavoro, mettere la cosa in evidenza qui).

Su un progetto di grosse dimensioni ci lavoro ogni giorno. Si tratta di un gestionale di un'azienda genovese con trentamila installazioni in tutta Italia.
Non faccio il nome qui per non fare pubblicità. Se vuoi, in privato, sono disponibile a fornirti tutti i dati.
I sorgenti sono in C++/MFC e, quando ci mandano una nuova versione, per compilarla col visual studio ci vuole mezza giornata. Non ho mai avvertito la necessità di adorare altri linguaggi.
Peccato, perché per progetti di simile dimensione un derivato del Pascal avrebbe impiegato 30 secondi per creare la build del progetto. :cool:
x Cdimauro:

Il test possiamo farlo anche su un file di piccole dimensioni effettuando ripetutamente il parsing all'interno di un ciclo.
In rete trovi esempi già pronti per i linguaggi esistenti. Meglio inventarne uno nuovo. Potremmo crearne uno che contenga le migliori caratteristiche di quelli esistenti.
Per il linguaggio direi di venirci incontro: utilizziamo Java per il quale esistono tools automatici per generare parser dell'uno e dell'altro tipo(LR, LL).
Per le specifiche tecniche e la grammatica fai tu. Ogni grammatica LL(k) è, come ben sai, anche una grammatica LR(k).
Lo so.

Io continuo a sostenere l'idea di prendere un linguaggio esistente LL(1) ed eseguire il parsing dei file di un grosso progetto. I benchmark sintetici con programmi realizzati ad hoc non mi sono mai piaciuti: preferisco prendere sempre esempi reali. ;)

Comunque oltre ai tool automatici esistono anche i parser recursive descent realizzati a mano: anche questi sono degni di menzione, visto che... sono pure parecchio usati (Turbo Pascal & co, e Free Pascal ne sono eccellenti esempi). :cool:

P.S. Comunque non hai risposto alle domande di cui sopra. :O

EDIT: leggi un po' qui (http://home.earthlink.net/~slkpg/documentation.html#SLK_Quotations). :cool:
A questo punto sono molto curioso di sapere se nel "Dragon book" è scritto a chiare lettere che un parser LL(k) è SEMPRE meno efficiente di uno LR(k). Se riesco a recuperare il libro gli do un'occhiata. ;)

^TiGeRShArK^

05-10-2008, 01:30

Ohé Tiger,

così racconti solo la mezza messa. Vogliamo raccontarla tutta?
Vero è che ci ho messo un sacco di tempo in più, rispetto agli altri, ed è verissimo che le mie prime versioni erano piene di bug.
Ma è anche vero che, alla fine, sono riuscito a spuntarla(tranne nel terzo contest ma lì è intervenuta una grande repne scasb).
Non ho mai detto di essere un programmatore C in gamba(anzi, in altre discussioni, ho sempre sostenuto il contrario). Altri avrebbero fatto meglio di me e molto più in fretta(e la soluzione di repne, al terzo contest, ne è la conferma).

Nell'ultimo contest, il quinto, la versione C impiega un decimo del tempo(e molta meno memoria) rispetto a quella in C# di Gugo(e mi dispiace, nei confronti di Gugo che ha fatto un gran bel lavoro, mettere la cosa in evidenza qui).

Su un progetto di grosse dimensioni ci lavoro ogni giorno. Si tratta di un gestionale di un'azienda genovese con trentamila installazioni in tutta Italia.
Non faccio il nome qui per non fare pubblicità. Se vuoi, in privato, sono disponibile a fornirti tutti i dati.
I sorgenti sono in C++/MFC e, quando ci mandano una nuova versione, per compilarla col visual studio ci vuole mezza giornata. Non ho mai avvertito la necessità di adorare altri linguaggi.

E non credi che utilizzare un linguaggio + semplice e strumenti migliori vi avrebbe potuto semplificare la vita?
Noi avevamo circa una 10ina di installazioni, ma gestivano aziende *lievemente* grosse, e dato che tu ne citi 30.000 italiane direi che come pesantezza delle cose da gestire siamo almeno un'ordine di grandezza di differenza dato che ne avevamo una per ogni nazione.... e che in italia non mi pare ci siano 30000 aziende (ma nemmeno 30) paragonabili come dimensione.
Alla fine però Eclipse, come strumenti per la programmazione pura, è MOLTO + avanti rispetto a Visual Studio (non parlo delle interfacce grafiche in cui Visual Studio è una o due spanne sopra).
Infatti ora io sto lavorando praticamente da gennaio quasi sempre con visual studio e ogni volta mi mangio le mani per delle cose che in eclipse facevi nel giro di un battito di ciglia e con visual studio devi farti a mano..... :muro:
C'è da dire però che il C# con Linq, per l'analisi di dati, imho è inarrivabile dagli altri linguaggi che ho provato.
Alla fine la cosa + importante è la possibilità che ha il programmatore di lavorare nel miglior modo possibile, sia grazie al linguaggio che agli strumenti disponibili.
Soddisfatto questo requisito, imho assolutamente essenziale, allora il cliente ne trarrà solo benefici.
Invece lavorare con strumenti inadeguati o con un linguaggio che ci impieghi il doppio del tempo a scrivere del codice, stai semplicemente togliendo tempo alle cose che sono davvero importanti.
Questo perchè all'utente ovviamente non interessa una mazza se un'elaborazione impiega 200ms o 600ms.
L'importante è che veda il risultato in meno di un secondo (generalmente).
Quindi per moli di dati non enormi e/o per elaborazioni non critiche è assolutamente controproducente ottimizzare, quindi basterebbe utilizzare un linguaggio o un algoritmo o uno strumento + semplice che permette di costruire quasi tutto nel minor tempo possibile e poi ottimizzare solo le parti che realmente necessitano di una maggiore potenza elaborativa, ovvero i colli di bottiglia.
Quindi riassumendo, ovviamente per me ottimizzare è assolutamente necessario, ma solo se esplicitamente richiesto dai requisiti e solo ed esclusivamente nelle parti critiche che vengono richiamate + volte, dato che se su una parte di codice che viene eseguita 20 volte al secondo abbiamo 50ms di tempo di esecuzione e con l'ottimizzazione passiamo a 40ms, notiamo molto di + la differenza rispetto ad una funzione che impiega 900ms ad essere eseguita, ma che non viene quasi mai utilizzata.

Vincenzo1968

05-10-2008, 14:36

E non credi che utilizzare un linguaggio + semplice e strumenti migliori vi avrebbe potuto semplificare la vita?
...

Questo dovresti chiederlo all'azienda che ha sviluppato il software. Io so solo che, ogni volta che il titolare della mia azienda gli chiede di convertire il progetto in C#, gli minacciano il ritiro.
E in ogni caso che c'entra tutto questo con l'argomento del thread? Stiamo parlando di algoritmi di parsing. Il linguaggio C fa schifo? Va bene. Ma non c'entra con l'argomento.

...
P.S. Comunque non hai risposto alle domande di cui sopra. :O

EDIT: leggi un po' qui (http://home.earthlink.net/~slkpg/documentation.html#SLK_Quotations). :cool:
A questo punto sono molto curioso di sapere se nel "Dragon book" è scritto a chiare lettere che un parser LL(k) è SEMPRE meno efficiente di uno LR(k). Se riesco a recuperare il libro gli do un'occhiata. ;)

Avevo già risposto:

Tratto da Compilers Principles, Tecniques and Tools (http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=pd_cp_b_0/103-4878654-5305440?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-41&pf_rd_r=0NFD5YSKHFP3NQC86NRA&pf_rd_t=201&pf_rd_p=413864201&pf_rd_i=0201100886) di Aho, Lam, Sethi, Ullman(2006):

LR parsers can be constructed to recognize virtually all programminglanguage
constructs for which context-free grammars can be written. Non-
LR context-free grammars exist, but these can generally be avoided for
typical programming-language constructs.

The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other,
more primitive shift-reduce methods (see the bibliographic notes).

An LR parser can detect a syntactic error as soon as it is possible to do
so on a left-to-right scan of the input.

The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or
LL methods. For a grammar to be LR(k), we must be able to recognize
the occurrence of the right side of a production in a right-sentential form,
with k input symbols of lookahead. This requirement is far less stringent
than that for LL(k) grammars where we must be able to recognize the
use of a production seeing only the first k symbols of what its right side
derives. Thus, it should not be surprising that LR grammars can describe
more languages than LL grammars.

Nella parte che ho evidenziato, per more primitive shift-reduce methods gli autori si riferiscono ai metodi LL(k). Leggiti le note bibliografiche se trovi il libro.
Se questo non ti basta, non ho che fare: non posso certo postare tutto il libro. Tu che sei bravo in matematica magari potresti postare la dimostrazione che un algoritmo a discesa ricorsiva sia, non dico superiore ma anche solo uguale a uno di tipo LR.

Mi pare che non sia sufficiente il fatto che una volta i compilatori Pascal erano giudicati i più veloci. Anche perché, l'hai detto tu, il processo di compilazione non consiste solo nella fase di parsing: c'è anche l'analisi lessicale, quella semantica, la generazione del codice, etc.(e, aggiungo io, bisogna vedere che algoritmo utilizzavano all'epoca gli altri compilatori).

Come si dice(mi pare dalle parti di Roma), le chiacchiere stanno a zero. Ho proposto di verificare in pratica come stanno le cose implementando un compilatore(o interprete) verificando i tempi di esecuzione.

Edit: Nel link che hai indicato c,è, tra i riferimenti bibliografici, questo bel libro:
The Theory of Parsing, translation, and compiling di Aho, Alfred V., and Jeffrey D. Ullman

All'inizio del capitolo 8, in cui vengono trattati i sistemi minori(p.es. simple precedence parsing e, indovina un po', LL ;)) si può leggere quanto segue:

This chapter is the caviar of the book. However, it is not essential to a strict diet of "theory of compiling", and it can be skipped on a first reading

Come dire... se proprio ci tenete a leggerlo, leggetelo; io eviterei di perdeci tempo ;)

P.S. e poi, ti pare cosa citare affermazioni da un sito che implementa un parser di tipo top-down(LL)? È chiaro che ognuno tira l'acqua al proprio mulino.

cdimauro

05-10-2008, 16:34

Questo dovresti chiederlo all'azienda che ha sviluppato il software. Io so solo che, ogni volta che il titolare della mia azienda gli chiede di convertire il progetto in C#, gli minacciano il ritiro.
E in ogni caso che c'entra tutto questo con l'argomento del thread? Stiamo parlando di algoritmi di parsing. Il linguaggio C fa schifo? Va bene. Ma non c'entra con l'argomento.
L'argomento che ti stava tanto a cuore era l'efficienza, mi pare, e i compilatori C non brillano per efficienza quanto a tempi di compilazione.

Esistono linguaggi che, invece, permettono di essere parserizzati MOLTO più velocemente.

Penso che era questo che intendesse "Tiger". ;)
Avevo già risposto:

Tratto da Compilers Principles, Tecniques and Tools (http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=pd_cp_b_0/103-4878654-5305440?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-41&pf_rd_r=0NFD5YSKHFP3NQC86NRA&pf_rd_t=201&pf_rd_p=413864201&pf_rd_i=0201100886) di Aho, Lam, Sethi, Ullman(2006):

Nella parte che ho evidenziato, per more primitive shift-reduce methods gli autori si riferiscono ai metodi LL(k). Leggiti le note bibliografiche se trovi il libro.
Guarda che ti stai confondendo: i parser shift-reduce sono quelli bottom-up. Lo trovi riportato all'inizio del paragrafo 4.5, quando parla di questo tipo di parser (per poi introdurre quelli LR), e nella parte finale prima della bibliografia, quando fa un sunto degli argomenti trattati nel capitolo.

Tant'è che successivamente scrive esplicitamente LL(k) quando parla delle classi di grammatiche che sono parserizzabili e afferma che i parser LR(k) ne sono un superset.

Infine, quando cita le note bibliografiche lo fa relativamente all'efficienza dei parser LR(k) rispetto a quelli shift-reduce, cioé quelli bottom-up.

Controlla pure e, se hai la possibilità di avere il libro in forma elettronica, posta pure le parti in questione (a me scoccia ricopiarle a mano).
Se questo non ti basta, non ho che fare: non posso certo postare tutto il libro. Tu che sei bravo in matematica magari potresti postare la dimostrazione che un algoritmo a discesa ricorsiva sia, non dico superiore ma anche solo uguale a uno di tipo LR.
Non serve tutto il libro: basta leggere bene e capire ciò di cui si sta parlando.

Comunque un esempio è banale: per k = 1, un algoritmo a discesa ricorsiva NON necessita della parsing table, quindi per lo meno risparmia sullo spazio rispetto a un parser LR(1) che ne deve costruire una.
Dai un'occhiata all'algoritmo in pseudocodice che descrive un parser recursive descente e confrontalo con lo stesso per un parser LR: dovresti notare già a al primo sguardo le differenze.

Poi ti faccio notare (ma lo trovi sempre nel libro) che raramente si fa uso del backtracking nei linguaggi di programmazione. Difatti per molti è possibile scrivere una grammatica LL(1) che... non richiede nessun backtracking.
Mi pare che non sia sufficiente il fatto che una volta i compilatori Pascal erano giudicati i più veloci. Anche perché, l'hai detto tu, il processo di compilazione non consiste solo nella fase di parsing: c'è anche l'analisi lessicale, quella semantica, la generazione del codice, etc.(e, aggiungo io, bisogna vedere che algoritmo utilizzavano all'epoca gli altri compilatori).
Vedi sopra. Dovrebbe essere sufficiente il fatto che un linguaggio che ha una grammatica LL(1) non richiede né backtracking né una tabella di parsing, come appunto capitava coi compilatori Pascal in questione.
Come si dice(mi pare dalle parti di Roma), le chiacchiere stanno a zero. Ho proposto di verificare in pratica come stanno le cose implementando un compilatore(o interprete) verificando i tempi di esecuzione.
Qui ti devi decidere: prima concordi con me che un compilatore non fa soltanto parsing, e adesso mi riproponi di verificare l'efficienza dei parser LL(k) ed LR(k)... usando un compilatore! :rolleyes:

Per me, ripeto, non c'è problema. Prendiamo un linguaggio esistente per cui esiste una grammatica LL(1).
Edit: Nel link che hai indicato c,è, tra i riferimenti bibliografici, questo bel libro:
The Theory of Parsing, translation, and compiling di Aho, Alfred V., and Jeffrey D. Ullman

All'inizio del capitolo 8, in cui vengono trattati i sistemi minori(p.es. simple precedence parsing e, indovina un po', LL ;)) si può leggere quanto segue:

Come dire... se proprio ci tenete a leggerlo, leggetelo; io eviterei di perdeci tempo ;)
Ha detto bene: è il caviale. Non posso che concordare. :cool:

E ti faccio anche notare che gli stessi autori sono quelli che hanno POI scritto "The Dragon Book", il quale dedica non poco spazio ai parser top-down ed LL(k). :O

Tutto tempo perso, vero? :read: :Prrr:
P.S. e poi, ti pare cosa citare affermazioni da un sito che implementa un parser di tipo top-down(LL)? È chiaro che ognuno tira l'acqua al proprio mulino.
Ciò non toglie la validità delle citazioni riportate, che NON sono farina del sacco dell'autore del sito, ma di autori anche piuttosto apprezzati e blasonati.

Tra l'altro proprio il libro di cui hai riportato la frase di cui sopra afferma:

Aho & Ullman (1973) state that top-down parsing is better suited to syntax directed translation than is bottom-up parsing. From page 273:

When we look at translation, however, the left parse appears more desirable.

Eh, sì, il caviale, il caviale... :cool:

Vincenzo1968

05-10-2008, 16:40

Tratto dal sito che hai indicato:

http://home.earthlink.net/~slkpg/parsing.html

What parsing technique should I use?[b]
It depends on the language to be parsed. If the language is highly ambiguous, a GLR parser is a good choice because the GLR method was designed specifically to handle ambiguity. If the language is very small, and you have not already used a parser generator, hand-coded recursive-descent is probably a good choice. It is possible that you could be finished with the parser in less time than it would take to master the intricacies of a complicated tool like YACC. [b]For larger projects, the time invested in learning to use a parser generator will probably be offset by the time saved in coding and debugging a recursive-descent parser. This is because recursive-descent parsers require considerably more hand-written code than when a parser generator is used.

If a suitable grammar for the language can be found or constructed, a top-down parser generator is probably a better choice than a bottom-up parser generator like YACC. Top-down parser generators are usually easier to use, and also easier to learn to use. They follow the familiar paradigm of recursion. Bottom-up parsing is a little like recursion that is turned inside out, or maybe upside down. It takes some getting used to before it becomes comfortable.

Nota, nel giustificare l'uso di un parser LL(k), come l'accento sia posto sulla facilità d'uso e non sull'efficienza(ed è una cosa che ho specificato fin dall'inizio). E nota anche come l'autore giustamente dica che, per progetti di grosse dimensioni, vale sicuramente la pena utilizzare strumenti come Yacc.
Evidentemente l'autore, i libri che consiglia nei riferimenti bibliografici, li ha letti ;)

Vincenzo1968

05-10-2008, 17:17

...
Per me, ripeto, non c'è problema. Prendiamo un linguaggio esistente per cui esiste una grammatica LL(1).
... :cool:

Eh no, il bello sta proprio qui. Utilizzare una grammatica già bell'e pronta è facile. Per me è molto meglio inventarci un linguaggio nuovo. Chissà che non ne esca fuori qualcosa di interessante.
Hai difficoltà ad impostare una grammatica di tipo LL? Non è un divertimento farlo con ANTLR Work?

Possiamo anche metterlo ai voti. Io invito tutti a partecipare ai due progetti, anche se non si hanno conoscenze approfondite delle tecniche di parsing. Conoscenze del linguaggio assembly, per esempio, risultano utili nella fase finale di generazione e ottimizzazione del codice.

cdimauro

05-10-2008, 19:29

Tratto dal sito che hai indicato:

http://home.earthlink.net/~slkpg/parsing.html
Sostanzialmente è condivisibile.
Nota, nel giustificare l'uso di un parser LL(k), come l'accento sia posto sulla facilità d'uso e non sull'efficienza(ed è una cosa che ho specificato fin dall'inizio).
Nota tu che non ha MAI menzionato l'efficienza. Inoltre NON ha mai parlato di parser LL(k).
E nota anche come l'autore giustamente dica che, per progetti di grosse dimensioni, vale sicuramente la pena utilizzare strumenti come Yacc.
Sì, ma mi sa che tu non hai letto il perché: lo dice prima.
Evidentemente l'autore, i libri che consiglia nei riferimenti bibliografici, li ha letti ;)
Evidentemente abbiamo letto due cose diverse. Rileggi meglio tutto il pezzo che hai quotato perché hai preso soltanto singole frasi "dimenticando" di portarti dietro il contesto in cui sono state dette. :O
Eh no, il bello sta proprio qui. Utilizzare una grammatica già bell'e pronta è facile. Per me è molto meglio inventarci un linguaggio nuovo. Chissà che non ne esca fuori qualcosa di interessante.
Hai difficoltà ad impostare una grammatica di tipo LL? Non è un divertimento farlo con ANTLR Work?
Certamente, e lo ribadisco. Realizzare parser con ANTLR (specialmente con ANTLRWork) è una passeggiata, e chi l'ha provato sa benissimo cosa intendo.

Ma non è questo il punto, perché non stiamo confrontando ANTLR, ma i parser LL(k) e quelli LR(k). O sbaglio? Ne parlo meglio dopo.
Possiamo anche metterlo ai voti. Io invito tutti a partecipare ai due progetti, anche se non si hanno conoscenze approfondite delle tecniche di parsing. Conoscenze del linguaggio assembly, per esempio, risultano utili nella fase finale di generazione e ottimizzazione del codice.
L'invito che faccio io è ben diverso: riporta dal "Dragon Book" lo pseudocodice del parser recursive descent e quello del parser LR(k). Si tratta di codice che si applica e funziona a prescindere da qualunque grammatica e implementazione si voglia scegliere, che ridurrebbero i risultati del confronto alla sole scelte effettuate, appunto.

Analizziamo i due codici e la loro complessità computazionale, sia per il tempo che per lo spazio. In particolare analizziamo i dati per parser LL(1) e LR(1), che era ciò che chiedevo prima.

Così risolviamo molto prima e, soprattutto, i risultati sono applicabili sempre a qualunque contesto. :read: :cool:

Vincenzo1968

05-10-2008, 21:08

Credo che gli autori del libro avrebbero qualcosa da ridire se riportassi per intero gli algoritmi che vi sono contenuti. Non pensi? :)

Direi piuttosto di passare ai fatti e cominciare a scaldare i muscoli con qualcosa di semplice.

Da qui (www.guidealgoritmi.it/public/BisonCalculator.zip) si può scaricare un file .zip che contiene due progetti per visual studio 2008.
Nella cartella BisonExpr c'è un progetto che ho scritto io qualche tempo fa.
Nella cartella BisonCalc c'è il progetto descritto in questo articolo (http://www.ibm.com/developerworks/library/l-flexbison.html).

Entrambi i programmi eseguono il parsing di espressioni matematiche e riportano il risultato finale.
Il programma dell'articolo di Hagen fornisce una migliore gestione degli errori. Per ogni errore trovato riporta dove si è verificato(riga e colonna) e di che tipo di errore si tratta.
Ho dato in pasto i file .l e .y rispettivamente a Flex e Bison e li ho aggiunti a quelli scaricabili dal link, in modo da avere il progetto completo e funzionante.
Nella cartella Release(sia in BisonExpr che in BisonCalc) è presente l'eseguibile per windows insieme a due file di prova. Per altri sistemi operativi è sufficiente compilare i sorgenti .c e .h col compilatore adatto.
I programmi vanno eseguiti specificando, da riga di comando, il file da parsare.
Per esempio:

BisonCalc Prova.txt

oppure

BisonExpr Prova.txt

Riporto il contenuto del file Prova2.txt tanto per dare l'idea di che tipo di parsing venga effettuato:

a = 5;
aa = a * 4;
b = aa / ( a - 3 );

Questo è invece il contenuto del file Prova.txt che contiene degli errori:

a = 3;
3 aa = a * 4;
b = aa / ( a - 3 );

E questo è l'output del programma BisonCalc:

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc1.jpg

e

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc2.jpg

Se mi fai avere qualcosa di simile realizzato con ANTLR(o qualunque altro strumento tu preferisca) cominciamo a fare delle prove.

cdimauro

05-10-2008, 21:27

Non hai capito. Rileggi meglio il mio messaggio precedente.

P.S. Non ti sei fatto scrupoli, prima, a riportare un bel pezzo dal "Dragon Book".

Vincenzo1968

05-10-2008, 22:31

Non hai capito. Rileggi meglio il mio messaggio precedente.

P.S. Non ti sei fatto scrupoli, prima, a riportare un bel pezzo dal "Dragon Book".

Ho capito benissimo. Di parole ne abbiamo sprecate un sacco. Passiamo ai fatti.

Se ci tieni postali tu gli algoritmi. Io non ho la versione pdf(esiste?).
Una cosa è postare un paragrafo(e non credo che la cosa dispiacerebbe agli autori, anzi) e un'altra è postare pagine e pagine. :)

cdimauro

06-10-2008, 07:55

Senti Vincenzo, non fare il finto tonto con me e non insultare la mia intelligenza, oltre che abusare della mia pazienza.

I fatti sono che è da 3 pagine che eviti di rispondere alle mie domande e osservazioni, e nei casi in cui l'hai fatto tutto ciò che hai riportato finora ti si è sistematicamente rivoltato contro.

I fatti sono che ti chiedo di postare gli algoritmi (che hanno valenza UNIVERSALE, a prescindere dalle grammatiche e dalle implementazioni dei parser) per confrontarli e hai tentato per l'n-esima volta di ridurre il tutto al banale confronto fra YACC e ANTLR, giusto per appagare la tua sete di ricerca dell'efficienza (perché solo questo t'interessa).

I fatti sono che fai lo gnorri quando parlo del PDF del "Dragon Book", quando in precedenza nei hai sfacciatamente copiato un bel pezzo qui (http://www.hwupgrade.it/forum/showpost.php?p=24353085&postcount=9) riportando persino i tipici errori di formattazione dell'operazione di copia & incolla da Acrobat Reader:
LR parsers can be constructed to recognize virtually all programminglanguage
constructs for which context-free grammars can be written. Non-
LR context-free grammars exist, but these can generally be avoided for
typical programming-language constructs.

The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other,
more primitive shift-reduce methods (see the bibliographic notes).

An LR parser can detect a syntactic error as soon as it is possible to do
so on a left-to-right scan of the input.

The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or
LL methods. For a grammar to be LR(k), we must be able to recognize
the occurrence of the right side of a production in a right-sentential form,
with k input symbols of lookahead. This requirement is far less stringent
than that for LL(k) grammars where we must be able to recognize the
use of a production seeing only the first k symbols of what its right side
derives. Thus, it should not be surprising that LR grammars can describe
more languages than LL grammars.
I fatti sono che non ti ho chiesto di copiarmi un intero libro, ma alcune PICCOLISSIME parti che l'attuale normativa in materia di editoria e diritti d'autore consente (se non erro si può riprodurre fino a un massimo del 10 o 15% dell'intera opera), che è pratica comune e consolidata visto che non stiamo piratando alcunché, ma diffondendo cultura (prova di ciò è il servizio Google Books, ad esempio) .

Questi sono i fatti. Adesso, se vogliamo finirla di giocare e chiudere il discorso, riporta gli algoritmi del parser a discesa ricorsiva e quello LR, e fissiamo k = 1. Io analizzerò la complessità in termini di tempo e spazio del primo, e tu del secondo, e poi li confronteremo. OK?

Vincenzo1968

06-10-2008, 16:02

Voscenza benedica, bacio le mani :ave:

Visto che usi espressioni tratte da Il Padrino, non insultare la mia intelligenza, m'è venuto spontaneo salutarti cosi ;)

Senti Cdimauro, gli algoritmi li trovi in gran quantità new web. Ecco qua:

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/LR_parser

...
Comunque un esempio è banale: per k = 1, un algoritmo a discesa ricorsiva NON necessita della parsing table, quindi per lo meno risparmia sullo spazio rispetto a un parser LR(1) che ne deve costruire una.
Dai un'occhiata all'algoritmo in pseudocodice che descrive un parser recursive descente e confrontalo con lo stesso per un parser LR: dovresti notare già a al primo sguardo le differenze.

Poi ti faccio notare (ma lo trovi sempre nel libro) che raramente si fa uso del backtracking nei linguaggi di programmazione. Difatti per molti è possibile scrivere una grammatica LL(1) che... non richiede nessun backtracking.

Vedi sopra. Dovrebbe essere sufficiente il fatto che un linguaggio che ha una grammatica LL(1) non richiede né backtracking né una tabella di parsing, come appunto capitava coi compilatori Pascal in questione.
...
Eh, sì, il caviale, il caviale... :cool:

Ti faccio notare che il tempo per la costruzione delle tabelle, in entrambi i metodi LL e LR, non è da includere nella complessità.
Le tabelle vengono calcolate e costruite dai generatori(ANTLR, Yacc/Bison) e inserite nei sorgenti risultanti.

qui trovi maggiori dettagli sui sorgenti prodotti da Bison:

http://cs.uic.edu/~spopuri/cparser.html

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/78/683/CS-TR-78-683.pdf

Cerca di mantenere la calma e non cominciare a insultare e a fare insinuazioni. Ho entrambi i libri nel tradizionale formato cartaceo. E basta.

In quanto a chiudere il discorso, così mi sembra troppo comodo.
Hai consigliato di usare ANTLR?
Mostraci in pratica com'è facile e divertente costruire un parser con questo strumento. Il confronto magari non lo facciamo, accontentiamoci dei risultati teorici, ma vediamo un esempio pratico almeno.

Vincenzo1968

06-10-2008, 19:10

Forse nell'analisi ti possono essere d'aiuto i due esempi riportati nel libro(mi riferisco alla seconda edizione, quella del 2006):

Parsing della stringa id + id * id" :

LL:
http://www.guidealgoritmi.it/images/ImgForums/ParsingLL.jpg

LR:
http://www.guidealgoritmi.it/images/ImgForums/ParsingLR.jpg

sono 17 passi contro 14.

variabilepippo

06-10-2008, 19:23

Per pura curiosità, visto che il topic è "Creazione di un compilatore TurboPascal", ho provato a compilare una codebase da 1MLOC con Delphi su un portatile non di ultima generazione. I tempi complessivi di compilazione sono mediamente tra 4 e 5 secondi, qualcuno ha informazioni tecniche dettagliate su quale sia la tipologia di parser adottata dalla Borland per le versioni più recenti di Delphi?

cdimauro

06-10-2008, 20:09

Senti Cdimauro, gli algoritmi li trovi in gran quantità new web. Ecco qua:

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/LR_parser

Ti faccio notare che il tempo per la costruzione delle tabelle, in entrambi i metodi LL e LR, non è da includere nella complessità.
Le tabelle vengono calcolate e costruite dai generatori(ANTLR, Yacc/Bison) e inserite nei sorgenti risultanti.

qui trovi maggiori dettagli sui sorgenti prodotti da Bison:

http://cs.uic.edu/~spopuri/cparser.html

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/78/683/CS-TR-78-683.pdf
Te l'avevo già scritto, ma vedo che devo ripetertelo nuovamente: i parser a discesa ricorsiva non hanno bisogno di nessuna tabella da creare.

Visto che hai tirato fuori i link da wikipedia, lo faccio pure io: http://en.wikipedia.org/wiki/Recursive_descent_parser

Da notare l'esempietto in C.
Cerca di mantenere la calma e non cominciare a insultare e a fare insinuazioni. Ho entrambi i libri nel tradizionale formato cartaceo. E basta.
Non cercare di cambiare discorso: non è il possesso dei libri in forma cartacea che è in discussione, ma il fatto che tu abbia fatto "orecchie da mercante" quando si parlava della loro esistenza in formato PDF, quando invece ne avevi già fatto uso prima.

Comunque non ti preoccupare: la parola basta la metteremo fra qualche ora, quando potrò fare il copia & incolla da Acrobat e confronterò il risultato col pezzo che hai riportato prima.
In quanto a chiudere il discorso, così mi sembra troppo comodo.
Hai consigliato di usare ANTLR?
Mostraci in pratica com'è facile e divertente costruire un parser con questo strumento. Il confronto magari non lo facciamo, accontentiamoci dei risultati teorici, ma vediamo un esempio pratico almeno.
Per me non c'è problema: definisci pure i requisiti che deve avere questo linguaggio, e ti faccio vedere com'è facile tirare fuori il lexer e il parser con ANTLR.

Ovviamente utilizzerò Python come linguaggio di output, ma con ANTLR è possibile specificarne molti altri, per cui chi vuole può adattare l'esempio a Java, C, Delphi, ecc. ecc.

Visto che lo scopo è didattico, possiamo cominciare con delle espressioni da stampare semplicemente a video, e man man aggiungere costrutti via via più complicati (assegnazione di variabili, if, ecc.).
Forse nell'analisi ti possono essere d'aiuto i due esempi riportati nel libro(mi riferisco alla seconda edizione, quella del 2006):

Parsing della stringa id + id * id" :

LL:
http://www.guidealgoritmi.it/images/ImgForums/ParsingLL.jpg

LR:
http://www.guidealgoritmi.it/images/ImgForums/ParsingLR.jpg

sono 17 passi contro 14.
Non ce la fai proprio, eh? Se non misuri la velocità di esecuzione non sei contento...

Già che ci sei, prova a misurare anche lo spazio necessario per costruire le tabelle di parsing, e confrontalo con lo spazio richiesto da un parser a discesa ricorsiva.
Per pura curiosità, visto che il topic è "Creazione di un compilatore TurboPascal", ho provato a compilare una codebase da 1MLOC con Delphi su un portatile non di ultima generazione. I tempi complessivi di compilazione sono mediamente tra 4 e 5 secondi, qualcuno ha informazioni tecniche dettagliate su quale sia la tipologia di parser adottata dalla Borland per le versioni più recenti di Delphi?
Non credo che abbiano usato qualcosa di diverso da un parser a discesa ricorsiva, che è stato usato per la famiglia di prodotti "Turbo Pascal": il linguaggio Pascal è LL(1) ed è abbastanza semplice da implementare, per cui un approccio di questo tipo è molto pratico e diffuso.

Personalmente al posto loro non avrei cambiato, visto che l'approccio ha dato ottimi frutti in passato.

Vincenzo1968

06-10-2008, 20:49

...
Comunque non ti preoccupare: la parola basta la metteremo fra qualche ora, quando potrò fare il copia & incolla da Acrobat e confronterò il risultato col pezzo che hai riportato prima.
...

Non mi aspettavo un'Inquisizione Spagnola (http://digilander.libero.it/digitalgreg/Monty.htm) (vedi il 4° episodio).

ACCORDO DRAMMATICO - La porta si spalanca ed entra il Cardinale Ximinez, affiancato da due apprendisti cardinali. Il Cardinale Biggles ha un guanto infilato sulla testa. Il Cardinale Fang è giusto il Cardinale Fang)
XIMINEZ: NESSUNO si aspetta l'Inquisizione Spagnola! La nostra arma principale è la sorpresa, sorpresa e paura, paura e sorpresa... Le nostre due armi sono paura e sorpresa, e una spietata efficienza. Le nostre TRE armi sono paura, sorpresa, e spietata efficienza. E una devozione quasi fanatica verso il Papa. Le nostre QUATTRO, no... TRA le nostre armi, nel nostro arsenale, ci sono elementi come paura, sorpresa... Rifaccio l'entrata. (escono)

...
Per me non c'è problema: definisci pure i requisiti che deve avere questo linguaggio, e ti faccio vedere com'è facile tirare fuori il lexer e il parser con ANTLR.
...

Partiamo da un esempio semplice semplice come gli esempi di calcolatrice in Bison che ho postato.
Io ho provato a implementarla con ANTLR ma non ci sono riuscito. Piano piano possiamo estendere il parser con l'aggiunta delle varie funzionalità(nuovi operatori, funzioni definite dall'utente, classi, etc).
Anche partendo con l'esempio di calcolatrice fornito nel sito, non ho trovato facile(né, tantomeno, divertente) estenderlo per aggiungervi le funzionalità equivalenti a quelle degli esempi che ho postato(error recovery, per esempio: e cioè, il parser non deve fermarsi al primo errore che incontra ma cercare di gestirlo e riportare all'utente la maggior quantità possibile di errori, così come fa un qualunque compilatore moderno). Cercando sul web non si trova un cavolo(almeno io non ci sono riuscito: può darsi che utilizzi male il motore di ricerca). Anzi... qualcosa si trova: un sacco di gente, in vari forums, che chiede esempi sull'implementazione di calcolatrici con ANTLR.

cdimauro

06-10-2008, 21:19

Non mi aspettavo un'Inquisizione Spagnola (http://digilander.libero.it/digitalgreg/Monty.htm) (vedi il 4° episodio).
Faresti una figura migliore mettendo da parte il sarcasmo e ammettendo che hai il PDF del libro in questione. Sbagliare è umano, ma perseverare è diabolico.

Tanto io sono un tipo che non molla, dovresti averlo capito ormai. E domattina, se tutto va bene, dovrei avere la prova che l'hai usato quell'ebook.
Partiamo da un esempio semplice semplice come gli esempi di calcolatrice in Bison che ho postato.
Io ho provato a implementarla con ANTLR ma non ci sono riuscito. Piano piano possiamo estendere il parser con l'aggiunta delle varie funzionalità(nuovi operatori, funzioni definite dall'utente, classi, etc).
Non c'è problema. Domani comincio a postare un po' di roba (adesso vado a nanna, che ho avuto una giornata pesante). Cominciamo con la classica calcolatrice.
Anche partendo con l'esempio di calcolatrice fornito nel sito, non ho trovato facile(né, tantomeno, divertente) estenderlo per aggiungervi le funzionalità equivalenti a quelle degli esempi che ho postato(error recovery, per esempio: e cioè, il parser non deve fermarsi al primo errore che incontra ma cercare di gestirlo e riportare all'utente la maggior quantità possibile di errori, così come fa un qualunque compilatore moderno). Cercando sul web non si trova un cavolo(almeno io non ci sono riuscito: può darsi che utilizzi male il motore di ricerca). Anzi... qualcosa si trova: un sacco di gente, in vari forums, che chiede esempi sull'implementazione di calcolatrici con ANTLR.
Io ho fatto questa (http://www.google.it/search?client=opera&rls=it&q=site:antlr.org+error+recovery&sourceid=opera&ie=utf-8&oe=utf-8) semplice ricerca, e ho trovato un bel po' di pagine, ma già il primo link (http://www.antlr.org/blog/antlr3/error.handling.tml) faceva al caso tuo.

Comunque nei miei parser finora ho impostato che al primo errore dev'essere sollevata un'eccezione (questo è il modello che preferisco, da anni).

Normalmente, invece, ANTLR prova a recuperare l'errore e ad andare avanti con l'esecuzione.

Vincenzo1968

06-10-2008, 21:50

Faresti una figura migliore mettendo da parte il sarcasmo e ammettendo che hai il PDF del libro in questione. Sbagliare è umano, ma perseverare è diabolico.

Tanto io sono un tipo che non molla, dovresti averlo capito ormai. E domattina, se tutto va bene, dovrei avere la prova che l'hai usato quell'ebook.

Si Ill.mo Mons. Jiménez de Cisneros (http://en.wikipedia.org/wiki/Francisco_Cardinal_Jim%C3%A9nez_de_Cisneros) :ave:
Una volta avuta la prova che fai? Secondo me ti stai rendendo ridicolo con questa storia. Ho copiato quel paragrafo su MS-Word e a questo è dovuta la formattazione particolare(per esempio, l'uso del trattino quando va a capo);uso un templete 60x30(60 colonne per 30 righe) che da un layout simile a quello delle vecchie macchine da scrivere di una volta.
Comunque, contento tu...

Io ho fatto questa (http://www.google.it/search?client=opera&rls=it&q=site:antlr.org+error+recovery&sourceid=opera&ie=utf-8&oe=utf-8) semplice ricerca, e ho trovato un bel po' di pagine, ma già il primo link (http://www.antlr.org/blog/antlr3/error.handling.tml) faceva al caso tuo.

Si si ma non sembra così divertente :cool:

Comunque nei miei parser finora ho impostato che al primo errore dev'essere sollevata un'eccezione (questo è il modello che preferisco, da anni).

Normalmente, invece, ANTLR prova a recuperare l'errore e ad andare avanti con l'esecuzione.
:eek: E dunque, se un sorgente contiene, diciamo una ventina di errori, ogni volta il tuo parser si ferma, l'utente lo corregge e poi... di nuovo: segnalazione dell'errore, correzione e via di questo passo? :cool:
Ti faccio notare che non è il modello preferito da chi sviluppa compilatori(a prescindere dal linguaggio).

cdimauro

07-10-2008, 07:36

Si Ill.mo Mons. Jiménez de Cisneros (http://en.wikipedia.org/wiki/Francisco_Cardinal_Jim%C3%A9nez_de_Cisneros) :ave:
Una volta avuta la prova che fai? Secondo me ti stai rendendo ridicolo con questa storia. Ho copiato quel paragrafo su MS-Word e a questo è dovuta la formattazione particolare(per esempio, l'uso del trattino quando va a capo);uso un templete 60x30(60 colonne per 30 righe) che da un layout simile a quello delle vecchie macchine da scrivere di una volta.
Comunque, contento tu...
Ridicolo c'è chi ha falsamente attestato che non era in possesso del PDF del libro, quando invece già prima l'aveva usato. E le scuse di aver usato Word lasciano il tempo che trovano, visto che incollando il testo anche su notepad si ottiene ESATTAMENTE lo stesso risultato, formattazione ed errori inclusi:
LR parsers can be constructed to recognize virtually all programminglanguage
constructs for which context-free grammars can be written. Non-
LR context-free grammars exist, but these can generally be avoided for
typical programming-language constructs.

The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other,
more primitive shift-reduce methods (see the bibliographic notes).

An LR parser can detect a syntactic error as soon as it is possible to do
so on a left-to-right scan of the input.

The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or
LL methods. For a grammar to be LR(k), we must be able to recognize
the occurrence of the right side of a production in a right-sentential form,
with k input symbols of lookahead. This requirement is far less stringent
than that for LL(k) grammars where we must be able to recognize the
use of a production seeing only the first k symbols of what its right side
derives. Thus, it should not be surprising that LR grammars can describe
more languages than LL grammars.
Non mi risulta che notepad metta il trattino quando va a capo...

Ma la prova "provata", come si dice in gergo, è quella che ho evidenziato. Nel libro c'è scritto programming-language (com'è ripetuto anche dopo), ma nell'operazione di copia & incolla il trattino si perde e le due parole vengono "fuse".

Che dire: non solo "casualmente" la formattazione che hai usato è identica a quella che si ottiene facendo il copia & incolla, ma a quanto pare hai avuto cura di riprodurre fedelmente anche quell'errore di trascrizione...

Per chi volesse provare personalmente, si "trovano" diverse versioni del "Dragon Book" in forma elettronica. Io ho "trovato" l'edizione del 2006 e il file era di 50.581.341 byte per l'esattezza.

Una volta avuto la prova cosa faccio? Beh, faccio vedere che una persona a 40 anni suonati (se il nick corrisponde alla realtà) avrebbe dovuto imparare da un pezzo a prendersi le responsabilità di ciò che dice, e che "le bugie hanno le gambe corte".

Adesso abbi l'onestà di riconoscerlo e la chiudiamo qui, ok?
Si si ma non sembra così divertente :cool:

:eek: E dunque, se un sorgente contiene, diciamo una ventina di errori, ogni volta il tuo parser si ferma, l'utente lo corregge e poi... di nuovo: segnalazione dell'errore, correzione e via di questo passo? :cool:
Ti faccio notare che non è il modello preferito da chi sviluppa compilatori(a prescindere dal linguaggio).
Anche questo non è vero: col Turbo Pascal la prassi era quella di fermarsi al primo errore con l'editor che puntava alla riga e colonna incriminata e il messaggio di errore in bella evidenza.

E' stato con Delphi, se non erro, a essere stata aggiunta la possibilità di continuare a compilare e riportare tutti gli errori.

Perché questo modello? Perché la velocità di compilazione con questi IDE è talmente elevata (5 secondi su un progetto di un milione di righe di codice, come ha riportato variabilepippo, è un tempo assolutamente irrisorio) che ci si può permettere il lusso di lanciare la compilazione, trovarsi sull'errore, correggerlo, e ripetere l'operazione fino a ottenere il sorgente perfettamente compilato.

A parte che ormai gli errori di sintassi i compilatori te li segnalano mentre stai editando, per cui li correggi al volo.

Comunque è questione di gusti, come al solito. Io sono abituato così, e per i progetti per cui ho realizzato dei parser questo modello va benissimo.

cdimauro

07-10-2008, 10:15

Come promesso, ecco il classico esempio della calcolatrice realizzato in ANTLR e con generazione del codice in Python.

Una volta generato il codice (usando il comando che ho messo nel commento alla prima riga della grammatica; purtroppo l'ultima versione ANTLRWork ha un bug nel generatore di parser) verrà prodotto un file SELParser.py che è già pronto all'uso (notare l'uso della sezione @footer: è tutto codice che viene aggiunto alla fine del file e lo rende, appunto, immediatamente eseguibile).
// "c:\Program Files (x86)\Java\jre6\bin"\java.exe -cp \Progs\Programming\ANTLR\antlr-3.1.jar org.antlr.Tool SEL.g

grammar SEL;

options {
language=Python;
}

@footer {
import SELLexer

def Run():

while True:
CharStream = ANTLRStringStream(raw_input('Necessito input: ') + '\n')
Lexer = SELLexer.SELLexer(CharStream)
TokenStream = CommonTokenStream(Lexer)
Parser = SELParser(TokenStream)
Parser.program()

if __name__ == '__main__':
Run()
}

program
: statement+
;

statement
: e = expression NEWLINE {print e}
| NEWLINE
;

expression returns[Value]
: Left = multiply {Value = Left}
('+' Right = multiply {Value += Right}
|'-' Right = multiply {Value -= Right}
)*
;

multiply returns[Value]
: Left = terminal {Value = Left}
('*' Right = terminal {Value *= Right}
|'/' Right = terminal {Value /= Right}
)*
;

terminal returns[Value]
: INT {Value = int($INT.text)}
| '(' e = expression ')' {Value = e}
;

// Lexer

INT
: ('0'..'9')+
;

NEWLINE
: '\n' // UNIX
| '\r' // MacOS
| '\r\n' // Windows
;

WHITE_SPACE
: (' ' | '\t')+ {self.skip()}
;
Da notare anche che con ANTLR si può scrivere anche il lexer: non bisogna, quindi, ricorrere a lexer esterni.
La sintassi ovviamente è la stessa del generatore di parser, ma gli identificatori devono essere in maiuscolo (mentre per quelli dei parser ovviamente in minuscolo).

L'esempio è molto semplice: ci sono giusto le 4 operazioni matematiche di base e le parentesi.

Per eventuali commenti, dubbi, ecc. chiedete pure. ;)

Vincenzo1968

07-10-2008, 14:43

Ridicolo c'è chi ha falsamente attestato che non era in possesso del PDF del libro, quando invece già prima l'aveva usato. E le scuse di aver usato Word lasciano il tempo che trovano, visto che incollando il testo anche su notepad si ottiene ESATTAMENTE lo stesso risultato, formattazione ed errori inclusi:
LR parsers can be constructed to recognize virtually all programminglanguage
constructs for which context-free grammars can be written. Non-
LR context-free grammars exist, but these can generally be avoided for
typical programming-language constructs.

The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other,
more primitive shift-reduce methods (see the bibliographic notes).

An LR parser can detect a syntactic error as soon as it is possible to do
so on a left-to-right scan of the input.

The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or
LL methods. For a grammar to be LR(k), we must be able to recognize
the occurrence of the right side of a production in a right-sentential form,
with k input symbols of lookahead. This requirement is far less stringent
than that for LL(k) grammars where we must be able to recognize the
use of a production seeing only the first k symbols of what its right side
derives. Thus, it should not be surprising that LR grammars can describe
more languages than LL grammars.
Non mi risulta che notepad metta il trattino quando va a capo...

Ma la prova "provata", come si dice in gergo, è quella che ho evidenziato. Nel libro c'è scritto programming-language (com'è ripetuto anche dopo), ma nell'operazione di copia & incolla il trattino si perde e le due parole vengono "fuse".

Che dire: non solo "casualmente" la formattazione che hai usato è identica a quella che si ottiene facendo il copia & incolla, ma a quanto pare hai avuto cura di riprodurre fedelmente anche quell'errore di trascrizione...

Per chi volesse provare personalmente, si "trovano" diverse versioni del "Dragon Book" in forma elettronica. Io ho "trovato" l'edizione del 2006 e il file era di 50.581.341 byte per l'esattezza.

Una volta avuto la prova cosa faccio? Beh, faccio vedere che una persona a 40 anni suonati (se il nick corrisponde alla realtà) avrebbe dovuto imparare da un pezzo a prendersi le responsabilità di ciò che dice, e che "le bugie hanno le gambe corte".

Adesso abbi l'onestà di riconoscerlo e la chiudiamo qui, ok?

Anche questo non è vero: col Turbo Pascal la prassi era quella di fermarsi al primo errore con l'editor che puntava alla riga e colonna incriminata e il messaggio di errore in bella evidenza.

E' stato con Delphi, se non erro, a essere stata aggiunta la possibilità di continuare a compilare e riportare tutti gli errori.

Perché questo modello? Perché la velocità di compilazione con questi IDE è talmente elevata (5 secondi su un progetto di un milione di righe di codice, come ha riportato variabilepippo, è un tempo assolutamente irrisorio) che ci si può permettere il lusso di lanciare la compilazione, trovarsi sull'errore, correggerlo, e ripetere l'operazione fino a ottenere il sorgente perfettamente compilato.

A parte che ormai gli errori di sintassi i compilatori te li segnalano mentre stai editando, per cui li correggi al volo.

Comunque è questione di gusti, come al solito. Io sono abituato così, e per i progetti per cui ho realizzato dei parser questo modello va benissimo.

Bene, abbiamo accertato che a quarant'anni suonati sono un bugiardo e disonesto. Ti ringrazio per la magnanimità nel volerla chiudere qui. Pensavo che, a coronamento dello sforzo investigativo, tu volessi organizzare un bel autodafé (http://it.wikipedia.org/wiki/Autodaf%C3%A9).

Sulla gestione degli errori mi permetto di insistere che le cose non vanno come dici tu. Mi sembra assurdo dover correggere e ricompilare errore dopo errore. Leggi nel libro come la pensano in proposito gli autori. Il metodo è lo stesso, e nell'edizione del 1986 e in quella del 2006.

Vincenzo1968

07-10-2008, 14:45

...
Per eventuali commenti, dubbi, ecc. chiedete pure. ;)

Puoi postare, a beneficio di chi non ha Python, l'output effettuando il parsing dei due file che ho indicato in precedenza? Grazie ;)

Gentilmente puoi provare anche su questi file?:

a = 5.8;
aa = a * 4.25e-34;
b = aa / ( a - 3 );

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc3.jpg

a = 5.8;
aa = -8.5 + a * 4.25e-34;
b = aa / ( a - 3 );

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc4.jpg

Vincenzo1968

07-10-2008, 16:11

Una curiosità : (chiedo a chi utilizza Delphi): in compilazione come avviene la gestione degli errori? Si ferma al primo errore o ne mostra quanti più possibile indicando approssimativamente, per ogni errore riscontrato, dove s'è verificato?

variabilepippo

07-10-2008, 16:15

Delphi non si ferma al primo errore ma mostra tutti gli errori, i warning e gli hint, con relativo numero di riga...

Ho volutamente introdotto degli errori in un codice:

mistakes.pas(85) Error: E2003 Undeclared identifier: 'FDisplayDriver'
mistakes.pas(85) Error: E2003 Undeclared identifier: 'TheForm'
mistakes.pas(85) Error: E2066 Missing operator or semicolon
mistakes.pas(88) Error: E2029 Declaration expected but 'CASE' found
mistakes.pas(96) Error: E2029 'IMPLEMENTATION' expected but ';' found
mistakes.pas(161) Error: E2035 Not enough actual parameters
mistakes.pas(164) Error: E2035 Not enough actual parameters
mistakes.pas(167) Error: E2035 Not enough actual parameters
mistakes.pas(170) Error: E2035 Not enough actual parameters
mistakes.pas(173) Error: E2035 Not enough actual parameters
mistakes.pas(176) Error: E2035 Not enough actual parameters
mistakes.pas(179) Error: E2035 Not enough actual parameters
mistakes.pas(182) Error: E2035 Not enough actual parameters
mistakes.pas(185) Error: E2035 Not enough actual parameters
mistakes.pas(192) Error: E2035 Not enough actual parameters
mistakes.pas(196) Error: E2035 Not enough actual parameters
mistakes.pas(199) Error: E2035 Not enough actual parameters
mistakes.pas(202) Error: E2035 Not enough actual parameters
mistakes.pas(205) Error: E2035 Not enough actual parameters

In caso di compilazione completata con successo:

KOLDEF.INC(168)
KOLDEF.INC(168)
delphidef.inc(48)
delphicommctrl.inc(1513)
KOL_ansi.inc(2307)
KOL_ansi.inc(2307)
KOL_ASM.inc(17896)
kol.pas(57671)
82072 lines, 0.34 seconds, 177275 bytes code, 68196 bytes data.

PS. Si noti come 82000 LOC vengano compilate in appena 0.34 secondi. :)

Vincenzo1968

07-10-2008, 16:28

Delphi non si ferma al primo errore ma mostra tutti gli errori, i warning e gli hint, con relativo numero di riga...

Ho artificialmente introdotto degli errori in un codice:

mistakes.pas(85) Error: E2003 Undeclared identifier: 'FDisplayDriver'
mistakes.pas(85) Error: E2003 Undeclared identifier: 'TheForm'
mistakes.pas(85) Error: E2066 Missing operator or semicolon
mistakes.pas(88) Error: E2029 Declaration expected but 'CASE' found
mistakes.pas(96) Error: E2029 'IMPLEMENTATION' expected but ';' found
mistakes.pas(161) Error: E2035 Not enough actual parameters
mistakes.pas(164) Error: E2035 Not enough actual parameters
mistakes.pas(167) Error: E2035 Not enough actual parameters
mistakes.pas(170) Error: E2035 Not enough actual parameters
mistakes.pas(173) Error: E2035 Not enough actual parameters
mistakes.pas(176) Error: E2035 Not enough actual parameters
mistakes.pas(179) Error: E2035 Not enough actual parameters
mistakes.pas(182) Error: E2035 Not enough actual parameters
mistakes.pas(185) Error: E2035 Not enough actual parameters
mistakes.pas(192) Error: E2035 Not enough actual parameters
mistakes.pas(196) Error: E2035 Not enough actual parameters
mistakes.pas(199) Error: E2035 Not enough actual parameters
mistakes.pas(202) Error: E2035 Not enough actual parameters
mistakes.pas(205) Error: E2035 Not enough actual parameters

In caso di compilazione completata con successo:

KOLDEF.INC(168)
KOLDEF.INC(168)
delphidef.inc(48)
delphicommctrl.inc(1513)
KOL_ansi.inc(2307)
KOL_ansi.inc(2307)
KOL_ASM.inc(17896)
kol.pas(57671)
82072 lines, 0.34 seconds, 177275 bytes code, 68196 bytes data.

PS. Si noti come 82000 LOC vengano compilate in appena 0.34 secondi. :)

Grazie Variabilepippo,

gentilissimo :)

cdimauro

07-10-2008, 20:25

Bene, abbiamo accertato che a quarant'anni suonati sono un bugiardo e disonesto. Ti ringrazio per la magnanimità nel volerla chiudere qui. Pensavo che, a coronamento dello sforzo investigativo, tu volessi organizzare un bel autodafé (http://it.wikipedia.org/wiki/Autodaf%C3%A9).
Sei troppo orgoglioso per ammettere di avere sbagliato, eh? :rolleyes:
Sulla gestione degli errori mi permetto di insistere che le cose non vanno come dici tu. Mi sembra assurdo dover correggere e ricompilare errore dopo errore. Leggi nel libro come la pensano in proposito gli autori. Il metodo è lo stesso, e nell'edizione del 1986 e in quella del 2006.
Mi permetto di insistere anch'io. Le vecchie versioni di Turbo Pascal sono liberamente scaricabili da qui (http://dn.codegear.com/museum/): controlla tu stesso.
Puoi postare, a beneficio di chi non ha Python, l'output effettuando il parsing dei due file che ho indicato in precedenza? Grazie ;)

Gentilmente puoi provare anche su questi file?:

a = 5.8;
aa = a * 4.25e-34;
b = aa / ( a - 3 );

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc3.jpg

a = 5.8;
aa = -8.5 + a * 4.25e-34;
b = aa / ( a - 3 );

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc4.jpg
Intanto posto la grammatica adattata alla sintassi di BisonCalculator:
// "c:\Program Files (x86)\Java\jre6\bin"\java.exe -cp \Progs\Programming\ANTLR\antlr-3.1.jar org.antlr.Tool SEL.g
grammar SEL;

options {
language = Python;
backtrack = true;
}

@footer {
import sys, SELLexer
from decimal import Decimal

def Run():

def Dump():

print 'final content of variables\n\%10s \%10s' \% ('Name', 'Value')
for Name in sorted(Vars):
print '\%10s = \%10s' \% (Name, Vars[Name])

def Execute(CharStream):

Lexer = SELLexer.SELLexer(CharStream)
TokenStream = CommonTokenStream(Lexer)
Parser = SELParser(TokenStream)
Parser.Vars = Vars
Parser.program()

Vars = {}
if len(sys.argv) >= 2:
for Line in open(sys.argv[1]):
Execute(StringStream(Line))
Dump()
sys.exit()
else:
while True:
Execute(StringStream(raw_input('Necessito input: ')))
Dump()

if __name__ == '__main__':
Run()
}

program
: (statement ';')+
;

statement
: e = expression {print e}
| IDENTIFIER '=' e = expression {self.Vars[$IDENTIFIER.text] = e}
;

expression returns[Value]
: Left = multiply {Value = Left}
('+' Right = multiply {Value += Right}
|'-' Right = multiply {Value -= Right}
)*
;

multiply returns[Value]
: Left = signed {Value = Left}
('*' Right = signed {Value *= Right}
|'/' Right = signed {Value /= Right}
)*
;

signed returns[Value]
: '-' t = terminal {Value = -t}
| '+' t = terminal {Value = t}
| t = terminal {Value = t}
;

terminal returns[Value]
: VALUE {Value = Decimal($VALUE.text)}
| IDENTIFIER {Value = self.Vars[$IDENTIFIER.text]}
| '(' e = expression ')' {Value = e}
;

// Lexer

IDENTIFIER
: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*
;

VALUE
: ('0'..'9')+ ('.' ('0'..'9')* (('e' | 'E') ('+' | '-')? ('0'..'9')+ )?)?
;

NEWLINE
: '\n' // UNIX
| '\r' // MacOS
| '\r\n' // Windows
;

WHITE_SPACE
: (' ' | '\t' | NEWLINE)+ {self.skip()}
;
Da notare che in 97 linee c'è tutto: lexer, parser e codice per testare.

Questo è l'output:
D:\Test>python SELParser.py Prova.txt
3
line 1:2 missing ';' at u'aa'
Traceback (most recent call last):
File "SELParser.py", line 585, in <module>
Run()
File "SELParser.py", line 576, in Run
Execute(StringStream(Line))
File "SELParser.py", line 571, in Execute
Parser.program()
File "SELParser.py", line 84, in program
self.statement()
File "SELParser.py", line 176, in statement
e = self.expression()
File "SELParser.py", line 214, in expression
Left = self.multiply()
File "SELParser.py", line 333, in multiply
Value /= Right
File "C:\Python25\lib\decimal.py", line 1183, in __div__
return self._divide(other, context=context)
File "C:\Python25\lib\decimal.py", line 1265, in _divide
return context._raise_error(DivisionByZero, 'x / 0', sign)
File "C:\Python25\lib\decimal.py", line 2325, in _raise_error
raise error, explanation
decimal.DivisionByZero: x / 0

D:\Test>python SELParser.py Prova2.txt
final content of variables
Name Value
a = 5
aa = 20
b = 10

D:\Test>python SELParser.py Prova3.txt
final content of variables
Name Value
a = 5.8
aa = 2.4650E-33
b = 8.803571428571428571428571429E-34

D:\Test>python SELParser.py Prova4.txt
final content of variables
Name Value
a = 5.8
aa = -8.500000000000000000000000000
b = -3.035714285714285714285714286
Ho verificato con la calcolatrice di Windows e i risultati sono corretti.

Spero di aver soddisfatto la tua curiosità.
Una curiosità : (chiedo a chi utilizza Delphi): in compilazione come avviene la gestione degli errori? Si ferma al primo errore o ne mostra quanti più possibile indicando approssimativamente, per ogni errore riscontrato, dove s'è verificato?
Te l'avevo già scritto qui (http://www.hwupgrade.it/forum/showpost.php?p=24454484&postcount=57):

Anche questo non è vero: col Turbo Pascal la prassi era quella di fermarsi al primo errore con l'editor che puntava alla riga e colonna incriminata e il messaggio di errore in bella evidenza.

E' stato con Delphi, se non erro, a essere stata aggiunta la possibilità di continuare a compilare e riportare tutti gli errori.

:rolleyes:

Vincenzo1968

07-10-2008, 20:45

Bene, adesso abbiamo una base in comune dalla quale partire. Vuoi essere tu a specificare le caratteristiche del linguaggio?
Prima di continuare io ti rinnovo l'invito che ti avevo già fatto: veniamoci incontro e utilizziamo Java come linguaggio target. Bison genera sorgenti solo in C o C++;posso utilizzare GOLD (http://www.devincook.com/goldparser/about/comparison-parsers.htm).

cdimauro

07-10-2008, 20:59

http://www.hwupgrade.it/forum/showpost.php?p=24434656&postcount=45

non è questo il punto, perché non stiamo confrontando ANTLR, ma i parser LL(k) e quelli LR(k).

http://www.hwupgrade.it/forum/showpost.php?p=24446548&postcount=50

In quanto a chiudere il discorso, così mi sembra troppo comodo.
Hai consigliato di usare ANTLR?
Mostraci in pratica com'è facile e divertente costruire un parser con questo strumento. Il confronto magari non lo facciamo, accontentiamoci dei risultati teorici, ma vediamo un esempio pratico almeno.

http://www.hwupgrade.it/forum/showpost.php?p=24450583&postcount=53

Per me non c'è problema: definisci pure i requisiti che deve avere questo linguaggio, e ti faccio vedere com'è facile tirare fuori il lexer e il parser con ANTLR.

Ovviamente utilizzerò Python come linguaggio di output, ma con ANTLR è possibile specificarne molti altri, per cui chi vuole può adattare l'esempio a Java, C, Delphi, ecc. ecc.

Visto che lo scopo è didattico, possiamo cominciare con delle espressioni da stampare semplicemente a video, e man man aggiungere costrutti via via più complicati (assegnazione di variabili, if, ecc.).

:read:

P.S. GOLD genera codice Python.

P.P.S. http://en.wikipedia.org/wiki/Recursive_descent_parser#Example_parser è un linguaggio con una grammatica molto semplice.

Vincenzo1968

07-10-2008, 21:07

cdimauro

07-10-2008, 21:14

Vincenzo1968

07-10-2008, 21:24

Non è questo il punto. Dove vuoi arrivare? T'ho già detto che confrontare due tool come ANTLR o YACC nulla dimostrerà sulla bontà dei parser LL(k) e LR(k).

P.S. DigitalMars = D (http://en.wikipedia.org/wiki/D_(programming_language)) Per te che sei innamorato di C & derivati dovrebbe essere allettante. ;)

Se non sbaglio avevi dato la tua disponibilità per il progetto del compilatore. Man mano che il lavoro procede, possiamo verificare quanto sia divertente utilizzare l'uno o l'altro strumento, no?
A proposito, com'è finita con l'analisi matematica degli algoritmi? Su wikipedia sono sostanzialmente uguali a quelli riportati nel libro(e le immagini sono pure più carine ;) ).

Si, l'output del file BisonCalc.exe è sbagliato. Non per cercare facili scuse, ma non l'ho scritto io. :ciapet: L'altro file BisonExpr(che ho scritto io ma che fa schifo dal punto di vista della gestione degli errori in quanto si ferma al primo) riporta il risultato corretto. Ho provato con questo sorgente:

a = 5.8
aa = a * 4.25e-34
aa / ( a - 3 )
$

Vedo di sistemare anche l'altro.

cdimauro

07-10-2008, 21:33

Se non sbaglio avevi dato la tua disponibilità per il progetto del compilatore. Man mano che il lavoro procede, possiamo verificare quanto sia divertente utilizzare l'uno o l'altro strumento, no?
Veramente s'era parlato di realizzare parser (non compilatori) per un linguaggio, e a scopo didattico (giusto per far vedere, appunto, quanto sia divertente).
A proposito, com'è finita con l'analisi matematica degli algoritmi? Su wikipedia sono sostanzialmente uguali a quelli riportati nel libro(e le immagini sono pure più carine ;) ).
Su Wikipedia non c'è quello del parser a discesa ricorsiva (http://en.wikipedia.org/wiki/Recursive_descent_parser).

Appena ho un po' di tempo (devo ancora finire di scrivere l'articolo per domani) li copio tutti e due dal Dragon Book.
Si, l'output del file BisonCalc.exe è sbagliato. Non per cercare facili scuse, ma non l'ho scritto io. :ciapet: L'altro file BisonExpr(che ho scritto io ma che fa schifo dal punto di vista della gestione degli errori in quanto si ferma al primo) riporta il risultato corretto. Ho provato con questo sorgente:

a = 5.8
aa = a * 4.25e-34
aa / ( a - 3 )
$

Vedo di sistemare anche l'altro.
La cosa comica è che l'ha scritto uno che lavora all'IBM, mi pare. :asd:

Vincenzo1968

07-10-2008, 21:47

Veramente s'era parlato di realizzare parser (non compilatori) per un linguaggio, e a scopo didattico (giusto per far vedere, appunto, quanto sia divertente).

Al di la di tutto, anche degli screzi che abbiamo avuto, mi sembra una cosa interessante. E il linguaggio che propongo, Java, potrebbe servire a far aggregare quanta più gente possibile visto che è uno dei più diffusi. Magari si potrebbe aprire un thread apposito, cosi com'è stato fatto per il gioco in Java(ma a chi bisogna rivolgersi per ottenere l'autorizzazione?).

Su Wikipedia non c'è quello del parser a discesa ricorsiva (http://en.wikipedia.org/wiki/Recursive_descent_parser).

Dammi un po' di tempo e lo posto.

cdimauro

07-10-2008, 22:08

Vincenzo1968

07-10-2008, 22:16

E' sicuramente interessante, ma richiede tempo e io ne ho ben poco a mia disposizione.

Fino a quando si tratta di tirar su un parser, una tantum si può anche fare. Anche perché oggettivamente non ci vuole molto. Specialmente con Python, come puoi vedere uno se la cava con poche righe di codice (ma soprattutto, almeno nel mio caso, mi diverto).

Aggiungere però funzionalità per farlo diventare qualcosa di complesso, o addirittura un compilatore o interprete, per me è troppo, troppo oneroso. Non ho tutto questo tempo e ho già dei progetti messi nel congelatore a cui tengo decisamente di più.

Comunque per aprire una sottosezione bisogna chiedere ai moderatori, che poi si interesseranno, eventualmente, con gli amministratori.

Ok, allora non insisto.

Solo per chi fosse interessato(se non hai tempo o voglia, dico, fottitene dell'analisi matematica): questo è l'algoritmo Recursive-Descent Parsing così com'è riportato a pag. 219 della seconda edizione:

void A()
{
Choose an A-production, A -> X1X2...Xk
for(i = 1 to k)
if( Xi is a nonterminal )
{
call procedure Xi();
}
else if ( Xi equals the current input symbol a )
{

advance the input to the next symbol;
}
else
{
/* an error has occurred */
}
}

In realtà X1, per esempio, è da leggersi X pedice 1; Xk -> X pedice k, e così via. :)

Vincenzo1968

08-10-2008, 00:30

...
La cosa comica è che l'ha scritto uno che lavora all'IBM, mi pare. :asd:

tacci sua :mad: domani (anzi oggi) alle 8 debbo essere da un cliente e Catania, a due ore da casa mia e questo qui mi ha tenuto sveglio fino a quest'ora.

Scherzo, l'autore ha fatto un gran bel lavoro. C'era un piccolo errore su una espressione regolare che non permetteva di riconoscere i numeri in formato scientifico.

Ho aggiornato il file zip (www.guidealgoritmi.it/public/BisonCalculator.zip) contenente i progetti Flex/Bison/Visual C++.

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc5.jpg

La regex giusta, nel file lex.l, è questa:

-?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?)

cdimauro

08-10-2008, 07:31

Ok, allora non insisto.

Solo per chi fosse interessato(se non hai tempo o voglia, dico, fottitene dell'analisi matematica): questo è l'algoritmo Recursive-Descent Parsing così com'è riportato a pag. 219 della seconda edizione:

void A()
{
Choose an A-production, A -> X1X2...Xk
for(i = 1 to k)
if( Xi is a nonterminal )
{
call procedure Xi();
}
else if ( Xi equals the current input symbol a )
{

advance the input to the next symbol;
}
else
{
/* an error has occurred */
}
}

In realtà X1, per esempio, è da leggersi X pedice 1; Xk -> X pedice k, e così via. :)
Supponendo che il lexer restituisca n simboli, per una grammatica LL(1) non c'è backtracking, per cui il numero di chiamate alle procedure dovrebbe essere O(n * m), dove m dovrebbe essere uguale all'altezza (massima) dell'albero di parsing.
Per lo spazio occupato, dovrebbe essere sufficiente quello per un solo simbolo, più m, quindi O(m).

Nei recursive descent parser non ci sono tabelle di parsing, per cui non serve altro spazio.

Per un parser LR(1) la situazione dovrebbe essere la stessa in termini di tempo, ma per lo spazio bisogna aggiungere quello occupato dalle tabelle (non ricordo quant'è al momento).
tacci sua :mad: domani (anzi oggi) alle 8 debbo essere da un cliente e Catania, a due ore da casa mia e questo qui mi ha tenuto sveglio fino a quest'ora.
Sei un pazzo. Io me ne sarei fregato e sarei andato a ronfare. :D
Scherzo, l'autore ha fatto un gran bel lavoro. C'era un piccolo errore su una espressione regolare che non permetteva di riconoscere i numeri in formato scientifico.

Ho aggiornato il file zip (www.guidealgoritmi.it/public/BisonCalculator.zip) contenente i progetti Flex/Bison/Visual C++.

http://www.guidealgoritmi.it/images/ImgForums/BisonCalc5.jpg

La regex giusta, nel file lex.l, è questa:

-?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?)

Suppongo che www.guidealgoritmi.it sia un tuo sito. ;)

Vincenzo1968

08-10-2008, 14:35

...
Sei un pazzo. Io me ne sarei fregato e sarei andato a ronfare. :D

Suppongo che www.guidealgoritmi.it sia un tuo sito. ;)

Sono arrivato in ritardo all'appuntamento e c'è mancato poco che un autodafé me lo organizzassero per davvero(e senza neanche usarmi la cortesia di strozzarmi prima: bruciato vivo, direttamente) :D

Si, è il mio sito. Quando hai un po' di tempo a disposizione, se scrivi un articolo che illustra brevemente il funzionamento di ANTLR, lo pubblico. Ti avviso, soldi niente; ché non me lo posso permettere col magro stipendio che guadagno. Se decidi per il si, fammi avere anche i sorgenti dell'esempio che hai postato qui, impacchettati in un file zip.

:)

cdimauro

08-10-2008, 19:54

Francamente pensavo di farne un articolo da pubblicare per AD. :D

Comunque non si tratta di un approfondimento, per cui un eventuale articolo più "sostanzioso" lo posso anche scrivere appena ho un po' di tempo. Per i soldi non c'è problema, figuriamoci: è nato tutto come un gioco. ;)

I sorgenti li posto appena ho la possibilità di dargli una ritoccata per renderlo ancora più leggibile (ho anche rimosso il backtracking eliminando la ricorsione a sinistra: adesso è una grammatica LL(1) con tutte le carte in regola; prima era una grammatica LL(*)).

vincent19851

04-05-2009, 11:46

Salve a tutti è la prima volta che posto su questo forum.
Sto realizzando un compilatore del linguaggio c. Ho realizzato dei file per l'analisi lessicale e sintattica tramite flex e bison sotto windows.
Ora mi manca l'analisi semantica.
voglio ad esempio implementare delle regole che segnalino un errore nel caso in cui io uso una variaible non precedentemente dichiarata.
Come posso fare? Avete dei suggerimenti da darmi.
Vi ringrazio in anticipo.
grazie a tutti.

Vincenzo1968

04-05-2009, 14:40

Ciao Vincent,

La situazione che hai segnalato puoi gestirla così: ogni volta che incontri una variabile utilizzata in un'espressione, consulti la tabella dei simboli(solitamente implementata come hashtable). Se la variabile è presente, ne estrai il valore e prosegui nel calcolo dell'espressione. Se non è presente stampi il messaggio di errore "identificatore non dichiarato" e prosegui con lo statement successivo.
La tabella dei simboli contiene tutte le informazioni relative ad ogni variabile(nome, tipo, valore). La situazione in cui una variabile è stata dichiarata ma non inizializzata, può essere gestita, per esempio, consultando la tabella dei simboli e controllando che sia presente il valore(oltre al tipo e al nome).
Un altro caso in cui la tabella dei simboli risulta molto utile, è nel controllo dei tipi. Per esempio, nel codice seguente:

...
...
int x;

x = "ciao";
...
...

Stiamo assegnando un valore di tipo string a una variabile di tipo int. Possiamo segnalare all'utente questo errore consultando la tabella e verificando che il tipo della variabile x sia string(nell'esempio la variabile x è di tipo int; dobbiamo, dunque, segnalare l'errore).