Teoría de Lenguajes

2do Cuatrimestre de 2008

Información

Aulas y Horarios

Teórica

Lunes: 18 a 21 hs. Aula 11 del Pabellón I.

Práctica

Miércoles: 17 a 19:30 hs. Aula 13 del Pabellón I.
Jueves: 17 a 19:30 hs. Aula 2 del Pabellón I.

Correlatividad

Lógica y Computabilidad

Objetivos

Presentar las nociones de lenguaje formal y de sintaxis y semántica de lenguajes, imprescindibles para la construcción de compiladores.

Bibliografía

Temario

  1. Introducción.
  2. Lenguajes y gramaticas
  3. Clasificación de Chomsky
  4. Lenguajes regulares. Autómatas.
  5. Expresiones regulares.
  6. Equivalencias entre expresiones regulares, gramáticas regulares y autómatas.
  7. Lema de pumping.
  8. Minimización de autómatas.
  9. Decidibilidad de problemas básicos y propiedades de clausura
  10. Analizadores lexicográficos.
  11. Lenguajes independientes de contexto.
  12. Arboles de derivación.
  13. Lema de pumping para lenguajes independientes de contexto. Gramáticas reducidas.
  14. Autómatas de pila.
  15. Lenguajes determinísticos. Equivalencias entre autómatas de pila y gramáticas libres de contexto.
  16. Lenguajes tipo 1 y tipo 0. Máquinas asociadas.
  17. Parsers ascendentes y descendentes.
  18. Método LL(1).
  19. Parser descendente recursivo y por tablas.
  20. Transformación de gramáticas.
  21. Propiedades de las gramáticas LL(1).
  22. Métodos ascendentes.
  23. Métodos de precedencia.
  24. Métodos LR. LR(0). Propiedades.
  25. Métodos LR(0), SLR(1), LR(1) y LALR(1).
  26. Gramáticas de atributos. Definiciones guiadas por la sintaxis.
  27. Esquemas de traducción.
  28. Aplicación al análisis semántico y la generación de código.
  29. Semántica de los lenguajes de programación. Semántica operacional natural.
  30. Semántica operacional de computación.