Materia	Carrera	Plan	Año	Periodo
DISEÑO Y CONSTRUCCION DE COMPILADORES	LIC.CS.COMP.	32/12	2018	2° cuatrimestre

Docente	Función	Cargo	Dedicación
ARAGON, VICTORIA SOLEDAD	Prof. Responsable	P.Adj Exc	40 Hs
FERRETTI, EDGARDO	Responsable de Práctico	JTP Exc	40 Hs
GARCIARENA UCELAY, MARIA JOSE	Auxiliar de Práctico	E.Beca Fac	5 Hs

Los conceptos involucrados en 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 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 del 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 Currículum Task force en 2012, para el área de compiladores.

Al finalizar el curso se espera que el alumno sea capaz de:

a) Diseñar e implementar un compilador para un subconjunto del lenguaje de Programación.
b) Diseñar las distintas etapas involucradas en la construcción de un compilador para un lenguaje que defina alguna aplicación.

BOLILLA 1: INTRODUCCIÓN
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 LEXICOGRÁFICO O SCANNER
Breve recapitulación de los conceptos fundamentales vistos previamente en la materia Autómatas y Lenguajes.

BOLILLA 3: ANÁLISIS SINTÁCTICO TOP DOWN o DESCENDENTE DETERMINÍSTICO
Definiciones de gramáticas LL(k) y LL(k) fuerte. Condición de LL(k) fuerte. Definición de los conjuntos FIRSTk, FOLLOWk. Teoremas Fundamentales. Parser descendente del tipo “table driven”. Construcción de tablas de parsing para gramáticas LL(k) con k = 1. Análisis sintáctico descendente por el método recursivo descendente. Generalidades. Algoritmos de implementación de un parser descendente recursivo. Errores en la etapa sintáctica. Esquema de recuperación de errores en entornos de descendentes recursivos, pánico y antipánico.

BOLILLA 4: TRADUCCIÓN 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 y L-atribuidas. Esquemas de traducción dirigidos por la sintaxis. Restricciones para el cálculo de los valores de los atributos. Implementación de esquemas de traducción L-atribuidos en un parser descendente recursivo.

BOLILLA 5: TABLA DE SÍMBOLOS
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. Revisión de posibles implementaciones: lista, hash, árbol, otras. Representación de la información sobre tipos. Manipulaciones básicas. Control de bloques y de amplitud.

BOLILLA 6: ANÁLISIS SEMÁNTICO
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. Errores semánticos. Esquema de recuperación de errores semánticos.

BOLILLA 7: AMBIENTES DE TIEMPO DE EJECUCIÓN
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, semi-diná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 re-uso.

BOLILLA 8: REPRESENTACIONES INTERMEDIAS DE LOS PROGRAMAS FUENTES
Notación polaca, de n-uplas, de árboles de sintaxis abstracta. Código de máquina abstracta.

BOLILLA 9: SISTEMA DE EJECUCIÓN 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 sentencia entrada-salida, estructuras de control a nivel de procedimiento, pasaje de parámetros por dirección y por valor. Referenciación global y local. Variables sub-indicadas: acceso, pasaje de arreglos y elementos de arreglos como parámetros.

BOLILLA 10: GENERACION DE CÓDIGO INTERMEDIO
Ubicación del generador de código dentro del proceso de compilación. Esquema de traducción dirigido 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.

I. PLAN DE TRABAJOS PRÁCTICOS DE AULA (Corresponden a ejercicios de lápiz y papel con la finalidad de comprensión, fijación y aplicación de los conceptos asociados)

PRÁCTICO 1: Gramáticas LL(k).

Descripción: Esta guía está orientada a que los alumnos fijen y comprendan los conceptos asociados con las gramáticas LL(k) y LL(k) fuertes como asimismo que puedan identificar cuándo una gramática es LL(k) y/o LL(k) fuerte aplicando para ello o bien las respectivas definiciones o los teoremas que correspondan.

Objetivos Específicos: Al finalizar práctico se espera que el alumno sea capaz de:

a) Identificar cuándo una gramática no es LL(k) para ningún k.
b) Determinar cuándo una gramática es o no es LL(1).
c) Dada una gramática CF, si no es LL(1)fuerte realizar las transformaciones necesarias para que lo sea.
f) Construir los conjuntos Firstk y Followk para distintas gramáticas.
g) Construir las tablas de parsing descendente para gramáticas LL(k) fuerte con k=1.

PRÁCTICO 2: Parsing Descendente Recursivo.

Descripción: Esta guía está orientada a que los alumnos fijen, comprendan y apliquen los conceptos relacionados con el parser descendente recursivo.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Transformar gramáticas expresadas en forma BNF a forma BNFE.
b) Expresar las ventajas/desventajas (si existen) de ambas formas de expresar las gramáticas.
c) Implementar los reconocedores del parser descendente recursivo para diferentes gramáticas expresadas en BNF y/o BNFE.

PRÁCTICO 3: Recuperación de errores.

Descripción: Esta guía está orientada a que los alumnos fijen, comprendan y apliquen los conceptos relacionados con el esquema de recuperación de errores:

a) Pánico y su implementación en un parser descendente recursivo.
b) Antipánico y su implementación en un parser descendente recursivo.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Comprender la función de los distintos componentes de los métodos de recuperación de errores estudiados.
b) Reconocer cuáles son las características de los lenguajes que favorecen el uso de cada método, sus ventajas y desventajas.
c) Consolidar los conceptos previos a través de su aplicación en ejercicios sobre lenguajes académicos.

PRÁCTICO 4: Traducción dirigida por la sintaxis en entorno de parser top descendente.

Descripción: Esta guía está orientada a que los alumnos fijen, comprendan y apliquen los conceptos relacionados con la traducción de lenguajes guiadas por las gramáticas libres de contexto.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Conocer los mecanismos de traducción dirigida por la sintaxis: definiciones dirigidas por la sintaxis y esquemas de traducción dirigidas por la sintaxis.
b) Comprender para qué entornos de parser son útiles las definiciones/esquemas S-atribuidos y L-atribuidos.
c) Reconocer las diferencias entre ambos métodos y los requerimientos de implementación de cada uno de ellos.
d) Implementar los distintos métodos sobre lenguajes académicos y alguna aplicación.

PRÁCTICO 6: Tabla de símbolos.

Descripción: En este práctico se le entrega al alumno el código fuente del módulo que implementa la tabla de símbolos más una guía de ejercicios que orienta a los alumnos en la comprensión del tipo de organización de la TS seleccionada y su manipulación. Los alumnos ya tienen conocimientos y experiencias de implementación de estructuras de datos y de archivos y de las operaciones que sobre ellos se efectúan. Por lo anterior, no se consideró necesario que desarrollaran este módulo, sino que pudieran interpretarlo.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Identificar posibles representaciones de almacenamiento en la tabla de símbolos para diferentes objetos de datos que puedan aparecer en un programa.
b) Identificar en el código fuente las principales funciones de administración de la tabla de símbolos comprendiendo las tareas que realizan.
c) Explicar la organización de la tabla de símbolos implementada.

PRÁCTICO 7: Chequeo de tipos.

Descripción: Esta guía está orientada a que los alumnos implementen el análisis semántico referido al control de tipos usando esquemas de traducción sobre lenguajes académicos con la finalidad de comprensión y fijación de conceptos.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Desarrollar esquemas de traducción para controlar diferentes sistemas de tipos.
b) Incorporar dichos esquemas en parser descendentes recursivos.

PRÁCTICO 8: Sistema de Ejecución Básico.

Descripción: Dada la definición del sistema de ejecución requerido para la implementación del compilador a desarrollar, esta guía tiene por finalidad que el estudiante pueda pensar en representaciones de tiempo de ejecución de distintos tipos de objetos computacionales, definiendo si fuere necesario nuevas instrucciones de la máquina virtual para su manipulación en tiempo de ejecución.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Extender, si fuera necesario, el soporte de tiempo de ejecución definido en clase para soportar distintos objetos computacionales y/o estructuras sintácticas, definiendo formas de representación en tiempo de ejecución y/o instrucciones de la máquina virtual según corresponda.


PRÁCTICO 9: Generación de Código.

Descripción: Esta guía está orientada a que los alumnos implementen la generación de código intermedio para distintas construcciones sintácticas usando esquemas de traducción, con la finalidad de comprensión y fijación de conceptos.

Objetivos Específicos: Al finalizar el práctico se espera que el alumno sea capaz de:

a) Desarrollar esquemas de traducción para generar código intermedio para diferentes construcciones sintácticas.
b) Incorporar dichos esquemas en parsers descendentes recursivos.


II. PLAN DE TRABAJOS PRÁCTICOS DE LABORATORIO (formación práctica: formación experimenta y actividad de diseño y proyecto, 75 horas).

Descripción General: Los prácticos de laboratorio comprenden dos tipos de formación práctica:

Actividades de diseño y proyecto: El alumno debe trabajar sobre el proyecto de diseño e implementación de un compilador para un subconjunto de un lenguaje de programación determinado, para ello trabajarán con una metodología modular, esto es diseñar los distintos módulos del compilador de manera incremental, esto es primero el desarrollo del parser, una vez verificada su corrección, le incorporarán el análisis semántico y luego la generación de código intermedio.

Actividades de formación experimental: Consistirá en la programación del diseño de cada módulo del compilador, cada uno de los cuales tendrá una entrega y aprobación parcial, en las fechas predeterminadas en el cronograma de la materia.

Objetivo General del Laboratorio:

a) Diseñar e implementar un compilador para un subconjunto del lenguaje de Programación.


PRÁCTICO DE LABORATORIO 1: Parser Descendente Recursivo
Dado que la materia se desarrolla en un cuatrimestre y la programación del parser no presenta mayores dificultades, se optó por entregar el código del parser descendente, requiriéndoles a los alumnos su interpretación y que completen algunas de las funciones reconocedores del mismo.


PRÁCTICO DE LABORATORIO 2: Tabla de Símbolos y Análisis Semántico
Dado que la materia se desarrolla en un cuatrimestre y los alumnos traen como conceptos estudiados en materias anteriores conceptos de estructuras de datos y sus manipulaciones, se optó por entregar el código de la Administración de la Tabla de Símbolos, requiriéndoles a los alumnos su interpretación y que completen algunas de las funciones de la misma. Los alumnos deben diseñar un chequeador de tipos, usando un esquema de traducción dirigido por la sintaxis para el lenguaje del proyecto e incluirlo en el parser descendente recursivo.

PRÁCTICO DE LABORATORIO 3: Generación de Código Intermedio
Los alumnos usando un esquema de traducción dirigido por la sintaxis y la máquina virtual definida para el lenguaje del proyecto, deben incorporar al parser la generación de código intermedio.

F.1. Régimen para alumnos regulares

Para regularizar la materia los alumnos deberán aprobar:

1. Los prácticos de laboratorio (fuente y ejecutable) y/o su correspondiente recuperación en las fechas estipuladas a tal efecto. La no aprobación de un trabajo 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 alguna de sus dos recuperaciones, con un porcentaje de ejercicios correctos del 70%.

F.2. Régimen de aprobación para alumnos regulares

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

F.3. Régimen de alumnos libres

En estos casos, el alumno tendrá una evaluación dividida en partes. En una se pedirá un Trabajo Especial, el cual es un compilador desarrollado bajo las pautas que se dan en el curso de la asignatura. En otra parte se tomará un examen escrito de carácter práctico. Finalmente, una parte oral y/o escrita de teoría. Para su aprobación, se requiere la aprobación de las tres partes.

F.4. En la asignatura no se admite el régimen por promoción.

[1] Aho, A. y Ullman, J.D. : "The Theory of parsing. Translation and Compiling", Vol. I y II, Prentice Hall.
[2] Aho, A.V y Ullman, J.D : "Principles of Compiler Design", Addison Wesley.
[3] Aho A.V, Sethi R.y Ullman J.D : "Compilers. Principles, Techniques and Tools", First Edition,Addison Wesley, 1986.
[4] Aho, A.V.,Lam M.S, Sethi R. and Ullman J.D.: "Compilers. Principles, Techniques, & Tools", Second Edition, 2007, Pearson/Addison Wesley, 2007.

[1] Gries, Davis: "Compilers Construction", John Wiley, 1975.
[2] Backhouse, R. C : "Syntax of Programming Language", Prentice Hall.
[3] Davie, A. et al.: "Recursive Descendent Compiling", John Wiley.
[4] Wilhelm R., Maurer D. : Compiler Design, Addison Wesley, 1995
[5] Bauer et al.: "An advanced course on Compilers", Springer Verlag.
[6] Waite W.M, Carter L. R. : " An Introduction to Compiler Construction ", Harper Collins College, Publishers, 1993.
[7] Bornat Richard: "Understanding and Writing Compilers", The Macmillan Press LTD, 1982.
[8] Tremblay y Sorenson : "the Theory and Paractice of Compiler Writing", Mc Graw Hill, Computer Science Series, 1985
[9] Appel A. W.: "Modern Compiler Implementation in Java", Second Edition, Cambridge University Press, 2006.

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

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