Inicio

Ejemplo 110

Objetivo

Como resumen y refuerzo de lo visto anteriormente, se va a mostrar un ejemplo de cómo sería el proceso de traducción de un programa en un lenguaje básico. Se verá cómo pasa el programa de entrada por las distintas fases y lo que hace cada una de ellas con el mismo.

La entrada a traducir es la siguiente, implementada en un lenguaje ficticio al estilo C.

int x, y;
y = x + (int) 3.14;

Analizador Léxico

Todo empieza con el analizador léxico. Esta fase es la que lee el fichero de entrada carácter a carácter y convierte dicha secuencia de caracteres en tokens, es decir, lexemas junto con su tipo.

En el caso del programa anterior, los tokens que produciría como salida el analizador léxico (con sus lexemas en naranja) son:

Analizador Sintáctico

El analizador sintáctico recibiría la secuencia de tokens anterior e identificaría las estructuras que hay en la misma. Una vez encontradas, las mostraría utilizando un abstract syntax tree (AST). Un AST es la información mínima que se necesita de la entrada para poder ser procesada por el resto de las fases; es la esencia de la entrada.

Por tanto, dados los tokens anteriores, el analizados sintáctico produciría a la salida el siguiente AST:

Analizador Semántico

Una vez creado el AST en la fase anterior, el analizador semántico debe validarlo. Este trabajo recae en las etapas de:

  • Identificación. Que consiste en comprobar que todo símbolo (variable, función, tipo, ...) haya sido definido.
  • Comprobación de Tipos. Que se encarga de comprobar que, en las distintas operaciones, los operandos sean del tipo adecuado.

Es por esta segunda etapa, la de Comprobación de Tipos, por la que el analizador semántico, antes de realizar su trabajo, debe definir los predicados que deben cumplirse (notas de color arena) y las funciones semánticas que asignan valores a los atributos (notas color verde). Esta preparación daría el siguiente AST:

Una vez que ha asociado las funciones y los predicados a los nodos necesarios, el analizador semántico ya recorrería el AST evaluando dichos elementos y, al acabar, produciría a la salida el siguiente resultado:

Los cambios realizados por el analizador semántico han sido:

  • La etapa de Identificación enlazó todas las dos variables con su definición (flechas discontinuas verdes).
  • La etapa de Comprobación de Tipos:
    • Ejecutó las funciones semánticas con las que se dio valor al atributo tipo en cinco nodos (señalados en rojo).
    • Comprobó que se cumplían todos los predicados (las tres marcas ✔), por lo que la entrada es válida.

Por tanto, lo que sale de esta fase es el mismo AST que entro, sólo que con información adicional (los enlaces a las definiciones y los atributos tipo en ciertos nodos).

Generación de Código

Una vez validada la entrada, al fin se puede hacer la fase que realmente hace el trabajo característico de un traductor: la generación de código.

Esta fase se divide en dos etapas principalmente:

  • Gestión de Memoria, en la que se asignan direcciones a las variables.
  • Selección de Instrucciones, en la que se asocian a los nodos del AST plantillas de código que indican qué instrucciones debe generar cada nodo para que, mediante la unión del código generado por todos los nodos, se obtenga el programa de salida completo.

Pero, antes de recorrer el AST para realizar ambas etapas, hay que prepararlas definiendo dos aspectos:

  • Para la etapa de gestión de memoria, hay que definir el tamaño de cada tipo. En este caso, que sólo hay tipo entero, se establecerá que los enteros ocupan 2 bytes.
  • Para la etapa de selección de instrucciones, hay que definir las plantillas de los nodos. En este caso, se definen las plantillas de la imagen siguiente.

Una vez definido todo lo anterior, la fase de generación de código realizaría ambas etapas recorriendo el AST y produciendo a la salida el siguiente resultado:

Los cambios realizados por el generador de código han sido:

  • La etapa de Gestión de Memoria añadió el atributo dirección de memoria a ambas variables (señalado en rojo).
  • La etapa de Selección de Instrucciones, siguiendo las plantillas definidas, generó a la salida el programa que aparece a la derecha de la imagen.

Con esto acabaría el proceso de traducción del fichero de entrada.