cc50a - Compiladores

Objetivos:

Entregar los elementos teóricos y prácticos necesarios para implementar la traducción, o compilación, de un leguaje de programación de alto nivel al lenguaje de máquina de un computador digital. También se estudiará la aplicación de las técnicas de compilación a otros problemas que involucren estructurar información secuencial, transformar formatos y generalmente traducir una especificación declarativa a una implementación operacional.

Se espera que el alumno adquiera una visión sólida de cómo se asocian los conceptos abstractos de lenguajes programación a su implementación concreta utilizando la base teórica de autómatas y gramáticas formales. Se espera además que el alumno sepa resolver problemas concretos utilizando herramientas como LEX y YACC.

Contenidos:

1. Conceptos básicos
   Caracterización de compiladores. Estructura interna de un compilador (fases, pasadas, manejo de símbolos y errores). Herramientas para construir compiladores.
2. Análisis léxico (scanning)
   Unidades léxicas de un programa (tokens). Especificación de unidades léxicas. Lenguajes y expresiones regulares. Reconocimiento de unidades léxicas. Autómatas finitos. Herramientas LEX (FLEX) y JLEX.
3. Análisis sintáctico (parsing)
   Estructura sintáctica de un programa. Lenguajes y gramáticas libres de contexto. Análisis ascendente/descendente. Autómatas recursivos. Descenso recursivo. Analizadores LR y LALR. Uso de gramáticas ambiguas. Herramientas YACC (BISON) y CUP.
4. Generación de código intermedio
   Traducción dirigida por la sintaxis. Análisis semántico (verificación de tipos). Código intermedio. Árboles sintácticos. Máquinas de stack (JVM). Interpretación de código intermedio. Código de tres direcciones. Manejo de tipos, arreglos, control de flujo, llamados a procedimientos.
5. Optimización de código
   Optimización de ciclos. Recursividad terminal.
6. Generación de código final
   Arquitectura típica de microprocesadores. Traducción de código intermedio. Compiladores just-in-time.
   

Actividades:

Clases expositivas del profesor (3 horas semanales). Trabajo personal de alumnos y clases auxiliares (7 horas semanales).

Evaluación:

Controles y tareas individuales (construcción de un compilador). La nota de controles y la nota de tareas tendrán la misma ponderación en la nota final del curso. Para aprobar se requiere por lo menos un 4.0 en controles y en tareas.

Bibliografía:

• Aho, Sethi & Ullman (1986) Compilers, principles, techniques, and tools, Benjamin Cummings.
• Manuales de LEX (o FLEX, JLEX) y de YACC (o BISON, CUP).