Faces de los compiladores

Hoy en día estamos tan acostumbrados a usar compiladores para generar nuestros programas, que nos resulta algo completamente natural y fácil de utiliza, esta simple como escribo mi programa, guardo y le doy ejecutar, ya ni siquiera nos preocupamos por compilar el programa para que esté listo para funcionar, y eso es lo que convierte a los nuevos lenguajes de programación en un éxito. Sin embargo, pocas veces estamos conscientes del proceso de compilación como tal, pocas personas conocen el procesamiento interno y los pasos que debe hacer un compilador antes de entregarnos un programa compilado. Pues bien, durante mi estancia por la universidad tuve la fortuna de que me enseñaran como es que funciona un compilador, las fases y lo más importante, a hacer uno.

Escribir un compilador no es simple, ya que se tiene que realizar en varias fases y cada una de ellas ataca al proceso de compilación desde un ángulo distinto pero relacionado. Pero antes de entrar en materia me gustaría presentarles el compilador que yo desarrolle, al cual bautice con el nombre de Oscar++ (Crean o no batalle mucho pensando en el nombre), el cual es un compilador bastante simple que procesa solo unas cuantas expresiones, que para aquel entonces que estaba apenas en la universidad ya era un gran logro. Les dejo una imagen para que vean un poco de lo que hablo:

Hablare de mi compilador en un siguiente post para no extenderme demasiado, por lo pronto quisiera explicar el funcionamiento de los compiladores…

Como les comenté, los compiladores son procesos complejos debido a que tiene varias fases por las que un programa fuente debe de pasar antes de convertirse en un programa ejecutable, los pasos son los siguiente:

Analizador léxico:

El analizador léxico o lexicográfico (Scanner en inglés) es la primera etapa del proceso de compilación, el cual se encarga de dividir el programa en Tokens, los cuales, según una tabla de símbolos previamente definida por el mismo lenguaje, de esta forma cada token del programa es clasificado según su significado para ser procesados en la segunda etapa del proceso de compilación.

Ejemplo:

Dado un lenguaje, se tiene la siguiente tabla de símbolos:

if = 1

else = 2

startBraket = 3

endBraket = 4

startParent = 5

endParent = 6

variable = 7

Y el siguiente programa:

if(ok){

}else{

}

Cuando el analizador léxico procese el programa empezara a analizar token por token arrojando el tipo de token que encontró, sin importarle el orden en que estos vengan y si realmente tiene sentido. Para este programa el analizador léxico arrojara los siguientes resultados. 1, 5, 7, 6, 3, 4, 2, 3, 4. Dicha salida será el resultado de identificar cada token dentro de la tabla de símbolos. Cabe mencionar dos cosas, si un token no puede ser clasificado dentro de la tabla de símbolos, entonces el proceso termina con error y segundo, es requerido implementar algoritmos de expresiones regulares que sean capaces de identificar correctamente cada token.

Analizador sintáctico:

El analizador sintáctico (Parse en inglés), es la segunda fase del proceso de compilación la toma como entrada la salida el analizador léxico y tiene como finalidad la generación de un Árbol sintáctico abstracto, el cual no es más que una estructura de datos compleja que permite representar de una forma más simple al programa fuente. Los compiladores modernos utilizan estructuras de objetos para representa a un programa, de esta forma existe una clase específica para representa cada posible token de nuestra tabla de símbolos.

Retomando el ejemplo anterior, tendríamos las siguientes clases:

Statement //Representa de forma abstracta cualquier instrucción

IfExp(BoolExp, Statement, Statement) //Exp representaría una expresión boolean, el primer statement representa las instrucciones contenidas en el IF  y el segundo las instrucciones del ELSE

VarExp // Representaría de forma abstract una variable

De tal forma que cada parte del programa es representada como un objeto que a la vez es contenido por uno cada vez más abstracto, hasta llegar a una clase final que representa todo el programa, es por esta razón que se llama Árbol sintáctico abstracto y el cual podría ser representado fácilmente como Árbol. Este tipo de estructuras siguen el patrón de diseño Composición del cual también hablo en mi libro.

Como ya mencioné anteriormente, el analizador léxico solo clasifica los token pero no le interesa el orden ni si tiene coherencia el programa escrito, pero para el analizador sintáctico es todo lo contrario, para el cada token debe de tener un orden y un significado, y si el orden de los tokens no hace sentido con la definición del lenguaje este lo detecta y termina el proceso de compilación con error, por ejemplo, analicemos el siguiente programa:

else{

}if(ok){

}

Podemos apreciar rápidamente que la instrucción if..else  está incorrectamente escrita, pero veamos que pasa… Primero llega el analizador léxico, al cual no le interesa el orden ni el significado de los token, solo le interesa que los token sean válidos según la tabla de símbolos, por lo tanto arrojara la siguiente salida, 2, 3, 4, 1, 5, 7, 6, 3, 4. El analizador léxico terminaría correctamente, pero una vez finalizado este proceso e inicie el analizado sintáctico este si validara que los tokens tenga una coherencia, tomara el primer token, el else , pero al detectar que no está primero el if  , terminar el proceso de inmediato.

Para finalizar este proceso terminaría con Árbol sintáctico abstracto parecido al siguiente:

Program p = new Program(
  new IfExp(
    new BolExp(
      new VarExp("ok")
    ), 
    new Statement(), 
    new Statement())
);

Analizador semántico:

El analizador semántico es el último paso antes de empezar a compilar realmente el código, esta este paso, lo único que hacemos es preparar el programa para ser compilado, pero no nos adelantemos. El analizador semántico parte del árbol sintáctico abstracto y tiene la finalidad de validar los puntos más finos del programa, como por ejemplo, validar compatibilidad en tipos de datos, que la variable utilizada en una instrucción este previamente declara o que estén dentro del contexto, si implementamos una interface que todos los métodos estén definidos, etc, etc.

El analizador semántico es el que analiza que todo el programa tenga un significado exacto y que este no pueda fallar en tiempo de ejecución, analicemos algunos ejemplos:

boolean b = "hola mundo"

El ejemplo anterior estaría correcto para el analizador léxico y sintáctico debido a que es trata de una expresión de asignación y los token son válidos, pero en realidad no tiene sentido asignar un String a un booleano. En tal caso el analizador semántico si sería capaz de detectar esta incoherencia y terminar con error el proceso de compilación.

Gato g = (Perro)o;

El siguiente ejemplo es un Cast del objeto o  a la clase Perro  para después asignarlo a la variable g  la cual es de clase Gato . Suponiendo que no tiene un ancestro en común (herencia), el cast no se podría dar, debido a que fueran tipos incompatibles. Sin embargo, como ya hablamos antes, para el analizador léxico y sintáctico estaría bien aunque no tenga sentido, pero el analizador semántico si es capaz de detectar estas cosas.

Como resumen, esta fase no afecta en lo absoluto al árbol sintáctico abstracto, solo lo válida para poder empezar el proceso de compilación. En este paso es común utilizar patrón de diseño Visitante (Visitor) el cual lo explico en mi libro.

Generación de código intermedio:

Este proceso se caracteriza por generar un código que es posible ejecutar con un intérprete, lo que significa que aún no es código máquina. Esta fase convierte nuestra entrada en instrucciones más compactas y fáciles de ejecutar que el código que escribimos originalmente, estos códigos por lo general son programas de una instrucción por línea y cada línea hace una sola cosa a la vez. Para los que han tenido la fortuna o la desgracia como yo de trabajar con el lenguaje ensamblador entenderán perfectamente a que me refiero, pero para los que no han tenido la experiencia, les dejo un pequeño código en lenguaje ensamblador:

.model small
.stack
.data
   hw   db "Hola mundo", "$"
.code
main  proc             
   mov   ax,seg hw     
   mov   ds,ax          
   mov   ah,09          
   lea   dx,hw         
   int   21h               
   mov   ax,4c00h       
   int   21h            
main  endp              
end main

No te preocupes si no entiendes el código anterior, te resumo que imprime en pantalla Hello Word!!

Pues bien, en resumen, esta fase tiene como entrada el árbol sintáctico abstracto y genera como salida un código más fácil de interpretar.

Optimización del código:

Para algunos lenguajes como Java, esta es la fase final de la compilación y es la etapa en la que se reprocesa el código intermedio para optimizar el programa, es decir, se buscan patrones y repeticiones de código, optimización de operaciones matemáticas como conversión de expresiones infijas a postfijas o prefijas, etc. De esta forma se obtiene un código más ligero en tamaño y algoritmos más eficientes.

Un ejemplo de optimización sería:

x = (2+(3*4));  //Programa original (infija)
x = 2 3 4 * +;  //Programa optimizado (postfija)

Las cadenas posfijas e prefijas crean expresiones matemáticas que no requieren el uso de paréntesis lo que los hace de mucho más rápido en el procesamiento.

Generación de código:

Etapa final de un compilador en la cual se genera como resultado un código máquina que puede ser ejecutado por el procesador sin necesidad de un intérprete, el patrón interprete también lo abordo en mi libro.

Alcance de los compiladores:

Algo a tomar muy en cuenta y que en ocasiones se suele confundir, es que los compiladores tiene como única responsabilidad la generación del código, por lo que la ejecución del programa debe ser abordado por separado; existen compiladores que como salida generan código máquina, en estos casos el programa puede ser ejecutado directamente por el procesador, sin embargo, existe compiladores que generan solamente código intermedio el cual requiere forzosamente el desarrollo de in Interprete el cual ejecute el programa y convierte las instrucciones en código intermedio a instrucciones para el procesador, este es el caso de Java, el cual tiene su compilador javac y aparte tiene el Java Runtime Environment (JRE).

Conclusiones:

Como verás el proceso de compilación tiene un grado de complicación muy alto, ahora bien, no crear que todo lo que vimos aquí se tenga que hacer a mano, existen diversas herramientas que nos pueden ayudar a la generación del analizador léxico, sintáctico y la generación del Árbol sintáctico abstracto como lo son Lex/Yacc, JFlex/Cup y JavaCC.

Por otra parte, si lo que quieres es profundizar más en el arte de los compiladores estas obligado a leer el libro Compiladores Principios Tecnicas Y Herramientas

muy pronto subiré un segundo post donde explico el compilador que desarrollo con su respectivo código fuente, así que regístrate a mi blog para notificarte en cuanto lo publique.