• Author / Uploaded
• ProssCardenasAlvarez

Citation preview

Compiladores. Guía 8

1

Facultad: Ingeniería Escuela: Computación Asignatura: Compiladores

Tema: Análisis de código intermedio Contenido En esta guía se abordarán los conceptos pertenecientes al componente de análisis de código intermedio, se analizaran los bloques de básicos de código a partir de un código en cualquier lenguaje previamente indicado. Además se analizara el uso de la notación polaca inversa y el uso de direcciones en ellas.

Objetivos Específicos Conocer las características y principal función de un bloque básico de código. Analizar e interpretar como un compilador ordena los bloques de código para posterior ejecución. Aprender a usar la notación polaca inversa para aplicar su uso en la asignación de memoria para variables.

Material y Equipo Guía de Laboratorio Nº 8. Computadora con programa “Dev C++”.

Introducción Teórica Generación de código intermedio

Guía 3

Representación de bloques básicos Los bloques básicos son trozos de código intermedio en los Guía 4 que el flujo de control es lineal, es decir, trozos de código cuyas instrucciones se ejecutan una detrás de otra sin saltos fía intermedios. Los bloques básicos tienen por tanto una única instrucción de comienzo de bloque y una única instrucción de

2

Compiladores. Guía 8

salida del bloque. Por ejemplo, la siguiente secuencia de instrucciones de tres direcciones forma un bloque básico. (100) (101) (102) (103) (104) (105) (106)

t1:=-c t2:=b*t1 t3:=-c t4:=b*t3 t5:=t2*t4 a :=t5 if(a>0) goto (712)

Para identificar los bloques básicos que componen una secuencia de instrucciones en código máquina puede seguirse el siguiente algoritmo: 1. Buscar los puntos de entrada, que corresponden a: 1. La primera instrucción de código máquina. 2. Cualquier instrucción situada en la dirección a la que se refiere una instrucción de salto condicional o incondicional. 3. Cualquier instrucción consecutiva a una instrucción de salto condicional o incondicional. 2. Para cada punto de entrada construir un bloque básico que vaya desde el punto de entrada hasta el siguiente punto de entrada. 3. Los arcos del diagrama de flujo se obtienen mediante las reglas: 1. Si el bloque básico termina en un salto incondicional, entonces incluir un arco hasta la dirección señalada 2. Si el bloque básico termina en un salto condicional, entonces incluir un arco hasta la dirección señalada y otro al siguiente bloque básico. Una instrucción de tres direcciones del tipo x:= y + z, se dice que define a x y que hace referencia a y (y también a z). Una variable se dice que está activa en un determinado punto de la secuencia de instrucciones de tres direcciones si después de haber sido definida se hace referencia a ella en cualquier otro punto del programa que se ejecute posteriormente, (en el mismo bloque básico o en cualquier otro). Es decir, una variable está activa desde que nace con una definición, hasta que muere con el último uso que de ella hace cualquier instrucción del programa. Por el contrario,

Compiladores. Guía 8 3

una variable esta inactiva, desde la última vez que se usa hasta que se define nuevamente. El concepto de actividad e inactividad de las variables tiene importancia para la asignación de registros que se efectúa durante la generación de código máquina. Ejemplo: Considere el siguiente lenguaje C while (j < n) { k = k + j * 2; m = j * 2; j++; }

fragmento

de

código

en

Este ciclo se traduce en la representación en proposiciones de tres direcciones que se muestra a continuación: (101) (102) (103) (104) (105) (106) (107) (108) (109) (110) (111) (112) (113) (114) (115) (116)

t1 := j t2 := n t3 := t1 < t2 if(t3) goto (105) t4 := k t5 := j t6 := t5 * 2 t7 := t4 + t6 k := t7 t8 := j t9 := t8 * 2 m := t9 t10 := j t11 := t10 + 1 j := t11 goto (101)

En la figura 1, podremos observar el diagrama de bloques básicos correspondiente a este programa. NOTACIÓN POLACA / NOTACIÓN POLACA INVERSA Notación prefija (polaca): Se escribe primero el nombre de la función seguida de los operando de izquierda a derecha. Si un operando es a su vez operación con operando, se aplican las mismas reglas. Por ejemplo: ( a + b ) * ( c – a ) == + a b – c a No hay ambigüedad alguna ni se necesitan paréntesis para saber cómo evaluar la expresión. Debido a que el matemático

4

Compiladores. Guía 8

polaco Lucasiewicz inventó la notación libre de paréntesis, se ha aplicado el término de polaca a esta notación y sus derivados.

Figura 1: Diagrama de bloques básicos Notación postfija (o polaca inversa): Es similar a la notación postfija, excepto que el símbolo de operación sigue a la lista de operando. Por ejemplo: a b + c a - * Notación infija: Es la más adecuada para operaciones binarias. El operador se escribe entre los operando. Por su uso natural, ha sido adoptada por muchos lenguajes para operaciones aritméticas y lógicas. Cuando la operación no es binaria, se usa de manera algo torpe empleando varios delimitadores; por ejemplo el comando condicional en C: (?S1:S2) Tripletes No se pone el resultado, se sustituye por referencias a tripletes. Por ejemplo: la expresión a * b + c * d equivale a:

Compiladores. Guía 8 5

(1) (*,a,b) (2) (*,c,d) (3) (+,(1),(2)) Mientras que a * b + 1 equivale a: (1) (*,a,b) (2) (*,(1),1) Tripletes indirectos: se numeran arbitrariamente los tripletes y se da el orden de ejecución. Solucionan el problema de la reordenación mediante indirecciones. Ejemplo, sean las instrucciones: a = b * c b = b * c Equivalen a los tripletes (1) (*,b,c) (2) (=,(1),a) (3) (=,(1),b) Y el orden de ejecución es (1), (2), (1), (3). Esta forma es útil para preparar la optimización de código. Si hay que alterar el orden de las operaciones o eliminar alguna, es más fácil hacerlo ahí.

Procedimiento Considérese el fragmento de código fuente que se muestra a Guía 3 continuación, el cual calcula el producto punto de dos vectores a y b de longitud 20.

Guía 4

begin prod := 0; fía i := 1; do begin prod := prod + a[i] * b[i]; i := i + 1; end while i