Arbol Semantico

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, sinnecesidad 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 direccionescorresponden 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
50
I.S.C. Leonel Vázquez Aguirre
en otra, etc.
instrucción arg1 arg2 resultado
+:= x y zif.>.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 esequivalente 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
51
I.S.C. Leonel Vázquez Aguirre
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 deejemplo se va a estudiar el tipo de instrucciones que pueden usarse:
•Instrucciones de asignación:
directa: a := b
de un operando: a := opunario b
de dos operandos: a := b opbinario c
•Saltos en ejecución:
incondicionales: goto L
condicionales: if a opcond b then goto L
etiquetas: label L
•Definición de parámetros y llamada a procedimientos:
definición de parámetros: param X
llamada:call p, n
Por lo general se usan conjuntamente varias instrucciones de tres direcciones
para realizar la llamada a un procedimiento o función. Primero se definen las variables
que van a usarse como parámetros y luego se transfiere el control mediante una
instrucción de llamada, indicando la dirección del procedimiento y el número de
parámetros.
•Operaciones de direccionamiento indirecto:...