Programmazione del compilatore: quali sono gli ingredienti più fondamentali?

Question

Mi interessa scrivere un compilatore molto minimalista.

Voglio scrivere un piccolo pezzo di software (in C/C++) che soddisfa i seguenti criteri:

• output in formato ELF (* nix)
• ingresso è un singolo file di testo
• C-come grammatica e la sintassi
• non linker
• senza preprocessore
• molto piccola (max. 1-2 KLOC)

caratteristiche dell'abbonamento lingua:

• nativi tipi di dati: char, int e galleggia
• array (per tutti i tipi di dati nativi)
• variabili
• strutture di controllo (if-else)
• funzioni
• loop (sarebbe bello)
• algebra semplice (div, aggiungere, sub, mul, espressioni booleane, bit-turno, etc.)
• asm inline (per le chiamate di sistema)

Qualcuno può dirmi come iniziare? Non so in che cosa consista un compilatore (almeno non nel senso che potrei iniziare direttamente dallo scaffale) e come programmarli. Grazie per le tue idee.

Answer 1

In primo luogo, è necessario decidere se si intende creare un compilatore o un interprete. Un compilatore traduce il tuo codice in qualcosa che può essere eseguito direttamente sull'hardware, in un interprete, o viene compilato in un'altra lingua che poi viene interpretata in qualche modo. Entrambi i tipi di lingue sono completi, quindi hanno le stesse capacità espressive. Ti suggerisco di creare un compilatore che compili il tuo codice in bytecode .net o Java, in quanto offre un interprete molto ottimizzato per l'esecuzione oltre a molte librerie standard.

Una volta preso la tua decisione ci sono alcuni passi comuni da seguire

1. definizione del linguaggio In primo luogo, è necessario definire come la lingua dovrebbe apparire sintatticamente.

2. Lexer Il secondo passaggio consiste nel creare le parole chiave del codice, note come token. Qui, stiamo parlando di elementi molto basilari come numeri, segno di addizione e stringhe.

3. Parsing Il passaggio successivo consiste nel creare una grammatica che corrisponda all'elenco di token. Puoi definire la tua grammatica usando, ad es. una grammatica senza contesto. Un certo numero di strumenti può essere alimentato con una di queste grammatiche e creare il parser per te. Di solito, i token analizzati sono organizzati in un albero di analisi. Un albero sintattico è la rappresentazione della tua grammatica come una struttura di dati che è possibile muoversi in.

4. compilazione o Interpretazione L'ultimo passo è quello di eseguire una logica sul vostro albero sintattico. Un modo semplice per creare il proprio interprete è creare una logica associata a ciascun tipo di nodo nella struttura e attraversare l'albero dal basso verso l'alto o dall'alto verso il basso. Se si desidera compilare in un'altra lingua, è possibile inserire la logica di come tradurre il codice nei nodi.

Wikipedia è ottimo per saperne di più, potresti voler iniziare here.

Per quanto riguarda il materiale di lettura del mondo reale, suggerirei "Programmare i processori del linguaggio in JAVA" di David A Watt & Deryck F Brown. Ho usato quel libro nel mio corso per compilatori e imparare con l'esempio è fantastico in questo campo.

Answer 2

Queste sono le parti assolutamente essenziali:

• Scanner: Questo rompe il file di input in token
• Parser: questo costruisce un albero di sintassi astratta (AST) dai gettoni individuate dallo scanner.
• Generazione codice: produce l'output dall'AST.

Potrai anche probabilmente vogliono:

• gestione degli errori: Questo dice al parser che cosa fare se si incontra un token imprevisto
• Optimization: Ciò consentirà al compilatore di produrre macchina più efficiente codice

Modifica: hai già progettato la lingua? Altrimenti, ti consigliamo di esaminare anche il design della lingua.

Answer 3

Il numero uno essenziale è un libro sulla scrittura del compilatore. Un sacco di persone ti diranno di leggere il "Dragon Book" di Aho et al, ma il miglior libro che ho letto sui compilatori è "Brinch Hansen su Pascal Compilers". Sospetto che sia fuori stampa (Amazon è tuo amico), ma ti porta attraverso tutti i passaggi della progettazione e della scrittura di un compilatore usando la discesa ricorsiva, che è il metodo più semplice da comprendere per i neofiti del compilatore.

Sebbene il libro utilizzi Pascal come lingua di implementazione e di destinazione, le lezioni e le tecniche presentate si applicano allo stesso modo a tutte le altre lingue.

Answer 4

Non so cosa speri di ottenere da questo, ma se si sta imparando, e guardando il codice esistente funziona per te, c'è sempre tcc.

Answer 5

Gli esempi sono tutti in Perl, ma Exploring Programming Language Architecture in Perl è un buon libro (e gratuito).

Answer 6

Con tutto ciò che si spera di realizzare, il requisito più impegnativo potrebbe essere "molto piccolo (massimo 1-2 KLOC)". Penso che il tuo primo requisito da solo (generare output ELF) possa prendere da solo oltre un migliaio di righe di codice.

Un modo per semplificare il problema, almeno per iniziare, consiste nel generare codice nel testo del linguaggio assembly che viene quindi inserito in un assemblatore esistente (nasm sarebbe una buona scelta).L'assemblatore si occuperà di generare il codice macchina effettivo, nonché tutto il codice specifico ELF necessario per creare un eseguibile eseguibile reale. Quindi il lavoro viene ridotto all'analisi del linguaggio e alla generazione del codice di assemblaggio. Quando il tuo progetto raggiunge il punto in cui desideri rimuovere la dipendenza da un assemblatore, puoi riscriverlo da solo e collegarlo in qualsiasi momento.

Se fossi in te, potrei iniziare con un assemblatore e costruire pezzi su di esso. Il "compilatore" più semplice potrebbe prendere una lingua con pochi semplici dichiarazioni possibili:

print "hello" 
a = 5 
print a 

e tradurre che al linguaggio assembly. Una volta che hai capito, puoi costruire un lexer e un parser e un albero di sintassi e un generatore di codice astratti, che sono la maggior parte delle parti di cui avrai bisogno per un linguaggio strutturato a blocchi moderno.

Buona fortuna!

Answer 7

Io consiglio sempre flex e bison per questo tipo di lavoro come principiante. Puoi sempre imparare i dettagli della scrittura del tuo scanner e del parser in un secondo momento, anche se potrebbero aumentare le dimensioni del codice, almeno saranno generati automaticamente dagli strumenti. :)

Answer 8

Davvero un buon set di riferimenti liberi, secondo me, sono i seguenti:

complesso compilatore tutorial: costruiamo un compilatore da Jack Crenshaw (http://compilers.iecc.com/crenshaw/) E 'prolisso, ma mi piace.

Assemblatore: NASM (nasm.us) valido per Linux e Windows/DOS e, soprattutto, molto doco ed esempi/tutorial. (FASM è anche un bene, ma meno documentazione/tutorial là fuori)

Altre fonti L'Assemblea PC libro (http://www.drpaulcarter.com/pcasm/index.php)

Sto cercando di scrivere un LISP, quindi sto usando il Lisp 1.5 Manual. Potresti voler ottenere le specifiche della lingua per qualsiasi lingua tu stia scrivendo.

Fino a 1-2KLOC, assumendo che si utilizzi un linguaggio di alto livello (come Py o Rb) si dovrebbe essere vicini se non si è troppo ambiziosi.