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

Docente	Función	Cargo	Dedicación
ARAGON, VICTORIA SOLEDAD	Prof. Responsable	P.Adj Exc	40 Hs
FERRETTI, EDGARDO	Responsable de Práctico	P.Adj Exc	40 Hs

Los conceptos involucrados en el diseño y construcción de compiladores forman parte del conocimiento general de un Licenciado en Ciencias de la Computación, con el perfil requerido por los correspondientes planes de estudios. Es importante resaltar la pertinencia de la asignatura y todas las motivaciones que justifican su inclusión como una materia de estudio obligatorio en los planes de estudio de esta licenciatura. Durante todo el cursado se recuperarán los conocimientos previos adquiridos en el contexto de diseño y construcción de un compilador, ya que esta materia profundiza los conocimientos dados en la materia Análisis Comparativo de Lenguajes y aplica conceptos ya apropiados en Autómatas y Lenguajes, Organización de Archivos y Bases de Datos I y Arquitectura I. Los principios, técnicas y herramientas que se aprenderán en el curso son aplicables a múltiples problemas. Seguramente ningún estudiante tendrá que utilizar en su vida profesional los conocimientos y las habilidades adquiridos en esta materia para diseñar un compilador propiamente dicho. No obstante, sí se enfrentará a una variedad de contextos donde estos conocimientos y habilidades son aplicables: traductores de un lenguaje a otro (por ejemplo, de Latex a HTML, de un formato de archivo binario a gráficos, de preguntas en lenguaje natural en un dominio específico a SQL, procesamiento de XML, etc.). Estas aplicaciones se resaltarán durante el cursado para propiciar la transferencia lejana en los estudiantes.
En la asignatura se aborda el diseño y la construcción del front-end de un compilador, haciendo hincapié en las decisiones de diseño que se deben tomar en cada fase que lo componen, y el impacto que tienen las decisiones tomadas en una fase con respecto al resto. Si bien el propósito de la asignatura es que el estudiante sea capaz de diseñar e implementar parte de un compilador para un subconjunto del lenguaje de programación C++, estos conocimientos son un medio a través del cual se persiguen alcanzar una serie de objetivos necesarios para la formación profesional de un licenciado en ciencias de la computación: se trabaja en un proyecto completo, el cual hay que documentar, depurar, probar y revisar aplicando el concepto de ciclo de vida del software de forma natural. Además, la construcción de un compilador impone desafíos algorítmicos, como ser, la utilización de distintos tipos de estructuras de datos (árboles, grafos, pilas, rebalses, etc.) y algoritmos (tablas LL(k) fuertes, recorridos de árboles, ordenación, etc.). Es necesario, dada la magnitud del proyecto, el uso de herramientas para el desarrollo y presentación del mismo (Flex, depuradores, lex, sistemas de control de versiones, audiovisuales, etc.). Por último, estudiar compiladores permite aprender cómo funcionan y se construyen los lenguajes de programación mejorando así las habilidades de programación de los estudiantes.
Los contenidos del curso se corresponden con las propuestas curriculares recomendadas por la ACM/IEEE Computer Society JointCurrículum Task force en 2013, para el área de compiladores.

Se consideran a continuación un conjunto de objetivos tanto de carácter general como de carácter específico, que se pretenderá que alcance el estudiantado a lo largo del curso.
Objetivos generales
- Fomentar el análisis crítico y evaluación de diferentes alternativas.
- Fomentar el espíritu de mejora continua y autoconocimiento.
- Mejorar las habilidades de trabajo en equipo y comunicativas.
Objetivos específicos
La asignatura pretende que el estudiante sea capaz de:
- Identificar los elementos constitutivos de un compilador: comprender y dominar su funcionamiento.
- Aplicar conocimientos previos de gramáticas y autómatas para la especificación y construcción de compiladores.
- Diferenciar y dominar las diferentes técnicas para llevar a cabo las fases de análisis de lenguajes.
- Generar código intermedio para una máquina virtual para un lenguaje fuente.

Contenidos mínimos dispuestos en el plan de estudios: Concepto y tipos de traductores. Compiladores de una o más pasadas. Estructura Clásica de un Compilador. Analizador Lexicográfico: Breve recapitulación. 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. Posibles implementaciones: lista, hash, árbol, otras. Representación de la información sobre tipos. Manipulaciones básicas. Control de bloques y de amplitud. Parser top-down determinístico. Gramáticas LL(k) y LL(k) fuertes. Condición de LL(k) fuerte. Conjuntos FIRSTk, FOLLOWk. 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. Detección y recuperación de errores. Ambientes de ejecución: Repaso de conceptos fundamentales. Representaciones intermedias. Traducción dirigida por la sintaxis. Análisis Semántico. Sistema de Ejecución. Generación de código.


Unidad temática 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.

Unidad temática 2: ANALIZADOR LEXICOGRÁFICO O SCANNER y ANÁLISIS SINTÁCTICO TOP DOWN o DESCENDENTE DETERMINÍSTICO (Parser top-down determinístico)
Breve recapitulación de los conceptos fundamentales vistos previamente en la materia Autómatas y Lenguajes. 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. Análisis top down por medio de tablas para k = 1. Análisis sintáctico top down por el método descendente recursivo. 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.

Unidad temática 3: 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.

Unidad temática 4: TABLA DE SÍMBOLOS y ANÁLISIS SEMÁNTICO
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. Introducción al análisis semántico. 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.

Unidad temática 5: AMBIENTES DE TIEMPO DE EJECUCIÓN, SISTEMA DE EJECUCIÓN BÁSICO Y EXTENDIDO y GENERACIÓN DE CÓDIGO INTERMEDIO
Ambientes de ejecución: Repaso de conceptos fundamentales. 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. Representaciones intermedias de los programas: Notación polaca, de n-uplas, de árboles de sintaxis abstracta. Código de máquina abstracta. Arquitectura de la máquina virtual. 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 de repetición y selección, secuencia de llamado y retorno, 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. 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 e invocación y retorno de procedimientos. Generación de código intermedio embebido en un parser descendente recursivo.

Metodología de trabajo

Las 5 unidades temáticas en las que están agrupados los contenidos de la materia se dictarán durante las 15 semanas del cuatrimestre. Para trabajar cada Unidad temática, se deja el material didáctico en el repositorio digital de la materia. Para cada Unidad temática se presentan una serie de actividades, a través de una programación didáctica, que permite, tras el desarrollo por parte de los estudiantes y junto a las clases teóricas, alcanzar las pretensiones planteadas en los objetivos específicos. Además, para cada Unidad temática, se designará una o más de esas actividades, de carácter integrador, las cuales deben ser desarrolladas y luego compartidas por cada estudiante en las clases para ser contrastadas y puestas en debate por los demás estudiantes y así generar espacios de intercambios. Las actividades contenidas en la programación didáctica para cada Unidad temática apuntan a que los estudiantes sean capaces de:

Unidad temática 1
- Identificar las partes constitutivas de un compilador y sus funcionalidades.
- Recuperar los conceptos previos ya adquiridos para la temática compiladores a lo largo de la carrera.
- Identificar las decisiones de diseño iniciales para la construcción de un compilador.

Unidad temática 2
- Identificar cuándo una gramática no es LL(k) para ningún k.
- Determinar cuándo una gramática es o no es LL(1).
- Dada una gramática libre de contexto, si no es LL(1) fuerte realizar las transformaciones necesarias para que lo sea.
- Construir los conjuntos Firstk y Followk para distintas gramáticas.
- Transformar gramáticas expresadas en forma BNF a forma BNFE. Expresar las ventajas/desventajas (si existen) de ambas formas de expresar las gramáticas.
- Implementar los reconocedores del parser descendente recursivo para diferentes gramáticas expresadas en BNF y/o BNFE.
- Implementar en un parser descendente recursivo un esquema de recuperación de errores pánico.
- Implementar en un parser descendente recursivo un esquema de recuperación de errores antipánico.
- Comprender la función de los distintos componentes de los métodos de recuperación de errores estudiados.
- Reconocer cuáles son las características de los lenguajes que favorecen el uso de cada método de recuperación, sus ventajas y desventajas.
- Consolidar los conceptos previos a través de su aplicación en ejercicios sobre lenguajes académicos.
- Identificar decisiones involucradas en el diseño de un analizador lexicográfico y uno sintáctico.

Unidad temática 3
- Conocer los mecanismos de traducción dirigida por la sintaxis: definiciones dirigidas por la sintaxis y esquemas de traducción dirigidas por la sintaxis.
- Comprender para qué entornos de parser son útiles las definiciones/esquemas S-atribuidos y L-atribuidos.
- Reconocer las diferencias entre ambos métodos y los requerimientos de implementación de cada uno de ellos.
- Implementar los distintos métodos sobre lenguajes académicos y alguna aplicación.
- Identificar decisiones involucradas en el diseño de una traducción dirigida por la sintaxis.

Unidad temática 4
- Identificar posibles representaciones de almacenamiento en la tabla de símbolos para diferentes objetos de datos que puedan aparecer en un programa.
- Diseñar entradas en la tabla de símbolos para los objetos computacionales de acuerdo con su clase.
- Identificar en el código fuente (provisto) las principales funciones de administración de la tabla de símbolos comprendiendo las tareas que realizan.
- Explicar la organización de la tabla de símbolos implementada dada.
- Desarrollar esquemas de traducción para controlar diferentes sistemas de tipos.
- Incorporar dichos esquemas en parser descendentes recursivos.
- Identificar las decisiones involucradas en el diseño del chequeador semántico y la tabla de símbolos.

Unidad temática 5
- 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.
- Desarrollar esquemas de traducción para generar código intermedio para diferentes construcciones sintácticas.
- Incorporar dichos esquemas en parsers descendentes recursivos.
- Identificar las decisiones involucradas en el diseño de la generación de código intermedio.

PLAN DE TRABAJOS PRÁCTICOS DE LABORATORIO

Los prácticos de laboratorio comprenden tres tipos de formación práctica:
- Actividades de diseño y proyecto: El estudiante 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 se trabajará con una metodología modular, esto es diseñar los distintos módulos del compilador de manera incremental, primero el desarrollo del parser con el esquema de recuperación de errores, 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: El estudiante debe programar el 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.
- Expresión escrita y oral: El estudiante debe presentar en forma oral (presencial o a través de un video o sincrónicamente de acuerdo con las posibilidades de conexión de estudiantes y docentes) y escrita un informe que releve las características y decisiones de diseño tomadas para la implementación del compilador junto con el rol que desempeñó cada integrante del grupo (de ser grupal) y la dinámica grupal con la cual trabajaron, entre otros.
El objetivo general del Laboratorio es diseñar e implementar un compilador para un subconjunto del lenguaje de Programación C++. Los módulos establecidos son:
- PRÁCTICO DE LABORATORIO 1: Parser Descendente Recursivo
- Dado que la materia se desarrolla en un cuatrimestre y la programación de los analizadores lexicográfico y sintáctico (parser descendente recursivo) no presentan mayores dificultades, se optó por entregar los códigos de ambos, requiriéndoles a los estudiantes su interpretación y la inclusión de un esquema de recuperación de errores antipánico al parser.
- 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 estudiantes traen como conceptos estudiados en actividades curriculares 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 estudiantes su interpretación y que completen algunas de las funciones de la misma. Los estudiantes 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 estudiantes 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.
Toda consulta teórica-práctica podrá realizarse en los horarios de las clases o en horarios extra previamente coordinados.

Régimen para estudiantes promocionales
Para promocionar la materia los estudiantes deberán:
1. Aprobar los prácticos de laboratorio (fuente y ejecutable) y/o sus correspondientes recuperaciones en las fechas estipuladas a tal efecto. Estos prácticos se Aprueban o No aprueban.
2. Aprobar un examen práctico o alguna de sus dos recuperaciones, con un porcentaje de ejercicios correctos de al menos el 80%, con nota no menor a 7.
3. Aprobar la presentación oral y escrita del informe referente a los prácticos de laboratorio, con nota no menor a 7.
4. Aprobar las actividades que se propongan, con nota no menor a 7.
5. Aprobar coloquio integrador (oral o escrito) con nota no menor a 7.
6. Asistir al menos al 80% de las clases.
La nota final será el promedio de las notas obtenidas en las entregas, examen práctico, informe y coloquio integrador no pudiendo ser menor a 7.
Régimen para estudiantes regulares
Para regularizar la materia los estudiantes deberán:
1. Aprobar los prácticos de laboratorio (fuente y ejecutable) y/o sus correspondientes recuperaciones en las fechas estipuladas a tal efecto. Estos trabajos se Aprueban o No aprueban.
2. Aprobar un examen práctico o alguna de sus dos recuperaciones, con un porcentaje de ejercicios correctos del 70% con nota no menor a 6.
3. Aprobar la presentación oral y escrita del informe referente a los prácticos de laboratorio, con nota no menor a 6.
4. Participar en las actividades que se propongan.
5. Asistir al menos al 80% de las clases.
Régimen de aprobación para estudiantes regulares
Los estudiantes que han regularizado la materia para aprobarla deberán rendir un examen final que podrá ser escrito u oral.
Régimen de estudiantes libres
En estos casos, el estudiante 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 materia. 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.

[1] Aho A.V, Sethi R.y Ullman J.D: "Compilers. Principles, Techniques and Tools", First Edition, Addison Wesley, 1986.
[2] Aho, A.V., Lam M.S, Sethi R. and Ullman J.D.: "Compilers. Principles, Techniques, & Tools", Second Edition, 2007, Pearson/Addison Wesley, 2007

[1] Aho, A.V 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.

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

Unidad temática 1: INTRODUCCIÓN
Unidad temática 2: ANALIZADOR LEXICOGRÁFICO O SCANNER y ANÁLISIS SINTÁCTICO TOP DOWN o DESCENDENTE DETERMINÍSTICO (Parser top-down determinístico)
Unidad temática 3: TRADUCCIÓN DIRIGIDA POR LA SINTAXIS
Unidad temática 4: TABLA DE SÍMBOLOS y ANÁLISIS SEMÁNTICO
Unidad temática 5: AMBIENTES DE TIEMPO DE EJECUCIÓN, SISTEMA DE EJECUCIÓN BÁSICO Y EXTENDIDO y GENERACIÓN DE CÓDIGO INTERMEDIO

 

Las vías de comunicación con los estudiantes son las siguientes:
- Correo electrónico del docente: aragon.victoria.soledad@gmail.com
- Oficina 4 – 1° piso – 2° Bloque
- Teléfono: +54 (266) 4520300 - Interno 2104