Lenguajes de Programación II (CI-4721)

Esta es la primera materia de la cadena de especialización del área de Lenguajes de Programación. Se ofrece cada dos años, los años pares, en el trimestre Enero-Marzo. Como se trata de una electiva de especialización supongo que Ud. está interesado en el tema, así que no se trata de «pasar» sino de ver cuán dedicado e interesado está en el tema, y la calidad del resultado de su trabajo.

Los tópicos fundamentales de estudio son:

Teoría Matemática de Reconocedores LL y LR.
Aplicación de las variantes LR(0), LR(1) y LALR(1).
Resolución de conflictos sintácticos.
Detección y recuperación de errores.
Gramáticas de Atributos
- Aplicación a la verificación estática de tipos.
- Aplicación a la generación de código «inocente».
Elementos del front-end de un compilador.

Evaluación

La materia tiene un componente teórico cuya evaluación corresponde al 65% del total. La evaluación será completada en dos exámenes escritos individuales de 35% y 30% respectivamente. Consulte el calendario de la materia para conocer las fechas definitivas y contenido a evaluar en cada caso.

La materia tiene un componente práctico cuya evaluación corresponde al 35% del total y se manifiesta en el proyecto de programación. La evaluación es continua con dos hitos resumen de 15% y 20%. Note que durante las sesiones de laboratorio Ud. deberá exhibir los avances de su proyecto de manera concreta mediante la exposición y discusión de sus decisiones de diseño e implementación; llegada la fecha hito, simplemente se resumirán los resultados parciales alcanzados y se redondeará la calificación final.

En síntesis, todas las semanas tiene que entregar algo.

El Proyecto

Su proyecto de programación, que se extiende durante dos trimestres continuos, consiste en la implantación de un compilador para un lenguaje de programación concreto diseñado por Ud. El léxico y sintaxis del lenguaje de programación es libre, pero el diseño debe incluir al menos:

Lenguaje imperativo sin orientación a objetos.
Alcance estático con anidamiento arbitrario de bloques.
Sistema de tipos con verificación estática.
Tipos escalares: caracter, booleano, entero y punto flotante.
Tipos colección: arreglo y cadena.
Tipos estructurados: registro y unión.
Apuntadores «sólo al heap».
Un selector, iteraciones acotadas e iteraciones condicionadas.
Pasaje de parámetros por valor y por referencia.
Retorno de valores vacíos o escalares.
Recursión.

Elementos como manejo automático de memoria dinámica, compilación separada y manejo de procedimientos como objetos de primera clase no son viables en tan corto tiempo, así que ni siquiera los considere. Cualquier otro elemento que Ud. quiera incorporar al lenguaje debe ser discutido antes de la tercera semana para mantener el trabajo factible.

Herramientas de Programación

El compilador para su lenguaje puede desarrollarse con:

GNU C/C++, usando Flex y Bison como herramientas auxiliares para la generación del analizador lexicográfico y sintáctico, además de las librerías que Ud. considere adecuadas para el manejo de tabla de símbolos y grafos (aunque comenzar con STL y Boost es conveniente).
Haskell (GHC), usando Alex y Happy como herramientas auxiliares para la generación del analizador lexicográfico y sintáctico, además de las librerías Data.Map para el manejo de tabla de símbolos y Data.Graph para el manejo de grafos. Note que necesita dominar el uso de Functor, Monad y Monad Transformers para poder considerar el uso de Haskell para este proyecto.

Este curso no es un tutorial de C/C++, Haskell o ninguna de las librerías. Puedo ofrecer orientación general y conducirlos a la documentación, sin embargo se espera que Ud. tenga razonable dominio del lenguaje y de las técnicas de programación asociadas.

Independientemente del lenguaje de programación que Ud. haya escogido, se espera que el desarrollo de su proyecto ocurra apoyado en el sistema de control de versiones Git, con repositorios sobre los cuales yo pueda supervisar que en efecto hay trabajo en curso. Su repositorio debe albergar tanto su código (documentado) como también los documentos de soporte y notas de implantación.

Los equipos son de dos (2) personas.

Bibliografía

El curso estará basado sobre cuatro libros de texto.

   Scott, Michael
   Programming Language Pragmatics
   Morgan Kaufmann
   ISBN 0-12-633951-1

Pueden usar la Tercera (tapa blanca, como el que muestro el primer día de clase), la Segunda Edición (tapa negra) o Primera Edición por igual. En los cronogramas y material de apoyo hago referencia a la tercera edición de ese libro como [Scott].

El [Scott] asiste en los elementos de diseño del lenguaje y su manifestación en el diseño del compilador. A diferencia de lo que ocurre en CI-3641, en la cadena de lenguajes se utiliza casi todo el contenido del libro.

   Sudkamp, Thomas
   Languages and Machines
   Addison-Wesley Publishing
   ISB 0-321-32221-5
   QA267.3.S83

Pueden usar la Tercera Edición (tapa verde, como el que muestro el primer día de clase) o la Segunda Edición (tapa roja) por igual. En los cronogramas y material de apoyo hago referencia a la tercera edición de ese libro como [Sudkamp].

El [Sudkamp] asiste en los elementos de teoría matemática relacionados con análisis sintáctico generalizado. A diferencia de lo que ocurre en CI-3725, en la cadena de lenguajes solamente se desarrollan los capítulos relacionados con reconocedores LL y LR pero en toda su extensión (k arbitrario).

    Aho, Sethi & Ullman
    Compilers: Principles, Techniques and Tools
    Addison-Wesley Publishing
    ISBN 0-201-10088-6

    Aho, Lam, Sethi & Ullman
    Compilers: Principles, Techniques and Tools
    Addison-Wesley Publishing
    ISBN 0-321-48681-1

Estos son, respectivamente, las dos últimas ediciones de «el dragón», por la imagen que tiene en la portada. La Primera Edición (tapa blanca) es útil para CI-4721, pero se queda corta para CI-4722. La Segunda Edición (tapa morada) no incluye algunos tópicos de CI-4721, pero es completo para CI-4722. En los cronogramas hago referencia a estos libro como [ASU] y [ALSU], respectivamente.

Cronograma habitual y Láminas de Clase

Sigue el cronograma habitual del curso. Cada una de las sesiones de clase incluye el enlace a las versiones más recientes de las láminas que uso para dirigir las clases, adeḿas de las referencias al material de lectura necesario.

Las versiones de cursos anteriores no están disponibles. Si durante alguna clase se hacen correcciones o agregados, espere encontrar la versión corregida aquí eventualmente.

Teoría

Repaso — [Sudkamp] 3.1-3.5, 7.1-7.3
- Gramáticas Libres de Contexto.
- Autómatas de Pila.
- Equivalencia CFG y PDA explotando no-determinismo.
- PDA Descendente para cualquier CFG.
- PDA Ascendente para cualquier CFG.
Matemática LL — [Sudkamp] 19.1-19.5
- Análisis sintáctico descendente general.
- Lookahead como criterio para desambiguar.
- FIRST y FOLLOW para k-prefijos.
- Gramáticas Fuertemente LL(k).
Técnica LL — [ASU] 4.4
- Reconocedor por tabla.
- Reconocedor recursivo descendente.
Matemática LR — [Sudkamp] 20.1-20.4
- Análisis sintáctico ascendente general.
- Contextos LR(0) como criterio para desambiguar.
- Máquina Caraterística de Prefijos Viables LR(0)
- Reconocedor LR(0) inocente.
Más matemática LR — [Sudkamp] 20.5
- Análisis sintáctico LR(k).
- Contextos LR(k) como criterio para desambiguar.
- Máquina Caraterística de Prefijos Viables LR(k)
- Reconocedor LR(k).
Técnica LR — [ASU] 4.6 y 4.7
- Reconocedor por tabla.
- Tabla LR(0).
- Tabla SLR(1).
- Tabla Canónica LR(1).
- Recuperación de Errores.
Más Técnica LR — [ASU] 4.7
- Tabla LALR(1).
- Comparación LR(1) y LALR(1).
- Técnicas de Compactación de Tablas.
- Procesamiento eficiente de gramáticas.
Aún más Técnica LR — [ASU] 4.8
- Gramáticas de Precedencia.
- Resolución de conflictos.
Definición Dirigida por Sintaxis — [ASU] 5.1 y 5.2, [Scott] 4.1 y 4.3
- Gramáticas de Atributos.
- Esquemas de Traducción.
- Definiciones S-Atribuidas.
- Definiciones L-Atribuidas.
Traducción Dirigida por Sintaxis — [ASU] 5.4, [Scott] 4.1 y 4.3
- Esquema postfijo.
- Esquema S-Atribuido sobre Reconocedores LR.
- Eliminación de recursión para Reconocedores LL.
Traducción Dirigida por Sintaxis — [ASU] 5.5, [Scott] 4.1 y 4.3
- Esquema L-Atribuido sobre reconocedor LR.
- Simulación de atributos heredados por copia.
- Técnica de No-Terminales Marcadores.
- Esquema L-Atribuido sobre reconocedor recursivo.
- Esquema L-Atribuido sobre reconocedor LL.
Verificación de Tipos — [ASU] 6.1-6.2
- Grafo para Expresiones de Tipo.
- Verificación Dirigida por Sintaxis.
- Notación Formal para Verificación.
Verificación de Tipos — [ASU] 6.3-6.5, [ALSU] 6.3.3, 6.5.1-6.5.3
- Manejo de Equivalencia Estructural.
- Manejo de Equivalencia por Nombres.
- Implantación de Conversión de Tipos.
- Implantación de Sobrecarga.
Verificación de Tipos — [ASU] 6.6
- Funciones Polimórficas.
- Sustitución y Unificación.
Verificación de Tipos — [ASU] 6.6, [ALSU] 6.3.3 y 6.3.6
- Verificación con Polimorfismo Paramétrico.
- Cálculo de Anchuras y Desplazamientos.
- Gestión de Anidamiento de Bloques.
- Equivalencia de Tipos en OOP.
Representaciones Intermedias — [ASU] 8.1-8.3, [ALSU] 6.1, 6.2, 6.4.1 y 6.4.2
- Relevancia en el modelo análisis-síntesis.
- Representaciones gráficas y generación.
- Representación postfija y generación.
- Código de Tres Direcciones (TAC).
- Generación de TAC para expresiones.
Generación de Código Intermedio — [ASU] 8.3-8.4, [ALSU] 6.4.3-6.4.4
- Generación de TAC para arreglos.
- Generación de TAC para flujo de control.
- Generación de TAC «jumping code».
Generación de Código Intermedio — [ASU] 8.5-8.7, [ALSU] 6.7.1-6.7.3 y 6.8.3
- Generación de TAC con «backpatching».
- Generación de TAC para switch/case.
- Generación de TAC para llamadas a procedimientos.
LLVM — (no se evalúa)

Laboratorio

El cronograma del laboratorio varía según el desempeño de los equipos. En cada sesión presentaré algún tópico relevante a su trabajo práctico, estableciendo el hito de entrega para la siguiente sesión (aparece destacado en cada sesión).

En general, el cronograma consiste en:

Requerimientos del proyecto y herramientas.
- Ejemplo de Diseño de Lenguaje.
- Markdown para documentar.
- Condiciones para usar C/C++.
- Condiciones para usar Haskell.
- Generadores para lexicográficos.
- Generadores para reconocedores sintácticos.
Construcción del analizador lexicográfico.
- Ejemplo con Flex o Alex.
- Problemas frecuentes.
- ¿Cómo probarlo?
- Revisión del Diseño Inicial.
Construcción del analizador sintáctico.
- Ejemplo con Bison o Happy.
- Problemas frecuentes.
- ¿Cómo probarlo?
- Revisión del Analizador Lexicográfico.
Tabla de Símbolos para Alcance Anidado
- Modelo Arbol de Tablas.
- Modelo LeBlanc-Cook ([Scott] CD 3.4)
- ¿Como probarlo?
- Revisión del Analizador Sintáctico
Análisis de Contexto — Declaración y uso de símbolos.
- Ejemplo de «Acciones» con Bison o Happy.
- Separación de constantes de compilación (cadenas).
- Errores de contexto en uso de símbolos.
- Revisión de Tabla de Símbolos.
Primer Corte – Reconocedor con Tabla de Símbolos
Grafos de Tipos
- Ejemplo de Grafos de Tipos en C++ o Haskell.
- Técnica «singleton»
- ¿Cómo probarlo?
Análisis de Contexto — Construcción de Tipos
- Ejemplo de «Acciones» con Bison o Happy.
- Revisión de Grafos de Tipos.
Análisis de Contexto — Verificación de Tipos
- Ejemplo de «Acciones» con Bison o Happy.
- Revisión de Construcción de Tipos.
Representación Intermedia — Arbol Abstracto
- Ejemplo de AST en C++ o Haskell.
- Co-dependencia con Tablas de Símbolos.
- Revisión de Verificación de Tipos.
Segundo Corte – Front-End completo