Materia	Carrera	Plan	Año	Periodo
DISEÑO Y CONSTRUCCION DE COMPILADORES	LIC. CS. COMP.	006/05	4	2c

Docente	Función	Cargo	Dedicación
ESQUIVEL, SUSANA CECILIA	Prof. Responsable	P.TIT EXC	40 Hs
BERON, MARIO MARCELO	Responsable de Práctico	JTP EXC	40 Hs
ARAGON, VICTORIA SOLEDAD	Auxiliar de Práctico	A.1RA SIM	10 Hs

El diseño y construcción de compiladores deben formar parte del conocimiento general de un Licenciado en Ciencias de la Computación, con el perfil requerido por el correspondiente plan de estudios.
Esta materia profundiza los conocimientos introductorios dados en la materia Análisis Comparativo de Lenguajes y aplica conceptos ya adquiridos en Autómatas y Lenguajes.
Además las técnicas involucradas en la construcción de un compilador pueden aplicarse en el ámbito del desarrollo de software de base como en el desarrollo de software de aplicación.
Los contenidos del curso se corresponden con las propuestas curriculares recomendadas por la ACM/IEEE Computer Society Joint Curriculum Task Force en 2001, para el área de compiladores.

Desarrollar en el alumno la capacidad de diseñar e implementar un compilador para un subconjunto del Lenguaje de Programación C++.

BOLILLA 1: INTRODUCCION


Concepto y tipos de traductores. Compiladores de una o más pasadas.Estructura Clásica de un Compilador: Modelo de Análisis y Síntesis de un compilador. Sintaxis y Semántica.


BOLILLA 2: ANALIZADOR LEXICOGRAFICO O SCANNER


Breve recapitulación de los conceptos fundamentales.


BOLILLA 3: TABLA DE SIMBOLOS


Finalidad. Entradas de la tabla de símbolos. Descripción de objetos en la tabla de símbolos. Tratamiento de nombres de longitud fija y variable. Posibles implementaciones: lista, hash, árbol, otras. Representación de la información sobre tipos. Manipulaciones básicas. Control de bloques y de amplitud.


BOLILLA 4: PARSING TOP DOWN DETERMINISTICO


Definiciones de gramáticas LL(k) y LL(k) fuerte. Condición de LL(k) fuerte. Conjuntos FIRSTk, FOLLOWk, algoritmos de construcción de dichos conjuntos. Teoremas Fundamentales. Análisis top down por medio de tablas para k = 1. Análisis sintáctico top-down por el método recursivo descendente. Generalidades. Algoritmos de implementación de un parser descendente recursivo.


BOLILLA 5: DETECCION Y RECUPERACION DE ERRORES


Errores en las etapas lexicográfica, sintáctica, semántica y de ejecución. Esquema de recuperación de errores en entornos de parsing top-down.


BOLILLA 6: AMBIENTES DE TIEMPO DE EJECUCION


Revisión de las características básicas de los lenguajes de programación. Representación de tiempo de ejecución de objetos computacionales estáticos, semidinámicos y dinámicos. Organización de la memoria en tiempo de ejecución. Administración dinámica de la memoria como stack: activación de procedimientos, referenciación local, registros de activación, referenciación global, vector display. Administración dinámica de la memoria como heap: organización, administración del heap con elementos de tamaño fijo y variable, asignación inicial y reuso.


BOLILLA 7: REPRESENTACIONES INTERMEDIAS DE LOS PROGRAMAS FUENTES


Notación polaca, de n-uplas, de árboles de sintaxis abstracta. Código de máquina abstracta. Portabilidad.


BOLILLA 8: SISTEMA DE EJECUCION BASICO Y EXTENDIDO


Representación interna de los objetos en tiempo de ejecución: lógicos, caracteres, enteros, reales, arreglos. Análisis y traducción de expresiones aritméticas y lógicas, asignaciones, estructuras de control a nivel de sentencias, entrada-salida, estructuras de control a nivel de procedimientos, pasaje de parámetros por dirección y por valor. Referenciación global y local. Variables subindicadas: acceso, pasaje de arreglos y elementos de arreglos como parámetros.


BOLILLA 9: TRADUCCION DIRIGIDA POR LA SINTAXIS


Definiciones dirigidas por la sintaxis: atributos, atributos sintetizados y heredados, forma general de una definición dirigida por la sintaxis, grafo de dependencia de atributos. Definiciones S-atribuidas: traductores bottom up. Definiciones L-atribuidas. Esquemas de traducción dirigidos por la sintaxis. Restricciones para el cálculo de los valores de los atributos. Implementación de definiciones L-atribuidas en un entorno de parser top down. Eliminación de recursividad a izquierda en los esquemas de traducción. Parsing descendente recursivo que implementa definiciones L-atribuidas.


BOLILLA 10: CONTROL DE TIPOS


Introducción. Expresiones de tipo. Sistema de tipos. Salvaguarda de información del tipo asociado a los identificadores. Chequeo de tipo de expresiones y sentencias. Equivalencia de expresiones de tipo estructural.


BOLILLA 11: GENERACION DE CODIGO INTERMEDIO


Ubicación del generador de código dentro del proceso de compilación. Esquemas de traducción dirigidos por la sintaxis para la generación de código intermedio para expresiones, asignaciones, estructuras de control a nivel de sentencias y unidades. Generación de código intermedio embebido en un parser descendente recursivo.

1. Plan de trabajos prácticos de aula


PRACTICO 1: Tabla de Símbolos.

PRACTICO 2: Gramáticas LL(k).

PRACTICO 3: Parsing Descendente Recursivo.

PRACTICO 4: Recuperación de errores.

PRACTICO 6: Sistema de Ejecución Básico.

PRACTICO 7: Soporte de Tiempo de Ejecución.

PRACTICO 8: Traducción dirigida por la sintaxis en entorno top down.

PRACTICO 9: Chequeo de tipos y Generación de Código.

2. Plan de trabajos prácticos de laboratorio


1. Completar unidad de Tabla de Símbolos.
2. Completar código del parser descendente recursivo.
3. Diseño e implementación de un esquema de recuperación de errores.
4. Diseño e implementación de un chequeador de tipos.
5. Generación de código en una representación intermedia.

F.1. Regimen para alumnos regulares

Para regularizar la materia los alumnos deberán aprobar:

1.Los prácticos de programación propuestos (fuente y ejecutable) y/o su correspondiente recuperación en las fechas estipuladas a tal efecto. La no aprobación de un trabajo práctico de máquina y/o su recuperación implicará la pérdida automática de la regularidad de la materia.
2.Un examen parcial práctico o su respectiva recuperación, con un porcentaje de ejercicos correctos del 70%.
3. Aquellos alumnos que han presentado, en tiempo y forma, el comprobante de trabajo, contarán con una recuperación adicional.

F.2. Los alumnos que han regularizado la materia para aprobarla deberán rendir un examen final que podrá ser escrito u oral.

F.3. Regimen de alumnos libres

Dadas las características de los trabajos prácticos de máquina durante el desarrollo de la materia y la imposibilidad de suplantarlos por un único práctico de examen libre, la Profesora Responsable decide la no admisión de alumnos libres.
EXCEPCION: Aquellos alumnos que habiendo cursado la materia y han aprobado los prácticos de máquina, pero no así el parcial o su recuperación, podrán rendir la materia como alumnos libres.
Para ello deberán rendir un examen escrito sobre temas de los prácticos de aula y teóricos.
El plazo de que dispone el alumno, que se acoja a esta excepción, para rendir la materia será el mismo del que dispone un alumno regular, según las reglamentaciones vigentes.

[1] Aho, A. y Ullman, J. : "The Theory of Parsing, Translation and Compiling", Vol. I y II, Prentice Hall.
[2] Aho, A. y Ullman, J. : "Principles of Compiler Design", Addison Wesley.
[3] Aho, Setti y Ullman : "Compilers. Principles, Techniques and Tools", Addison Wesley.

[1] Gries, Davis: "Compilers Construction", John Wiley.
[2] Backhouse, R.C.: "Syntax of Programming Language", Prentice Hall.
[3] Davie, A. et al.: "Recursive Descendent Compiling",John Wiley.
[4] Barret y Coch: "Compiler Construction: Theory and Practice", Chicago SRA.
[5] Bauer et. al.: "An Advanced Course on Compilers", Springer Verlag.
[6] Waite y Goos: "Compiler Construction", Springer Verlag.
[7] Holub Allen: "Compiler Design in C", Prentice Hall
[8] Tremblay y Sorenson : “The Theory and Practice of Compiler Writing”, Mc Graw Hill, Computer Science Series.

Desarrollar en el alumno la capacidad de diseñar e implementar un compilador para un subconjunto del Lenguaje de Programación C++.

Descripción de los módulos de un compilador. Análisis Lexicográfico.Tabla de Símbolos. Análisis Sintáctico. Recuperación de errores. Análisis Semántico.Traducción dirigida por la sintaxis. Chequeo de tipos. Generación de código.