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 5 STORE X LOAD X LOAD 10 BGT COND L1 L2 L1 LOAD X LOAD 1 BADD STORE X GOTO 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
| Página siguiente |