Escribir un compilador en su propio idioma

Question

Intuitivamente, parece que un compilador para el lenguaje Foo no se puede escribir en Foo. Más específicamente, el compilador first para el lenguaje Foo no puede escribirse en Foo, pero cualquier compilador posterior podría escribirse para Foo .

¿Pero es esto realmente cierto? Tengo un recuerdo muy vago de leer sobre un idioma cuyo primer compilador fue escrito en sí mismo. ¿Es esto posible y, de ser así, cómo?

Answer 1

Esto se llama "bootstrapping". Primero debe crear un compilador (o intérprete) para su idioma en algún otro idioma (generalmente Java o C). Una vez hecho esto, puede escribir una nueva versión del compilador en lenguaje Foo. Utiliza el primer compilador de arranque para compilar el compilador, y luego usa este compilador compilado para compilar todo lo demás (incluidas las versiones futuras de sí mismo).

La mayoría de los idiomas se crean de esta manera, en parte porque a los diseñadores de idiomas les gusta usar el lenguaje que están creando, y también porque un compilador no trivial a menudo sirve como un punto de referencia útil sobre cómo "completar". el idioma puede ser.

Un ejemplo de esto sería Scala. Su primer compilador fue creado en Pizza, un lenguaje experimental de Martin Odersky. A partir de la versión 2.0, el compilador fue completamente reescrito en Scala. A partir de ese momento, el viejo compilador de Pizza podría descartarse por completo, debido al hecho de que el nuevo compilador de Scala podría usarse para compilarse para futuras iteraciones.

Answer 2

Recuerdo haber escuchado un Ingeniería de software Radio podcast en el que Dick Gabriel habló sobre el arranque del intérprete LISP original escribiendo una versión básica en LISP en papel y ensamblando a mano en código máquina. A partir de entonces, el resto de las funciones de LISP se escribieron e interpretaron con LISP.

Answer 3

Agregar curiosidad a las respuestas anteriores.

Aquí hay una cita del Linux From Scratch , en el paso donde uno comienza a construir el compilador GCC de su fuente. (Linux From Scratch es una forma de instalar Linux que es radicalmente diferente de instalar una distribución, ya que debe compilar realmente cada binario del sistema de destino).

make bootstrap

     

El objetivo 'bootstrap' no solo compila GCC, sino que lo compila varias veces. Utiliza los programas compilados en un primer       redondear para compilarse por segunda vez, y luego nuevamente por tercera vez. Luego compara estos segundos y terceros       compila para asegurarse de que pueda reproducirse sin problemas. Esto también implica que se compiló correctamente.

El uso del objetivo 'bootstrap' está motivado por el hecho de que el compilador que se usa para construir la cadena de herramientas del sistema de destino puede no tener la misma versión del compilador de destino. Procediendo de esa manera, uno seguramente obtendrá, en el sistema de destino, un compilador que pueda compilarse a sí mismo.

Answer 4

Cuando escribe su primer compilador para C, lo escribe en otro lenguaje. Ahora, tiene un compilador para C en, digamos, ensamblador. Eventualmente, llegará al lugar donde debe analizar las cadenas, específicamente las secuencias de escape. Escribirás código para convertir \ n al carácter con el código decimal 10 (y \ r a 13, etc.).

Una vez que el compilador esté listo, comenzará a volver a implementarlo en C. Este proceso se llama " bootstrapping " ;.

El código de análisis de cadenas se convertirá en:

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

Cuando esto se compila, tienes un binario que entiende '\ n'. Esto significa que puede cambiar el código fuente:

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

Entonces, ¿dónde está la información de que '\ n' es el código para 13? ¡Está en el binario! Es como el ADN: compilar el código fuente C con este binario heredará esta información. Si el compilador se compila solo, transmitirá este conocimiento a su descendencia. A partir de este momento, no hay forma de ver solo desde la fuente lo que hará el compilador.

Si desea ocultar un virus en la fuente de algún programa, puede hacerlo así: Obtenga la fuente de un compilador, busque la función que compila las funciones y reemplácela por esta:

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

Las partes interesantes son A y B. A es el código fuente de compileFunction incluyendo el virus, probablemente encriptado de alguna manera, por lo que no es obvio al buscar el binario resultante. Esto asegura que compilar al compilador consigo mismo preservará el código de inyección de virus.

B es lo mismo para la función que queremos reemplazar con nuestro virus. Por ejemplo, podría ser la función " login " en el archivo fuente " login.c " que probablemente sea del kernel de Linux. Podríamos reemplazarlo con una versión que acepte la contraseña "Joshua" para la cuenta raíz además de la contraseña normal.

Si compila eso y lo difunde como un binario, no habrá forma de encontrar el virus mirando la fuente.

La fuente original de la idea: http: //cm.bell-labs .com / who / ken / trust.html

Answer 5

No puede escribir un compilador en sí mismo porque no tiene nada para compilar su código fuente inicial. Hay dos enfoques para resolver esto.

El menos favorecido es el siguiente. Usted escribe un compilador mínimo en ensamblador (yuck) para un conjunto mínimo de lenguaje y luego usa ese compilador para implementar características adicionales del lenguaje. Ábrete camino hasta que tengas un compilador con todas las características del lenguaje por sí mismo. Un proceso doloroso que generalmente solo se realiza cuando no tienes otra opción.

El enfoque preferido es usar un compilador cruzado. Cambia el back-end de un compilador existente en una máquina diferente para crear una salida que se ejecute en la máquina de destino. Entonces tienes un buen compilador completo y trabajando en la máquina de destino. El más popular para esto es el lenguaje C, ya que hay muchos compiladores existentes que tienen back-end conectables que se pueden intercambiar.

Un hecho poco conocido es que el compilador GNU C ++ tiene una implementación que usa solo el subconjunto C. La razón es que generalmente es fácil encontrar un compilador de C para una nueva máquina de destino que le permite construir el compilador completo de GNU C ++ a partir de él. Ahora ha arrancado a sí mismo para tener un compilador de C ++ en la máquina de destino.

Answer 6

Generalmente, primero debe tener un corte de trabajo (si es primitivo) del compilador funcionando, luego puede comenzar a pensar en hacerlo autohospedaje. En realidad, esto se considera un hito importante en algunos idiomas.

Por lo que recuerdo de "mono", es probable que necesiten agregar algunas cosas a la reflexión para que funcione: el equipo de mono sigue señalando que algunas cosas simplemente no son posibles con Reflection .Emit ; por supuesto, el equipo de MS podría demostrar que están equivocados.

Esto tiene algunas ventajas reales : es una prueba unitaria bastante buena, para empezar. Y solo tiene que preocuparse por un idioma (es decir, es posible que un experto en C # no conozca mucho C ++; pero ahora puede arreglar el compilador de C #). Pero me pregunto si no hay una gran cantidad de orgullo profesional en el trabajo aquí: simplemente quieren que sea de alojamiento propio.

No es un compilador, pero recientemente he estado trabajando en un sistema que es autohospedaje; el generador de código se usa para generar el generador de código ... así que si el esquema cambia, simplemente lo ejecuto en sí mismo: nueva versión. Si hay un error, vuelvo a una versión anterior e intento nuevamente. Muy conveniente y muy fácil de mantener.

---

Actualización 1

Acabo de ver este video de Anders en PDC y (acerca de una hora) da algunas razones mucho más válidas: todo sobre el compilador como servicio. Solo para el registro.

Answer 7

Aquí hay un volcado (tema difícil de buscar, en realidad):

• Smalltalk

• C

Esta es también la idea de PyPy y Rubinius :

(Creo que esto también podría aplicarse a Adelante , pero no lo hago no sé nada sobre Forth.)

Answer 8

GNAT, el compilador Ada de GNU, requiere un compilador Ada para estar completamente construido. Esto puede ser una molestia al portarlo a una plataforma donde no hay binarios GNAT disponibles.

Answer 9

En realidad, la mayoría de los compiladores están escritos en el idioma que compilan, por las razones indicadas anteriormente.

El primer compilador de arranque generalmente se escribe en C, C ++ o ensamblado.

Answer 10

El compilador del proyecto Mono C # ha sido "autohospedado" desde hace mucho tiempo, lo que significa es que se ha escrito en C #.

Lo que sé es que el compilador se inició como código C puro, pero una vez que el "básico" Se implementaron características de ECMA, comenzaron a reescribir el compilador en C #.

No conozco las ventajas de escribir el compilador en el mismo idioma, pero estoy seguro de que tiene que ver al menos con las características que el lenguaje en sí puede ofrecer (C, por ejemplo, no admite objetos programación orientada).

Puede encontrar más información aquí .

Answer 11

Quizás pueda escribir un BNF describiendo BNF.