Parseo y generación de código

Teóricas

• [Clase 01] [video] Introducción a la materia. Intérpretes y compiladores. Introducción a los lenguajes formales.
• [Clase 02] [video] Análisis léxico. Autómatas finitos y expresiones regulares.
• [Clase 03] [video] Lenguajes regulares y normalización de gramáticas.
• [Clase 04] [video] Análisis sintáctico descendente.
• [Clase 05] [video] Análisis sintáctico ascendente.
• [Clase 06] [video] Intérpretes.
• [Clase 07] [video] Inferencia de tipos.
• [Clase 08] [video] Generación de código intermedio.
• [Clase 09] [video] Análisis estático y optimización.
• [Clase 10] [video] Asignación de registros y manejo automático de memoria.

Guías de ejercicios

• Práctica 01 – Gramáticas independientes del contexto.
• Práctica 02 – Lenguajes regulares.
• Práctica 03 – Normalización de gramáticas.
• Práctica 04 – Análisis sintáctico descendente.
• Práctica 05 – Análisis sintáctico ascendente.
• Práctica 06 – Interpretación.
• Práctica 07 – Tipos y unificación.
• Práctica 08 – Generación de código intermedio.
• Práctica 09 – Análisis de flujo de datos.
• Práctica 10 – Asignación de registros.

Parciales

• 2016c2_p1
• 2016c2_p2
• 2016c2_r1
• 2016c2_r2
• 2017c2_p2
• 2017c2_r1
• 2018c2_p1
• 2018c2_p2
• 2018c2_r2
• 2019c2_p1
• 2019c2_p2
• 2019c2_r1
• 2020c2_p1
• 2020c2_p2
• 2020c2_r1
• 2021c2_p1
• 2022c2_p1
• 2022c2_p2
• 2023c2_p1
• 2023c2_p2
• 2023c2_r1
• 2023c2_r2
• 2024c2_p1
• 2024c2_p2

Trabajos prácticos

• 2016_TP1
• 2016_TP2
• 2017_TP1
• 2018_TP1
• 2019_TP1
• 2019_TP2

Programa

• Estructura de un compilador. Fases de un compilador, compilación vs. interpretación.
• Análisis léxico. Lenguajes regulares, expresiones regulares, autómatas finitos.
• Análisis sintáctico. Gramáticas independientes del contexto, árboles de sintaxis, parsers descendentes y ascendentes, generadores de parsers.
• Interpretación. Ejemplos de interpretación para lenguajes imperativos, funcionales, orientados a objetos.
• Análisis semántico. Tablas de símbolos, inferencia de tipos, unificación.
• Generación de código intermedio. Máquinas de pila, máquinas de registros, análisis y síntesis de atributos.
• Análisis estático. Grafos de flujo, análisis de flujo de datos local hacia adelante y hacia atrás.
• Optimización. Eliminación de código muerto, propagación de constantes, loop unrolling.
• Soporte en tiempo de ejecución. Representaciones tagged vs. tagless, registros de activación, garbage collection.
• Generación de código. Register allocation y spilling, selección de instrucciones.

Bibliografía

• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2006.
• Andrew W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. *Introduction to Automata Theory, Languages and Computation*.
• Simon Peyton Jones. The Implementation of Functional Programming Languages. Prentice Hall, 1987.
• Christian Queinnec. LiSP in Small Pieces.
• Guy L. Steele. RABBIT: A Compiler for SCHEME.
• Adele Goldberg, David Rodson. Smalltalk-80: The Language and Its Implementation.
• Benjamin Pierce. Types and Programming Languages.
• Richard Jones, Antony Hosking, Eliot Moss. The Garbage Collection Handbook: The Art of Automatic Memory Management.