5.35. CS342. Compiladores (Obligatorio)

• Semestre: 6to Sem. Créditos: 4
• Horas del curso: Teoría: 2 horas; Práctica: 2 horas; Laboratorio: 2 horas;

• Prerrequisitos:

  • CS211. Teoría de la Computación (4to Sem)

5.35.1. Justificación

Este curso proporciona una comprensión profunda de cómo los lenguajes de alto nivel se transforman en código máquina ejecutable. El estudio de los compiladores permite a los estudiantes comprender la semántica de los lenguajes, la gestión de memoria y la optimización de código, que son habilidades fundamentales para diseñar lenguajes específicos de dominio y realizar ingeniería de software de alto rendimiento.

5.35.2. Objetivos Generales

1.

Comprender las fases de un compilador y las herramientas de construcción.

2.

Implementar analizadores léxicos y sintácticos basados en gramáticas.

3.

Generar y optimizar código intermedio para una arquitectura específica.

5.35.3. Contribución a los resultados (Outcomes)

AG-C08) Análisis de Problemas: Identifica, formula y analiza problemas complejos de computación. (Usage)

AG-C12) Aplica la teoría de la ciencia de la computación y los fundamentos de desarrollo de software para producir soluciones basadas en computadora. (Usage)

5.35.4. Contenido

5.35.4.1. Análisis de Programas y Analizadores (20 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Aho et al., 2006, Appel, 2004]

Temas

1.

Representaciones de programa relevantes, como bloques básicos (basic blocks), grafos de flujo de control (control-flow graphs), cadenas definición-uso (def-use chains) y asignación única estática (static single assignment)

2.

Indecidibilidad y consecuencias para el análisis de programas

3.

Análisis insensible al flujo (flow-insensitive), como verificación de tipos y análisis de punteros y alias escalables

4.

Análisis sensible al flujo (flow-sensitive), como análisis de flujo de datos (dataflow) hacia adelante y hacia atrás

5.

Análisis sensible a la ruta (path-sensitive), como verificación de modelos de software (software model checking) y verificación de software

6.

Herramientas y frameworks para implementar analizadores

7.

Papel del análisis estático en la optimización de programas y el análisis de dependencia de datos durante la explotación de concurrencia

8.

Papel del análisis de programas en la verificación (parcial) y la búsqueda de errores (bug-finding)

9.

Paralelización:

a)

Análisis para auto-paralelización

b)

Análisis para detectar errores de concurrencia

Aprendizaje esperado (Learning Outcomes)

1.

Explicar la diferencia entre grafo de flujo de datos (dataflow graph) y grafo de flujo de control [Explicar]

2.

Explicar por qué los análisis de programa no triviales y sólidos (sound) deben ser aproximados [Explicar]

3.

Argumentar por qué un análisis es correcto (sound y terminante) [Argumentar]

4.

Explicar por qué el alias potencial limita el análisis de programa sólido y cómo el análisis de alias puede ayudar [Explicar]

5.

Usar los resultados de un análisis de programa para optimización de programas y/o corrección parcial del programa [Usar]

5.35.4.2. Traducción y Ejecución de Lenguajes (24 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Aho et al., 2006, Appel, 2004]

Temas

1.

Modelos de ejecución para JIT (Just-In-Time), compilador, intérprete

2.

Uso de código intermedio, por ejemplo, bytecode

3.

Limitaciones y beneficios de JIT, compilador e intérprete

4.

Compiladores/transpiladores cruzados (cross compilers/transpilers)

5.

Representación BNF y BNF extendida de gramática libre de contexto

6.

árbol de análisis (parse tree) usando una oración simple como expresión aritmética o sentencia if-then-else

7.

Ejecución como código nativo o dentro de una máquina virtual

8.

Canalización de traducción de lenguaje: análisis sintáctico, análisis (parsing), verificación de tipos opcional, generación de código/traducción y optimización, enlace (linking), carga (loading), ejecución

9.

Representación en tiempo de ejecución de construcciones centrales del lenguaje como objetos (tablas de métodos) y funciones que pueden pasarse como parámetros a y devolverse desde funciones (clausuras)

10.

Desarrollo seguro de compiladores

Aprendizaje esperado (Learning Outcomes)

1.

Explicar y comprender las diferencias entre implementaciones de lenguaje compilado, JIT e interpretado, incluyendo los beneficios y limitaciones de cada una [Explicar]

2.

Diferenciar sintaxis y análisis (parsing) de semántica y evaluación [Diferenciar]

3.

Usar BNF y BNF extendida para especificar la sintaxis de construcciones simples como if-then-else, declaración de tipo y construcciones iterativas para lenguajes conocidos como C++ o Python [Usar]

4.

Ilustrar el árbol de análisis usando una oración/expresión aritmética simple [Aplicar]

5.

Ilustrar traducción de diagramas de sintaxis a BNF/BNF extendida para construcciones simples como if-then-else, declaración de tipo, construcciones iterativas, etc [Aplicar]

6.

Ilustrar ambigüedad en el análisis usando if-then-else anidado/expresión aritmética y mostrar resolución usando orden de precedencia [Aplicar]

7.

Discutir los beneficios y limitaciones de la recolección de basura, incluyendo la noción de alcanzabilidad [Debatir]

5.35.4.3. Comportamiento en Tiempo de Ejecución y Sistemas (20 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Aho et al., 2006, Cooper and Torczon, 2011]

Temas

1.

Modelos de proceso usando pilas y montones para asignar y desasignar registros de activación y recuperar entornos usando punteros de marco (frame pointers) y direcciones de retorno durante una llamada a procedimiento, incluyendo ejemplos de paso de parámetros

2.

Esquemas de búsqueda de código usando tablas hash para métodos en implementaciones de programas orientados a objetos

3.

Distribución de datos para objetos y registros de activación

4.

Asignación de objetos en el montón (heap)

5.

Implementar entidades virtuales y métodos virtuales; tablas de métodos virtuales (virtual method tables) y su aplicación

6.

Comportamiento en tiempo de ejecución de programas orientados a objetos

7.

Comparar y contrastar la asignación de memoria durante el intercambio de información usando paso de parámetros y variables no locales (usando cadena de enlaces estáticos).

8.

Enfoques y técnicas de gestión dinámica de memoria: malloc/free, recolección de basura (mark-sweep, copying, reference counting), regiones (también conocidas como arenas o zonas)

9.

Compilación justo a tiempo (just-in-time) y recompilación dinámica

10.

Interfaz con el sistema operativo (por ejemplo, para inicialización del programa)

11.

Interoperabilidad entre lenguajes de programación incluyendo mecanismos de paso de parámetros y representación de datos:

a)

Big endian, little endian

b)

Distribución de datos de tipos de datos compuestos como arreglos

12.

Otras características comunes de las máquinas virtuales, como carga de clases (class loading), hilos (threads) y verificación de seguridad

13.

Sandboxing

Aprendizaje esperado (Learning Outcomes)

1.

Discutir beneficios y limitaciones de la gestión automática de memoria [Debatir]

2.

Explicar el uso de metadatos en representaciones en tiempo de ejecución de objetos y registros de activación, como punteros de clase, longitudes de arreglo, direcciones de retorno y punteros de marco (frame pointers) [Explicar]

3.

Comparar y contrastar asignación estática vs asignación basada en pila vs asignación basada en montón de elementos de datos [Comparar]

4.

Explicar por qué algunos elementos de datos no pueden desasignarse automáticamente al final de una llamada a procedimiento/método (necesidad de recolección de basura) [Explicar]

5.

Discutir ventajas, desventajas y dificultades de la compilación justo a tiempo y la recompilación dinámica [Debatir]

6.

Discutir el uso del sandboxing en código móvil [Debatir]

7.

Identificar los servicios proporcionados por los sistemas en tiempo de ejecución de lenguajes modernos [Analizar]

5.35.5. Referencias Bibliográficas

[Aho et al., 2006]

[Appel, 2004]

[Cooper and Torczon, 2011]