Materia	Carrera	Plan	Año	Periodo
DISEÑO Y CONSTRUCCION DE COMPILADORES	LIC.CS.COMP.	006/05	2020	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 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 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 Currículum Task force en 2013, para el área de compiladores.

Al finalizar el curso se espera que el estudiante sea capaz de diseñar e implementar un compilador para un subconjunto del lenguaje de Programació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.

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 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.

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: SISTEMA DE EJECUCIÓN BÁSICO Y EXTENDIDO
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.

BOLILLA 9: GENERACIÓN 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 e invocación y retorno de procedimientos. Generación de código intermedio embebido en un parser descendente recursivo.

Las bolillas se agruparon en bloques de acuerdo con la etapa del compilador en la que esté involucrado el tema:
Bloque 1: Bolilla 1
Bloque 2: Bolillas 2 y 3
Bloque 3: Bolilla 4
Bloque 4: Bolillas 5 y 6
Bloque 5: Bolillas 7 a 9

Metodología de trabajo

El DECNU 520/2020 de distanciamiento social, obligatorio y preventivo, establecido por el Gobierno Nacional y la necesidad de reajustar el Calendario Académico de la Universidad Nacional de San Luis, en lo referente al Segundo Cuatrimestre 2020, el Consejo Superior en su sesión del día 01/09/2020 estableció en el Artículo 1 de la Resolución Nro 68/2020, que el Segundo Cuatrimestre sea de 13 semanas. A los efectos, el presente es un programa en fase no presencial para el cual se tuvo que repensar y reprogramar la metodología de enseñanza y aprendizaje.

Para trabajar cada bloque, las clases teóricas grabadas, las diapositivas de clase y los apuntes teóricos correspondientes se dejan disponibles en el aula virtual de la plataforma Classroom (https://classroom.google.com/c/MTQ4MDM3OTE5NzMy?cjc=ymr25ny). Para grabar las clases se utiliza la herramienta OBS-Studio y se sube a una cuenta de YouTube para luego compartirla en el aula virtual. Para una mejor organización, tanto de los estudiantes como del equipo docente, se presenta un cronograma con la descripción de las actividades que se van a realizar cada semana del cuatrimestre, junto con la programación didáctica propuesta para cada bloque (tareas que deben ser realizadas por los estudiantes), además, por cada bloque se designa un ejercicio de carácter integrador el cual debe ser compartido por cada estudiante en un foro del aula virtual para ser contrastado y puesto en debate por los demás estudiantes para generar espacios de intercambios.

Las metas de comprensión que se planean alcanzar a través de la resolución de actividades, por parte de los estudiantes, para cada bloque son:

-Bloque 1
- ¿Cuántas son y cómo interactúan las fases del compilador?¿Cuáles son los conceptos involucrados en la construcción de un compilador que ya poseo?
- ¿Cuáles son las decisiones involucradas en el diseño de un compilador?

-Bloque 2
- ¿Cuándo una gramática es apta para ser analizada por un parser descendente o top-down? ¿Cómo transformar una gramática no apta en una apta?
- ¿Cómo se aplican las técnicas de parser descendente recursivo y tablas LL(k) fuertes? ¿Es posible recuperarse de un error sintáctico y continuar analizando la cadena de entrada? ¿Cómo?
- ¿Cómo se reflejan las estructuras y acciones de la tabla de parsing LL(K) fuertes en el parser descendente recursivo?
- ¿Cuáles son las decisiones involucradas en el diseño de los análizadores lexicográfico y sintáctico?

-Bloque 3
- Conocer los mecanismos de traducción dirigida por la sintaxis: definiciones dirigidas por la sintaxis (DDS) y esquemas de traducción dirigidas por la sintaxis (ETDS).
- Identificar cuándo un atributo es heredado y cuándo sintetizado.
- Reconocer las diferencias entre DDS y ETDS, y los requerimientos de implementación de cada uno de ellos.
- ¿Cómo se integran el esquema de traducción dirigido por la sintaxis y el parser descendente recursivo?
- ¿Cuáles son las decisiones involucradas en el diseño de una traducción dirigida por la sintaxis?

-Bloque 4
- En el contexto de un compilador ¿qué significa analizar semánticamente una cadena de entrada? y ¿cuál es la información que debe contener una expresión de tipo de acuerdo con el sistema de tipos?
- En lenguajes fuertemente tipeados, es decir, lenguajes en los cuales su compilador puede garantizar que los programas que acepte se ejecutarán sin errores de tipo, ¿cuándo y cómo se emplean estas expresiones de tipo? ¿Dónde se resguardan estas expresiones de tipo para luego poder ser recuperadas?
- ¿Qué información almacena una entrada en tabla de símbolos para un identificador en relación con su clase y para qué lo hace?
- ¿Cómo puede organizarse la tabla de símbolos en función del tipo de lenguaje a ser compilado?
- ¿Cómo se realiza el manejo de tabla de símbolos en un lenguaje fuertemente tipeado?
- ¿Cuáles son las decisiones involucradas en el diseño del chequeador semántico y la tabla de símbolos?

-Bloque 5
- ¿Cómo se relaciona la entrada en Tabla de Símbolos de un objeto con su representación en tiempo de ejecución?
- ¿Cómo diseño el descriptor para un objeto de tipo estructurado?
- ¿Cómo impactan en la arquitectura de la Máquina Abstracta para C las características del lenguaje fuente?
- ¿De dónde proviene la información para determinar cuáles son las instrucciones Máquina Abstracta para C que debo diseñar?
- ¿Cuáles son las decisiones involucradas en el diseño de la generación de código intermedio?

Las prácticas de laboratorio se llevarán a cabo en el aula virtual y consisten en la programación del diseño de algunos módulos del compilador, cada uno de los cuales tendrá una entrega y aprobación parcial, en las fechas predeterminadas en el cronograma de la materia. Por lo que el objetivo general del laboratorio es 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 estudiantes su interpretación.

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 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 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.

Las vías de comunicación con los estudiantes son las siguientes:
- Correos electrónicos de los docentes:
vsaragon@email.unsl.edu.ar
iferretti@email.unsl.edu.ar
- Oficina: 04 - 1° piso - 2° Bloque - Teléfono: +54 (266) 4520300 - Int 2104
- Sitio web: https://sites.google.com/site/ddcompilersunsl/
- Aula Virtual: https://classroom.google.com/c/MTQ4MDM3OTE5NzMy?cjc=ymr25ny donde se pueden descargar las teorías, trabajos prácticos, avisos importantes, apuntes, cronograma, hacer consultas o comentarios, etc.
- Grupo de WhatsApp (administradora 2664-615081)

F.1. Régimen para estudiantes regulares

Para regularizar la materia los estudiantes 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%.
3. La presentación oral (a través de un video o sincrónicamente de acuerdo con las posibilidades de conexión de estudiantes y docentes) y escrita de 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 y la dinámica grupal con la cual trabajaron, entre otros.
4. La participación en el 80% de las tareas/foros que se propongan.

F.2. 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.

F.3. 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 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 estudiante 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.

A los efectos de que se impartan todos los contenidos y se respete el crédito horario establecido en el Plan de estudios de la carrera para la asignatura, se establece que se de cómo máximo 12hs por semana distribuidas en teorías, prácticos de aula, laboratorios, trabajos tutoriales, consultas, hasta completar las 150hs.

De habilitarse la presencialidad en el ámbito de la UNSL, el examen práctico como sus recuperaciones, así como también la presentación oral del informe serán realizadas en forma presencial.