2.2.4 - Teoría de Lenguajes

Segundo Año

Característica del Área Curricular
Plan	2015
Cuatrimestre	Segundo
Hs. Cat.	60
Res. C.S.	291/2015

Presentación

La asignatura se ubica en el segundo semestre de segundo año de la Carrera. Esta actividad curricular brinda al alumno el conocimiento de las etapas de generación de código ejecutable mediante la construcción de un compilador.

Esta materia continúa con la formación en la algoritmia, lenguajes funcionales e introduce práctica sobre autómatas y analizadores de gramáticas.

Objetivos

Contribuir a la elaboración de lenguajes nuevos mediante la presentación de varios lenguajes representantes de las categorías existentes, dotando al alumno con una perspectiva que le permita cambiar el nivel de abstracción según el problema que se le pueda presentar. La asignatura esta basada en el diseño e implementación de minilenguajes, presentando las herramientas disponibles para ellos.

Contenido Temático

Unidad 1: Introducción

Historia de los lenguajes de programación. Lenguajes imperativos, declarativos y funcionales. Sintaxis y semantica. Algunos modelos semánticos: operacional, denotacional y axiomático.

Unidad 2 : Análisis sintáctico.

Clasificación de Chomsky y máquinas asociadas. Expresiones regulares y autómatas finitos. Gramáticas libres de contexto, gramáticas lalr(1) y autómatas de pila. Derivaciones y gramáticas ambiguas. Conflictos shift-reduce y reduce-reduce. Programas sintetizadores de autómatas: Flex, Bison, Mosmllex y Mosmlyac.

Unidad 3: Árbol de sintaxis abstracta

Sintaxis abstracta. Arboles sintácticos. Tratamiento de contextos. Tablas de símbolos. Entornos. Adscripción de semántica a los AST. Atributos heredados y sintetizados. Constructores.

Unidad 4 : Reescritura del AST

Detección y eliminación de subexpresiones comunes. Problemas asociados. Strength reduction: reemplazo de productos. Algoritmo del Campesino Ruso. Cocientes enteros con divisores constantes. Ejemplos de evaluación parcial.

Bibliografía

Modern Compiler Implementation in ML - Appel, A. E. - Cambridge University Press.
Compiladores, Principios y tecnicas y herramientas - Aho, Sethi, y Ullman - Addison-Wesley Iberoamericana - 1986
Linguagens Formais e Automatos - P. Menezes - Ed. Sagra Luzzatto - 2002