Patiperros del DCC

Requisitos

CC30B, CC41A

Objetivos

El principal objetivo de este curso es entregar los elementos 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.

Se trata por lo tanto de asociar los conceptos abstractos de programación (vistos en el curso "lenguajes de programación") a su implementación concreta en el ámbito tecnológico actual (materia estudiada en el curso "introducción al hardware"). Adicionalmente, se recalcará la influencia de la compilación sobre los lenguajes de programación y de máquina (ciertas estructuras de programación se han popularizado porque se pueden compilar adecuadamente; por otra parte, el hardware ha evolucionado para facilitar o hacer más eficiente esta compilación).

Programa

La compilación puede dividirse en tres grandes fases:

Análisis léxico (scanning)

Consiste en determinar las unidades elementales del programa procesado (instrucciones, operadores, identificadores, constantes, etc), para lo cual existen herramientas de software basadas en la teoría de autómatas finitos (en Unix: Lex).

Análisis sintáctico (parsing)

Se encarga de descubrir la estructura sintáctica del programa procesado, utilizando métodos descendentes (descenso recursivo) o ascendentes (LR y LALR), cuyo fundamento teórico son las gramáticas libres de contexto.

Existen herramientas de software que ayudan a construir analizadores sintácticos (en Unix: Yacc).

Generación y optimización de código

La generación de código es una manera de explicitar la semántica del programa (que es lo que éste hace). El código se construye composicionalmente, mediante acciones semánticas asociadas a las reglas sintácticas. Para la optimización interesa además que el código generado sea eficiente.

Las técnicas de compilación no se limitan a los lenguajes de programación: pueden aplicarse a todo tipo de problemas que involucren estructurar información secuencial, transformar formatos y traducir una especificación declarativa a una implementación final.

Bibliografía

Aho, Sethi & Ullman (1986) Compilers, principles, techniques, and tools, Addison Wesley.

Además se pueden consultar los manuales de Lex y de Yacc.