Tomemos un ejemplo muy simple. Solo tendremos números y el operador ‘+’ en nuestro idioma, y lo único que puede hacer es imprimir el resultado de las adiciones.
Eso es demasiado simple para ser útil, por supuesto, pero es suficiente para mostrar el flujo.
Entonces, digamos que comenzamos con esto:
- Criptografía: ¿Qué sucedería si alguien encuentra un algoritmo significativamente más rápido para factorizar enteros grandes?
- Teoría de la complejidad computacional: ¿Hay conjeturas famosas que alguna vez se creyeron firmemente que eran ciertas pero que luego se demostraron falsas?
- ¿Por qué no todas las personas que son buenas en matemáticas también son buenas en programación de computadoras?
- Cómo implementar esto en Python: dada una matriz, encuentre tres números a, byc de modo que a ^ 2 + b ^ 2 = c ^ 2
- Para aquellos que son buenos en programación pero no en matemáticas, ¿qué les resulta difícil de las matemáticas?
1 + 3 + 5
Todos los compiladores funcionan como una serie de transformaciones de una forma a otra. Entonces, para nuestros primeros pasos, transformaremos esto en una representación con la que sea más fácil trabajar.
Nuestro primer paso es reconocer las piezas que componen nuestro programa. Llamamos a esto un tokenizador , y el resultado es un flujo de tokens. Piense que reconoce que las palabras y la puntuación forman un lenguaje escrito. Generalmente, asignamos un tipo a cada token; Esto simplifica las cosas más adelante, ya que no tenemos que seguir descubriendo lo que estamos viendo:
Numero 1
Operador: +
Numero 3
Operador: +
Número 5
Eso fue bastante trivial, pero si tuviéramos números más grandes, podría verse así, con múltiples dígitos en las fichas numéricas.
Número: 100
Operador: +
Número: 3563
Operador: +
Número: 512
Pero para mantener el siguiente diagrama simple, me quedo con el primer ejemplo.
Llamamos al segundo paso un analizador sintáctico. el analizador toma una serie de tokens y comprende su estructura. El resultado es un árbol de análisis o un árbol de sintaxis abstracta (AST) .
+
/ \
1 +
/ \
3 5
Bien, hasta ahora, no ha importado cómo es nuestro entorno objetivo. Pero ahora necesitamos saber cómo hacer que esto haga cosas. Para nuestro ejemplo, inventemos una máquina de destino simple. Vamos a darle a nuestra máquina de destino una pila y tres operaciones. Cada uno está representado por un código de operación de un byte, numerado como se muestra a continuación.
- CONST n – empuja un valor constante n en nuestra pila. n tiene 4 bytes de longitud y sigue el código de operación.
- AGREGAR: agregue los dos valores superiores en la pila, eliminándolos y reemplazándolos con su suma.
- IMPRIMIR: imprime el valor superior en la pila y retíralo.
La siguiente etapa es generar una secuencia de instrucciones. Todavía no hacemos esto como bytes reales. Podríamos, en este ejemplo simple, pero los compiladores reales hacen cosas como optimizaciones y necesitan completar la dirección de la sucursal, por lo que ahorraremos generando los bytes para la última etapa.
Primero, nuestra etapa de generación de código comienza en la parte superior del AST y ve el operador ‘+’, por lo que sabe que primero debe calcular las mitades izquierda y derecha, luego emitir un ADD.
Así que comienza con la izquierda. Es una constante, por lo que generamos:
CONST 1
Ahora, tenemos que hacer lo correcto. Es una operación ‘+’ nuevamente, por lo que necesitamos generar ese código para obtener el resultado en la pila. Este es simple, así que vamos a sumergirnos, llamando recursivamente a nuestro generador de código, generando los operandos izquierdo y derecho, y luego emitimos el ADD.
CONST 1
CONST 3
CONST 5
AÑADIR
OK, las 3 instrucciones que acabamos de agregar nos dan el operando del lado derecho, y finaliza nuestra llamada recursiva, y estamos de vuelta en nuestra primera llamada al generador de código, listos para emitir el ADD
CONST 1
CONST 3
CONST 5
AÑADIR
AÑADIR
Ahora que hemos llegado al final de nuestro programa, es hora de imprimir el resultado. Aquí está el resultado final:
CONST 1
CONST 3
CONST 5
AÑADIR
AÑADIR
IMPRESIÓN
Ahora todo lo que queda es convertirlo en bytes. Para facilitar la lectura, lo mantendré dividido en líneas, pero esto es solo una serie de bytes.
1 0 0 0 1
1 0 0 0 3
1 0 0 0 5
2
2
3
Escriba esos 18 bytes en un archivo para cargarlo como un programa en nuestra máquina de destino, ¡y listo!
Ahora, los compiladores reales tienen más pasos que este, y los idiomas de origen y destino serán mucho más complejos, con variables, condicionales, bucles, etc.
Y a veces hay un paso después de la compilación, que vincula varios resultados de compilación en un solo programa ejecutable.
Pero esto es suficiente para darle la estructura básica y el enfoque.
Apuesto a que podría implementar esto en una hora o unas pocas, y tener un lenguaje de trabajo que podría comenzar a ampliar, para explorar más los conceptos. La parte más difícil será el analizador. En el mundo real, probablemente desee evitar escribir un analizador directamente; Hay idiomas enteros dedicados a crear tokenizadores y analizadores. Para idiomas reales, recomiendo ANTLR4. No es simple, pero es mucho más simple que escribir un analizador sintáctico para un lenguaje complejo.
Pero para idiomas simples, puede escribir un tipo de analizador llamado analizador de “descenso recursivo” sin demasiada dificultad, y eso es lo que recomendaría para su primer compilador de juguetes.
