resumen de compilación preparado por manuel e. bermúdez, ph.d. associate professor university of...
Post on 23-Jan-2016
219 Views
Preview:
TRANSCRIPT
Resumen de Compilación
Preparado por
Manuel E. Bermúdez, Ph.D.Associate Professor
University of Florida
Traducido por Christian Torres
Universidad Ricardo Palma, Perú
Curso de Compiladores
Resumen de Traducción
• Definición: Un traductor es un algoritmo que convierte un código fuente en un programa objeto equivalente.
• Definición: Un compilador es un traductor donde el lenguaje objeto está un nivel “más bajo” que el lenguaje del código fuente.
TraductorCodigo Fuente
Programa Objeto
Resumen de Traducción (cont.)
• ¿ Cuándo es el nivel de un lenguaje menor que otro ?
• Definición: Un interpretador es un algoritmo que simula la ejecución de programas escritos en un determinado lenguaje fuente.
InterpretadorFuente
entrada
salida
Resumen de Traducción (cont.)
• Definición: La implementación de un lenguaje de programacion consiste de un traductor (o compilador) para ese lenguaje, y un interpretador para el correspondiente lenguaje objeto.
InterpretadorObjeto
entrada
salida
CompiladorFuente
Traducción• Un programa fuente puede ser traducido un
número arbitrario de veces antes que el programa objeto sea generado.
Traductor1
Fuente
Traductor2
TraductorN
Objeto
...
Traducción (cont.)
• Cada una de estas traducciones es llamada una fase, no se debe confundir con una pasada, i.e. una escritura al disco.
P: ¿ Cómo debiera ser divido en fases un compilador?
R: De manera que cada fase pueda ser descrita por un modelo formal de computación, y realizar la fase eficientemente.
Traducción (cont.)
P: ¿ Cómo se divide usualmente un compilador?
R: En 2 fases principales, con varias posibilidades de subdivisión.• Fase 1: Análisis (determina correctitud)• Fase 2: Síntesis (produce código objeto)
• Otros criterios:• Fase 1: Sintaxis (forma).• Fase 2: Semántica (significado).
División tipica de un compilador
• Scanning (Análisis lexico).• Objetivo: Agrupar secuencia de caracteres
que ocurren en la fuente, en unidades lógicas atómicas llamadas tokens.
• Ejemplos de tokens: Identificadores, palabras reservadas, enteros, hileras, signos de puntuación, “espacios en blanco”, caracteres de fin de línea, comentarios, etc., …
Scanner (Analizador Léxico)
Fuente
Secuenica de Tokens
Análisis Léxico
• Se debe tratar con carateres fin de línea y fin de archivo (end-of-file).
• Se hace una clasificación preliminar de tokens. Por ejemplo, ‘program’ y ‘Ex’ son clasificados como identificadores.
• Se tiene que dar reglas no-ambiguas para la formación de tokens.
• Ejemplo:
Filtraje (Screening)
• Objetivo:• Remover los tokens no deseados.• Clasificar las palabras reservadas.• Unir/simplificar tokens.
Screener
Secuencia de Tokens
Secuencia de Tokens
Filtraje (Screening)
• Reconoce (y reclasifica) palabras reservadas.
• Descarta espacios en blanco (y comentarios).
• Actua como una interfaz entre el “scanner” y la siguiente fase, el “parser” (analizador sintáctico).
• Ejemplo:
Análisis sintactico (Parsing)
• Objetivos:
• Determinar si la secuencia de tokens es sintácticamente correcta.
• Agrupar los tokens, en una estructura sintáctica correcta (árbol), de ser posible.
Análisis sintáctico (cont.)
• Estructura sintáctica de programas:
• Expresiones• Declaraciones• Procedimientos• Funciones• Módulos
• Metodología:• Usar “reglas de reescritura” (a.k.a. BNF).
Traducción hilera-a-árbol
• Objetivo: Construir un “árbol de sintaxis” a partir de una secuencia de reglas BNF. El árbol será la representación funcional del programa fuente.
• Método: Construir el árbol de abajo hacia arriba (“bottom-up”), conforme se utilizan las reglas de re-reescritura. Se hace uso de una pila de árboles.
• Ejemplo:
Análisis de Restricciones Contextuales
• Objetivo: Analizar la semántica estática, ej.,
• ¿ variables declaradas antes de ser usadas ?• ¿ Compatibilidad de tipos en la asignación ?
• ej, a:=3• ¿ Compatibilidad de tipos en la operación ?
• ej, a+3• Coinciden los tipos de parámetros formales y
actuales?• Aplicación de las reglas de visibilidad.
Análisis de Restricciones Contextuales
(cont.)
• Método: Se recorre el árbol recursivamente, deduciendo el tipo de cada (sub)expresión, y regresando ee tipo.
• Se hacer uso de una TABLA DE DECLARACIONES, para grabar informacion acerca de los nombres.
• Se “decora” el árbol con información de referencia.
Ejemplo
Cronológicamente,
– Se ingresa x en la tabla DCLN, con su tipo.– Se revisa la compatibilidad de tipo para x = 5.– X2 no esta declarado!– Se verifica que el tipo de ’>’ es booleano.– Se revisa la compatibilidad de tipo para ‘+’.– Se revisa la compatibilidad de tipo entre Id:x y
int:1 (nodo ‘+’).
Generación de Código
• Objetivo: Convertir el árbol de sintaxis a código objeto.
El código objeto podria ser:
• Lenguaje de máquina.• Lenguaje ensamblador.• Cuádruples para una máquina ficticia:
• Etiqueta• Cógo de operación• Operandos (1 o 2)
Generación de Código (cont.)
• Ejemplo: • “pc” en UNIX genera código ensamblador.• “pi” en UNIX genera código para la máquina
“p”, que es interpretado por… un interpretador.
• pc: Cómpilación lenta, ejecución rápida.• pi: Compilacion rápida, ejecución lenta.
• Método: Recorrer el árbol otra vez.
Código (para una máquina de pila)
LOAD 5STORE X
LOAD XLOAD 10BGTCOND L1 L2
L1 LOAD XLOAD 1BADDSTORE XGOTO L3
L2 . . .L3
Optimización de Código
• Objetivo:• Reducir el tamaño del programa objeto.• Disminuir el tiempo de ejecución del objeto.
• Nota: “Optimización” es un nombre incorrecto. “Mejoramiento”, sería màs adecuado.
• Dos tipos de optimización:
• Optimización “Peephole” (local).• Optimización Global (Mejorar iteraciones,
etc.).
Optimizacion de Codigo (cont.)
• Ejemplo (de la diapositiva anterior):
LOAD 5 se puede LOAD 5
STORE X reemplazar STND X
LOAD X con
Almacenamiento no-destructivo, i.e., almacena en X, pero no destruye el valor superior de la pila.
Resumen
Sintáctico
Fuente
Restrictor
Generador de código
Código
Interpretador
Filtro
Léxico
Entrada Salida
Manejo de Tablas
Rutinas de Errores
Tokens
Tokens
Arbol
Arbol
Resumen de Compilación
Preparado por
Manuel E. Bermúdez, Ph.D.Associate Professor
University of Florida
Traducido por Christian Torres
Universidad Ricardo Palma, Perú
Curso de Compiladores
top related