Teoría de Lenguajes

Teoría de Lenguajes es una materia que tiene como objetivo presentar las nociones de lenguaje formal y de sintaxis y semántica de lenguajes, imprescindibles para la construcción de compiladores. Pertenece al Departamento de Computación y segun el plan de la carrera, deberia cursarse en Cuarto Año. Es correlativa de Lógica y Computabilidad. Se cursa los Lunes, Miercoles y Jueves.

Programa

Primera Parte

Introducción. Lenguajes y gramáticas. Clasificación de Chomsky. Lenguajes regulares, Autómatas. Expresiones regulares. Equivalencias entre expresiones regulares, gramáticas regulares y autómatas. Lema de pumping. Minimización de autómatas. Decidibilidad de problemas básicos y propiedades de clausura. Analizadores lexicográficos. Lenguajes independientes de contexto. Arboles de derivación. Lema de pumping para lenguajes independientes de contexto, Gramáticas reducidas. Autómatas de pila. Lenguajes determinísticos, Equivalencias entre autómatas de pila y gramáticas libres de contexto.

Segunda Parte

Lenguajes tipo 1 y tipo 0. Máquinas asociadas. Parsers ascendentes y descendentes. Método LL(1). Parser descendente recursivo y por tablas. Transformación de gramáticas. Propiedades de las gramáticas LL(1). Métodos ascendentes. Métodos de precedencia. Métodos LR. LR(0). Propiedades. Métodos LR(0), SLR(1), LR(1) y LALR(1). Gramáticas de atributos. Definiciones guiadas por la sintaxis. Esquemas de traducción. Aplicación al análisis semántico y la generación de código. Semántica de los lenguajes de programación. Semántica operacional natural. Semántica operacional de computación.

Prácticas

Primer Parcial

• Práctica 0: Preliminares
• Práctica 1: Gramáticas Regulares y Autómatas Finitos
• Práctica 2: Expresiones regulares
• Práctica 3: Autómatas finitos -Continuación-
• Práctica 4: Lenguajes regulares y lema de pumping
• Práctica 5: Traductores finitos
• Práctica 6: Gramáticas libres de contexto y autómatas de pila

Segundo Parcial

• Práctica 7: Maquinas de Turing y ALL
• Práctica 8: Escritura y simplificacion de GLC
• Práctica 9: Parsers descendentes
• Práctica 10: Gramaticas y parsers de precedencia
• Práctica 11: Gramaticas y parsers LR
• Práctica 12: Gramaticas de atributos y TDS

Apuntes

Primer Parcial

• Apuntes Varios

Segundo Parcial

• Definiciones y teoremas

Final

• Notas de estudio de Raul Latashen
• Apunte para el final de Soledad Ramusio
• Demostraciones: Lista de las demostraciones vistas en la materia.
  • Lenguajes Regulares
• Preguntas: Lista de algunas preguntas de final tomados en los últimos años.
• Ejemplos: Ejemplos de lenguajes y gramáticas vistos en la materia.
• Apunte de toda la materia (Dr. Ramon Brena Pinero): Parte 1, Parte 2.

Finales

• Final del 11/08/08
• Final del 17/09/10

Parciales

Primeros Parciales

• Primer Parcial 1C 2012
• Primer Parcial Recuperatorio 2C 2006

Segundos Parciales

• Segundo Parcial 2C 2006
• Segundo Parcial Recuperatorio 2C 2006
• Segundo Parcial 1C 2006
• Segundo Parcial Recuperatorio 1C 2006

Trabajos Prácticos Viejos

• 2006 - 1er Cuatrimestre TP

Enlaces externos

• Pagina Oficial de la Materia
• Apunte sobre el calculo de Primeros y Siguientes para gramaticas
• Slides de un curso de compiladores de Oscar Bonilla
• Context-Free Grammar Tool: La Victorinox de las gramáticas libres de contexto. Genera todo tipo de autómatas y tablas y chequea muchas propiedades.