CURSO:
PROGRAMACION DE
SISTEMAS
ELEMENTOS DEL CURSO





Programa del Curso..... PDF
Datos del Profesor …. RZC
Contenido del Curso…. Diaps
Proyectos …. Archs
Software y Herramientas
Unidad I
Introducción a la Programación
de Sistemas
1.1 ¿Qué es y que estudia la P. de S. ?

Son los programas que residen en un
sistema de computación. Su función es
proporcionar al usuario o programador una
interfase mas eficiente y practica con relación
al hardware de la maquina.
La P. de S. estudia como están
implementados cada uno de los programas
de un Sistema (ver notas).
1.2 Herramientas desarrolladas
con la P de S
Ejemplos:







Compiladores (javac)
Ensambladores (Masm)
Interpretes (Visual Basic)
Ligadores (Link)
Cargadores
Sistema Operativo (Windows)
Utilerías de Sistemas (Debugger)
1.3 Lenguajes


Naturales (Traductores de Ingles-Español,
Ingles-Ruso, etc)
Artificiales (Compiladores de LP como Java,
C++, Ada, etc.)
1.4 Traductor y su Estructura

Ensambladores ….
(notas)

Compiladores…….
(notas)

Intérpretes……......
(notas)
1.5 Generador de Código para Compiladores
(Compilador de Compiladores)

Definición: Un compilador de compiladores o generador de
Parsers es una utilería para generar el código fuente de un
parser, intérprete o compilador a partir de una descripción de
lenguaje anotado en la forma de gramática (usualmente BNF)
mas código que es asociado con cada una de las reglas de la
gramática que debe ser ejecutada cuándo esas reglas sean
aplicadas por el parser. Esas piezas de código son algunas
veces llamadas rutinas de acciones semánticas ya que ellas
definen la semántica de las estructura sintáctica y que es
analizada por el parser. Dependiendo del tipo de parser que será
generado, las rutinas pueden construir un árbol de parsing (o
AST) o generar código ejecutable directamente (notas).
Unidad II
Introducción al Diseño de
Lenguajes de Programación





Visión del Problema.
Consideraciones Preliminares.
Objetivos y filosofías del diseño de los
lenguajes de programación.
Diseño detallado.
Caso de estudio.
Unidad III
Análisis de Léxico
3.1 Introducción a los Autómatas Finitos
y Expresiones Regulares

(ver apuntes de Lenguajes y Autómatas).
3.2 Analizador de Léxico.

Descompone la entrada en palabras individuales llamadas “tokens”. El
analizador de léxico (scanner) toma una cadena de caracteres que
forman la entrada y produce una cadena de nombres o identificadores,
palabras claves o reservadas (PC) signos o marcas de puntuación,
operadores aritméticos y lógicos, constantes (números, cadenas, etc.)
y otros. También el scanner tiene como función desechar espacios en
blanco y comentarios entre los tokens, otra función podría ser crear la
tabla de símbolos.
Ejemplo:
TIPO
ID
NUM
REAL
IF
COMMA
NOTEQ !=
LPAREN
EJEMPLOS
foo n14 last
73 0 00 515
66.1 .5 10. 1e67
if
,
(
Analizador de Léxico (cont.)
Tokens de puntuación como IF, VOID y
RETURN son llamadas palabras reservadas
y en la mayoría de los lenguajes no pueden
usarse como identificadores.
3.3 Manejo de “Buffers”

El analizador de léxico (scanner) y el analizador de
sintáxis (parser) forman un duo “productorconsumidor”. El scanner produce tokens y el parser
los consume.
La implementación de la lectura de los caracteres
de la entrada (disco) es usualmente hecha por un
buffer (memoria) que contendrá una buena parte de
la entrada, desde donde el scanner irá formando los
tokens. Esto agiliza la entrada que de otra forma
leería carácter por carácter desde el disco.
3.4 Creación de la Tabla de
Símbolos.

Checar notas
La tabla de símbolos es una estructura de datos
muy importante en casi todo el proceso de
compilación. En ella se guarda durante las primeras
fases de compilación los nombres de los
identificadores (símbolos) usados en el programa
fuente, además de los atributos de cada uno de
estos identificadores. Estos identificadores y
símbolos junto con sus atributos serán usados
posteriormente para realizar funciones como el
chequeo de tipos, la asignación de memoria,
generación de código objeto etc.
Ejemplo
Ejemplo.Programa X1;
Var X, Y: Integer;
Z: Real;
Arreglo: Array [1…100] of int
Procedure compara (a, b: Integer)
Var n, m: integer;
Begin
------End
Begin
------End
3.5 Manejo de Errores de Léxico

Errores posibles detectados en el análisis de
léxico son:



Patrones de tokens que no coincidan con algún
patrón válido. Por ejemplo el token #### sería
inválido en algunos L.P.
Caracteres inválidos para el alfabeto del el
lenguaje.
Longitud de ciertos tokens demasiado larga.
3.6 Generadores de Código
Léxico



La construcción de un scanner puede
automatizarse por medio de un generador de
analizadores de léxico.
El primer programa de este tipo que se hizo
popular fue Lex (Lesk, 1975) que generaba
un scanner en lenguaje C.
Hoy en día existen muchos programas de
este tipo: Flex, Zlex, YooLex, JavaCC,
SableCC, etc.
Ejemplo: Javacc



Javacc (Java Compiler Compiler) es un generador
de scanners y parsers (https://javacc.dev.java.net/).
Toma como entrada especificaciones de léxico
(expresiones regulares) y sintáxis (gramática de
contexto libre) y produce como salida un analizador
de léxico y un parser recursivo decendente.
Se puede usar como pre-procesador de Javacc, a
jjtree y a JTB para la construcción del árbol
sintáctico.
(cont.)
USO DE JAVACC
Miparser.jj
javacc Miparser.jj
Miparser.java
ParseException.java
TokenMgrError.java
otros archivos java
javac Miparser.java
Miparser.class
java Miparser <inputfile
mensajes
(cont.)
EJEMPLO DE ESPECIFICACION PARA GENERAR UN SCANNER
PARSER_BEGIN(PS1)
class PS1 {}
PARSER_END(PS1)
/* Para la expresión regular de la derecha lo de la izquierda será retornado */
TOKEN: {
<IF: "if">
|<#DIGIT: ["0"-"9"]>
|<ID: ["a"-"z"] (["a"-"z"]|<DIGIT>)*>
|<NUM: (<DIGIT>)+>
|<REAL: ((<DIGIT>)+ "." (<DIGIT>)*) |
((<DIGIT>)* "." (<DIGIT>)+)>
}
SKIP: {
<"--" (["a" - "z"])* ("\n" | "\r" | "\r\n")>
|" "
|"\t"
|"\n"
|"\r"
}
void Start():
{}
{
(<IF> | <ID> | <NUM> | <REAL>)* }
Unidad IV
Análisis de Sintáxis
4.1 Introducción a las gramáticas
Libres de Contexto y Árboles de
derivación

El tipo de gramáticas usadas en los LP son llamadas gramáticas de contexto libre, las cuáles,
junto con árboles de derivación, fueron estudiadas en el curso de Lenguajes y Autómatas.

Un ejemplo de una gramática para un LP simple es la siguiente:
1) SS;S
4) E id
8) L E


2) Sid := E
5) E num
9) L L , E
3) Sprint (L)
6) E E + E
7) E(S,E)
(ver ejemplo de derivaciones y árboles de parsing)
A continuación veremos un ejemplo de una gramática para Java en formato BNF (liga).
(cont.)

Gramática Ambigua. Una gramática es ambigua si
puede derivar una oración (cadena) con dos
diferentes árboles de parsing. La sig. Gramática es
ambigüa:
Eid
Enum
EE+E
EE*E
EE-E
EE/E
E(E)
ya que tiene dos árboles de parsing para la misma
oración (árboles para id:=id+id+id con primera
gramática y árboles para 1-2-3 con segunda en sig
“slice”).
(cont.)
S
S
Id
:=
E
E
Id
+
E
+
E
id
E
id
Id
:=
E
E
+
E
id
E
+
id
E
id
(cont.)
E
E
1
E
-
E
-
E
3
2
E
E
-
E
1
E
-
2
E
3
4.2 Diagramas de Sintaxis

Un método alternativo al BNF para desplegar
las producciones de ciertas gramáticas es el
diagrama de sintaxis. Ésta es una imagen
de la producciones que permite al usuario ver
las sustituciones en forma dinámica, es decir,
verlas como un movimiento a través del
diagrama.
Ejemplo en Java (liga)
4.3 Precedencia de Operadores

En los dos ejemplos vistos en sección 4.1, los dos
árboles de parsing para 1-2-3 significaba diferentes
cosas: (1-2)-3=-4 versus 1-(2-3)=2. Similarmente,
(1+2)x3 no es lo mismo que 1+(2x3). Es por eso
que gramáticas ambiguas son problemáticas para
un compilador. Afortunadamente, una gramática
ambigua puede convertirse en una no ambigua. Por
ejemplo, si queremos encontrar una gramática no
ambigua para el lenguaje de la segunda gramática
de sección 4.1, lo podemos hacer por medio de dos
operaciones: primero, aplicar orden de precedencia
a los operadores y segundo aplicar asociatividad
por la izquierda. Con esto, tenemos la sig.
gramática:
(cont.)
SE$
EE+T
T-->T*F
Fid
nota: “$” es EOF- marker
EE-T
TT/F
Fnum
ET
TF
F(E)
Esta gramática acepta el mismo lenguaje que la
de sección 4.1 pero solo produce un árbol de
parsing por oración. Esta gramática no podría producir
árboles como los siguientes:
X
+
?U
?Y
?V
+
+
*
4.4 Analizador Sintáctico




En esta fase se analiza la estructura de la frase del programa.
El parser es el programa que funciona como núcleo del compilador.
Alrededor del parser funcionan los demás programas como el scanner, el
analizador semántico y el generador de código intermedio. De hecho se
podría decir que el parser comienza el proceso de compilación y su primer
tarea es pedir al escáner que envíe los tokens necesarios para llevar a
cabo el análisis sintáctico, del estatuto, expresión o declaración dentro de
un programa.
También el parser llama rutinas del análisis semántico para revisar si el
significado del programa es el correcto.
Por ultimo el parser genera código intermedio para los estatutos y
expresiones si no se encontraron errores en ellos.
(cont.)
Existen diferentes técnicas o métodos para realizar un análisis
sintáctico “Parsing”. Estas técnicas se dividen en dos tipos:


Descendentes
Ascendentes
Las técnicas descendentes realizan su análisis partiendo desde el
símbolo inicial de la gramática y realizando derivaciones hasta
llegar a producir las hojas o tokens.
Por otra parte las técnicas ascendentes realizan su análisis
partiendo de las hojas o tokens y mediante una serie de
operaciones llamadas reducciones terminan en la raíz o símbolo
inicial de la gramática.
Por lo general las técnicas descendentes son mas sencillas de
implementar que las ascendentes, pero por otra parte son menos
eficientes
4.4.1 Analizador descendente (LL).
Parsing Predictivo
 Algunas gramáticas son sencillas de analizarse sintácticamente
usando un algoritmo o método cuyo nombre es recursivo
descendente. En esta técnica cada producción de la gramática
se convierte en una cláusula de una función recursiva.
 Un parser Predictivo es aquel que “ predice ” que camino tomar
al estar realizando el análisis sintáctico. Esto quiere decir que el
parser nunca regresara a tomar otra decisión ( back tracking )
para irse por otro camino, como sucede en las derivaciones.
Para poder contar con un parser predictivo la gramática debe de
tener ciertas características, entre ellas la mas importante es que
el primer símbolo de la parte derecha de cada producción le
proporcione suficiente información al parser para que este
escoja cual producción usar. Normalmente el primer símbolo
mencionado es un Terminal o token.
(cont.)

Esta técnica se utilizó o popularizó en los años 70 a partir del
primer compilador de pascal implementado con ella. A
continuación ilustraremos esto escribiendo un parser recursivo
descendente para la siguiente gramática:
S  if E then S else S
S begin S L
S print E
L end
L ; S L
E num = num
Nuestro Parser tendría 3 métodos (uno por cada producción)
Programa del Parser
Final int if = 1, then = 2, else = 3, begin = 4, end = 5, print = 6, semi = 7,
num = 8, EQ = 9
int tok = get token ( );
void advance ( ) { tok = get token ( ); }
void eat ( int t) { if ( tok == 1) advance ( ); else error ( ); }
void S ( ) { switch ( tok ) {
case If: eat ( if ); E ( ); eat ( then ); S ( );
eat ( else ); S ( ); break;
case begin: eat ( begin ); S ( ); L ( ); break;
case print: eat ( print ); E ( ); break;
default: error;
}}
void L ( ) { switch ( tok ) {
case end: eat ( end ); break;
case semi: eat ( semi ); S ( ); L ( ); break;
default: error ( );
}}
void E ( ) { eat ( num ); eat ( EQ ); eat ( num ); }
(cont.)



Un parser predictivo que examina la entrada de izquierda a
derecha (left-to-right) en un paso y realiza su derivación por la
izquierda es llamado “Parser LL”.
Cuando el parser solo necesita “mirar” el siguiente token para
hacer su función (llokahead(1)), recibe el nombre de Parser
LL(1).
Un parser podría necesitar “mirar” K tokens por adelantado para
tomar desiciones. En este caso recibe el nombre de parser
LL(K).
Ejemplo: (parte de una gramática)
IF-STM  if EXP then STM else STM
|  if EXP then STM
Eliminación de Recursión por la izquierda

Suponer que queremos construír un Parser
predictivo para la gramática de sección 4.3.
SE$
EE+T
EE-T
T-->T*F
Fid
TT/F
Fnum
TF
F(E)
ET
Producciones como E  E + T contienen recursión por la izquierda.
Parsers descendentes no pueden manejar recursión por la izquierda
en una gramática. Para eliminar este tipo de recursión utilizamos la
siguiente transformación:
(cont.)
En general, si tenemos producciones X  X g
y X  a, donde a no comience con X
podemos aplicar la siguiente transformación:
X  Xg1
X  Xg2
X  a1
X  a2
X  a1X’
X  a2X’
X’  g1X’
X’  g2X’
X’  l
(cont.)

Aplicando la transformación a la gramática anterior,
obtenemos la nueva equivalente gramática (sin
recursión por la izquierda):
S  E$
E  T E’
T  F T’
F  id
E’  + T E’
T’  * F T’
F  num
E’  - T E’
T’  / F T’
F  (E)
E’  l
T’  l
Factorización por la izquierda

Otro problema en una gramática ocurre cuando dos producciones
para el mismo no terminal comienza con el mismo símbolo. Por
ejemplo:
IF-STM  if EXP then STM else STM
IF-STM  if EXP then STM
En dicho caso podemos factorizar por la izquierda la gramática. El
resultado sería el sig:
IF-STM  if EXP then STM X
X l
X  else IF-STM
las producciones anteriores facilitarán el trabajo del parser
predictivo.
4.4.2 Analizador ascendente(LR y
LALR).



La debilidad de las técnicas descendentes LL(k) es que
deben predecir que producciones usar, después de
haber mirado los primeros k tokens de la cadena de
entrada.
Una técnica ascendente mas poderosa es la técnica
LR(K), la cual pospone la decisión hasta que ha visto
los tokens de la entrada correspondientes a la parte
derecha de la producción (además de k mas tokens
también).
LR(K) quiere decir parser de izquierda a derecha,
derivación por la derecha y “lookahead(k)”. Esta
técnica fue introducida por primera vez en 1965 por
Knuth.
(cont.)

Un Parser LR(K) está compuesto de:




La cadena de entrada
Una pila
Una tabla de Parsing LR
El parser obtiene los tokens de la entrada y
dependiendo de el token actual y de lo que
está en el tope de la pila, ejecuta una de dos
acciones (shift-reduce) con la ayuda de la
tabla de parsing
Algoritmo de Parsing LR (aho,Sethi y Ullman)
Tomar el primer token de w$
/* w es la cadena */
Repeat forever begin
Sea s el estado en el tope de la pila y a el token actual;
if acción[s,a] = shift s’ then begin
push a’ primero y sedpués s’ al tope de la pila;
obten el siguiente token de la cadena de entrada
else if acción[s,a] = reduce A->B then begin
pop 2*|B| símbolos fuera de la pila;
Sea s’ ahora el estado en el tope de la pila;
Push A y después goto[s’,A] al tope de la pila;
Imprime la producción A->B
end
else if acción[s,a] = accept then
return
else error()
end
Ejemplo: Parser LR(K)
TABLA DE PARSING
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
id
S4
num
print
s7
;
,
+
:=
(
)
s3
S4
$
S
g2
E
L
a
s7
g5
s6
r1
S20
s8
s9
g12
s10
g15
r5
r2
s18
r3
s19
r8
r5
s16
r5
r5
r2
r3
s13
r8
s10
s8
r6
S20
S20
g11
s7
r5
r2
s3
r3
S20
r1
s10
S4
S20
r1
r6
s16
s10
s10
g17
r6
r6
s8
s8
r4
r4
r4
r7
r7
r9
r7
s16
g21
g23
r4
s22
r7
r9
r4
r7
g14
Ejemplo (cont.):
PILA
1
1 id4
1 id4 := 6
ENTRADA
ACCION
a:=7;B:=c+(d:=5+6,d)$
shift
:= 7;B:=c+(d:=5+6,d)$
7;B:=c+(d:=5+6,d)$
shift
shift
1 id4 := 6 num10
;B:=c+(d:=5+6,d)$
reduce
E->num
1 id4 := 6 E11
;B:=c+(d:=5+6,d)$
reduce
S->id:=E
.
.
.
.
.
.
.
1 S2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
$
accept
Parsing LALR





La técnica de parsing LALR (LookAhead-LR) evita el uso
de tablas muy grandes, como las manejadas en la
técnica de parsing LR.
Esta técnica fue inventada por DeRemer en 1971.
Casi cualquier construcción sináctica de un LP puede
ser expresado de manera conveniente por una
gramática LALR.
Generadores de Parsers famosos como YACC (Yet
Another Compiler-Compiler-Johnson) producen un
parser LALR.
Para una gramática de un LP como Pascal una tabla de
parsing LALR ocuparía varios cientos de estados,
mientras que una tabla LR serían miles de estados.
4.5 Administración de tablas de
símbolos.



Como se estudió en la unidad anterior,
durante el análisis de léxico se inicia la
construcción de la tabla de símbolos.
Esto ocurre al detectarse las declaraciones
en el programa fuente.
Sin embargo también el parser ayuda a
realizar esta tarea pues el es quien llama a
las respectivas rutinas semánticas para que
realicen funciones relacionada con la tabla
de símbolos (ver figura).
4.6 Manejo de errores sintácticos y su
recuperación.



Dentro del código del parser predictivo estudiado en
clase se puede observar que el parser llama un
metodo “error” para el manejo de errores
sintácticos, que es cuando el parser obtiene un
token no esperado.
¿Cómo se maneja el error para esta clase de
parsers? Una forma simple es ejecutar una
excepción y parar la compilación. Esto como que no
es muy amigable par el usuario.
La mejor técnica es desplegar un mensaje de error
y recuperarse de este, para que otros posibles
errores sintácticos puedan ser encontrados en la
misma compilación.
(cont.)



Un error sintáctico ocurre cuando la cadena de
tokens de entrada no es una oración en el lenguaje.
La recuperación del error es una forma de encontrar
alguna oración correcta, similar a la cadena de
tokens.
Esto se puede realizar por medio de borrar,
reemplazar o insertar tokens.
Por ejemplo la recuperación de un error en S,
podría ser al insertar un token if,begin o print (o
pretender que existe en la cadena), desplegar el
mensaje del error y continuar la compilación.
Ejemplo:
void S ( ) { switch ( tok ) {
case If: eat ( if ); E ( ); eat ( then ); S ( );
eat ( else ); S ( ); break;
case begin: eat ( begin ); S ( ); L ( ); break;
case print: eat ( print ); E ( ); break;
default: print(“se esperaba if, begin o print”);
}}
Un problema que puede ocurrir al insertar un token faltante es que el programa
caiga en un ciclo infinito, por eso a veces es preferible y mas seguro borrar el
token, ya que el ciclo terminará cuando el EOF sea encontrado. Esta técnica
trabaja muy cercanamente con la tabla de parsing (cuando el parser se
implementa con tablas).
En un parser del tipo LR o LALR, la tabla de parsing tiene 4 acciones: shift,
reduce, accept y error (entrada nula). Cuando el parser encuentra una acción
error, se para el proceso de análisis y se reporta la falla.
4.7 Generadores de código para
analizadores sintácticos




Como se vio al final del capítulo 3, Javacc es un generador
de scanners y de parsers (https://javacc.dev.java.net/).
Javacc produce un parser del tipo descendente (recursivo) o
LL(k) donde k (lookahead) puede ser cualquier número entero
positivo.
El parser producido puede correr en cualquier plataforma que
cuente con el compilador de Java.
En el ejemplo siguiente del uso de Javacc, utilizamos de
nuevo la gramática presentada anteriormente (sección 4.4.1)
para un parser predictivo. Ejecutamos Javacc con la anterior
gramática y obtendremos un parser recursivo descendente
para dicha gramática.
Ejemplo: gramática para estatutos
“begin”, “if” y “print”
PARSER_BEGIN(MiniParser)
public class MiniParser {
public static void main(String[] args) {
MiniParser parser;
try {
// RGC: added line
if( args.length == 0 )
parser = new MiniParser(System.in);
// RGC: added lines
else
parser= new MiniParser
( new java.io.FileInputStream( args[0] ) );
}
// RGC: End
parser.Program();
} catch (ParseException e) {
System.out.println(e.getMessage());
}
//RGC: added lines
catch( Exception e ) {
System.out.println(e.getMessage());
} //RGC :End
}
}
PARSER_END(MiniParser)
SKIP : {
|
|
|
}
""
"\t"
"\n"
"\r"
(cont. Ejemplo)
TOKEN : {
|
|
|
|
|
|
|
|
|
}
<INT: "INT">
<IF: "if">
<THEN: "then">
<ELSE: "else">
<BEGIN: "begin">
<PRINT: "print">
<END: "end">
<SEMI: ";">
<EQUAL: "=">
<ID: (["a"-"z"]|["A"-"Z"]) (["a"-"z"]|["A"-"Z"]|["0"-"9"])* >
void Program() :
{}
{ S() <EOF> }
void S() :
{}
{
<BEGIN> S() L()
| <PRINT> E()
| LOOKAHEAD(12) "if" E() "then" S() "else" S()
| "if" E() "then" S()
}
void L() :
{}
{ <END>
| <SEMI> S() L()
}
void E() :
{}
{ <ID> <EQUAL> <ID> }
Unidad V
Análisis Semántico
5.1 Analizador semántico




Un compilador no solo tiene que revisar la sintaxis de
código fuente, si no también la semántica de este.
Al igual que en los lenguajes naturales (español, ingles,
etc.) en los lenguajes de programación existen reglas
semánticas para definir el significado de los programas,
estatutos, expresiones, etc.
Por ejemplo un error semántico es usar (en pascal ó
java) un identificador que no fue anteriormente
declarado.
Otro ejemplo de error semántico en un programa es
cuando este es compilado y y no se detectan errores
pero el momento de ser ejecutado este programa no
funciona correctamente.
5.2 Verificación de tipos en
expresiones.



Cuando mezclamos diferentes tipos en una
misma expresión o que llamamos una rutina
que no existe existe un error semántico.
Una de las funciones del analizador smántico
es verificar que los tipos de una expresión
sean compatibles entre si.
Para hacer lo anterior el compilador cuenta
con información de los atributos (tipos,
tamaño, número de argumento, etc.) de los
identificadores en una tabla de símbolos.
5.3 Conversión de tipos.



Algunas veces los tipos de una expresión o estatuto son
diferente.
Por ejemplo en la asignación,
a = b * c;
el tipo del resultado de evaluar b*c es diferente al de el
identificador a.
El compilador algunas veces con ciertos diferentes tipos puede
hacer una conversión interna en forma implícita para solucionar
el problema. Otras veces el programador explícitamente es el
que hace la conversión (casting).
Ejemplo:
float
dinero;
int
cambio;
dinero = (float) cambio;
5.4 Acciones agregadas en un Analizador
sintáctico descendente (top-down).


En un parser recursivo-descendente, el código de las acciones semánticas
es mezclado dentro del flujo de control de las acciones del parser. En un
parser especificado en javaCC, las acciones semánticas son fragmentos de
código de programa en java unido a las producciones gramáticales.
Cada símbolo terminal y noterminal puede asociarse con su propio tipo de
valor semántico.
Por ejemplo en la siguiente gramática para YACC de una calculadora
simple, el tipo asociado con exp e INT podría ser int:
%token INT PLUS MINUS TIMES UMINUS
%start exp
%left PLUS MINUS
%left TIMES
%left UMINIS
exp: INT | exp PLUS exp | exp MINUS exp | exp TIMES exp 1
MINUS exp
%prec UMINUS
(cont.)



Los otros tokens no necesitarían tener un
valor.
Por otra parte el tipo asociado a un token
debe por supuesto coincidir con el tipo de
token que el scanner retorne.
Para una regla ABCD, la acción semántica
debe retornar un valor cuyo tipo es el
asociado al noterminal A. Pero puede
construír este valor de los valores asociados
a los terminales y noterminales B, C, D.
Recursivo-descendente



En un parser recursivo-descendente, las acciones
semánticas son los valores retornados por las
funciones de parsing, o los efectos laterales de
esas funciones o ambos.
Por cada símbolo terminal y noterminal, asociamos
un tipo (desde el lenguaje de implementación del LP
del compilador) de valor semántico representando
frases derivadas desde ese símbolo.
El siguiente programa es un intérprete recursivo
descendente para una parte de la gramática en la
cual eliminamos la recursión por la izquierda (por
conveniencia la volvemos a mostrar):
(cont.)
S  E$
T  F T’
F  id
E  T E’
T’  * F T’
F  num
E’  + T E’
T’  / F T’
F  (E)
E’  - T E’
T’  l
E’  l
Los tokens ID y NUM deben ahora acarrear valores de tipo string e int,
respectivamente. Asumiremos que existe una tabla “lookup” que mapea
identificadores a enteros. El tipo asociado con E, T, F, etc., es int, y la acción
semántica es fácil de implementar.
Interprete
Acciones semánticas
class Token2 {
int kind; Object val;
Token2(int k, Object v)
{
kind=k;
val=v;
}
}
final int EOF=0, ID=1, NUM=2, PLUS=3,
MINUS=4,LPAREN=5, RPAREN=6, TIMES=7;
int lookup(String id) { …. }
int F_follow[] = {PLUS,TIMES,RPAREN,EOF};
int F() {switch(tok.kind) {
case ID: int i=lookup((String)(tok.val));advance()return i;
case NUM: int i=((integer)(tok.val)).intVal();
advance();return i;
case LPAREN: eat(LPAREN);
int i=E();
eatOrSkipTo(RPAREN,F_follow);
return i;
case EOF:
default: print("1 esperaba ID,NUM, o parent izq");
//skipto(F_follow); return 0;
}}
int T_follow[]= {PLUS,RPAREN,EOF};
int T() {switch(tok.kind) {
case ID:
case NUM:
case LPAREN: return Tprime(F());
default: print("2 esperaba ID, NUM o parent izq");
//skipto(T_follow);
return 0;
}}
int Tprime(int a) {switch (tok.kind) {
case TIMES: eat(TIMES); return Tprime(a*F());
case PLUS:
case RPAREN:
case EOF: return a;
default: print("3 esperaba ID, NUM o parent izq");
//skipto(T_follow);
return 0;
}}
void eatOrSkipTo(int expected, int[] stop) {
if (tok.kind==expected)
eat(expected);
else {print("4 esperaba ID, NUM o parent izq");
//skipto(stop);}
}
Parser Automáticamente generado

Una especificación del parser para javaCC consistiría de un conjunto de reglas
gramaticales, cada una anotada o agregada con una acción semántica el cual sería
un estatuto java.
Ejemplo:
void Start():
{ int i; }
{ i=Exp() <EOF> {System.Out.println(i);}
}
Int Exp():
{ int a,i; }
{ a=Term()
( “+” i=Term() {a=a+i;}
| “-” i=Term() {a=a-i;}
)*
{ return a; }
}
Int Term():
{ int a,i; }
{ a=factor()
( “*” i=Factor() { a=a*i;}
| “/” i=Factor() {a=a/i;}
)*
{ return a; }
}
Int Factor():
{ Token t; int i; }
{ t=<IDENTIFIER> { return lookup(t.image); }
| t=<INTEGER_LITERAL>
{return Integer.parseInt(t.image); }
| “(“ i=Exp() “)” {return i; }
}
Árboles de Parsing Abstractos



Para mejorar la modularidad del compilador, es recomendable separar detalles de la
sintaxis con detalles de la semántica (chequeo de tipos y traducción a código
máquina).
Una forma de hacerlo es producir un árbol de sintaxis abstracta (una forma
condensada de árbol de parsing útil para representar construcciones del LP).
Por ejemplo la producción S  if B then S1 else S2 pudiera aparecer en un arbol
sintáctico como:
Árbol
sintáctico
Árbol
De
parsing
If-then-else
If
B
S1
Est-if
Exp ( Exp ) Est
S2
En un árbol sintáctico, los operadores y las palabras claves (reservadas)
no aparecen como hojas, sino que están asociadas con el nodo interior
que sería el padre de esas hojas en el arbol de parsing.
(cont.)

Otro ejemplo es en el árbol de parsing:
L
T
F
E
+
T
*
F
F
4
8
2
+
Cuyo árbol sintáctico abstracto sería:
*
2
8
4
Ejemplo:



La gramática siguiente nos muestra una sintaxis
abstracta de un lenguaje para expresiones:
EE+E
EE-E
EE*E
EE/E
Eid Enum
Esta gramática es impráctica para un parser ya que
es ambigua pues no tiene precedencia de
operadores.
Sin embargo, esta gramática no es para el parser.
El analizador semántico podría usarla el cual no se
molesta por la ambiguedad puesto que ya tiene su
arbol.
Árboles de Sintaxis en Java

En Java las estructuras de datos para el
árbol de sintaxis contienen una clase
abstracta para cada noterminal y una
subclase para cada producción. Así, las
clases de el programa siguiente son las
clases de la sintaxis abstracta para la
gramática de la diapositiva anterior.
Programa de clases para Exp
public abstract class ExpCh4 {
public abstract int eval();
}
class PlusExp extends ExpCh4 {
private ExpCh4 e1,e2;
public PlusExp(ExpCh4 a1, ExpCh4 a2)
{e1=a1; e2=a2;}
public int eval() {
return e1.eval()+e2.eval();
}
}
class MinusExp extends ExpCh4 {
private ExpCh4 e1,e2;
public MinusExp(ExpCh4 a1, ExpCh4 a2)
{e1=a1; e2=a2;}
public int eval() {
return e1.eval()-e2.eval();
}
}
class TimesExp extends ExpCh4 {
private ExpCh4 e1,e2;
public TimesExp(ExpCh4 a1, ExpCh4 a2)
{e1=a1; e2=a2;}
public int eval() {
return e1.eval()*e2.eval();
}
}
class DivideExp extends ExpCh4 {
private ExpCh4 e1,e2;
public DivideExp(ExpCh4 a1, ExpCh4 a2)
{e1=a1; e2=a2;}
public int eval() {
return e1.eval()/e2.eval();
}
}
class Identifier extends ExpCh4 {
private String f0;
public Identifier(String n0) {f0=n0;}
public int eval() {
return (7); //return lookup(f0);
}
}
class IntegerLiteral extends ExpCh4 {
private String f0;
public IntegerLiteral(String n0) {f0=n0;}
public int eval() {
return (4);
//return Integer.parseInt(f0);
}
}
(cont.)

Ahora veamos un intérprete para el lenguaje de
expresiones de la gramática de sección 4.1.1. Por
conveniencia la mostramos de nuevo.
S  E$
ETE’
T  F T’
F  id
E’  + T E’
T’  * F T’
F  num
E’  - T E’
T’  / F T’
F  (E)
E’  l
T’  l
Nuestro intérprete primero construye árboles
sintácticos y después
los interpreta. El siguiente
código es el de la gramática JavaCC con acciones
semánticas para interpretar (evaluar) y producir
(construir) árboles sintácticos. Cada clase de nodos
de árbol sintáctico contiene una función eval que
cuando es llamada retorna el valor de la expresión
representada.

Gramática con acciones semánticas para
árboles sintácticos
PARSER_BEGIN(InterSinTree)
class InterSinTree {}
PARSER_END(InterSinTree)
ExpCh4 Exp():
TOKEN: {
{ ExpCh4 e1,e2; }
{ e1=Term()
("+" e2=Term() { e1=new PlusExp(e1,e2);}
|"-" e2=Term() { e1=new MinusExp(e1,e2);}
)*
{ return e1;}
}
<#DIGIT: ["0"-"9"]>
|<ID: ["a"-"z"] (["a"-"z"]|<DIGIT>)*>
|<INTEGER_LITERAL: (<DIGIT>)+>
}
ExpCh4 Term():
SKIP: {
<"--" (["a" - "z"])* ("\n" | "\r" | "\r\n")>
|" "
|"\t"
|"\n"
|"\r"
}
ExpCh4 Start():
{ ExpCh4 e; }
{ e=Exp() <EOF>
{System.out.println(e.eval()); return e; }
}
{ ExpCh4 e1,e2; }
{ e1=Factor()
("*" e2=Factor() { e1=new TimesExp(e1,e2);}
|"/" e2=Factor() { e1=new DivideExp(e1,e2);}
)*
{ return e1;}
}
ExpCh4 Factor() :
{ Token t; ExpCh4 e; }
{ (t=<ID>
{return new Identifier(t.image); } |
t=<INTEGER_LITERAL>
{return new IntegerLiteral(t.image); } |
"(" e=Exp() ")" {return e; })
}
VISITADORES

Es una técnica de patrones (opuesta a la orientada
a objetos) que se puede usar para implementar el
árbol sintáctico del compilador o intérprete. Un
visitador es un objeto que contiene un método visit
por cada clase de árbol sintáctico. Cada clase de
árbol sintáctico debe contener un método accept.
Cada método accept sirve como enganche para
cada diferente tipo de operación sobre el árbol y es
llamado por un visitador donde tiene una tarea:
pasar el control de ida y venida (back and forth)
entre el visitador y las clases del árbol sintáctico.
(cont.)

A continuación veremos un ejemplo del
intérprete de expresiones anterior pero ahora
implementado con visitadores. Cada visitador
implementa la interfase Visitor. Cada
método accept toma un visitador como
argumento y cada método visit toma un
objeto de un nodo del árbol sintáctico como
argumento.
Sintáxis Abstracta para MiniJava

En la siguiente figura (siguiente diapositiva) mostramos las clases
de la sintaxis abstracta para minijava. Solo los constructores son
mostrados en la figura. Cada una de las clases de listas se
implementa en la misma forma. Por ejemplo:
public class ExpList {
private Vector list;
public ExpList() {
list=new vector();
}
Public void addElement (Exp n) {
list.addElement(n);
}
public Exp elementAt(int i) {
return (exp)list.elementAt(i);
}
public int size() {
return list.size();
}
}
Package syntaxtree;
Program(MainClass m, ClassDeclList cl)
MainClass(Identifier i1, Identifier i2, Statement s)
Abstract class ClassDecl
ClassDeclSimple(Identifier i, VarDeclList vl, MethodDeclList ml)
ClassDeclExtends(Identifier i, identifier j, VarDeclList vl, MethodDeclList ml)
VarDecl(Type t, Identifier i)
MethodDecl(Type t, Identifier i, FormalList fl, VarDeclList vl, StatementList,
Exp e)
Formal(Type t, Identifier i)
Abstract class Type
IntArrayType()
BooleanType()
IntegerType()
Abstract class Statement
Block(StatementList sl)
If(Exp e, Statement s1, Statement s2)
While(Exp e, Statement s)
Print(Exp e)
Assign(Identifier i, Exp e)
ArrayAssign(Identifier i, Exp e1, Exp e2)
IdentifierType(String s)
(cont. figura)
Abstract class Exp
And(Exp e1, Exp e2)
LessThan(Exp e1, Exp e2)
Plus(Exp e1, Exp e2)
Minus(Exp e1, Exp e2)
ArrayLoockup(Exp e1, Exp e2)
ArrayLength(Exp e)
Call(Exp e, Identifier i, ExpList el)
IntegerLiteral(int i)
True()
False()
IdentifierExp(String s)
This()
NewArray(Exp e)
NewObject(Identifier i)
Not(Exp e)
Times(Exp e1, Exp e2)
Identifier(String s)
List classes
ClassDeclList()
ExpList()
FormalList()
StatementList()
MethodDeclList()
VarDeclList()
Arbol Sintáctico

Cada una de las clases que no son listas
tiene un método accept para usarse con el
patrón visitador. La interface Visitador se
muestra en la siguiente diapositiva.
Visitador
MiniJava
public interface Visitor {
public void visit(Program n);
public void visit(MainClass n);
public void visit(ClassDeclSimple n);
public void visit(ClassDeclextends n);
public void visit(VarDecl n);
public void visit(MethodDecl n);
public void visit(Formal n);
public void visit(IntArrayType n);
public void visit(BooleanType n);
public void visit(IntegerType n);
public void visit(IdentifierType n);
public void visit(Block n);
public void visit(If n);
public void visit(While n);
public void visit(Print n);
public void visit(Assign n);
public void visit(ArrayAssign n);
public void visit(And n);
public void visit(LessThan n);
public void visit(Pluss n);
public void visit(Minus n);
public void visit(Times n);
public void visit(ArrayLoockup n);
public void visit(ArrayLength n);
public void visit(Call n);
public void visit(IntegerLiteral n);
public void visit(True n);
public void visit(False n);
public void visit(IdentifierExp n);
public void visit(This n);
public void visit(NewArray n);
public void visit(NewObject n);
public void visit(Not n);
public void visit(Identifier n);
}
(cont. Arbol Sintáctico)

Podemos construir un árbol sintáctico usando expresiones new
anidadas. Por ejemplo el árbol sintáctico para el estatuto MiniJava:
x = y.m(1,4+5);
usaría el siguiente código:
ExpList el= new ExpList();
el.addElement(new IntegerLiteral(1));
el.addelement(new Plus(new IntegerLiteral(4),
new IntegerLiteral(5)));
Statement s = new Assign(new Identifier “x”),
new Call(new identifierExp(“y”),
new Identifier(“m”),
el));
5.5 Pila semántica en un analizador
sintáctico ascendente (bottom-up).



Como fue visto en el capitulo anterior (4), un parser ascendente
utiliza durante el análisis una pila. En esta va guardando datos
que le permiten ir haciendo las operaciones de reducción que
necesita.
Para incorporar acciones semánticas como lo es construir el
árbol sintáctico, es necesario incorporar a la pila del parser otra
columna que guarde los atributos de los símbolos que se van
analizando.
Estos atributos estarían ligados a la correspondiente producción
en la tabla de parsing
(consultar sección 5.3 del libro de “Aho, Ullman, Sethi” para ver
mas detalles de la implementación).
5.6 Administración de la tabla de
símbolos



El análisis semántico conecta las definiciones de las
variables con sus usos, checa que cada expresión
tenga un tipo correcto y traduce la sintaxis abstracta
a una representación mas simple para generar
código máquina.
Esta fase es caracterizada por el mantener la tabla
de símbolos (también llamada “environment”) la cual
mapea identificadores con sus tipos y localidades.
Cada variable local en un programa tiene un ámbito
(scope) dentro del cual es visible. Por ejemplo, en
un método MiniJava m, todos los parámetros
formales y variables locales declarados en m son
visibles solo hasta que finalice m.
(cont.)

Un ambiente es un conjunto de atados
(bindings) denotados por . Por ejemplo,
podemos decir que el ambiente z0 contiene
los atados {gstring,aint}, que significa
que el identificador a es una variable entero y
g es una variable string.
Ejemplo:
1
2
3
4
5
6
7
8
9
10
11
Class C {
int a, int b; int c;
public void m() {
System.out.println(a+c);
int j=a+b;
String a=“hello”;
System.out.println(a);
System.out.println(j);
System.out.println(b);
}
}
Suponer que compilamos esta clase en el ambiente z0. Las declaraciones de
campo en línea 2 nos da la tabla z1 igual a z0 + {aint,bint,cint}. Los
identificadores en línea 4 pueden encontrarse (look up) en ambiente z1. En
línea 5, la tabla o ambiente z2=z1+{jint} es creada; y en línea 6,
z3=z2+{astring} es creada.
Implementación de la Tabla

Existen dos opciones: El estilo funcional
donde cuando z1 existe y z2 es creado, z1
sigue existiendo. Y el imperativo en donde z1
es destruido al crearse z2. Mientras z2 existe
no podemos mirar z1. Pero al morir z2, z1 de
nuevo existe.
Múltiple Tablas de Símbolos

En algunos LP pueden existir varios
ambientes a la vez: Cada módulo, o clase o
registro en el programa tiene una tabla de
símbolos z propia. Ejemplos (ML y Java).
Structure M = struct
structure E = struct
val a= 5;
end
structure N = struct
val b=10
val a=E.a+b
end
structure D = struct
val d=E.a+N.a
end
end
Package M;
class E {
static int a=5;
}
Class N {
static int b=10;
static int a=E.a+b;
}
Class D {
static int d=E.a+N.a;
}
(cont.)

Al anlizar los 2 programas anteriores, sea z0 el
ambiente base conteniendo funciones predefinidas,
y sea
z1={aint}
z2={Ez1}
z3={bint,aint}
z4={Nz3}
z5={dint}
z6={Dz5}
z7=z2+z4+z6
(cont.)


En ML, N es compilado usando el ambiente
z0+z2 para buscar los identificadores en la
tabla;D es compilado usando z0+z2+z4 y el
resultado del análisis es {Mz7}.
En Java, referencias adelantads son
permitidas (dentro de N la expresión D.d
sería legal), asi E,N y D son compilados en el
ambiente z7.
TABLAS DE SIMBOLOS EN
LENGUAJES IMPERATIVOS


Un programa grande puede contener miles de
distintos identificadores. Esto hace que la búsqueda
en la tabla (loock up) tenga que ser eficiente.
En ambientes imperativos usualmente se usan
tablas de dispersión. La operación z’=z+{at} es
implementada insertando t en la tabla de dispersión
usando la llave a. Una tabla de dispersión con
encadenamiento externo funciona bien y soporta
eliminación fácil de at para recuperar z al final del
ambito de a. El siguiente programa implementa una
tabla de dispersión. El “bucket i” es una lista ligada
de todos los elementos cuya llave genere “i mod
SIZE”.
(cont.)

Considere z+{at2} cuando z ya contiene
at1. La función insert deja at1 en el
“bucket” y pone at2 antes en la lista.
Entonces, cuando pop se realiza después del
ambito de a, z es restaurado.
SIMBOLOS


Para evitar comparaciones innecesarias de
cadenas podemos convertir cada cadena a
un símbolo, y así todas las diferentes
ocurrencias de cualquier cadena se
conviertan a un mismo objeto símbolo.
El módulo símbolo implementa los símbolos
y tiene estas propiedades:


Comparar símbolos por igualdad o por mayor es
rápido (comparación por apuntador o por entero).
Extraer una llave “hash” de tipo entero es rápido
(cont.)





Los ambientes son implementados en la clase Symbol.Table
como Tables mapeando Symbols a ligados (bindings).
Para eso se manejan ligaduras para diferentes propósitos en el
compilador – ligadura para tipos, para variables, para funciones,
etc.
Entonces, una ligadura es un Objeto.
Para implementar la clase Symbol, usaremos el método intern()
(java.lang.String), para darnos un objeto único a partir de una
cadena de caracteres.
Para el uso de la tabla de símbolos usaremos
java.util.Hashtable. La función beginScope “recuerda” el estado
actual de la tabla y endScope restaura la tabla a donde estaba
en el mas reciente beginScope que no ha terminado.
(cont.)



Cuando la atadura xb es metido a la tabla (table.put(x,b)), x es
dispersado a un índice i, y un objeto “binder” xb es puesto en
la cabeza de la lista ligada para el bucket i.
Si la tabla ya tiene una ligadura xb’, esto permanecería en el
bucket, pero escondido por xb. Esto es importante ya que
soportaría la implementación de undo (beginScope y endScope).
También deberá existir una pila auxiliar, que muestre en que
orden los símbolos son metidos (pushed) a la tabla de símbolos.
Cuando xb es encontrado, entonces x es metido a la pila
(beginScope). Entonces, para implementar endScope, los
símbolos deben sacarse de la pila.
Chequeo de Tipos en MiniJava


¿Con que se llena una tabla de símbolos? Esto es,
¿Qué es la ligadura o “binding”?
Para realizar el chequeo de tipos de programas
MiniJava, la tabla de símbolos debe contener toda
la información declarada:




Cada nombre de variable y nombre de parámetro formal
debe ser ligado a su tipo.
Cada nombre de método debe ser ligado a sus
parámetros, tipo de resultado y variables locales.
Cada nombre de clase debe ser ligado a su variable y
declaraciones de métodos.
Liga a página con mas información.
(cont.)

Por ejemplo, considere la siguiente figura,
que muestra un programa y su tabla de
símbolos.
PARAMS
Class B {
C f; int [ ] j; int q;
public int start(int p, int q) {
int ret; int a;
/* …… */
return ret;
}
public boolean stop(int p) {
/* ….. */
return false;
}
}
Class C {
/* ….*/
}
p
q
B
C
FIELDS
f
j
q
C
int [ ]
int
METHODS
start
int
stop
bool
……
int
int
LOCALS
ret
int
a
int
PARAMS
p
int
LOCALS
(cont.)



Los tipos primitivos en MiniJava son int y boolean;
todos los otros tipos son arreglo de enteros o
nombres de clases.
Por simplicidad todos los tipos son “string”, en lugar
de símbolos; esto nos permite checar igualdad de
tipos por medio de comparación de “strings”.
El chequeo de tipos de un programa MiniJava
ocurre en dos fases. Primero, construimos la tabla
de símbolos y después checamos los tipos de los
estatutos y las expresiones. Lo hacemos en dos
fases porque en MiniJava (igual que en Java) las
clases son mutuamente recursivas.
(cont.)



La primera fase de el checador de tipos se puede
implementarse por medio de un visitador que visite
los nodos del árbol sintáctico de MiniJava y
construya la tabla de símbolos.
Por ejemplo el método visitador en el siguiente
programa maneja declaraciones de variables. Este
agrega el nombre de la variable y el tipo a la
estructura de datos para la clase actual que mas
tarde será agregada a la tabla de símbolos.
El método visitador checa si la variable ya fue
declarada anteriormente.
Método Visitador
Class ErrorMsg {
boolean anyErrors;
void complain (String msg) {
anyErrors = true;
System.out.println(msg);
}
}
// Type t;
// Identifier i;
Public void visit(VarDecl n) {
Type t = n.t.accept(this);
String id= n.i.toString();
if (currMethod ==null) {
if (!currClass.addVar(id,t))
error.complain(id + “is already defined in “ + currClass.getId());
} else if (!currentMethod.addVar(id,t))
error.Complain(id + “is already defined in “
+ currClass.getId( ) + “.” + currMethod.getId( ));
(cont.)




La segunda fase del checador de tipos puede ser implementada
por un visitador que cheque tipos de todas los estatutos y
expresiones.
El tipo del resultado de cada método visitador es String, que
representa los tipos de MiniJava.
La idea es que cuando el visitador visita una expresión, entonces
retorna el tipo de esa expresión.
El siguiente método (siguiente diapositiva) es el visitador que
implementa la adición (plus) e1 + e2. En MiniJava ambos
operandos deben ser de tipo entero (el checador revisa esto) y el
resultado debe ser entero (el checador retorna este tipo).
Método Visitador para
expresiones Plus
// Exp e1, e2;
Public Type visit(Plus n) {
if (! (n.e1.accept(this) instanceOf IntegerType) )
error.complain(“Left side of LessThan must be of type integer”);
if (! (n.e2.accept(this) instanceOf IntegerType) )
error.complain(“Right side of LessThan must be of type integer”);
return new IntegerType( );
}
5.7 Manejo de errores semánticos.





Cuando el checador de tipos detecta un error de
tipos o un identificador no declarado, debe imprimir
el mensaje de error y continuar.
Esto debido a que normalmente el programador
prefiere que le describan todos los errores posibles
del programa fuente.
Esto quiere decir, que si un error de tipos es
encontrado, no debe producirse un programa objeto
por parte del compilador.
Así, las siguientes fases no deben ejecutarse.
Hasta esta etapa (chequeo de tipos), la parte del
compilador se conoce con el nombre de “front End”.
REGISTROS DE ACTIVACION


En casi cualquier LP, una función (método)
puede tener variables locales que son
creadas cuando se llama la función (al entrar
a esta).
Diferentes invocaciones a la función pueden
existir a la vez, y cada invocación tiene su
propia “instanciación” de variables.
(cont.)

En el siguiente método de Java
Int f(int x) {
int y= x+x;
if (y<10)
return f(y);
else
return y-1;
Una nueva instancia de x es creada (e inicializada por el
llamador de “f”) cada vez que “f” es llamada. Debido a
que existen llamadas recursivas, muchas de esas x
existen simultáneamente. Similarmente, una nueva
instancia de y es creada cada vez que el cuerpo f es
iniciado.
(cont.)

En muchos LP (incluyendo Pascal, C y java),
las variables locales son destruidas cuando
una función retorna. Ya que las variables
locales son creadas y destruidas en una
forma LIFO, podemos usar una pila para
manejarlas.
MARCOS DE PILA




Debido a que se trabaja con bloques de datos por
función un “push” y “pop” no funciona.
Entonces la pila es tratada como si fuera un gran
arreglo, con un registro especial- el “stack pointer”
que apunta a una localidad.
Todas las localidades después del apuntador son
basura y todas las que están antes están
asignadas.
El área en la pila dedicada a las variables locales,
parámetros, dirección de retorno y otras variables
temporales para una función es llamada el registro
de activación o marco de pila de la función.
(cont.)


El diseño de la estructura de los marcos es
de acuerdo con la arquitectura y el LP que se
compila.
Aunque normalmente el constructor de la
arquitectura define un diseño de marco
standard para todos los compiladores para
esa arquitectura.
Ejemplo: Un marco de pila
Direcciones de Memoria
mas altas
Argumentos
de entrada
Apuntador
Del marco
Argumento n
…
…
Argumento 1
Liga estática
Marco anterior
Variables
locales
Dirección retorno
Marco
actual
Temporales
Registros salvados
Argumentos
De salida
Apuntador
De pila
Argumento m
…
…
Argumento 1
Liga estática
Marco siguiente
Marco de Pila





Los argumentos de entrada son los pasados por el
llamador (técnicamente son parte del marco anterior
pero pueden accesarse usando un desplazamiento
del apuntador de marco).
Cuando la función actual llama otras funciones,
puede usar el espacio de los argumentos de salida
para pasar parámetros.
La dirección de retorno es creada por la instrucción
CALL.
Las variables locales también tienen su espacio.
Las variables mantenidas en registros algunas
veces son salvadas a memoria.
El Apuntador de Marco (FP)




Suponer que una función g(…) llama la función f(a1,…an).
Diremos que g es el llamador (caller) y f el llamado (callee). Al
entrar a f, el apuntador de la pila (SP) apunta al primer
argumento que g pasa a f. Al entrar, f coloca un marco solo con
restar el tamaño del marco de el SP.
El viejo SP se convierte en el actual FP y el viejo FP es salvado
en el marco.
Cuando FP termina, solo copia FP de regreso a SP y regresa el
valor viejo salvado de FP.
Si los marcos son siempre del mismo tamaño entonces no es
necesario contar con FP y todo se simplifica sumando o
restando la constante framesize a SP.
Registros



Por eficiencia, es importante mantener las variables
locales, resultados intermedios y otros valores en
registros en lugar de la pila de marcos.
Si función f llama a g y ambas hacen uso de registro
r, entonces r debe ser salvado (dentro de la pila de
marcos) antes de que lo use g y restaurado (desde
la pila) después de que termine g.
¿de quien es responsabilidad de salvar r? ¿de f o
g? si lo salva f se dice que r es un registro callersave; si lo salva g se llama callee-save.
Pase de Parámetros


Estudios actuales han mostrado que
raramente una función pasa mas de 4
parámetros.
Debido a esto, la mayoría de las máquinas
definen que los primeros k argumentos (con
k=4) se pasan en registros y el resto en
memoria.
Direcciones de Retorno



Si g llama a f, entonces si la instrucción call
dentro de g está en dirección a, el lugar de
retorno en g es a+1, la siguiente instrucción
del call.
En máquinas modernas la dirección de
retorno es pasada a un registro en lugar de la
memoria.
En funciones “hoja” la dirección no necesita
ponerse en la pila.
Registros vs. Memoria

Registros siempre deben usarse en asignación a
menos que:






La variable sea pasada por referencia
La variable es accesada por una función anidada dentro
de la función actual.
El valor es demasiado grande para un registro.
La variable es un arreglo, donde es necesario realizar
aritmética de direcciones.
El registro que contiene la variable es necesitado para
otros propósitos.
Existen demasiadas variables locales y valores temporales
Ligas Estáticas (Static Links)


En LP que admiten funciones anidadas (Pascal,ML
y Java) las funciones de mas adentro pueden usar
variables declaradas en funciones de mas afuera
(Estructuras de Bloque).
En el siguiente programa (sig. Diapositiva) la
función write hace referencia a la variable de afuera
output e indent hace referencia a n y output. Para
cumplir con esto, indent debe tener acceso no solo
a su propio marco (para i y s) sino también a los
marcos de show (por n) y prettyprint (por output).
Programa de funciones Anidadas
Type tree= {key: string, left: tree, right: tree}
Function prettyprint(tree:tree): string=
let
var output := “ “
function write(s:string) =
output :=concat(output,s)
function show(n:int, t:tree) =
let function indent(s:string)=
(for i:= 1 to n
do write(“ “);
output:=concat(output,s);write(“ “);
in if t=nil then indent(“.”)
else (indent(t.key);
show(n+1,t.left);
show(n+1,t.right))
end
in show(0,tree); output
end
Ligas Estáticas (cont.)

Existen varios métodos para solucionar lo anterior:



Siempre que una función f sea llamada, puede pasarse un
apuntador a el marco de la función que estáticamente
encierra a f; este apuntador es la liga estática.
Un arreglo global puede mantenerse, conteniendo -en
posición i - un apuntador a el marco del procedimiento mas
recientemente activado cuyo profundidad de anidamiento
estático es i. Este arreglo es llamado un “display”.
A continuación describimos el método de liga
estática para el ejemplo de la diapositiva anterior.
(cont.)







Línea 21: prettyprint llama show, pasando el apuntador del marco del propio
prettyprint como una liga estática de show.
Línea 10: show guarda su liga estática (la dirección del marco de prettyprint)
dentro de su propio marco.
Línea 15: show llama indent, pasando su propio apuntador de marco como liga
estática de indent.
Línea 17: show llama a show,pasando su propia liga estática (no su propio
apuntador de marco) como la liga estática.
Línea 12: indent usa el valor n del marco de show. Para hacer esto, trae un
desplazamiento apropiado de la liga estática de indent (que apunta al marco de
show).
Línea 13: indent llama a write. Debe pasar el apuntador de marco de
prettyprinter como la liga estática. Para obtener esto, primero trae un
desplazamiento de su propia liga estática (desde el marco de show), la liga
estática que había sido pasada a show.
Líea 14: indent usa la variable output del marco de prettyprint. Para hacer esto,
comienza con su propia liga estática, entonces trae a show, y luego trae a
output.
Unidad VI
Generación de Código
Intermedio
6.1 Lenguajes intermedios.

El código intermedio en una estructura de código
cuya complejidad está entre un código fuente en un
lenguaje de alto nivel y el código máquina.
Código fuente


Código intermedio

Código Objeto
Un compilador produce primero un código
intermedio, pues producir directamente el código
objeto resulta sumamente complicado e ineficiente.
(cont.)
Ventajas de producir código intermedio:
 Más fácil de producir código objeto después,
si se parte de un código intermedio.
 Facilita y hace eficiente la optimización de
código (algunos tipos de optimización).
 El código intermedio es transportable (puede
usarse en diferentes arquitecturas) ya que no
hace referencia a componentes de la
máquina.
6.2 Notaciones.

Infija. Es la notación habitual. El orden es primer
operando, operador, segundo operando.
Ejemplo: a/b/c
La notación infija tiene el problema de que en
expresiones con más de un operador existe
ambiguedad sobre cual es el orden de evaluación.
Por ejemplo, la expresión 8/4/2 se puede interpretar
como (8/4)/2 o bien como 8/(4/2). Las otras
notaciones (prefija y postfija) no sufren este
problema.
(cont.)

Postfija. El orden es primer operando, segundo operando, operador.
Ejemplo: La expresión X+Y-X*Y
en notación Postfija es XY+XY*Por lo general la notación postfija se emplea en máquinas de pilas ya que la pila facilita la
ejecución. Al analizar una notación postfija de izquierda a derecha, cada vez que se detecta un
operando se mete a la pila. La ocurrencia de un operador con ‘m' operandos significa que el
enésimo operando estará m-n posiciones por debajo del tope de la pila. Después se sacan los
operandos de la pila y se mete el resultado de la operación.
Por ejemplo, suponer que X=1 y Y=2.
Las operaciones serían:
push 1 (meter 1)
push 2
' + ' requiere de 2 operandos, se sacan, se suman y se mete el resultado (3)
push 1
push 2
' * ' se mete el resultado(2)
' - ' se mete el resultado (1)

Notación prefija: El orden es operador, primer operando, segundo operando.
6.3 Representación de código
intermedio.

Existen muchas clases de representaciones
intermedias. Algunas de las mas comunes
son:





Notación polaca.
Código P (Pascal).
Triples y Cuadruples.
Bytecodes (Java)
MSIL (C#)
Notación Polaca

También conocida como notación postfija. Se
utiliza como se dijo anteriormente en
máquinas de Pila.
Ejemplos:
Pascal Notación Polaca
a+b-c
ab+ca+b*c
abc*+
a+b*c+d
abc*+d+
Código P




Se usó como código intermedio y objeto en las
primeras implementaciones de Pascal.
El código P era interpretado en una máquina
abstracta.
Algunas implementaciones de Basic y Pascal usan
código P el cual después es traducido a código
nativo por un compilador “Just-in-Time”.
La máquina P está orientada a usarse en una pila
(stack-oriented).
Ejemplo:
Insn. Stack
before
Stack
after
Description
adi
Adr
dvi
ldci
mov
i1 i2
r1 r2
i1 i2
i1 i1
a1 a2
i1+i2
r1+r2
i1/i2
add two integers
add two reals
integer division
load integer constant
move
not
b1
~b1
boolean negation
Triples y Cuadruplos
(Código de 3 Direcciones)

Ha sido uno de los mas populares. Sus
instrucciones constan de 3 direcciones o registros
para 2 argumentos u operandos y el resultado.
Su formato es:
resultado:= argumento1 operador argumento2
Donde resultado, argumento1 y argumento2 pueden
ser constantes, identificadores y variables
temporales definidos por el compilador mientras que
operador representa una operación arbitraria. Esta
forma se denomina Cuádruplo.
(cont.)
EJEMPLO:
ADD
MUL
SUB
STORE
Z:= X + Y – X * Y
X
Y
X
Y
VAR1 VAR2
VAR3
VAR1
VAR2
VAR3
Z
(cont.)


EJEMPLO: (Estructure de Control):
If (a==b)
a=0;
else
a=1;
En cuadruplos tendríamos:
1
A
2
3
4
5
6
JnZ
=
JP
=
t1
0
1
B
t1
5
A
6
A
(cont.)

En el código de 2 direcciones se evita el uso se
variables temporales. El formato es:
Operador argumento1 argumento2
EJEMPLO: Z = X + Y - X * Y
1.
2.
3.
4.
ADD
MUL
SUB
STORE
X
X
(1)
(3)
Y
Y
(2)
(Z)
Donde los números entre paréntesis representan
apuntadores a la secuencia de operaciones de 2 direcciones.
Java Bytecodes



El bytecode es un código intermedio más abstracto que el código
máquina. Habitualmente viene a ser un archivo binario que
contiene un programa ejecutable similar a un módulo objeto o
código máquina producido por el compilador.
El bytecode recibe su nombre porque generalmente cada código
de operación tiene una longitud de un byte, si bien la longitud del
código de las instrucciones varía.
Cada instrucción tiene un código de operación entre 0 y 255
seguido de parámetros tales como los registros o las direcciones
de memoria. Esta sería la descripción de un caso típico, si bien
la especificación del bytecode depende ampliamente del
lenguaje.
(cont.)



Como código intermedio, se trata de una forma de salida
utilizada por los implementadores de lenguajes para reducir la
dependencia respecto del hardware específico y facilitar la
interpretación.
Menos frecuentemente se utiliza el bytecode como código
intermedio en un compilador. Algunos sistemas, llamados
traductores dinámicos o compiladores just-in-time (JIT) traducen
el bytecode a código máquina inmediatamente antes de su
ejecución para mejorar la velocidad de ejecución.
Los programas en bytecode suelen ser interpretados por un
intérprete de bytecode (en general llamado máquina virtual, dado
que es análogo a un ordenador).
(cont.)




Su ventaja es su portabilidad: el mismo código binario puede ser
ejecutado en diferentes plataformas y arquitecturas. Es la misma
ventaja que presentan los lenguajes interpretados.
Sin embargo, como el bytecode es en general menos abstracto,
más compacto y más orientado a la máquina que un programa
pensado para su modificación por humanos, su rendimiento
suele ser mejor que el de los lenguajes interpretados.
A causa de esa mejora en el rendimiento, muchos lenguajes
interpretados, de hecho, se compilan para convertirlos en
bytecode y después son ejecutados por un intérprete de
bytecode.
Entre esos lenguajes se encuentran Perl, PHP y Python. El
código Java se suele trasmitir como bytecode a la máquina
receptora, que utiliza un compilador just-in-time para traducir el
bytecode en código máquina antes de su ejecución.
La Máquina Virtual de Java
(JVM)

La siguiente liga nos lleva a la información de
lo que es la JVM y mas sobre Java
bytecodes.
Árboles de Ensamblador



Un paso antes de generar Ensamblador Real
Permite mas fácil optimización de código
Primero vamos a estudiar la implementación
de asignación de memoria en el código
generado (stack y heap).
Implementación de variables



En Java las variables locales son
almacenadas en la pila y en registros.
Las variables de arreglos y de clases son
almacenadas en el heap.
Registros de Activación (RA).

Son los segmentos de la pila que contienen las
variables para una función. También se le llama
“stack frame”. También almacenan valores de
registros (saved registers), retornos, parámetros,
etc.
Por ejemplo, la función:
Int foo() {
int a;
int b;
/* body of foo */
}
Tendría el registro de activación
a
FP
b
Registros
salvados
SP
Existen dos apuntadores. FP que
apunta al inicio del RA actual y SP que
apunta a la primera localidad vacía. El
valor retornado de una función es
puesto en un registro especial en lugar
de la pila. Cuando una función es
llamada los valores de los parámetros
de entrada son puestos en la pila, y
cuando la función retorna un valor, el
valor es almacenado en el registro de
resultado.
(cont.)


Como el FP siempre apunta al comienzo del
RA actual, podemos acceder a las variables
locales usando un offset desde el FP.
Los parámetros de funciones son
almacenados en RA de la función que llama,
no la que es llamada. Los parámetros de
entrada a una función pueden ser accesados
por medio del FP, usando un offset en la
dirección opuesta a las variables locales. El
formato completo de un RA es mostrado en
la siguiente diapositiva.
Formato completo de RA
Input Parameter n
Previous Activation Record
…
Input Parameter 2
Input Parameter 1
FP
Local Variables
Current Activation Record
Saved Registers
SP
Considere el siguiente programa:
void foo(int a, int b);
void foo(int c, int d);
void main() {
int u;
int v;
/* Label A */
bar(1,2);
}
void bar(int a, int b) {
int w;
int x;
foo(3,4);
}
void foo(int c, int d) {
int y;
int z;
/* Label B */
}
En label A de el programa, la pila de RA se miraría de la
forma siguiente
u
FP
Activation
Record for
main
v
Saved Registers
SP
La variable local u puede accesarse examinando la localidad de
memoria apuntada por FP. La variable v puede accesarse
examinando (FP-wordsize). Algo para aclarar es que la pila
crece de direcciones altas a bajas.
En etiqueta B los RA se
mirarían así:
u
Activation Record
for main
v
Saved Registers
b
a
w
x
Activation Record
for bar
Saved Registers
d
c
y
Activation Record
for foo
FP
z
Saved Registers
SP
(cont.)


La variable y en función foo puede accesarse al
examinar la localidad de memoria apuntada por FP.
La variable z en foo puede accesarse examinando
la localidad (FP-wordsize). El parámetro de entrada
c en función foo puede accesarse examinando la
localidad (FP+wordsize), mientras que el parámetro
d puede accesarse con (FP+2*wordsize).
Algo importante es que la función llamadora es
responsable de poner los parámetros actuales y de
quitarlos cuando acabe la función llamada.
Ensamblador Abstracto


El ensamblador abstracto es dividido en árboles de
estatutos y árboles de expresiones. Árboles de
estatutos no tienen valores pero los de expresiones
si lo tienen.
Existen cinco diferentes tipos de árboles de
expresiones:



Constante. Consiste de un valor de la constante (solo
enteros).
Registro. Una cadena que especifica el registro.
Operador. Dos árboles de expresión para los operandos, y
el operador: +,-,*,/,<,>,<=,>=,=,&&,||,!.
(cont.)

CallExpression. Contiene una etiqueta de lenguaje ensamblador y
un árbol de expresión por cada uno de los parámetros en la llamada
de la función (function call). La etiqueta es la dirección del inicio de
la función llamada. Por ejemplo la función foo(3,4,5) se
representaría por el árbol de expresión:
CallExpresion(“foo”)
Constant(3)
Constant(4)
Constant(5)
El ensamblador abstracto en este caso no contiene instrucciones
explícitas para asignar los parámetros actuales a la pila. Cuando
se tradusca el ensamblador abstracto de una callExpression a
ensamblador real, se incluye el código para hacer la copia de los
parámetros actuales a la pila.

Memoria. Solo se denota la dirección de memoria.
Ejemplo:
Memory
Constant(1006)
Casi nunca se manejan direcciones absolutas sino que estas son
relativas al FP. Por ejemplo para referirse a la localidad de memoria de
una variable local con un desplazamiento (oofset) de 4 del FP es
representado con el árbol:
Memory
Operator(-)
Register(FP)
Constant(4)

Existen 8 tipos de árboles de estatutos:








Move. Tienen dos subárboles – el´subárbol izquierdo es el destino del move,
y el derecho es el valor a mover. El izquierdo necesita ser un árbol de
expresión de registro (mover un dato a un registro) o un árbol de expresión
de memoria (mover un dato a memoria). La parte derecha puede ser una
expresión arbitraria.
Label (Etiqueta). Se usan como destinos de “jumps” y “calls”.
Jump. Saltos incondicionales contienen una etiqueta.
Conditional Jump. Contienen un subárbol de expresión y una etiqueta de
lenguaje ensamblador. Si la expresión es verdadera se hace una
transferencia de control a una etiqueta. Si es falsa, entonces habrá un noop.
Sequential. Tiene dos subárboles. Representa la ejecución del izquierdo
seguido del derecho.
CallStatement. Contienen una árbol de etiqueta, y un árbol expresión de
cada uno de los parámetros actuales. “Calls” representan “void function
calls”.
Empty. Son “no-ops” y son removidos cuando se traduce a ensamblador
real.
Return. No retorna un valor (como Java). Solo cambia el flujo de control. Un
“return” de Java se implementa incluyendo código que retorne el valor de la
función (en el registro resultado) además del ensamblador abstracto del
“return”.
Ejemplos: (asumiremos que wordsize=4 y que un entero se
guarda en una palabra)
void foo(int a, int b) {
int x;
int y;
boolean z;
x = 1;
y = a * b;
y++;
bar(y, x + 1, a);
x = function(y+1, 3);
if (x > 2)
z = true;
else
z = false;
}
X=1;
Move
Memory Constant(1)
Register(FP)
y = a * b;
Move
Operator(*)
Memory
Memory
Memory
Operator (+)
Operator (+)
Operator (-)
Register(FP) Constant(4)
Register(FP)
Constant(4)
Register(FP)
Constant(8)
Y++;
Move
Operator(+)
Memory
Memory
Operator (-)
Operator (-)
Register(FP) Constant(4)
Register(FP)
Constant(4)
Constant(1)
bar(y,x+1,a);
CallStatement(“bar”)
Memory
Operator (-)
Register(FP) Constant(4)
Operator (+)
Memory
Constant(1)
Register(FP)
Memory
Operator (+)
Register(FP) Constant(4)
x=function(y+1,3);
Move
Callexpression(“function”)
Memory
Register(FP)
Constant(3)
Operator(+)
Memory
Constant(1)
Operator(-)
Register(FP)
Constant(4)
if (x > 2) z = true; else z = false;
Sequential
Sequential
ConditionalJump(“iftrue”)
Sequential
Operator(>)
Jump(“ifend”)
Sequential
Move
Memory Constant(2)
Sequential
Label(“iftrue”)
Memory
Constant(0)
Label(“ifend”)
Move
Register(FP)
Operator(-)
Register(FP) Constant(8)
Memory
Constant(1)
Operator(-)
Register(FP) Constant(8)
Creación de Ensamblador Abstracto

Variables

Variables base
void foo() {
int x;
int y;
/* Body of foo */
}

La variable x y y se representarían con los
árboles:
Memory
Memory
Register(FP)
Operator(-)
Register(FP)
Constant(4)

Variables Arreglo: Son almacenadas en el
heap, y usando un apuntador a la base del
arreglo el cual se almacena en la pila.
La siguiente función o método
void foo arrayallocation() {
int x;
int A[];
int B[];
A = new int [5];
B = new int [5];
/* Body of function */
}
La variable local x es almacenada en la pila,
igual que la dirección base del arreglo A y del
arreglo B.
Stack
FP
Heap
A[0]
x
A[1]
A
B
A[2]
A[3]
A[4]
Saved Registers
B[0]
B[1]
B[2]
SP
B[3]
B[4]
¿Cómo debemos representar
el arreglo A[3]
Memory
Operator(-)
Memory
Operator(-)
Register(FP)
Operator(*)
Constant(WORDSIZE)
Constant(WORDSIZE)
Constant(3)
¿ Y A[x] ?
Memory
Operator(-)
Memory
Operator(-)
Register(FP)
Operator(*)
Constant(WORDSIZE)
Constant(WORDSIZE)
Memory
Register(FP)
¿ Y para A[B[2]] ?
Memory
Operator(-)
Memory
Operator(-)
Operator(*)
Constant(WORDSIZE)
Memory
Operator(-)
Register(FP)
Constant(WORDSIZE)
Memory
Operator(-)
Register(FP)
Operator(*)
Constant(WORDSIZE)
Constant(2)
Constant(2*WORDSIZE)
Arreglos Multidimensionales se manejan de
manera similar.
Ejemplo:
void twoDarray {
int i;
int c [ ] [ ] ;
C = new int [3] [ ] ;
for (i=0; i<3; i++)
C[i] = new int[2] ;
/* Body of function */
}
El RA y el Heap se ven así:
Stack
FP
Heap
i
C[0]
C
C[1]
C[2]
Saved Registers
C[0] [0]
C[0] [1]
SP
C[1] [0]
C[1] [1]
C[2] [0]
C[2] [1]
La variable C sería representada así:
Memory
Operator(-)
Register(FP)
Constant(WORDSIZE)
La variable C[2] así:
Memory
Operator(-)
Memory
Operator(-)
Register(FP)
Operator(*)
Constant(WORDSIZE)
Constant(WORDSIZE)
Constant(2)
La variable c[2] [1]
Memory
Operator(-)
Memory
Operator(-)
Memory
Operator(-)
Operator(*)
Constant(WORDSIZE)
Operator(*)
Constant(WORDSIZE) Constant(2)
Register(FP) Constant(WORDSIZE)
Constant(1)
Variables Instanciadas
Son muy similares a las variables arreglo. La única diferencia es
que en las variables arreglo, el desplazamiento para el índice
necesita ser calculado, mientras que en las variables
instanciadas, el desplazamiento es conocido en tiempo de
compilación.
Ejemplo:
class simpleClass {
int x;
int y;
int A[ ];
}
void main() {
simpleClass();
s = new simpleClass();
s.A = new int[3]
/* Body of main */
}
¿Cuál es el árbol de ensamblador
para s.y ?
Memory
Él árbol de s:
Register(FP)
Para obtener y de s:
Memory
Operator(-)
Memory
Register(FP)
Constant(WORDSIZE)
El árbol de la variable s.x:
Memory
Memory
Register(FP)
El árbol para .A[3]:
Memory
Operator(-)
Memory
Operator(-)
Memory
Register(FP)
Operator(*)
Constant(WORDS Constant(3)
IZE)
Constant(2*WORD
SIZE)
Estatutos
•Estatutos de Asignación
<variable> = <expresión>
es representada por el árbol de ensamblador:
Move
<variable>
<expression>
Ejemplo:
Move
Void main() {
int x;
int y;
Memory
Operator(-)
Operator(+)
Memory
y = x + 4;
}
Register(FP)
Constant(4)
Register(FP)
Constant(4)
•Estatuto If
if (<test>) <estatuto1> else <estatuto2>
se puede traducir en
If (<test>) goto IFTRUE
<código para estatuto2>
goto IFEND
IFTRUE:
<código para estatuto1>
IFEND:
Y se representa con el árbol:
Sequential
ConditionalJump(“iftrue”)
<test>
Sequential
Sequential
<statement2>
Jump(“ifend”)
Sequential
Sequential
Label(“iftrue”)
Label(“ifend”)
<statement1>
•Estatuto while:
while (<test>) <estatuto>
se puede traducir en
WHILESTART:
if (not <test>) goto WHILEEND
<código de estatuto>
goto WHILESTART
WHILEEND:
aunque es mas eficiente
goto WHILETEST
WHILESTART:
<código de estatuto>
WHILETEST:
if (<test>) goto WHILESTART
WHILEEND:
•Estatuto for:
for (<initialize>;<test>;<increment>) <estatement>
es equivalent a:
<initialize>
while (<test>) {
<statement>
<increment>
}
Entonces queda como:
<initialize>
goto FORTEST
FORSTART:
<statement>
FORTEST:
<if (<test>) goto FORSTART
•Estatuto Return:
Cuando un estatuto return es ejecutado, el valor que
es retornado necesita salvarse en el registro
resultado, el registro de activación (RA) actual
necesita ser sacado de la pila (POP OFF) y el control
necesita ser retornado a la función llamadora. En
lugar de duplicar todo el código de ensamblador
abstracto para limpiar la pila por cada estatuto return,
podemos copiar el valor a ser retornado al registro
resultado y entonces saltar al final de la función,
donde una sola copia del código que limpia la pila
existe.
•Definiciones de Función o Métodos:
El ensamblador abstracto debe:
• Guardar el viejo SP, FP y registros de dirección de retorno en la pila.
• Apuntar el FP al inicio del RA actual.
• Apuntar el SP al final del RA actual.
• Incluir el ensamblador para el cuerpo de la función.
• Restaurar el viejo SP, FP y registros de dirección de retorno (el FP al último si se
usa para referenciar los datos en la pila).
• Retornar del método, con una instrucción de ensamblador abstracto return.
• Incluir etiquetas después del cuerpo para instrucciones return desde adentro del
cuerpo
El código ensamblador queda así:
<Etiqueta de inicio de el método>
<Código para asignar o meter el registro de activación>
<cuerpo de la función>
<Etiqueta del fin de método>
<Código para sacar el registro de activación>
<return>
Creación de Árboles de Ensamblador
Abstracto (AAT) en Java



Para construir AAT en Java, primero
definimos una interfase para construir AATs
para estatutos y para expresiones.
Entonces, se agregan en el análisis
semántico llamadas a las funciones definidas
en la interfase.
De esta forma, el analizador semántico
construirá los AATs al igual que checará por
los errores semánticos.
Etiquetas
Se necesitan tanto para las llamadas a métodos como para los
“if” y los ciclos “while” y “for”. La siguiente clase nos genera
etiquetas únicas (ifEnd001,ifEnd02,etc.) y etiquetas específicas
(llamadas a métodos).
import java.util.Hashtable;
class Label {
protected String label;
private static HashTable labelhash;
Integer last;
Int next;
public Label(String s) {
if (labelhash == null) {
labelhash = new HashTable(199);
}
last = (Integer) labelhash.find(s);
If (last == null) {
next = 1;
labelhash.insert(s, new Integer(1));
label = s + 1;
} else {
next = last.intValue() + 1;
labelhash.delete(s);
labelhash.insert(s, new Integer(next));
label = s + next;
}
}
public static Label AbsLabel(String s) {
Label abslab = new Label();
abslab.label = s;
return abslab;
}
public String toString() {
return label;
}
Interfase para Construir Árboles de
Ensamblador Abstracto
import java.util.Vector;
public interface AATBuildTree {
public AATSatement functionDefinition(AATStatemen body, int framesize, Label start, Label end);
public AATSatement ifStatement(AATExpression test, AATStatement ifbody, AATStatement elsebody);
public AATEexpression allocate(AATExpression size);
public AATStatement whileStatement(AATExpression test, AATStatement increment, AATStatemen body);
public AATStatement emptyStatement( ) ;
public AATStatement callStatement(Vector actuals, Label name);
public AATStatement assignmentStatement(AATExpression lhs, AATExpressionrhs);
public AATStatement sequentialStatement(AATStatement first, AATStatement second);
public AATExpression baseVariable(int offset);
public AATExpression arrayVariable(AATExpresion base, AATExpression index, int elementSiza);
public AATExpression classVariable(AATExpression(AATExpression base, int, offset);
public AATExpression constantExpression(int, value);
public AATExpression operatorExpression(AATExpression left, AATExpression rigth, int operator);
public AATExpression callExpression(Vector actuals, Label name);
public AATStatement returnStatement(AATExpression value, Label functioned);
}
EJEMPLOS:
void foo(int a) {
int b;
int c;
if (a > 2)
b = 2;
else
c = a+ 1;
}
Sea bt una instancia de una clase que implementa la interfase AATBuildTree, y sea 4 el
tamaño de la palabra de la máquina.
El árbol de ensamblador abstracto para la expresión (a > 2) en la función foo podría crearse
con:
AATExpression e1;
e1 = bt.operatorExpression(bt.baseVariable(4),
bt.constantExpression/(2),
AATOperator.GREATER_THAN);
Igual, el ensamblador abstracto para el estatuto b = 2; y c = a + 1, puede crearse con:
AATEstatement s1, s2;
s1 = bt.assignmentStatemen(bt.baseVariable(0), bt.constantExpression(2));
s2 = bt.assignment(bt.BaseVariable(-4), bt.operatorExpression(bt.baseVariable(4), bt.constantExpression(1),
AATOperator.PLUS));
Finalmente, dadas las definiciones anteriores, el ensamblador abstracto para el estatuto
if (a > 2) b = 2 else c = a + 1; puede crearse con:
AATstatement s3;
s3 = bt.ifStatement(e1,s1,s2);
Algunas de las funciones para construír árboles de
ensamblador abstracto pueden explicarse mejor:
•
public AATSatement functionDefinition(AATStatemen body, int framesize, Label
start, Label end); El árbol de ensamblador para definición de funciones comienza
con la etiqueta para la función, seguido de una serie de instrucciones para salvar los
valores viejos de la dirección de retorno, los registros FP y SP, seguido del código
para poner nuevos valores del FP y SP, seguido del cuerpo de la función, seguido
por una etiqueta para el final de la función, seguido del código para restaurar los
valores viejos de la dirección de retorno, registros FP y SP, seguido de un estatuto de
ensamblador abstracto return, para regresar el flujo de control a la función llamadora.
•
public AATStatement returnStatement(AATExpression value, Label functioned);
El árbol de ensamblador para un estatuto return copia el valor del estatuto return
dentro de el registro resultado y después salta a la etiqueta del final de la función.
•
public AATEexpression allocate(AATExpression size); Esta función es llamada
por medio de una expresión new, para asignar espacio en el heap. Es implementada
por una llamada a la función intrínseca (build-in) que asigna espacio- igual que una
función input/output son implementadas por medio de llamadas a funciones
intrínsecas. La función allocate toma un solo parámetro – el tamaño (en bytes) del
espacio a asignar – y retorna un apuntador al bloque nuevo asignado.
Modificaciones al Analizador Semántico


En lugar de crear un módulo separado que
recorra el AST de nuevo para construir un
AAT, se modifica el analizador semántico
para que mientras checa la semántica vaya
construyendo el AAT.
Cada uno de los métodos para visitar
expresiones y estatutos en el analizador
semántico retornará dos piezas de
información en lugar de una – el tipo del
subárbol, como antes, mas un AAT que
representa la expresión o el estatuto.
Ejemplo:
Para analizar un AST:
Integer_Literal(3)
El analizador semántico actualmente retorna IntegerType.
Para analizar el AST:
+
Integer_Literal(3)
Integer_Literal(4)
El analizador semántico llama al método accept para cada subárbol – constant(3)
y constant(4), se asegura que ambos sean enteros, y retorne un entero. Después
de modificar el analizador semántico para producir AATs, cunado se analiza el
AST:
Integer_Literal(3)
El analizador retornará dos valores: Integer_Type y bt.constantExpression(3).
Cuando se analiza el AST:
+
Integer_Literal(3)
Integer_Literal(4)
Primero se llama el método accept de los subárboles, se asegura que los
tipos sean enteros y entonces construye una expresión operador basado en
los valores de los subárboles (usando una llamada al método
operatorExpression en la interfase AATBuildTree).
VIII Generación de Código



La función de un generador de código es
básicamente la traducción de la salida del análisis
sintáctico y semantico (el código intermedio) a una
secuencia equivalente de instrucciones que pueden
ejecutarse en la maquina destino.
El código debe ser correcto y optimo.
El generador de código toma las desiciones
básicas:


Asignar Registros.- Registros generales, Prop. Específicos,
pares, impares, registros índices, etc.
Selección de Instrucciones.- La mejor secuencia de
instrucciones (la optima). Por ejemplo elegir INC en lugar
de MOV – ADD.

En el caso de nuestro compilador, una vez que se ha creado un
árbol de ensamblador, el próximo paso es crear código
ensamblador para una máquina específica.

Generaremos código ensamblador por medio de usar “tiles” para
rellenar huecos, con el árbol de ensamblador abstracto.

Vamos a crear un conjunto de “tiles” o rellenos cada uno de los
cuales pueden cubrir una porción pequeña de un árbol de
ensamblador abstracto.

Para generar el ensamblador real para un árbol de ensamblador
específico, primero cubriremos el árbol con “tiles”, asegurándose
que todas las partes del árbol estén cubiertas y que no existan
“tiles” traslapados. Después, se producirá el ensamblador
asociado con cada “tile”.
Código Ensamblador Objeto
Usaremos un subconjunto del ensamblador para MIPS
Instruction
Description
lw rt, <offset> (base)
Add the constant value <offset> to the register base to get an address. Load the contents of this address into the
register rt. Rt = M[base + <offset>]
sw rt, <offset> (base)
Add the constant value <offset> to the register base to get an address. Store the contents of rt into this address.
M[base + <offset>] = rt
add rd, rs, rt
Add contents of register rs and rt, put result in register rd.
sub rd, rs, rt
Subtract contents of register rt from rs, put result in register rd.
addi rt, rs, <val>
Add the constant value <val> to register rs, put result in register rt.
mult rs, rt
Multiply contents of register rs by register rt, put the low order bits in register LO and the high bits in register HI
div rs, rt
Dive contents of register rs by register rt, put the quotient in register LO and the remainder in register HI
mflo rd
Move contents of the special register LOW into the register rd.
j <target>
Jump to the assembly label <target>.
jal <target>
jump and link. Put the address of the next instruction in the return register, and then jump to the address <target>.
Used for function and procedure calls.
jr rs
Jump to the address stored in register rs. Used in conjunction with jal to return from function and procedure calls
slt rd, rs, rt
if rs < rt, rd = 1, else rd = 0
beq rs, rt, <target>
if rs == rt, jump to the label <target>
bne rs, rt, <target>
if rs ≠ rt, jump to the label <target>
bltz rs, <target>
if rs < 0, jump to the label <target>
Bgez rs, <target>
if rs ≥ 0, jump to the label <target>
Register that we will use for code generation
Mnemonic
Name
SPIM
Name
Description
$FP
$fp
Frame pointer – points to the top of the current activation record
$SP
$sp
Stack Pointer – Used for the activation record stack
$ESP
$esp
Expression Stack Pointer – The next expression stack holds temporary values for
expression avaluations
$result
$v0
Result Register – Holds the return value for functions
$return
$ra
Result Register – Holds the return address for the current function
$zero
$zero
Zero register – This register always has the value 0
$ACC
$t0
Accumulator Register – Used for expressioncalculation
$t1
$t1
General Purpose Register
$t2
$t2
General Purpose Register
$t3
$t3
General Purpose Register
Tiling Simple







Usaremos una pila para guardar valores temporales en
expresiones. Esta pila estará además de la pila normal de RA.
Primero describiremos una forma de producir código ineficiente.
Después veremos como producir código mas eficiente.
Tiling simple está basado en un recorrido post-order del árbol de
ensamblador abstracto.
Esto es, después de cubrir el árbol con tiles, emitiremos código para
cada tile en una forma post-order.
Primero emitiremos recursivamente tiles para cada uno de los subárboles del árbol de ensamblador, de izquierda a derecha.
Después, emitiremos el código para el tile de la raíz del árbol.
Ejemplos:
Tiling Simple para Árboles de Expresiones.
El código asociado con el tile colocará el valor de la expresión en el tope de la
pila de expresiones.
Expresiones de Constantes
Considere el siguiente árbol:
Constant(5)
El código asociado con este tile necesita poner un 5 en el tope de la pila de
expresiones.
addi $t1, $zero, 5
sw $t1, 0($ESP)
addi $ESP, $ESP, -4
% Load the constant value 5 into the register $t1
% Store $t1 on the top of the expression stack
% Update the expression stack pointer
En general, el tile para cualquier valor constante x es:
addi $t1, $zero, x
sw $t1, 0($ESP)
addi $ESP, $ESP, -4
% Load the constant value into x the register $t1
% Store $t1 on the top of the expression stack
% Update the expression stack pointer
Operaciones de Aritmética Binaria
+
Constant(3)
Constant(4)
En lugar de tratar de cubrir todo el árbol con un tile, usaremos tres. La
constante 4 y 5 pueden cubrirse cada una con un tile de constante, y
usaremos un tile “+” para cubrir la suma.
+
Constant(3)
Constant(4)
¿Cómo debe ser el código para +?
Recordemos que emitimos código en post-order (subárbol
izquierdo, subárbol derecho y luego raíz). Podemos asumir
que los valores de los operandos de la izquierda y la
derecha de el + ya están en la pila cuando el código de el tile
+ es emitido. Ntonces, todo lo que necesitamos es hacer es
sacar (pop off) esos valores , hacer la suma y meter (push)
el resultado de regreso a la pila. El código para el tile + es:
lw $t1, 8(ESP)
% Load the first operand into temporary $t1
lw $t2, 4(ESP)
% Load the second operand into temporary $t2
add $t1, $t1, $t2
% Do the addition. Storing result in $t1
sw $t1, 8(ESP)
% Store the result on the expression stack
add $ESP, $ESP, 4
% Update the expression stack pointer
y el código para toda la expresión es:
addi $t1, $zero, 3
% Load the constant value 3 into the register $t1
sw
% Store $t1 on the top of the expression stack
$t1, 0($ESP)
addi $ESP, $ESP, -4
% Update the expression stack pointer
addi $t1, $zero, 4
% Load the constant value into 4 the register $t1
sw
% Store $t1 on the top of the expression stack
$t1, 0($ESP)
addi $ESP, $ESP, -4
%Update the expression stack pointer
lw
$t1, 8($ESP)
% Load the first operand into temporary $t1
lw
$t2, 4($ESP)
% Load the second operand into temporary $t2
add $t1, $t1, $t2
% Do the addtion, storing result in $t1
sw
% Update the expression stack pointer
$t1, 8(ESP)
Registros
Considere el árbol de expresión
Register(FP)
Esto ocupa un tile.
sw $FP, 0($ESP)
addi $ESP, ESP, -4
Combinando otros tiles discutidos antes, el árbol
Register(FP)
Constant(8)
Puede ser los tiles:
Register(FP)
Constant(8)
Produciendo el árbol
sw
$FP, 0($ESP)
% Store frame pointer on the top of the expression stack
addi $ESP, $ESP, -4
% Update the expression stack pointer
addi $t1, $zero, 8
% Load the constant value 8 into the register $t1
sw
% Store $t1 on the top of the expression stack
$t1, 0($esp)
addi $ESP, $ESP, -4
% Update the expression stack pointer
lw
$t1, 8($ESP)
% Load the first operand into temporary $t1
lw
$t2, 4($ESP)
% Load the second operand into temporary $t2
sub $t1, $t1, $t2
% Do the subtraction, storing result in $t1
sw
% Store the result on the expression stack
$t1, 8($ESP)
add $ESP, $ESP, 4
% Update the expression stack pointer
Operaciones relacionales
ARBOL ABSTRACTO:
>
Constant(3)
Constant(4)
TILES:
>
Constant(3)
Constant(4)
El código para > es:
lw
lw
slt
sw
addi
$t1, 8($ESP)
$t2, 4($ESP)
$t1, $t2, $t1
$t1, 8($ESP)
$ESP, $ESP, 4
Thus, one posibility for the code for the == tile is:
lw
lw
slt
slt
add
sub
addi
sw
addi
$t1, 8($ESP)
$t2, 4($ESP)
$t3, $t2, $t1
$t2, $t1, $t2
$t1, $t1, $t2
$t1, $zero, $t1
$t1, $t1, 1
$t1, 8($ESP)
$ESP, $ESP, 4
% $t3 = (x < y)
% $t2 = (y < x)
% $t1 = (x < y) I I (y <x)
%
%
Acceso a Memoria
Un nodo en memoria es solo un “dereferencia” a memoria (indexamiento). Entonces, el
código de un nodo en memoria es:
Lw $t1, 4 ($ESP)
lw $t1, 0($t1)
sw $t1, 4($ESP)
% Pop the address to dereference off the top of the
% expression stack
% Dereference the pointer
% Push the result back on the expression stack
Ejemplo: El árbol de expresión
Para una variable simple es.
Memory
Register(FP) Constant(12)
Los tiles son:
Memory
Register(FP) Constant(12)
Que resulta en el siguiente ensamblador:
sw
$FP,
0($ESP)
% Store frame pointer on the top of the expression stack
addi $ESP, $ESP, -4
% Update the expression stack pointer
addi $t1,
$zero, 12
% Load the constant value 12 into the register $t1
sw
$t1,
0($ESP)
% Store $t1 on the top of the expression stack
addi
$ESP, $ESP, -4
% Update the expression stack pointer
lw
$t1,
4($ESP)
% Load the first operand into temporary $t1
lw
$t2,
8($ESP)
% Load the second operand into temporary $t2
sub
$t1,
$t1,
% Do the subtraction, storing result in $t1
sw
$t1,
8($ESP)
add
$ESP, $ESP, 4
% Update the expression stack pointer
lw
$t1,
% Pop the address to dereference off the top of
$t2
$4($ESP)
% Store the result on the expression stack
% the expression stack
lw
$t1,
$0($t1)
% Dereference the pointer
sw
$t1,
4($ESP)
% Push the result back on the expression stack
El resultado de este código es: El valor que estaba en memoria (FP – 12) es empujado (pushed onto)
en el tope de la pila de expresiones.
Llamadas a Funciones
Para implementar una llamada a función, necesitamos primero copiar
todos los parámetros de la función en el tope de la pila de llamadas
(opuesta a la pila de expresiones), y después saltar al inicio de la función.
Cuando la función regresa, necesitamos sacar los argumentos del tope de
la pila de llamadas, y meter el valor de retorno de la función al tope de la
pila de expresiones.
Ejemplo: Considere el siguiente árbol de expresión, el cual resulta de la
llamada a función foo(9,3).
Call(“Foo”)
Constant(9)
Constant(3)
Call(“Foo”)
Constant(9)
Constant(3)
El lenguaje ensamblador asociado con el tile Call es:
lw
$t1
4($ESP)
% Pop the first argument off the expression stack
sw
$t1
0($Sp)
% Store first argument on the call stack
lw
$t1
8($ESP)
% Pop second argument off the expression stack
sw
$t1
-4($SP)
% Store second argument on the call stack
addi
$SP,
$SP, -8
% Update call stack pointer
addi
$ESP,
$ESP, 8
% Update expression stack pointer
jal
foo
addi
$SP,
sw
$result, 0($ESP)
Addi
$ESP,
% Make the finction call
$SP, 8
% Update call stack pointer
% Store result of function on expression stack
$ESP, -4 % Update expression stack pointer
Así, el ensamblador para todo el árbol de expresión es:
addi
$t1
sw
addi
addi
$t1
sw
addi
lw
stack
sw
lw
stack
sw
addi
addi
jal
addi
sw
addi
$t1,
$zero, 9
% Load the constant value 9 into the register
$t1,
$ESP,
$t1,
0($ESP)
% Store $t1 on the top of the expression stack
$ESP, -4 % Update the expression stack pointer
$zero, 3
% Load the constant value into 3 the register
$t1,
$ESP,
$t1
0($esp)
% Store $t1 on the top of the expression stack
$ESP, -4 % Update the expression stack pointer
4($ESP)
% Pop the first argument off the expression
$t1
$t1
0($SP)
8($ESP)
$t1
$SP,
$ESP,
foo
$SP,
$result,
$ESP,
-4($ESP)
$SP, -8
$ESP, 8
% Store first argument on the call stack
% Pop second argument off the expression
% Store second argument on the call stack
% Update call stack pointer
% Update expression stac pointer
% Make the function call
$SP, 8
% Update call stack pointer
0($ESP)
% Store result of function on expression stack
$ESP, -4 % Update expression stack pointer
Tiles de Árboles de Estatutos
Mientras que el código de ensamlador para árboles de expresiones
mete (push) el valor de la expresión en el tope de la pila de
expresiones, el código ensamblador para árboles de estatutos
implementa el estatuto descrito por el árbol.
Árboles de Etiquetas
El subárbol Label(“label1”) puede ser cubierto con solo un tile. El
código para ese tile es:
Label1:
Árboles para Move
El lado izquierdo de un MOVE necesita que sea un registro o una
localidad de memoria.
Ejemplo:
Move
Register(r1)
Constant(8)
Será dividido en los tiles:
Move
Register(r1)
Constant(8)
Considere el tile del MOVE registro:
Move
Register(r1)
Cuando el código para este tile es ejecutado, el valor que es cargado
al registro está ya en el tope de la pila de expresiones. Entonces, todo
lo que necesitamos hacer es sacar el valor de la pila de expresiones y
meterlo al registro.
El tile del MOVE tiene el siguiente código asociado:
lw
$r1,
4($ESP)
% load the rhs of the move into a register
addi
$ESP,
$ESP, 4
% update expression stack pointer
Todo el código para el árbol es:
addi
$t1,
$zero, 8
% Store the constant 8 in a register
sw
$t1,
0($ESP)
% Push the value on the expression stack
addi
$ESP,
$ESP, -4 % Update the expression stack pointer
lw
$r1,
4($ESP)
% load the rhs of the move into a register
addi
$ESP,
$ESP, 4
% update expression stack pointer
Veamos ahora un MOVE a memoria. Consideremos el siguiente árbol:
Move
Memory
Constant(4)
Register(FP)
El árbol puede tener los tiles:
Move
Constatnt(4)
Mem
Register(FP)
El tile MOVE a memoria es:
Move
Necesita sacar dos valores del tope de la pila – el destino del MOVE y
el valor a almacenarse.
lw
$t1,
8($ESP)
lw
$t2,
4($ESP)
sw
$t2,
0($t1)
addi
$ESP,
$ESP, 8
Todo el árbol se puede implementar con el sig. Código:
sw
$FP
0($ESP)
addi
$ESP,
$ESP, -4
addi
$t1,
$ZERO, 4
sw
$t1,
0($ESP)
addi
$ESP,
$ESP, -4
lw
$t1,
8($ESP)
lw
$t2,
4($ESP)
sw
$t2,
0($t1)
Addi
$ESP,
$ESP, 8
Árboles para Estatutos Jump
Estatutos árbol como Jump(“label”) se pueden realizar con un solo tile:
j label
Árboles para Jump condicional
Considere el siguiente árbol de estatuto:
CondJump(“jumplab”)
<
Constant(3)
Constant(4)
Podemos crear los siguientes tiles:
Tile 4
CondJump(“jumplab”)
Tile 3
<
Tile 1
Constant(3)
Tile 2
Constant(4)
El código que emitimos para el subárbol de la expresión jump
condicional pone el valor de la expresión en el tope de la pila de
expresiones. Asi, necesitamos sacar la expresión del tope de la pila de
expresiones, y saltar a la etiqueta “jumplab” si la expresión es
verdadera. Todo el estatuto se implementa con el código:
addi
sw,
addi
addi
sw
addi
lw
lw
slt
sw
addi
bgtz
$t1,
$t1,
$ESP,
$t1,
$t1,
$ESP,
$t1,
$t2,
$t1,
$t1,
$ESP,
$t1,
$zero, 3
0($ESP)
$ESP, -4
$zero, 4
0($ESP)
$ESP -4
8($ESP)
4($ESP)
$t1, $t2
8($ESP)
$ESP, 4
jumplab
% salta a jumplab si $t1 es mayor a cero
Árboles de Secuencias
¿Qué hacemos después que creamos el código del árbol de la parte
izquierda y el árbol de la parte derecha? ¡nada! No existe código
asociado pues los dos árboles son ya traducidos.
Estatutos Call
Son muy similares a las llamadas a funciones. La única diferencia es
que en el call no existe resultado en el return. Esto significa que
después que termina el procedimiento, no necesitamos copiar el
resultado a la pila de expresiones.
Unidad VII
Optimización
7.1 Tipos de Optimización






Idealmente, los compiladores deben producir código objeto tan
bueno como el producido a mano por un programador experto.
En la realidad, este objetivo raramente es alcanzado.
Sin embargo, el código puede ser mejorado en tiempo y espacio
usando algoritmos eficientes.
Mejorar el código por un compilador es llamado optimización
del código, aunque el término optimizar no es el adecuado (mas
bien mejorar).
Los tipos de optimización de un compilador pueden ser: Locales,
Globales y de Bucles.
También los tipos de optimización se pueden dividir en
independientes y dependientes de la máquina.
Introducción
•Objetivo: Mejorar cód. objeto final,
preservando significado del programa
•Factores a optimizar :
velocidad de ejecución
tamaño del programa
necesidades de memoria
•Se sigue una aproximaci´on conservadora
•! No se aplican todas las posibles
optimizaciones, solo las “seguras”
Clasificación de las optimizaciones
1. En función de la dependencia de la arquitectura
Dependientes de la máquina:
• Aprovechan características específicas de la
máquina objetivo
• asignación de registros, uso de modos de
direccionamiento
• uso instrucciones especiales (IDIOMS)
• relleno de pipelines, predicción de saltos,
aprovechamiento estrategias de mem. caché, etc..
Independientes de la máquina:
• Aplicables en cualquier tipo de máquina objetivo
• ejecución en tiempo de compilaci´on
• eliminación de redundancias
• cambios de órden de ejecución, etc..
Descargar

CURSO: PROGRAMACION DE SISTEMAS