Compiladores

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
Guíabloques
4 básicos son trozos de código intermedio en los
que el flujo de control es lineal, es decir, trozos de código
cuyas instrucciones se ejecutan una detrás de otra sin saltos
intermedios.
fía 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) t1:=-c
(101) t2:=b*t1
(102) t3:=-c
(103) t4:=b*t3
(104) t5:=t2*t4
(105) a :=t5
(106) 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 fragmento de código en

lenguaje C
while (j < n) {
k = k + j * 2;
m = j * 2;
j++;
}
Este ciclo se traduce en la representación en proposiciones

de tres direcciones que se muestra a continuación:
(101) t1 := j
(102) t2 := n
(103) t3 := t1 < t2
(104) if(t3) goto (105)
(105) t4 := k
(106) t5 := j
(107) t6 := t5 * 2
(108) t7 := t4 + t6
(109) k := t7
(110) t8 := j
(111) t9 := t8 * 2
(112) m := t9
(113) t10 := j
(114) t11 := t10 + 1
(115) j := t11
(116) 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
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:
(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 <= 20
end
El código de tres direcciones para este algoritmo es:
(1) prod := 0
(2) i := 1
(3) t1 := 4 * i
(4) t2 := a [ t1 ] //calcula a[i]
(5) t3 := 4 * i
(6) t4 := b [ t3 ] //calcula b[i]
(7) t5 := t2 * t4
(8) t6 := prod + t5
(9) prod := t6
(10) t7 := i + 1
(11) i := t7
(12) if i <= 20 goto (3)
Dibuje el diagrama de bloques básicos para las proposiciones

de tres direcciones según las reglas indicadas en la
introducción teórica de esta guía.
Ahora escriba las proposiciones de tres direcciones y dibuje

el diagrama de bloques básicos para la generación de código
intermedio para las siguientes instrucciones:
int i=0;
int a[10];
while(i<=10)
a[i]=0;
Usando los conceptos de notación polaca y tripletas, re-

escriba las instrucciones en forma de tripletas.
Fuente:
w*x+(y+z)
Operaciones:
1. ___________________________________________________
2. ___________________________________________________
3. ___________________________________________________
Usando los conceptos de notación polaca y tripletas, re-

escriba las instrucciones en forma de tripletas indirectas.
Fuente:
A = B + C * D / E
F = C * D
Operaciones:
1. ___________________________________________________
2. ___________________________________________________
3. ___________________________________________________
4. ___________________________________________________
5. ___________________________________________________
Análisis de resultados
Escriba las proposiciones de tres direcciones y dibuje el
diagrama de bloques básicos para la generación de código
intermedio para el siguiente pseudocódigo del algoritmo de
burbuja:
for (i=1; i<TAM; i++)

for j=0 ; j<TAM - 1; j++)
if (lista[j] > lista[j+1])
temp = lista[j]
lista[j] = lista[j+1];
lista[j+1] = temp;
Traduzca las siguientes expresiones aritméticas a notación

polaca y re-escriba las expresiones en forma de tripletas.
X = (A * B) + (C – (D + E))
X = A/ (B + C) – D*(E + F)
X = A + (B + (C/D) * E) / (F * G – H * I)
Investigación complementaria
Investigue:
Que es un árbol en CoSeL y para qué sirve.
Que es, a partir de que se realiza y cual es el
resultado que se obtiene de la etapa de “Generación de
código” de un compilador.
Como se realiza la generación de código utilizando las
bibliotecas desarrolladas con lenguajes de alto nivel.
Bibliografía
Ejemplo de bloques básicos de código intermedio:

http://cnx.org/content/m38394/latest/?collection=col1
1356/latest
Estructura de datos, Luís Joyanes Aguilar, McGrawhill
Compiladores- principios, técnicas y herramientas. Aho -

Lam – Sethi – Ullman. Editorial Pearson – Addison Wesley
Segunda edición
Construcción de compiladores. Kenneth C. Louden.

Editorial Thomson
Guía 8: Análisis de código Hoja de cotejo: 8

intermedio
Docente: 1
Tema: Presentación
Alumno: del programa Máquina No:
Máquina No:
Alumno:
GL:
GL:
Máquina No:
Docente: Fecha:
a
Docente: GL:
EVALUACION
% 1-4 5-7 8-10 Nota
CONOCIMIENTO Del 20 Conocimie Conocimiento Conocimiento

al 30% nto y explicación completo y
deficient incompleta de explicación
e de los los clara de los
fundament fundamentos fundamentos
os teóricos teóricos
teóricos
APLICACIÓN Del 40%

DEL al 60%
CONOCIMIENTO
ACTITUD
Del 15% No tiene Actitud Tiene actitud
al 30% actitud propositiva y proactiva y sus
proactiva con propuestas son
. propuestas no concretas.
aplicables al
contenido de
la guía.
TOTAL 100%

Compiladores

Cargado por

Copyright:

Formatos disponibles

Compiladores

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Compiladores

Cargado por

Copyright:

Formatos disponibles

Compiladores.

Tema: Análisis de código intermedio

Conocer las características y principal función de un

Generación de código intermedio

Para identificar los bloques básicos que componen una

Una instrucción de tres direcciones del tipo x:= y + z, se

Una variable se dice que está activa en un determinado punto

una variable esta inactiva, desde la última vez que se usa

El concepto de actividad e inactividad de las variables tiene

Ejemplo: Considere el siguiente fragmento de código en

Este ciclo se traduce en la representación en proposiciones

En la figura 1, podremos observar el diagrama de bloques

NOTACIÓN POLACA / NOTACIÓN POLACA INVERSA

No hay ambigüedad alguna ni se necesitan paréntesis para

Figura 1: Diagrama de bloques básicos

Notación postfija (o polaca inversa): Es similar a la

Tripletes indirectos: se numeran arbitrariamente los

Equivalen a los tripletes

Y el orden de ejecución es (1), (2), (1), (3). Esta forma es

Considérese el fragmento de código fuente que se muestra a

El código de tres direcciones para este algoritmo es:

Dibuje el diagrama de bloques básicos para las proposiciones

Ahora escriba las proposiciones de tres direcciones y dibuje

Usando los conceptos de notación polaca y tripletas, re-

Usando los conceptos de notación polaca y tripletas, re-

for (i=1; i<TAM; i++)

Traduzca las siguientes expresiones aritméticas a notación

Ejemplo de bloques básicos de código intermedio:

Estructura de datos, Luís Joyanes Aguilar, McGrawhill

Compiladores- principios, técnicas y herramientas. Aho -

Construcción de compiladores. Kenneth C. Louden.

Guía 8: Análisis de código Hoja de cotejo: 8

% 1-4 5-7 8-10 Nota

CONOCIMIENTO Del 20 Conocimie Conocimiento Conocimiento

APLICACIÓN Del 40%

También podría gustarte