Escribir un compilador en su propio idioma

Intuitivamente, parece que un compilador para el lenguaje Foono se puede escribir en Foo. Más específicamente, el primer compilador para el lenguaje Foono se puede escribir en Foo, pero se puede escribir para cualquier compilador posterior Foo.

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

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 cuán "completo" puede ser el lenguaje.

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.

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

Agregar una curiosidad a las respuestas anteriores.

Aquí hay una cita del manual Linux From Scratch , en el paso donde uno comienza a construir el compilador GCC desde 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 una primera ronda para compilarse por segunda vez, y luego nuevamente por tercera vez. Luego compara estas compilaciones segunda y tercera 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.

Cuando escribe su primer compilador para C, lo escribe en otro lenguaje. Ahora, tiene un compilador para C en, por ejemplo, ensamblador. Finalmente, llegará al lugar donde debe analizar las cadenas, específicamente las secuencias de escape. Escribirás código para convertir \nal carácter con el código decimal 10 (y \ra 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, encuentre 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 para compileFunctionincluir el virus, probablemente encriptado de alguna manera, por lo que no es obvio al buscar el binario resultante. Esto asegura que compilar el 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 núcleo 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: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

No puede escribir un compilador en sí mismo porque no tiene nada con qué 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.

En general, primero debe tener un corte funcional (si es primitivo) del compilador, 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 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 (alrededor de una hora) da algunas razones mucho más válidas: todo sobre el compilador como servicio. Para que conste.

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

• Charla

• C

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

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

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 fácilmente disponibles.

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.

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

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

No conozco las ventajas de escribir el compilador en el mismo lenguaje, 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 programación orientada a objetos) .

Puedes encontrar más información aquí .

Escribí SLIC (Sistema de idiomas para implementar compiladores) en sí mismo. Luego lo compiló a mano en ensamblaje. Hay mucho para SLIC, ya que era un compilador único de cinco sub-idiomas:

• SYNTAX Parser Lenguaje de programación PPL
• Lenguaje de generación de código PSEUDO de rastreo de árboles basado en GENERATOR LISP 2
• Secuencia ISO, código PSEUDO, lenguaje de optimización
• PSEUDO Macro como código ensamblador que produce lenguaje.
• Instrucciones de máquina de ensamblaje MACHOP que definen el lenguaje.

SLIC se inspiró en CWIC (compilador para escribir e implementar compiladores). A diferencia de la mayoría de los paquetes de desarrollo de compiladores, SLIC y CWIC abordaron la generación de código con idiomas especializados y específicos de dominio. SLIC amplía la generación de código de los CWIC agregando los sub-idiomas ISO, PSEUDO y MACHOP que separan los detalles de la máquina de destino del lenguaje generador de rastreo de árboles.

LISP 2 árboles y listas

El sistema de gestión de memoria dinámica del lenguaje generador basado en LISP 2 es un componente clave. Las listas se expresan en el lenguaje entre corchetes, sus componentes separados por comas, es decir, una lista de tres elementos [a, b, c].

Arboles:

     ADD
    /   \
  MPY     3
 /   \
5     x

están representados por listas cuya primera entrada es un objeto de nodo:

[ADD,[MPY,5,x],3]

Los árboles se muestran comúnmente con el nodo separado antes de las ramas:

ADD[MPY[5,x],3]

Descompresión con funciones de generador basadas en LISP 2

Una función generadora es un conjunto con nombre de (sin analizar) => acción> pares ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Las expresiones sin analizar son pruebas que coinciden con patrones de árbol y / o tipos de objetos que los separan y asignan esas partes a la variable local para que sean procesadas por su acción procesal. Algo así como una función sobrecargada que toma diferentes tipos de argumentos. Excepto que las pruebas () => ... se intentan en el orden codificado. El primer análisis sin éxito que ejecuta su acción correspondiente. Las expresiones sin analizar son pruebas de desmontaje. ADD [x, y] coincide con un árbol ADD de dos ramas que asigna sus ramas a las variables locales x e y. La acción puede ser una expresión simple o un bloque de código acotado .BEGIN ... .END. Hoy usaría bloques c estilo {...}. La coincidencia de árbol, [], las reglas no analizadas pueden llamar a los generadores que pasan los resultados devueltos a la acción:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

Específicamente, el anterior expr_gen unparse coincide con un árbol ADD de dos ramas. Dentro del patrón de prueba, se llamará a un generador de argumento único colocado en una rama de árbol con esa rama. Sin embargo, su lista de argumentos son variables locales asignadas a objetos devueltos. Encima de unparse especifica que una rama dos es AGREGAR el desmontaje del árbol, presionando recursivamente cada rama para expr_gen. El retorno de la rama izquierda se coloca en variables locales x. Del mismo modo, la rama derecha pasó a expr_gen con y el objeto de retorno. Lo anterior podría ser parte de un evaluador de expresiones numéricas. Hubo funciones de acceso directo llamadas vectores que se encuentran en lo anterior, en lugar de la cadena de nodos, se podría usar un vector de nodos con un vector de acciones correspondientes:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

El evaluador de expresiones más completo anterior que asigna el retorno de la rama izquierda expr_gen a x y la rama derecha a y. El vector de acción correspondiente realizado en x e y regresó. Los últimos pares de acción unparse => coinciden con objetos numéricos y de símbolos.

Símbolo y atributos de símbolo

Los símbolos pueden tener atributos con nombre. val: (x) accede al atributo val del objeto de símbolo contenido en x. Una pila de tabla de símbolos generalizada es parte de SLIC. La tabla SÍMBOLO puede ser empujada y explotada proporcionando símbolos locales para funciones. Los símbolos recién creados se catalogan en la tabla de símbolos superior. La búsqueda de símbolos busca la pila de la tabla de símbolos desde la tabla superior primero hacia atrás en la pila.

Generando código independiente de la máquina

El lenguaje generador de SLIC produce objetos de instrucción PSEUDO, agregándolos a una lista de códigos de secciones. Un .FLUSH hace que se ejecute su lista de códigos PSEUDO eliminando cada instrucción PSEUDO de la lista y llamándola. Después de la ejecución, se libera una memoria de objetos PSEUDO. Los cuerpos procesales de las acciones PSEUDO y GENERATOR son básicamente el mismo lenguaje, excepto por su salida. PSEUDO está destinado a actuar como macros de ensamblaje que proporcionan secuenciación de código independiente de la máquina. Proporcionan una separación de la máquina de destino específica del lenguaje del generador de rastreo de árboles. Los PSEUDO llaman a las funciones de MACHOP para generar el código de máquina. Los MACHOP se utilizan para definir pseudooperaciones de ensamblaje (como dc, definir constante, etc.) y la instrucción de máquina o una familia de instrucciones formateadas similares que utilizan la entrada vectorial. Simplemente transforman sus parámetros en una secuencia de campos de bits que componen la instrucción. Las llamadas de MACHOP tienen el aspecto de un ensamblado y proporcionan formato de impresión de los campos para cuando el ensamblaje se muestra en la lista de compilación. En el código de ejemplo, estoy usando comentarios de estilo c que podrían agregarse fácilmente pero que no estaban en los idiomas originales. Los MACHOP están produciendo código en un poco de memoria direccionable. El enlazador SLIC maneja la salida del compilador. Un MACHOP para las instrucciones del modo de usuario DEC-10 usando la entrada vectorial: Los MACHOP están produciendo código en un poco de memoria direccionable. El enlazador SLIC maneja la salida del compilador. Un MACHOP para las instrucciones del modo de usuario DEC-10 usando la entrada vectorial: Los MACHOP están produciendo código en un poco de memoria direccionable. El enlazador SLIC maneja la salida del compilador. Un MACHOP para las instrucciones del modo de usuario DEC-10 usando la entrada vectorial:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

El .MORG 36, O (18): $ / 36; alinea la ubicación a un límite de 36 bits imprimiendo la ubicación $ / 36 palabra dirección de 18 bits en octal. El registro opcd de 9 bits, el registro de 4 bits, el registro indirecto de bits y el registro de índice de 4 bits se combinan e imprimen como si fuera un solo campo de 18 bits. La dirección de 18 bits / 36 o valor inmediato se emite e imprime en octal. Un ejemplo de MOVEI se imprime con r1 = 1 y r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Con la opción de ensamblaje del compilador, obtiene el código de ensamblaje generado en la lista de compilación.

Vincularlo juntos

El enlazador SLIC se suministra como una biblioteca que maneja los enlaces y las resoluciones de símbolos. Sin embargo, el formato de archivo de carga de salida específico de destino debe escribirse para las máquinas de destino y vincularse con la biblioteca de la biblioteca de vinculadores.

El lenguaje generador es capaz de escribir árboles en un archivo y leerlos, lo que permite implementar un compilador multipass.

Breve resumen de la generación y el origen del código.

Primero revisé la generación de código para asegurarme de que se entiende que SLIC fue un verdadero compilador. SLIC se inspiró en CWIC (compilador para compiladores de escritura e implementación) desarrollado en Systems Development Corporation a fines de la década de 1960. CWIC solo tenía los lenguajes SYNTAX y GENERATOR que producen código de bytes numéricos fuera del lenguaje GENERATOR. El código de bytes se colocó o se plantó (el término utilizado en la documentación de los CWIC) en memorias intermedias asociadas con secciones nombradas y escrito por una declaración .FLUSH. Un documento de ACM sobre CWIC está disponible en los archivos de ACM.

Implementar con éxito un lenguaje de programación importante

A fines de la década de 1970, SLIC se utilizó para escribir un compilador cruzado COBOL. Completado en aproximadamente 3 meses principalmente por un solo programador. Trabajé un poco con el programador según fue necesario. Otro programador escribió la biblioteca de tiempo de ejecución y los MACHOP para la mini COMPUTADORA TI-990 de destino. Ese compilador COBOL compiló sustancialmente más líneas por segundo que el compilador COBOL nativo DEC-10 escrito en ensamblador.

Más a un compilador que por lo general hablaba

Una gran parte de escribir un compilador desde cero es la biblioteca de tiempo de ejecución. Necesitas una tabla de símbolos. Necesita entrada y salida. Gestión de memoria dinámica, etc. Puede ser más fácil escribir la biblioteca de tiempo de ejecución para un compilador que escribir el compilador. Pero con SLIC esa biblioteca de tiempo de ejecución es común a todos los compiladores desarrollados en SLIC. Tenga en cuenta que hay dos bibliotecas de tiempo de ejecución. Uno para la máquina de destino del lenguaje (COBOL, por ejemplo). El otro es la biblioteca de tiempo de ejecución de los compiladores del compilador.

Creo que he establecido que estos no eran generadores de analizadores sintácticos. Así que ahora, con un poco de comprensión del back-end, puedo explicar el lenguaje de programación del analizador.

Lenguaje de programación del analizador

El analizador se escribe usando una fórmula escrita en forma de ecuaciones simples.

<name> <formula type operator> <expression> ;

El elemento del lenguaje en el nivel más bajo es el personaje. Los tokens se forman a partir de un subconjunto de los caracteres del idioma. Las clases de caracteres se usan para nombrar y definir esos subconjuntos de caracteres. El operador que define la clase de caracteres es el carácter de dos puntos (:). Los caracteres que son miembros de la clase están codificados en el lado derecho de la definición. Los caracteres imprimibles están encerrados en cadenas simples de primos. Los caracteres no impresos y especiales pueden representarse por su ordinal numérico. Los miembros de la clase están separados por una alternativa | operador. Una fórmula de clase termina con un punto y coma. Las clases de caracteres pueden incluir clases previamente definidas:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

Skip_class 0b00000001 está predefinido, pero puede estar definiendo una skip_class de manera general.

En resumen: una clase de caracteres es una lista de alternativas que solo puede ser una constante de caracteres, un ordinal de caracteres o una clase de caracteres previamente definida. Mientras implementaba las clases de caracteres: a la fórmula de clase se le asigna una máscara de bits de clase. (Se muestra en los comentarios anteriores) Cualquier fórmula de clase que tenga un carácter literal u ordinal hace que se asigne un bit de clase. Una máscara se forma ordeando la (s) máscara (s) de clase de las clases incluidas junto con el bit asignado (si lo hay). Se crea una tabla de clase a partir de las clases de caracteres. Una entrada indexada por el ordinal de un personaje contiene bits que indican la pertenencia a la clase del personaje. Las pruebas de clase se realizan en línea. Un ejemplo de código IA-86 con el ordinal del personaje en eax ilustra las pruebas de clase:

test    byte ptr [eax+_classmap],dgt

Seguido de un:

jne      <success>

o

je       <failure>

Se usan ejemplos de códigos de instrucciones IA-86 porque creo que las instrucciones IA-86 son más conocidas hoy en día. El nombre de clase que evalúa su máscara de clase se AND no destructivamente con la tabla de clase indexada por los caracteres ordinales (en eax). Un resultado distinto de cero indica pertenencia a la clase. (EAX se pone a cero a excepción de al (los 8 bits bajos de EAX) que contiene el carácter).

Los tokens eran un poco diferentes en estos viejos compiladores. Las palabras clave no se explicaron como tokens. Simplemente se correspondían con constantes de cadena entre comillas en el lenguaje analizador. Las cadenas citadas normalmente no se guardan. Se pueden usar modificadores. A + mantiene la cadena coincidente. (es decir, + '-' coincide con un carácter - manteniendo el carácter cuando tiene éxito) La operación, (es decir, 'E') inserta la cadena en el token. El espacio en blanco es manejado por la fórmula del token que omite los principales caracteres SKIP_CLASS hasta que se realiza una primera coincidencia. Tenga en cuenta que una coincidencia explícita de caracteres skip_class detendrá el salto permitiendo que un token comience con un carácter skip_class. La fórmula del token de cadena omite los principales caracteres skip_class que coinciden con un carácter de comillas simples o una cadena de comillas dobles. De interés es la coincidencia de un "carácter dentro de" una cadena citada:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

La primera alternativa coincide con cualquier carácter entre comillas simples. La alternativa correcta coincide con una cadena entre comillas dobles que puede incluir caracteres de comillas dobles usando dos caracteres "juntos para representar un solo carácter". Esta fórmula define las cadenas utilizadas en su propia definición. La alternativa interna correcta '"' $ (-" "" ".ANY |" "" "" "," "" ") '"' coincide con una cadena entre comillas dobles. Podemos usar un solo carácter 'entre comillas para que coincida con un carácter doble "entre comillas. Sin embargo, dentro de la cadena doble" entre comillas si deseamos usar un carácter "debemos usar dos" para obtener uno. Por ejemplo, en la alternativa interna izquierda que coincide con cualquier carácter, excepto una cita:

-"""" .ANY

un vistazo negativo adelante - "" "" se usa que cuando tiene éxito (no coincide con un "carácter") coincide con el carácter .ANY (que no puede ser un "carácter porque -" "" "eliminó esa posibilidad). La alternativa correcta está asumiendo: "" "" coincidir con un carácter "y fallar eran la alternativa correcta:

"""""",""""

intenta hacer coincidir dos "caracteres reemplazándolos con un solo doble" usando "" "" para insertar el único carácter ". Ambas alternativas internas que fallan en el carácter de comillas de cadena de cierre coinciden y se llama a MAKSTR [] para crear un objeto de cadena. El $ secuencia, bucle exitoso, el operador se utiliza para hacer coincidir una secuencia. Fórmula de token omitir los caracteres principales de la clase de omisión (con espacio). Una vez que se realiza una primera coincidencia, skip_class skipping está deshabilitado. Podemos invocar funciones programadas en otros idiomas usando []. MAKSTR [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [] y MAKINT [] son ​​funciones de biblioteca que convierten una cadena de token coincidente en un objeto escrito. La siguiente fórmula numérica ilustra un reconocimiento de token bastante complejo:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

La fórmula de token de número anterior reconoce números enteros y de coma flotante. Las alternativas son siempre exitosas. Se pueden usar objetos numéricos en los cálculos. Los objetos de token se insertan en la pila de análisis en caso de éxito de la fórmula. El exponente principal en (+ 'E' | 'e', ​​'E') es interesante. Deseamos tener siempre una E mayúscula para MAKEFLOAT []. Pero permitimos una 'e' minúscula reemplazándola usando 'E'.

Es posible que haya notado consistencias de la clase de caracteres y la fórmula del token. La fórmula de análisis continúa agregando alternativas de retroceso y operadores de construcción de árboles. Los operadores alternativos de retroceso y no retroceso no pueden mezclarse dentro de un nivel de expresión. Es posible que no tenga (a | b \ c) mezclando sin retroceso | con \ alternativa de retroceso. (a \ b \ c), (a | b | c) y ((a | b) \ c) son válidos. Una alternativa \ backtracking guarda el estado de análisis antes de intentar su alternativa izquierda y, en caso de falla, restaura el estado de análisis antes de intentar la alternativa correcta. En una secuencia de alternativas, la primera alternativa exitosa satisface al grupo. No se intentan otras alternativas. La factorización y la agrupación proporcionan un análisis continuo continuo. La alternativa de retroceso crea un estado guardado del análisis antes de intentar su alternativa izquierda. Se requiere retroceder cuando el análisis puede hacer una coincidencia parcial y luego falla:

(a b | c d)\ e

En lo anterior, si un fallo devuelve el CD alternativo se intenta. Si entonces c devuelve el fallo, se intentará la alternativa de retroceso. Si a tiene éxito yb falla, el análisis será retrocedido e intentado. Del mismo modo, una falla c exitosa yb falla, el análisis se remonta y se toma la alternativa e. El retroceso no se limita a una fórmula. Si alguna fórmula de análisis hace una coincidencia parcial en cualquier momento y luego falla, el análisis se restablece a la pista superior y se toma su alternativa. Se puede producir un error de compilación si el código se ha emitido al detectar que se creó la pista inversa. Se establece un retroceso antes de comenzar la compilación. Devolver la falla o retroceder a ella es una falla del compilador. Las pistas son apiladas. Podemos usar negativo - y positivo? eche un vistazo / mire a los operadores para probar sin avanzar el análisis. ser prueba de cadena es un vistazo por delante que solo necesita el estado de entrada guardado y restablecido. Una mirada hacia el futuro sería una expresión de análisis que hace una coincidencia parcial antes de fallar. Una mirada hacia el futuro se implementa utilizando el seguimiento hacia atrás.

El lenguaje del analizador no es un analizador LL o LR. Pero un lenguaje de programación para escribir un analizador recursivo decente en el que se programa la construcción del árbol:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Un ejemplo de análisis usado comúnmente es una expresión aritmética:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp y plazo usando un bucle crea un árbol zurdo. El factor usando la recursión correcta crea un árbol diestro:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Aquí hay un poco del compilador cc, una versión actualizada de SLIC con comentarios de estilo c. Los tipos de función (gramática, token, clase de caracteres, generador, PSEUDO o MACHOP se determinan por su sintaxis inicial después de su ID. Con estos analizadores de arriba hacia abajo, comienza con una fórmula que define el programa:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Observe cómo se factoriza la identificación y luego se combina al crear el árbol.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

Cabe destacar cómo el lenguaje del analizador maneja los comentarios y la recuperación de errores.

Creo que he respondido la pregunta. Habiendo escrito una gran parte del sucesor de SLIC, el lenguaje cc en sí mismo aquí. Todavía no hay compilador para ello. Pero puedo compilarlo a mano en código ensamblador, funciones desnudas asm c o c ++.

Sí, puedes escribir un compilador para un idioma en ese idioma. No, no necesita un primer compilador para ese lenguaje para arrancar.

Lo que necesita para arrancar es una implementación del lenguaje. Puede ser un compilador o un intérprete.

Históricamente, se pensaba que los idiomas eran idiomas interpretados o idiomas compilados. Los intérpretes solo se escribieron para el primero y los compiladores solo se escribieron para el segundo. Entonces, por lo general, si un compilador se escribiría para un idioma, el primer compilador se escribiría en otro idioma para arrancarlo, luego, opcionalmente, el compilador se volvería a escribir para el idioma de la asignatura. Pero escribir un intérprete en otro idioma es una opción.

Esto no es solo teórico. Actualmente estoy haciendo esto yo mismo. Estoy trabajando en un compilador para un lenguaje, Salmon, que desarrollé yo mismo. Primero creé un compilador de Salmon en C y ahora estoy escribiendo el compilador en Salmon, así puedo hacer que funcione el compilador de Salmon sin tener un compilador para Salmon escrito en ningún otro idioma.

Tal vez puedas escribir un BNF describiendo BNF.