Scrivere un compilatore nella propria lingua

Intuitivamente, sembrerebbe che un compilatore per il linguaggio Foo non possa essere esso stesso scritto in Foo. Più specificamente, il primo compilatore per il linguaggio Foo non può essere scritto in Foo, ma qualsiasi compilatore successivo potrebbe essere scritto per Foo .

Ma è vero? Ho un ricordo molto vago di leggere di una lingua il cui primo compilatore è stato scritto in “se stesso”. È ansible, e se sì, come?

Questo è chiamato “bootstrap”. Devi prima build un compilatore (o un interprete) per la tua lingua in qualche altra lingua (solitamente Java o C). Una volta fatto, puoi scrivere una nuova versione del compilatore in linguaggio Foo. Si utilizza il primo compilatore di bootstrap per compilare il compilatore e quindi si utilizza questo compilatore compilato per compilare tutto il resto (comprese le versioni future di se stesso).

La maggior parte delle lingue sono infatti create in questo modo, in parte perché i progettisti di linguaggi amano usare il linguaggio che stanno creando, e anche perché un compilatore non banale serve spesso come utile punto di riferimento per quanto “completo” possa essere il linguaggio.

Un esempio di questo sarebbe Scala. Il suo primo compilatore è stato creato in Pizza, un linguaggio sperimentale di Martin Odersky. A partire dalla versione 2.0, il compilatore è stato completamente riscritto in Scala. Da quel momento in poi, il vecchio compilatore Pizza potrebbe essere completamente scartato, perché il nuovo compilatore Scala potrebbe essere usato per compilare se stesso per le iterazioni future.

Ricordo di aver ascoltato un podcast di Software Engineering Radio in cui Dick Gabriel parlava del bootstrap dell’interprete LISP originale scrivendo una versione di bare-bone in LISP su carta e assemblandola a mano in codice macchina. Da quel momento in poi, il resto delle funzionalità di LISP sono state scritte e interpretate con LISP.

Aggiungendo una curiosità alle risposte precedenti.

Ecco una citazione dal manuale Linux From Scratch , nel punto in cui si inizia a compilare il compilatore GCC dalla sua origine. (Linux From Scratch è un modo per installare Linux che è radicalmente diverso dall’installazione di una distribuzione, nel senso che devi compilare davvero ogni singolo binario del sistema di destinazione.)

 make bootstrap 

L’objective ‘bootstrap’ non si limita a compilare GCC, ma lo compila più volte. Usa i programmi compilati in un primo round per compilare se stesso una seconda volta, e poi di nuovo una terza volta. Quindi confronta queste seconde e terze compilazioni per assicurarsi che possa riprodursi in modo impeccabile. Ciò implica anche che è stato compilato correttamente.

L’uso del target “bootstrap” è motivato dal fatto che il compilatore che si usa per build la toolchain del sistema di destinazione potrebbe non avere la stessa versione del compilatore di destinazione. Procedendo in questo modo si è sicuri di ottenere, nel sistema di destinazione, un compilatore che può compilare se stesso.

Quando scrivi il tuo primo compilatore per C, lo scrivi in ​​un’altra lingua. Ora, hai un compilatore per C, per esempio, assemblatore. Alla fine, arriverete al punto in cui dovrete analizzare stringhe, in particolare le sequenze di escape. Scrivere il codice per convertire \n nel carattere con il codice decimale 10 (e \r a 13, ecc.).

Dopo che il compilatore è pronto, inizierai a reimplementarlo in C. Questo processo è chiamato ” bootstrap “.

Il codice di analisi delle stringhe diventerà:

 ... if (c == 92) { // backslash c = getc(); if (c == 110) { // n return 10; } else if (c == 92) { // another backslash return 92; } else { ... } } ... 

Quando questo si compila, hai un binario che capisce ‘\ n’. Questo significa che puoi cambiare il codice sorgente:

 ... if (c == '\\') { c = getc(); if (c == 'n') { return '\n'; } else if (c == '\\') { return '\\'; } else { ... } } ... 

Allora, dov’è l’informazione che ‘\ n’ è il codice per 13? È nel binario! È come il DNA: la compilazione del codice sorgente C con questo binario erediterà queste informazioni. Se il compilatore si compila, passerà questa conoscenza alla sua progenie. Da questo punto in poi, non c’è modo di vedere dalla fonte da sola ciò che farà il compilatore.

Se vuoi hide un virus nel sorgente di qualche programma, puoi farlo in questo modo: Ottieni il sorgente di un compilatore, trova la funzione che compila le funzioni e sostituiscile con questa:

 void compileFunction(char * name, char * filename, char * code) { if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) { code = A; } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) { code = B; } ... code to compile the function body from the string in "code" ... } 

Le parti interessanti sono A e B. A è il codice sorgente per compileFunction include il virus, probabilmente crittografato in qualche modo, quindi non è ovvio cercare il binario risultante. Ciò assicura che la compilazione con il compilatore conservi il codice dell’iniezione del virus.

B è lo stesso per la funzione che vogliamo sostituire con il nostro virus. Ad esempio, potrebbe essere la funzione “login” nel file sorgente “login.c” che è probabilmente dal kernel di Linux. Potremmo sostituirlo con una versione che accetterà la password “joshua” per l’account root oltre alla normale password.

Se lo compili e lo diffondi come binario, non ci sarà modo di trovare il virus osservando la fonte.

La fonte originale dell’idea: http://cm.bell-labs.com/who/ken/trust.html

Non è ansible scrivere un compilatore in sé stesso perché non hai nulla per compilare il codice sorgente iniziale con. Ci sono due approcci per risolvere questo.

Il meno favorito è il seguente. Scrivi un compilatore minimale in assembler (yuck) per un set minimo del linguaggio e poi usa quel compilatore per implementare funzionalità extra del linguaggio. Costruisci fino a quando non hai un compilatore con tutte le funzionalità linguistiche per sé. Un processo doloroso che di solito viene fatto solo quando non hai altra scelta.

L’approccio preferito è usare un cross-compilatore. Si modifica il back-end di un compilatore esistente su un altro computer per creare l’output che viene eseguito sul computer di destinazione. Quindi hai un bel compilatore completo e lavora sul computer di destinazione. Il più popolare per questo è il linguaggio C, in quanto ci sono molti compilatori esistenti che hanno back-end collegabili che possono essere scambiati.

Un fatto poco noto è che il compilatore GNU C ++ ha un’implementazione che utilizza solo il sottoinsieme C. Il motivo è che è solitamente facile trovare un compilatore C per un nuovo computer di destinazione che consente di compilare il compilatore GNU C ++ completo da esso. Ora hai fatto il boot di te stesso per avere un compilatore C ++ sul computer di destinazione.

In generale, è necessario avere un taglio funzionante (se primativo) del compilatore che funzioni per primo, quindi puoi iniziare a pensare di renderlo self-hosting. Questo è in realtà considerato un importante traguardo in alcune lingue.

Da quello che ricordo da “mono”, è probabile che avranno bisogno di aggiungere alcune riflessioni per farlo funzionare: il team mono continua a sottolineare che alcune cose semplicemente non sono possibili con Reflection.Emit ; naturalmente, la squadra di MS potrebbe dimostrarli sbagliati.

Questo ha alcuni vantaggi reali : è un test unitario abbastanza buono, per i principianti! E hai solo una lingua di cui preoccuparti (cioè è ansible che un esperto di C # non conosca molto C ++, ma ora puoi aggiustare il compilatore C #). Ma mi chiedo se qui non ci sia un certo orgoglio professionale al lavoro: vogliono semplicemente che sia un self-hosting.

Non abbastanza un compilatore, ma di recente ho lavorato su un sistema che è self-hosting; il generatore di codice è usato per generare il generatore di codice … quindi se lo schema cambia, semplicemente lo eseguo su se stesso: nuova versione. Se c’è un bug, torno a una versione precedente e riprovo. Molto comodo e molto facile da mantenere.


Aggiornamento 1

Ho appena visto questo video di Anders su PDC, e (circa un’ora in) dà alcuni motivi molto più validi – tutto sul compilatore come servizio. Solo per la cronaca.

Nella teoria del compilatore, puoi usare diagrammi a T per descrivere il processo di bootstrap. Ad esempio, vedi qui .

Nella mia tesi di laurea, ho usato questi diagrammi a T per descrivere il processo di conversione e visualizzazione dei documenti quando si memorizzavano grandi quantità di documenti elettronici in formati diversi da piattaforms diverse.

Ecco un dump (argomento difficile da cercare, in realtà):

  • Smalltalk

  • C

Questa è anche l’idea di PyPy e Rubinius :

(Penso che questo potrebbe valere anche per Forth , ma non so nulla di Forth.)

GNAT, il compilatore GNU Ada, richiede che un compilatore Ada sia completamente compilato. Questo può essere un problema quando lo si trasferisce su una piattaforma dove non esiste un binario GNAT facilmente disponibile.

In realtà, la maggior parte dei compilatori sono scritti nella lingua che compilano, per le ragioni sopra esposte.

Il primo compilatore di bootstrap di solito è scritto in C, C ++ o Assembly.

Il compilatore C # del progetto Mono è stato “auto-ospitato” da molto tempo, ciò che significa è che è stato scritto in C # stesso.

Quello che so è che il compilatore è stato avviato come puro codice C, ma una volta implementate le funzionalità “di base” di ECMA, hanno iniziato a riscrivere il compilatore in C #.

Non sono a conoscenza dei vantaggi di scrivere il compilatore nella stessa lingua, ma sono sicuro che deve fare almeno con le funzionalità che il linguaggio stesso può offrire (C, ad esempio, non supporta la programmazione orientata agli oggetti) .

Puoi trovare maggiori informazioni qui .

Forse puoi scrivere un BNF che descrive BNF.