[Java] Creazione di un COMPILATORE in TurboPascal

[.:N3XV5:.]

Ciao ragazzi!
Assieme ad un paio di amici avevamo pensato di realizzare un compilatore per la tesina in linguaggio Java (per la caratteristica multipiattaforma) o TurboPascal (per la nostra conoscenza in merito). Partendo dai molti manuali trovati in rete, voi avete qualche consiglio da darci? Attendo vostre risposte, grazie...

[cdimauro]

Realizzare un compilatore non è cosa semplice, ma con strumenti come ANTLR diventa tutto molto più semplice.

ANTLR permette di generare parser in diversi linguaggi. Java è supportato, ma Turbo Pascal no, però è supportato Delphi che è il suo successore.

[Vincenzo1968]

ANTLR produce parser di tipo LL(k) che non sono il massimo dell'efficienza.
Io ti consiglio Flex/Bison che produce parser di tipo LALR. Genera sorgenti in linguaggio C. Un esempio di compilatore realizzato con Bison è il famoso GCC. Se proprio vuoi utilizzare Java, c'è JFlex/BYACC che ti permette di scegliere tra la generazione di sorgenti in C o in Java.

Questi strumenti ti danno una mano nelle prime due fasi del processo di compilazione: analisi lessicale(Flex, JFlex) e sintattica(Bison, BYACC).
Per le fasi successive, analisi semantica, generazione del codice, etc non esistono, purtroppo, tools automatici. Un corso che ho trovato molto buono è quello della Stanford University.

[.:N3XV5:.]

Interessante ragazzi, non avevo considerato la cosa... Però l'idea mia, strettamente personale (magari i miei amici preferiscono la vostra strada), era quella di creare questo parser che traducesse istruzioni semplici (+,-,*,/,:=,sqrt,sqr,abs,...) scritte in un codice il più vicino possibile ad uno pseudo-linguaggio di programmazione. A traduzione completata, dopo aver valutato la correttezza lessico/sintattica del file oggetto generato (ed eventualmente corretta), mi piacerebbe avere un sorgente in assembler da compilare, linkare ed eseguire direttamente in DOS... Se non è chiaro, l'obiettivo non è quello di realizzare un linguaggio ultra sofisticato ed evoluto... Già ne esistono... Mi basterebbe il mio compilatore personale da perfezionare nel tempo... Il fine è prettamente didattico... Ergo... Cosa dite?...

[variabilepippo]

Cosa dite?...

Che non ha senso fare tutto a mano, sviluppare un compilatore non è una cosa semplicissima, soprattutto se non si usano gli strumenti consigliati.

Al posto vostro (considerato il target) seguirei l'approccio proposto da cdimauro, così facendo vi risparmiereste tanti grattacapi. Date un'occhiata a ANTLRWorks, vi permette di creare la grammatica in maniera visuale.

[Vincenzo1968]

Originariamente inviato da .:N3XV5:.

... Il fine è prettamente didattico... Ergo... Cosa dite?...

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).
Qui trovi un esempio di un piccolo interprete per espressioni aritmetiche. Utilizza un automa a stati finiti di tipo pushdown(tecnica utilizzata da entrambi i tipi di parser, LL(k) e LALR).

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.

[cdimauro]

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

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.

[DanieleC88]

Originariamente inviato da .:N3XV5:.

Assieme ad un paio di amici avevamo pensato di realizzare un compilatore per la tesina

L'idea è bella, anche se forse per una tesina è abbastanza impegnativa.

[Vincenzo1968]

Originariamente inviato da cdimauro

...
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 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]

Originariamente inviato da .:N3XV5:.

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]

Il lavoro originale, del 1965, di colui che ha sviluppato le tecniche LR(k), il grande Knuth:

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

[cdimauro]

Originariamente inviato da Vincenzo1968

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 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.

[Vincenzo1968]

Originariamente inviato da cdimauro

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.

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

[cdimauro]

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

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

[Vincenzo1968]

Originariamente inviato da cdimauro

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

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

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?

[cdimauro]

Originariamente inviato da Vincenzo1968

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...

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!

E ci sarebbe da chiedersi perchè, tra le facili vie, non abbiano scelto ANTLR. È forse gente che non ama il divertimento?

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...

[Vincenzo1968]

Originariamente inviato da cdimauro

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...

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!

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...

CPython, da quanto si legge nel sito, è 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?

[Vincenzo1968]

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

tratto dalla documentazione del parser PyPy:

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)

[.:N3XV5:.]

Originariamente inviato da Vincenzo1968

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...

Originariamente inviato da Vincenzo1968

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]

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