generacion codigo intermedio
DESCRIPTION
teoría para compiladores e interpetesTRANSCRIPT
Generación de Código Intermedio
Análisis y Síntesis de un Compilador
Se pueden construir mxn compiladores con sólo escribir m front-ends y n back-ends.
Formas de representación intermedia
1. Notación posfija2. Árboles sintácticos3. Código de tres direcciones
Modelo de un front-end
Notación posfija
Árbol Sintáctico
Grafo Dirigido Acíclico
Código de tres direcciones
a+a*(b-c)+(b-c)*d
Tipos de Direcciones
Tipos de Instrucciones
Tipos de Instrucciones
Tipos de Instrucciones
Ejemplo Expresión Aritmética
a+a*(b-c)+(b-c)*d
Ejemplo condicional
if (x<100 || x > 200 && x != y) x =0;
Ejemplo Ciclo
do i=i+1; while (a[i] < v);
Representación Código Intermedio
● Cuádruplos
● Triples
● Triples indirectos
Cuádruplos
Ejemplo:a = b * - c + b * - c
Triples
Ejemplo:a = b * - c + b * - c
Cuadruplos vs Triples
Ejemplo:a = b * - c + b * - c
Triples Indirectos
Ejemplo:a = b * - c + b * - c
Ejercicios
Ejercicios
Generacion de Código IncrementalExpresiones Aritméticas
Traducción de ArreglosSi el ancho de cada elemento del arreglo es w entonces el i-ésimo elemento de un arreglo A inicia en la posición
base + i x w
donde base es la dirección relativa de memoria asignada al arreglo, es decir, base es la dirección relativa del elemento A[0]
Traducción de Arreglos
En el caso de dos dimensiones A[i1][i2] representa el elemento i2 en la fila i1.Si w1 es el ancho de una fila y w2 es el ancho de un elemento en una fila, entonces la dirección relativa de A[i1][i2] se puede calcular por la fórmula
base + i1 x w1 + i2 x w2
Traducción de Arreglos
En k dimensiones, la fórmula es
base + i1 x w1 + i2 x w2 + … + ik x wk
donde wj para 1 ≤ j ≤ k, es la generalización de w1 y w2 en la fórmula anterior.
Arreglos: Representación de Tipos
Ejemplo: int [2][3]
Arreglos: Representación de Tipos
Ejemplo: int [2][3]
Traducción de Arreglos
Atributos del no terminal L● L.addr representa un temporal usado para
calcular el desplazamiento● L.array es un apuntador a la entrada del
nombre del arreglo en la tabla de símbolos● L.array.base es la dirección de inicio del
arreglo● L.type es el tipo del subarreglo de L. Para
cualquier tipo de dato t, se asume que su ancho está dado por t.width y el tipo de cada elemento está dado por t.elem
Arreglos: Tamaño de Tipos
Ejemplo: int [2][3]
t=array(2,array(3,integer))t.width = 24t.elem = array(3,integer)t.elem.width = 12t.elem.elem = integert.elem.elem.width = 4
Traducción de Arreglos
Traducción de Arreglos
Traducción de Arreglos
Ejemplo: c+a[i][j]
Traducción de Arreglos
Ejercicios
Generacion de Código IncrementalExpresiones Booleanas
Generacion de Código IncrementalExpresiones Booleanas
Ejemplo Expresiones Booleanas
x < 100 || x > 200 && x != y
Generacion de Código IncrementalCondicionales y Ciclos
Generacion de Código IncrementalBloques de Sentencias
Ejercicio Backpatch (1)¿Cual el valor (i1 a i8) aplica el backpatch en las siguientes listas?
Ejercicio Backpatch (2)
S4
S5
S6
S7
S8
Calcular las siguientes listas en función de las listas anteriores
Funciones y procedimientos
1) param x (paso de parámetros)2) call p, n (llamadas a procedimientos)3) y = call p, n (llamadas a funciones)donde: p es el nombre del procedimiento/función n indica el número de parámetros actuales 4) return y (regreso de funciones)5) return (regreso de procedimientos)
Llamada a una función
La llamada a la función:p(x1, x2, … ,xn)
Genera el siguiente código de tres direcciones:param x1param x2… param xny = call p, n
Ejemplo (1) definición función suma
…
100 t1 = $1 + $2
101 return t1
…
Nombre Tipo Dirección
…
suma FUNC 100
…
Tabla de SímbolosDurante la definición de una función/procedimiento● se agrega su nombre en la tabla de símbolos● se agrega su tipo (FUNC/PROC)● se guarda su dirección de inicio
Definición
func suma(){ return $1 + $2}
Código de tres direcciones
Ejemplo (1) llamada a función suma
Llamada
a = suma(b, c);
…
200 param b
201 param c
202 t1 = call suma, 2
203 a = t1
…
Código de tres direcciones
¿Cual será el código de la siguiente llamada?
w = suma( x*2, suma(y, z/4) );
Ejemplo (2) definición func factorialCódigo fuente Código de tres direcciones
func factorial()
{
if ($1 <= 0)
return 1
else
return $1 * factorial($1 - 1)
}
100 if $1 <= 0 goto 102
101 goto 103
102 return 1
103 goto 109
104 t1 = $1 - 1
105 param t1
106 t2 = call factorial, 1
107 t3 = $1 * t2
108 return t3
109 endf
Ejemplo (2) llamada función factorial
x = factorial(a-b)
Genera el códigot1 = a - b
param t1
t2 = call factorial, 1
x = t2
Reglas gramaticales para funciones/procedimientos
D → func id ( ) { S }
Definición de una función
D → proc id ( ) { S }
Definición de un procedimiento
S → return E Regreso de una función
S → return Regreso de un procedimiento
E → id ( P ) Llamada a una función
S → id ( P ) ; Llamada a un procedimiento
P → P , E Paso de dos o más parámetros
P → E Paso de un parámetro
¿Paso de cero parámetros?
Ejercicio Funciones/Procedimientos
Elaborar un esquema de traducción para generar el código de tres direcciones para funciones y procedimientos.
Ejemplo Ordenación Burbuja
Ejemplo (3) función JuanitoCódigo fuente Código de tres direcciones
func juanito(){ if ($1 == 0 || $1 == 1) return $1 else return juanito($1 - 1) + juanito($1 - 2)}
if $1 == 0 goto L1goto L2L2:if $1 == 1 goto L1goto L3L1:return $1goto L4L3:t1 = $1 - 1param t1t2 = call juanito, 1t3 = $1 - 2param t3t4 = call juanito, 1t5 = t2 + t4return t5L4:
Ejemplo (4) fórmula de Stirling
func stirling(){ return sqrt(2*PI*$1)*($1/E)^$1+$1*(1+1/(12*$1))}
t1 = 2 * PIt2 = t1 * $1t3 = call sqrt, 1t4 = $1 / Et5 = t4 ^ $1t6 = t3 * t5t7 = 12 * $1t8 = 1 / t7t9 = 1 + t8t10 = t6 * t9return t10
Ejemplo (5) función mcdCódigo fuente Código de tres direcciones
func mcd(){ if ($2 <= $1 && $1 % $2 == 0) return $2 else if ($1 < $2) return mcd($2, $1) else return mcd($2, $1 % $2)}
if $2 <= $1 goto L1goto L3t1 = $1 % $2L1: if t1 == 0 goto L2goto L3L2: return $2goto L5L3: if $1 < $2 goto L4goto L5:L4: param $2param $1t2 = call mcd, 2return t2goto L5L5: param $2t3 = $1 % $2param t3t4 = call mcd, 2return t4L5:
Ejemplo (6) función ackfunc main()
{
do
{
read m;
read n;
val = ack(m,n);
print val;
} while ( m!=0 || n!=0 );
}
func ack()
{
if ($1 == 0) return $2+1;
else if ($1 > 0 && $2 == 0) return ack($1-1, 1);
else if ($1 > 0 && $2 > 0) return ack($1-1, ack($1, $2-1));
}