Come scrivere un compilatore di base

Intro

Un tipico compilatore esegue i seguenti passaggi:

• Analisi: il il testo sorgente viene convertito in un albero di sintassi astratto (AST).
• Risoluzione dei riferimenti ad altri moduli (il C rimanda questo passaggio fino al collegamento).
• Convalida semantica: eliminazione di dichiarazioni sintatticamente corrette che non ha senso, ad es codice non raggiungibile o dichiarazioni duplicate.
• Trasformazioni equivalenti e ottimizzazione di alto livello: lAST viene trasformato per rappresentare un calcolo più efficiente con la stessa semantica. Ciò include ad es. calcolo precoce di sottoespressioni comuni ed espressioni costanti, eliminando assegnazioni locali eccessive (vedere anche SSA ), ecc.
• Generazione di codice: lAST è trasformato in codice lineare di basso livello, con salti, allocazione di registri e simili. Alcune chiamate di funzione possono essere inline in questa fase, alcuni loop srotolati, ecc.
• Ottimizzazione dello spioncino: il codice di basso livello viene scansionato per semplici inefficienze locali che vengono eliminate.

La maggior parte dei compilatori moderni (ad esempio, gcc e clang) ripetono ancora una volta gli ultimi due passaggi. Usano un linguaggio intermedio di basso livello ma indipendente dalla piattaforma per la generazione iniziale del codice. Quindi quel linguaggio viene convertito in codice specifico della piattaforma (x86, ARM, ecc.) Facendo più o meno la stessa cosa in un modo ottimizzato per la piattaforma. Ciò include ad es. luso di istruzioni vettoriali quando possibile, il riordino delle istruzioni per aumentare lefficienza della previsione dei rami e così via.

Dopodiché, il codice oggetto è pronto per il collegamento. La maggior parte dei compilatori di codice nativo sa come chiamare un linker per produrre un eseguibile, ma non è un passaggio di compilazione di per sé. In linguaggi come Java e C # il collegamento può essere totalmente dinamico, eseguito dalla VM al momento del caricamento.

Ricorda le basi

• Fallo funzionare
• Rendilo bello
• Rendilo efficiente

Questa sequenza classica si applica a tutto lo sviluppo del software, ma è ripetibile.

Concentrati sul primo passaggio della sequenza. Crea la cosa più semplice che possa funzionare.

Leggi i libri!

Leggi il Dragon Book di Aho e Ullman. Questo è classico ed è ancora abbastanza applicabile oggi.

Modern Compiler Design è anche lodato.

Se questa roba è troppo difficile per te in questo momento, leggi prima alcune introduzioni sullanalisi; di solito sullanalisi delle librerie includi introduzioni ed esempi.

Assicurati di essere a tuo agio nel lavorare con i grafici, specialmente con gli alberi. Queste cose sono le cose di cui sono fatti i programmi a livello logico.

Definisci bene la tua lingua

Usa la notazione che vuoi, ma assicurati di avere una descrizione completa e coerente del tuo linguaggio. Ciò include sia la sintassi che la semantica.

È giunto il momento di scrivere frammenti di codice nella nuova lingua come casi di test per il futuro compilatore.

Usa la tua lingua preferita

È totalmente OK scrivere un compilatore in Python o Ruby o in qualsiasi altro linguaggio sia facile per te.Usa algoritmi semplici che conosci bene. La prima versione non deve essere veloce, efficiente o completa di funzionalità. Deve solo essere sufficientemente corretto e facile da modificare.

Va bene anche scrivere fasi diverse di un compilatore in lingue diverse, se necessario.

Preparati a scrivere molto di test

La tua intera lingua dovrebbe essere coperta da casi di test; effettivamente sarà definita da loro. Acquisisci familiarità con il tuo framework di test preferito. Scrivi test dal primo giorno. Concentrati sui test “positivi” che accettano il codice corretto, invece di rilevare il codice errato.

Esegui tutti i test regolarmente. Correggi i test interrotti prima di procedere. Sarebbe un peccato finire con un errore linguaggio definito che non può accettare codice valido.

Crea un buon parser

I generatori di parser sono molti . Scegli quello che preferisci Puoi anche scrivere il tuo parser da zero, ma ne vale la pena solo se la sintassi del tuo linguaggio è morto semplice.

Il parser dovrebbe rilevare e segnalare errori di sintassi. Scrivi molti casi di test, sia positivi che negativi ve; riutilizza il codice che hai scritto durante la definizione della lingua.

Loutput del tuo parser è un albero di sintassi astratto.

Se il tuo linguaggio ha moduli, loutput del parser potrebbe essere la rappresentazione più semplice di “codice oggetto” generato. Esistono molti modi semplici per eseguire il dump di un albero in un file e per caricarlo rapidamente.

Crea un validatore semantico

Molto probabilmente il tuo linguaggio consente costruzioni sintatticamente corrette che possono rendere non ha senso in certi contesti. Un esempio è una dichiarazione duplicata della stessa variabile o il passaggio di un parametro di un tipo sbagliato. Il validatore rileverà tali errori guardando lalbero.

Il validatore risolverà anche i riferimenti ad altri moduli scritti nella tua lingua, caricherà questi altri moduli e li userà nel processo di validazione. Ad esempio, questo passaggio assicurerà che il numero di parametri passati a una funzione da un altro modulo sia corretto.

Di nuovo, scrivi ed esegui molti casi di test. I casi banali sono indispensabili per la risoluzione dei problemi quanto intelligenti e complessi.

Genera codice

Usa le tecniche più semplici che conosci. Spesso va bene tradurre direttamente un costrutto di linguaggio (come unistruzione if) in un modello di codice leggermente parametrizzato, non diversamente da un modello HTML.

Di nuovo , ignora lefficienza e concentrati sulla correttezza.

Scegli come target una VM di basso livello indipendente dalla piattaforma

Suppongo che tu ignori le cose di basso livello a meno che tu non “sia vivamente interessato allhardware specifico dettagli. Questi dettagli sono cruenti e complessi.

Le tue opzioni:

• LLVM: consente una generazione efficiente del codice macchina, di solito per x86 e ARM.
• CLR : target .NET, multipiattaforma; ha un buon JIT.
• JVM: prende di mira il mondo Java, abbastanza multipiattaforma, ha un buon JIT.

Ignora lottimizzazione

Lottimizzazione è difficile. Quasi sempre lottimizzazione è prematura. Genera codice inefficiente ma corretto. Implementa lintero linguaggio prima di provare a ottimizzare il codice risultante.

Ovviamente, è possibile introdurre ottimizzazioni banali. Ma evita qualsiasi cosa astuta e pelosa prima che il tuo compilatore sia stabile.

E allora?

Se tutta questa roba non ti intimidisce, per favore procedi! Per un linguaggio semplice, ciascuno dei passaggi potrebbe essere più semplice di quanto potresti pensare.

Vedere un “Hello world” da un programma creato dal tuo compilatore potrebbe valere la pena.

Commenti

• Questa è una delle migliori risposte che ‘ abbia mai visto.
• Penso che tu mancava una parte della domanda … LOP voleva scrivere un compilatore molto semplice . Penso che tu vada oltre le basi qui.
• @ marco-fiset , al contrario, penso che sia ‘ è una risposta eccezionale che dice allOP come fare un compilatore molto semplice, sottolineando le trappole da evitare e definendo fasi più avanzate.
• Questa è una delle migliori risposte Lho mai visto nellintero universo Stack Exchange. Kudos!
• Vedere un ‘ Hello world ‘ da un programma creato dal tuo compilatore potrebbe valere la pena. – INDEED

Jack Crenshaw “s Let “s Build a Compiler , sebbene incompleto, è unintroduzione e un tutorial estremamente leggibili.

Nicklaus Wirth” s Compiler Construction è un ottimo libro di testo sulle basi della costruzione semplice del compilatore. Si concentra sulla discesa ricorsiva top-down, che, ammettiamolo, è MOLTO più facile di lex / yacc o flex / bison. Il compilatore originale PASCAL che il suo gruppo ha scritto è stato fatto in questo modo.

Altre persone hanno menzionato i vari libri di Dragon.

Commenti

• Una delle cose belle di Pascal, è che tutto deve essere definito o dichiarato prima di essere utilizzato. Pertanto può essere compilato in un unico passaggio. Turbo Pascal 3.0 è uno di questi esempi e cè molta documentazione sugli interni qui .
• PASCAL è stato specificamente progettato con uno- passare la compilazione e il collegamento in mente. Il libro del compilatore di Wirth ‘ menziona i compilatori multipass e aggiunge che sapeva di un compilatore PL / I che richiedeva 70 (sì, settanta) passaggi.
• Dichiarazione obbligatoria prima delluso risale ad ALGOL. Tony Hoare è stato bloccato dalle orecchie dal comitato ALGOL quando ha cercato di suggerire di aggiungere regole di tipo predefinito, simili a quelle di FORTRAN. Sapevano già dei problemi che questo poteva creare, con errori tipografici nei nomi e regole predefinite che creavano bug interessanti.
• Ecco una versione più aggiornata e completa del libro dello stesso autore originale: stack.nl/~marcov/compiler.pdf Modifica la tua risposta e aggiungi questa 🙂

Se vuoi davvero scrivere codice leggibile dalla macchina e non indirizzato a una macchina virtuale, dovrai leggere i manuali Intel e capire

• a. Collegamento e caricamento del codice eseguibile

• b. I formati COFF e PE (per Windows), in alternativa comprendono il formato ELF (per Linux)

• c. Comprendere i formati di file .COM (più semplici di PE)
• d. Comprendere gli assemblatori
• e. Comprendi i compilatori e il motore di generazione del codice nei compilatori.

Molto più difficile di quanto detto. Ti suggerisco di leggere Compilatori e interpreti in C ++ come punto di partenza (di Ronald Mak). In alternativa, “consente di creare un compilatore” di Crenshaw è OK.

Se non vuoi farlo, potresti anche scrivere la tua VM e scrivere un generatore di codice mirato a quella VM.

• Un altro punto di partenza: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book By Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Suggerimenti: impara PRIMA Flex e Bison. Quindi continua a creare il tuo compilatore / VM.

Buona fortuna!

Commenti

• Penso che il targeting LLVM e non il vero codice macchina è il modo migliore disponibile oggi.
• Sono daccordo, seguo LLVM da un po di tempo e dovrei dire che è stata una delle cose migliori che avessi visto negli anni in termini di impegno del programmatore necessario per selezionarlo come target!
• Che dire di MIPS e utilizzare spim per eseguirlo? Oppure MIX ?
• @MichaelT Non ho usato MIPS ma sono sicuro che andrà bene.
• @PrototypeStark Set di istruzioni RISC, processore del mondo reale ancora in uso oggi (comprendendo che sarà traducibile in sistemi embedded). Il set completo di istruzioni si trova in wikipedia . Guardando in rete, ci sono molti esempi ed è utilizzato in molte classi accademiche come bersaglio per la programmazione in linguaggio macchina. Cè un po di attività in SO .

In realtà “avrei iniziato scrivendo un compilatore per Brainfuck . È” un linguaggio abbastanza ottuso in cui programmare ma ha solo 8 istruzioni da implementare. È semplice quanto puoi ottenere e ci sono istruzioni C equivalenti là fuori per i comandi coinvolti se trovi la sintassi scoraggiante.

Commenti

• Ma poi, una volta che hai il tuo compilatore BF pronto, devi scrivere il tuo codice al suo interno 🙁
• @ 500-InternalServerError usa il metodo del subset C

Lapproccio fai-da-te per un semplice compilatore potrebbe assomigliare a questo (almeno così appariva il mio progetto uni):

1. Definisci la grammatica della lingua. Senza contesto.
2. Se la tua grammatica non è ancora “t LL (1), fallo ora. Nota che alcune regole che sembravano a posto in semplice CF la grammatica può risultare brutta. Forse la tua lingua è troppo complessa …
3. Scrivi Lexer che taglia il flusso di testo in token (parole, numeri, letterali).
4. Scrivi dallalto verso il basso parser discendente ricorsivo per la tua grammatica, che accetta o rifiuta linput.
5. Aggiungi la generazione dellalbero della sintassi nel tuo parser.
6. Scrivi ma generatore di codice chine dallalbero della sintassi.
7. Profitto & Beer, in alternativa puoi iniziare a pensare a come eseguire un parser più intelligente o generare codice migliore.

Dovrebbe abbondanza di letteratura che descrive ogni passaggio in dettaglio.

Commenti

• Il settimo punto è ciò su cui si chiede OP.
• 1-5 sono irrilevanti e non lo meritano una grande attenzione. 6 è la parte più interessante.Sfortunatamente, la maggior parte dei libri segue lo stesso schema, dopo il famigerato libro del drago, prestando troppa attenzione allanalisi e lasciando le trasformazioni del codice fuori ambito.