Aquí intenté mostrar en la práctica cuáles son algunos conceptos importantes del campo de la creación de compiladores. Existe la posibilidad de que tales historias completas de 15 minutos sean una buena manera de sumergirse en temas complejos. Solo sería bueno no leer pasivamente lo que se presenta a continuación, sino también verificar el código en el trabajo.
Si la primera experiencia es exitosa, en el futuro puede esperar otros "bocetos" de 15 minutos sobre el tema de los compiladores.
Lo que se discutirá
Hagamos un compilador de expresiones aritméticas. Uno que traduce el texto fuente en notación polaca inversa (también se llama RPN o POLIZ) en código intermedio que funciona con la pila. Pero podemos prescindir de intérpretes aquí. Luego, traducimos inmediatamente el resultado en una representación en C. Es decir, obtenemos un compilador de RPN a C.
Por cierto, escribiremos el compilador en Python. Pero no dejes que esto detenga a aquellos que prefieren algún otro lenguaje de programación. Aquí hay un ejercicio útil para usted: traduzca el siguiente código a su idioma favorito. O use una traducción ya completada:
Implementación de F # (por gsomix ):
primera versión
Versión SSA
Comencemos con el análisis
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
Que hemos hecho aqui La función de escaneo recibe una cadena del usuario en notación polaca inversa ("2 2 +").
Y en la salida obtenemos su representación intermedia. Aquí hay un ejemplo:
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
Entonces, ya tenemos el compilador. Pero él es muy frívolo. Recordemos que inicialmente se trataba del código C.
Vamos a transmitir en C
def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
¿Qué está pasando aquí? Veamos el resultado de esta función (usando el mismo ejemplo con "2 2 +").
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
Sí, ya se parece al código C. Array st desempeña el papel de la pila, y sp es su puntero. Por lo general, las máquinas de pila virtual funcionan con estas cosas.
Esa es solo la máquina misma: el intérprete, no tenemos. Hay un compilador ¿Qué nos queda? Es necesario agregar los marcos necesarios para el programa C.
Nuestro primer compilador terminado
ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
Queda por compilar la salida de este programa con el compilador de C.
¿Todavía estás listo para continuar? Entonces discutamos lo que hicimos. Hay un momento dudoso: nuestro compilador traduce expresiones constantes y puede calcularlas simplemente en la etapa de compilación. No tiene sentido traducirlos a código. Pero supongamos por ahora que algunos argumentos pueden llegar a la pila desde el exterior. Detengámonos en el hecho de que el significado práctico de nuestro desarrollo se puede dar más adelante. Ahora es importante tener una idea general de construir los compiladores más simples, ¿verdad?
¿Te gusta el titular? SSA: esto suena muy sólido para cualquier compilador. Y ahora usaremos este mismo SSA. Que es esto Movámonos en orden.
Actualmente estamos generando código C, sin máquinas virtuales. Pero, ¿por qué necesitamos un rudimento en forma de operaciones de pila? Reemplacemos estas operaciones con trabajar con variables ordinarias de C. Además, no guardaremos variables, tendremos un nuevo nombre para cada expresión. Deje que el compilador de C se ocupe de todo esto. Resulta que con nosotros a cada variable se le asigna un valor solo una vez. Y esto, por cierto, es la forma de SSA .
Aquí está nuestro nuevo compilador.
C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
Tenga en cuenta que ya no hay una pila en el código C, y trabajar con él se simula durante la traducción. La pila que se usa en el proceso de compilación no contiene valores, sino nombres de variables.
Aquí está el resultado final:
#include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
Resumen
Parece que el tiempo para nuestra lección conjunta ha expirado. Nos dedicamos a traducir el programa de un idioma a otro. Esto se llama traducción de fuente a fuente. O bien, solo una traducción, que puede considerarse un sinónimo de compilación, pero generalmente el compilador traduce el programa de una representación de alto nivel a una de bajo nivel. También está la palabra de moda "transpiler" para el traductor de fuente a fuente. Pero la mención del "transpilador" puede ser molesto para los expertos en compilación, ¡tenga cuidado!
Experimenta con el código. A la espera de comentarios!