Para todos nosotros, los compiladores son programas que traducen un código fuente a un código objeto. Estos traductores han permitido que los lenguajes puedan alcanzar mayores grados de abstracción y claridad en su sintaxis. Estamos ajenos a cómo el CPU realiza lo que necesitamos; el código compilado es el encargado de explicárselo. El objetivo de este artículo es introducirnos en el proceso de compilación, cómo funciona a grandes rasgos y cuáles son sus principales características.
[CóDIGO FUENTE] -> (COMPILADOR) -> [CóDIGO OBJETO]
El proceso de compilación está dividido en diferentes etapas con propósitos individuales, pero que juntos alcanzan la tarea final: traducirnos nuestro código. El código objeto o final no tiene que ser específicamente código máquina, puede perfectamente ser un lenguaje intermedio como el Byte Code de Java o el MSIL de .NET. He dividido el trabajo en las etapas que conforman la compilación.
1ra: Análisis Lexicológico o Lexicográfico::
Todo lenguaje está formalizado por una gramática, que define cuáles son las características del mismo. Define, por ejemplo, cuáles son los caracteres terminales: operadores, delimitadores, palabras claves, características de los identificadores, etc. El Analizador Lexicológico o Lexer, se encarga de convertir todo el código fuente en una secuencia de tokens, que no son más que esos caracteres terminales. Los ejemplos siguientes nos ayudarán:
Código fuente 1: int a := 25;
Cadena de tokens: INT,ID,ASIG,CONST,SEMICOLON.
Código fuente 2: int b:= (a*2)+4;
Cadena de tokens: INT,ID,ASIG,LP,ID,MULT,CONST,RP,PLUS,CONST,SEMICOLON.
Las comas las puse para aclararlo un poco, pues el Lexer sólo devuelve una secuencia de tokens y se come todos los espacios, cambios de líneas, comentarios y tabulaciones que escribimos en nuestro código original. Hay lenguajes como Python que son indentados (ver referencias), donde las tabulaciones y saltos de líneas cumplen un objetivo; pero en la mayoría de ellos podemos escribir todo un programa en una sola línea.
El Lexer también trabaja con el Gestor de Errores, que acumula todos los errores en el código detectables por el compilador: los llamados errores en tiempo de compilación. El Lexer es capaz de detectar todo lo que no es válido para la gramática, como identificadores que empiezan con un número y operadores indefinidos (3 +(4@5) // la arroba no pinta nada). La Tabla de Símbolos se encarga de ir acumulando todos los campos o identificadores que se definan en el programa; luego, cuando el Lexer encuentre lo que él supone que sea un identificador, lo agrega a la Tabla.
El resultado final del Lexer es, como dijimos, una secuencia de tokens, pero éstos pueden a su vez contener atributos. Por ejemplo, el ID guarda su nombre, CONST puede ser numérico o secuencia de caracteres; luego guarda su tipo y el valor que contiene.
2da Etapa: Análisis Sintáctico::
Este analizador también se conoce como Parser y es el encargado de reconocer si el orden de los tokens es correcto, además de generar árboles de análisis sintácticos. El análisis sintáctico se especifica mediante una gramática libre de contexto.
Es imprescindible hablar un poco de las gramáticas si queremos ver cómo funcionan los compiladores. Una gramática está compuesta por objetos terminales (son los identificadores, constantes, operadores...), objetos no terminales (son expresiones booleanas, aritméticas...) y un conjunto de reglas que transforman una secuencia de terminales y no terminales en otra. El estudioso Noam Chomsky (amigo de Cuba, ha salido en las Mesas Redondas analizando cuestiones políticas) definió una jerarquía de gramáticas para clasificarlas de acuerdo a la estructura de sus reglas.
Las Gramáticas Libres del Contexto son aquellas cuyas reglas tienen la siguiente forma:
A-> x, donde A es un No terminal y x es una secuencia de terminales y no terminales cualesquiera.
Entrando en nuestro problema nuevamente, un lenguaje de programación está definido por una gramática -en muchos casos libre del contexto. Las reglas no son más que la sintaxis de los mismos, por ejemplo:
<asignación> -> <variable> < := > <expresión>
Donde <asignación>, <variable> y <expresión> son no terminales, luego tienen a su vez otras reglas que los derivan, y <:=>, que es un terminal. El hecho de definir los lenguajes de esta manera nos permite estructurar un programa en forma de árbol, llamado árbol de derivación.
Dada la siguiente gramática veremos cómo la flecha roja del ejemplo genera el árbol de derivación para A:= A+B:
<sent_asig> -> <var> := <expresión>
<expresión> -> <expresión> + <término> | <expresión> - <término>|<término>
<término> -> <término> * <factor> | <término> / <factor>|<factor>
<factor> -> ( <expresión> ) |<var> | <num>
<var> -> A | B | C | D | ... |Z
<num> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Trata ahora de generar el árbol siguiente, correspondiente a la sentencia C:=D-E*F:
3ra Etapa: Análisis Semántico (AS)::
Toda gramática tiene una sintaxis y una semántica propia. La sintaxis son las reglas que determinan cómo se deben escribir las oraciones en el caso de los lenguajes comunes, y la semántica le da el significado a estas composiciones. El AS es el encargado de interpretar lo que estamos escribiendo, verificando lo siguiente:
- Verificar que las variables han sido declaradas previamente cuando se usan.
- Comprobación de tipos en las expresiones.
- Comprobación de los parámetros de una función. El tipo de los parámetros deben coincidir entre el llamado y la definición.
- Elección de la función u operador en caso de sobrecarga o polimorfismo.
Cuando no se cumple lo anterior, se emiten errores al Gestor de Errores que ya vimos anteriormente. El AS es el encargado de construir el Árbol de Sintaxis Abstracta (ASA), dado el árbol hecho por el Parser.
A la izquierda de la figura hay un árbol de derivación hecho por el Parser y a la derecha un ASA hecho por el Analizador Semántico. Como podemos percibir, el ASA es más específico que el árbol de sintaxis logrado por el Parser, pues adiciona a los nodos del árbol atributos que describen su función y elimina algunos innecesarios.
4ta Etapa: Generación de Código Intermedio::
El código intermedio tiene varios usos. Puede ser un lenguaje de alto nivel diferente (generalmente C), para el cual ya existe un compilador eficiente. Esta solución se aplica comúnmente a lenguajes declarativos como Prolog y Haskell.
La segunda -y de gran importancia en el código intermedio- es que sirve de plataforma para varios lenguajes y diferentes tipos de computadoras. Por ejemplo, si queremos escribir en cinco lenguajes unos programas para correrlos en tres arquitecturas de computadoras diferentes, necesitamos 5*3 compiladores. Si tenemos un código intermedio, necesitamos cinco para llevar cada lenguaje a éste y otros tres para convertirlo en el código de máquina específico. Comparamos 5*3 con 5+3 y quedamos convencidos; ¿se imaginan como sería con todos los lenguajes que soporta .NET (C#, VB, J#, C++, Python...)?
El código intermedio también posibilita el polimorfismo entre lenguajes. La idea es diseñar un carro en Visual Basic y su conductor en C#, pues como ambos terminan en IL (Intermediate Language de .NET) son claramente compatibles.
Existen muchos códigos intermedios, como el Byte Code de Java, el MSIL de Microsoft, o el mismo C. No me propongo definir ninguno en específico, pues creo que nos llevamos la idea de qué se trata. Son independiente de la máquina (hasta cierto punto), no tienen en cuenta características como la arquitectura del procesador, el número de registros del mismo o la funcionalidad de estos. Son lenguajes de alto nivel, pero más orientados a la generación de código máquina.
5ta Etapa: Optimización de Código Intermedio::
Muchos compiladores dividen todo el proceso en Front End y Back End. El primero es la parte que analiza el código fuente, comprueba su validez, genera el árbol de derivación y rellena los valores de la tabla de símbolos. Toda esta parte es independiente a la plataforma para la que se compila. La segunda etapa, Back End, se encarga de generar el código máquina.
A partir de ahora estamos en Back End, trabajando en base a una plataforma específica (puede ser Intel, Mac, o cualquier otra). Idealmente, los compiladores deben producir código objeto tan bueno como el producido a mano por un programador experto. En la realidad, este objetivo raramente es alcanzado. Sin embargo, el código puede ser mejorado en tiempo y espacio usando algoritmos eficientes.
Concluyendo, la idea es mejorar el código objeto final preservando el significado original del programa, realizando sólo optimizaciones seguras. Las optimizaciones están alrededor de mejorar la velocidad de ejecución y disminuir tanto el tamaño del programa como sus necesidades de memoria.
6ta Etapa: Generación de Código Objeto::
Ahora nos toca generar el código ensamblador y tomaremos como ejemplo el de la tecnología i383. En otras palabras, las representaciones intermedias dejarlas a nivel de MOV, ADD y goto.Vamos a ver dos ejemplos solamente y de forma muy abstracta, pues esta etapa es sumamente compleja.
Intermedio:
if <condición>
then <sentencia1>
else <sentencia2>
Ensamblador:
;resultado de condición lo guardo en tmp
if tmp == false goto label_false
<código de sentencia1>
goto label_fin
label_false:
<código de sentencia2>
label_fin:
Intermedio:
A = B+C;
Ensamblador:
MOV ebx, BYTE PTR [B]
MOV ecx, BYTE PTR [C]
ADD ebx,ecx
MOV [A], ebx
Conclusiones::
El código que genera todo el Back End normalmente no se puede ejecutar directamente, sino que necesita ser enlazado por un programa enlazador (ver en referencias: linker). No obstante, ya todo el trabajo duro quedó aquí.
Como pudimos apreciar, compilar es una tarea larga que toma cierto tiempo para el CPU. Pero buenos compiladores nos reducen el margen para futuros errores en tiempo de ejecución y nos optimiza el código; luego vale la pena esperar que hagan su trabajo.
No quiero terminar sin hablar de ANTLR, no es más que una de esas herramientas que nos ayuda en la creación de compiladores. Posee características que lo recomiendan para construir una herramienta procesadora de lenguajes, por ejemplo: a diferencia de otras herramientas, que solamente se encargan de una de las fases del proceso antes mencionadas, ANTLR se encarga del análisis lexicográfico y del sintáctico -además de dejar parte del trabajo hecho para el semántico. Genera código para C++, Java, Phyton y C# y, lo mejor, es independiente de la plataforma.
El proceso completo de compilación quedaría de la siguiente manera:
Black Hat por Email
Black Hat por Feed
No hay comentarios:
Publicar un comentario