Scrivere un compilatore nella sua lingua

StackOverflow https://stackoverflow.com/questions/193560

Domanda

Intuitivamente, sembrerebbe che un compilatore per la lingua Foo non possa essere scritto da solo in Foo. Più specificamente, il primo compilatore per la lingua Foo non può essere scritto in Foo, ma qualsiasi compilatore successivo potrebbe essere scritto per Foo .

Ma è davvero vero? Ho un vago ricordo della lettura di una lingua il cui primo compilatore è stato scritto in "stesso". È possibile, e se sì, come?

È stato utile?

Soluzione

Questo si chiama " bootstrap " ;. Devi prima compilare un compilatore (o interprete) per la tua lingua in un'altra lingua (solitamente Java o C). Fatto ciò, puoi scrivere una nuova versione del compilatore in lingua Foo. Si utilizza il primo compilatore 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 effettivamente create in questo modo, in parte perché i progettisti di lingue amano usare il linguaggio che stanno creando, e anche perché un compilatore non banale spesso serve da utile punto di riferimento per come "completare". la lingua potrebbe essere.

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, a causa del fatto che il nuovo compilatore Scala poteva essere utilizzato per compilare se stesso per future iterazioni.

Altri suggerimenti

Ricordo di aver ascoltato un Ingegneria del software Radio podcast in cui Dick Gabriel ha parlato del bootstrap dell'interprete LISP originale scrivendo una versione bare-bones in LISP su carta e assemblandolo a mano in codice macchina. Da quel momento in poi, le altre funzionalità di LISP sono state sia scritte che interpretate con LISP.

Aggiunta di una curiosità alle risposte precedenti.

Ecco una citazione dal Linux From Scratch , nella fase in cui si inizia a costruire il compilatore GCC dalla sua fonte. (Linux From Scratch è un modo per installare Linux che è radicalmente diverso dall'installazione di una distribuzione, in quanto devi compilare davvero ogni singolo binario del sistema di destinazione.) 

make bootstrap
     

Il target 'bootstrap' non solo compila GCC, ma lo compila più volte. Utilizza i programmi compilati in un primo momento       round per compilare se stesso una seconda volta, e poi di nuovo una terza volta. Quindi confronta questi secondi e terzi       si compila 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 costruire la toolchain del sistema target potrebbe non avere la stessa versione del compilatore target. Procedendo in questo modo si ottiene sicuramente, nel sistema di destinazione, un compilatore in grado di compilare se stesso.

Quando scrivi il tuo primo compilatore per C, lo scrivi in ??un'altra lingua. Ora, hai un compilatore per C in, diciamo, assemblatore. Alla fine, verrai nel posto in cui devi analizzare le stringhe, in particolare sfuggire alle sequenze. Scriverai il codice per convertire \ n nel carattere con il codice decimale 10 (e \ r in 13, ecc.)

Dopo che il compilatore è pronto, inizierai a reimplementarlo in C. Questo processo è chiamato " bootstrapping ".

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 viene compilato, 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 {
        ...
    }
}
...

Quindi dove sono le informazioni che '\ n' è il codice per 13? È nel binario! È come il DNA: la compilazione del codice sorgente C con questo file binario erediterà queste informazioni. Se il compilatore si compila da solo, passerà questa conoscenza alla sua prole. Da questo punto in poi, non c'è modo di vedere solo dalla fonte cosa farà il compilatore.

Se vuoi nascondere un virus nella fonte di alcuni programmi, puoi farlo in questo modo: Ottieni la fonte di un compilatore, trova la funzione che compila le funzioni e sostituiscila 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 incluso il virus, probabilmente crittografato in qualche modo quindi non è ovvio dalla ricerca nel binario risultante. Ciò garantisce che la compilazione con il compilatore stesso conserverà il codice di 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 proviene 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 guardando la fonte.

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

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

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

L'approccio preferito è usare un compilatore incrociato. Si modifica il back-end di un compilatore esistente su una macchina diversa per creare output che viene eseguito sulla macchina di destinazione. Quindi hai un bel compilatore completo attivo e funzionante sulla macchina target. Il più popolare per questo è il linguaggio C, poiché 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 usa solo il sottoinsieme C. Il motivo è che di solito è facile trovare un compilatore C per un nuovo computer di destinazione che consente di compilare il compilatore C ++ GNU completo da esso. Ora hai avviato te stesso con un compilatore C ++ sul computer di destinazione.

Generalmente, devi prima avere un taglio funzionante (se primitivo) del compilatore - quindi puoi iniziare a pensare di renderlo self-hosting. Questo è in realtà considerato un importante traguardo in alcuni linguaggi.

Da quello che ricordo da " mono " ;, è probabile che dovranno aggiungere alcune cose alla riflessione per farlo funzionare: il team mono continua a sottolineare che alcune cose semplicemente non sono possibili con Reflection .Emit ; ovviamente, il team MS potrebbe dimostrarli sbagliati.

Questo ha alcuni reali vantaggi: è un test unitario abbastanza buono, per cominciare! E hai solo un linguaggio di cui preoccuparti (cioè è possibile che un esperto di C # non conosca molto C ++; ma ora puoi correggere il compilatore C #). Ma mi chiedo se non c'è un certo orgoglio professionale al lavoro qui: semplicemente vogliono essere self-hosting.

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

Aggiornamento 1

Ho appena visto questo video di Anders al PDC e (circa un'ora dopo) fornisce alcune ragioni molto più valide - tutto sul compilatore come servizio. Solo per la cronaca.

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

Questa è anche l'idea di PyPy e Rubinius :

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

GNAT, il compilatore GNU Ada, richiede che un compilatore Ada sia completamente compilato. Questo può essere un problema quando si esegue il porting su una piattaforma in cui non è disponibile alcun binario GNAT.

In realtà, la maggior parte dei compilatori sono scritti nella lingua che compilano, per i motivi sopra indicati.

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

Il compilatore C # del progetto Mono è stato "ospitato da solo" da molto tempo, ciò significa che è stato scritto in C # stesso.

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

Non sono consapevole dei vantaggi della scrittura del compilatore nella stessa lingua, ma sono sicuro che abbia a che fare almeno con le funzionalità che il linguaggio stesso può offrire (C, ad esempio, non supporta l'oggetto programmazione orientata).

Puoi trovare maggiori informazioni qui .

Forse puoi scrivere un BNF che descrive BNF.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top