Codigo Interedio

Tipos y Representaciones del Código Intermedio.

Existen muchas formas de código intermedio, de hecho, el diseñador del compilador puede definir la máquina abstracta que considere mas adecuada al lenguaje fuente o a la clase de máquinas a las que va destinado. Las representaciones que más se emplean son:

Árboles semánticos y grafos acíclicos dirigidos

Código de tres direcciones. Cuartetos, Tercetos o Tercetos indirectos.

Existen algunas máquinas abstractas o lenguajes intermedios ya clásicos en generación de código que se han definido para la compilación de lenguajes concretos, como el código P, que se utiliza en la compilación de Pascal, o la máquina de Warren para la compilación del lenguaje Prolog.

Árboles semánticos y grafos acíclicos dirigidos

Una forma de representar el código generado por un compilador es mediante una estructura de tipos arborescente, a la que se denomina árbol semántico a fin de diferenciarlo del árbol sintáctico o árbol del análisis sintáctico que representa la estructura gramatical.

Así, por ejemplo, para la representación de la sentencia: a:=b*-c+b*-c, se tiene:

En el árbol semántico los nodos son ocupados por operadores y sus operandos se obtienen evaluando las operaciones de sus nodos descendientes.

Pueden usarse grafos acíclicos dirigidos (DAG) para obtener una representación condensada de los árboles semánticos. Cuando se encuentran subestructuras idénticas dentro de un mismo árbol basta usar múltiples referencias a la misma subestructura, sin necesidad de duplicar la subestructura repetida. Esta representación consigue por si misma una mejora considerable en el tamaño y la eficiencia del código generado.

Código de tres direcciones

La representación mediante código de tres direcciones se basa en un conjunto de instrucciones capaces de manejar un máximo de tres direcciones de memoria. En general dos de estas direcciones corresponden a los argumentos y la tercera al resultado. Una instrucción de tres direcciones por ejemplo puede consistir en sumar el contenido de dos direcciones y situar el resultado en una tercera dirección, o saltar a una determinada dirección si el valor contenido en una dirección es mayor que el contenido en otra, etc.

instrucción arg1 arg2 resultado

+:= x y z

if.>.goto a b L

Fig 2. Ejemplos de código de tres direcciones

Usando un adecuado conjunto de instrucciones de este tipo, cualquier sentencia o conjunto de sentencias del código fuente, puede traducirse por una secuencia de instrucciones de tres direcciones. Por ejemplo, la sentencia a:=b*(c+d) puede traducirse como la secuencia de instrucciones de tres direcciones:

instr. arg1 arg2 rest.

(100) +:= c d t1

(101) *:= b t1 a

En donde las letras minúsculas representan las direcciones de memoria asociadas a cada una de las variables del programa, y t1 representa una dirección de memoria temporal (auxiliar) que permite realizar los cálculos. Para mayor comodidad se escribe el código auxiliar con la notación infija:

(100) t1 := c + d

(101) a := b * t1

Esta representación es equivalente a la representación mediante árbol semántico o mediante grafo acíclico dirigido que se ha visto anteriormente, siempre que se limite la ramificación del árbol a un máximo de dos descendientes. Para obtener la representación en código de tres direcciones basta con recorrer el árbol ascendentemente de izquierda a derecha y generar una variable temporal para cada nodo intermedio del árbol, resumiendo mediante ella la estructura descendiente. Así, por ejemplo, a partir de los grafos de la figura 1b y 1c, se obtienen las siguientes secuencias de código intermedio:

(100) t1 := - c (100) t1 := - c

(101) t2 := b * t1 (101) t2 := b * t1

(102) t3 := - c (102) t3 := t2 + t2

(103) t4 := b * t3 (103) a := t3

(104) t5 := t2 + t4

(105) a := t5

Fig 3a. Código corresp. fig. 1b Fig 3b. Código corresp. fig. 1c

El conjunto de instrucciones de tres direcciones del código intermedio debe definirse adecuadamente según el lenguaje a compilar, y teniendo en cuenta que cada instrucción del mismo debe convertirse fácilmente en una o varias instrucciones del código máquina. No cabe por tanto definir un lenguaje intermedio universal, pero a título de ejemplo se va a estudiar el tipo

...