MATERIA:Compiladores

CLAVE:COMP-550

SEMESTRE DE UBICACION:Quinto

AREA:Ciencias de la Computación

OBJETIVOS: Este curso consiste de un estudio profundo de los principios y aspectos de diseño de los traductores de Lenguajes de Programación. Se discuten los componentes principales de un compilador: análisis léxico, análisis sintáctico, chequeo de tipos, generación de código y optimización. Se ven estrategias alternativas para el reconocimiento (descenso recursivo, reconocimiento descendente, predictivo, LR) y se comparan entre sí respecto al uso eficiente de tiempo y espacio. Entre los subtemas se incluye la ambigüedad, representación de datos, recuperación desde errores, diseño de tablas de símbolos, ligado, herramientas para la generación de compiladores, compilación incremental e intérpretes.

Trabajo sugerido: Se deberá contar con ejercicios de laboratorio que ayuden al estudiante a fijar y reforzar los conceptos, haciendo que diseñen e implementen componentes de un compilador para un lenguaje pequeño pero representativo. Se deberán implementar distintas estrategias de reconocimiento y comparar su eficiencia. El trabajo de laboratorio de este curso es adecuado para trabajo en equipo.

TEMARIO:

  1. Descripción general de un compilador

    Se describen las distintas organizaciones que puede presentar un compilador, desde la elección del lenguaje anfitrión hasta las etapas y fases de su implementación.

    • Introducción. Los lenguajes fuente, objeto y anfitrión

    • Estructura lógica de un compilador

  2. El analizador lexicográfico

    Se dan las principales características de esta etapa, así como las herramientas disponibles para implementarla. Se muestran los modelos matemáticos correspondientes a esta etapa.

    • Funciones principales

    • Implementación del analizador lexicográfico

    • Descripción formal de los conjuntos de átomos

    • Utilización de las distintas notaciones para el analizador léxico

    • Implementación de autómatas finitos

    • El problema de identificación

  3. Análisis sintáctico

    Los temas a tratar incluyen las características principales de esta etapa, su entrada y su salida y la manera como ella puede corresponder a la columna vertebral de todo el compilador.

    • Gramáticas libres del contexto

    • Arboles de derivación

    • Presentación del reconocimiento ascendente

    • Presentación del reconocimiento descendente

    • Descenso recursivo. Generación de código en descenso recursivo

    • Generación de código en gramáticas LL(1)

  4. Reconocimiento desde abajo

    Se muestran ejemplos de este tipo de reconocimiento que va desde el método por precedencia de operadores hasta los que se sustentan en la simulación de una máquina de stack.

    • Generalidades

    • Precedencia de operadores

    • Reconocimiento por tablas de precedencia simple.

    • Generación de código en reconocedores desde abajo

  5. Reconocedores LR(k)

    Se ve con detalle esta modalidad de reconocedores sintácticos que es hoy en día la mas poderosa disponible

    • Generalidades

    • Las tablas para los reconocedores LR(k)

    • Reconocedores LR(0)

    • Reconocedores SLR(1)

    • Construcción de tablas LR canónicas

    • Construcción de tablas LALR

    • Implementación de reconocedores LR.

    • Generación de código en gramáticas LR(k)

  6. La tabla de símbolos

    En esta sección se estudian distintas organizaciones posibles para la tabla de símbolos, dependiendo de las características que tenga el lenguaje fuente a compilar y la máquina y el lenguaje anfitriones.

    • Introducción

    • Organización de la tabla de símbolos

    • Información relevante en la tabla de símbolos

    • Estructuras de datos para la tabla de símbolos

    • Representación del rango y vigencia en la tabla de símbolos

  7. Manejo de memoria durante ejecución

    Se ve en esta sección el importantísimo tema de la administración de la memoria durante la ejecución del programa que nuestro compilador va a producir. Se cubren temas como la asignación estática, a través de un stack, memoria dinámica y recolección de basura.

    • Manejo estático de memoria

    • Manejo dinámico de memoria: Recursividad

    • Manejo dinámico de memoria: Asignación durante ejecución

  8. Generación de código intermedio

    Se ven distintas notaciones para representar al código intermedio, y que sea susceptible de ser optimizado. Se busca que estas representaciones tengan independencia de la máquina objeto en la cual el programa a traducirse va a ejecutarse.

    • Acciones semánticas y traducción dirigida por la sintaxis

    • Representaciones intermedias: Arboles sintácticos; gráficas dirigidas acíclicas (dag’s); notación postfija; código de tres direcciones; lenguajes intermedios

    • Traducción con reconocimiento ascendente

    • Gramáticas de atributos; atributos heredados y sintetizados

    • Acciones semánticas

  9. Optimización

    Se revisa en qué consiste la optimización que se pueden llevar a cabo. Se revisan las herramientas y metodologías existentes para llevar a cabo dicha optimización.

    • Optimización independiente de la máquina objeto

    • Gráficas dirigidas acíclicas en optimización

    • Análisis de flujo de datos

    • Optimización de ciclos

    • Otro tipo de optimizaciones

    • Optimización dependiente de la máquina objeto: registros e instrucciones.

BIBLIOGRAFIA:

  • Fischer, C>N>; Leblanc, R.J. Jr., Crafting A Compiler The Benjamin/Cummings Publishing Company, Inc., 1988

  • Tremblay, J.P.; Sorenson, P.G., The Theory And Practice Of Compiler Writting Mc Graw-Hill Book Company, 1985

BIBLIOGRAFIA COMPLEMENTARIA:

  • Gough, K. J. Syntax Analysis and Software Tools

  • Addison-Wesley Publishing Company,1988

  • Holub, A. I., Compiler Design In C, Prentice-Hall Inc.,1990

  • Terry, P.D., Programming Language Translation, A Practical Approach

  • Addison-Wesley Publishing Company,1986

  • Parsons, T.W., Introduction To Compiler Construction,

  • Computer Science Press, W.H. Freeman and Company, 1992