Teoría de Lenguajes

De Cuba-Wiki

Teoria 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 Computacion y segun el plan de la carrera, deberia cursarse en Cuarto Año. Es correlativa de Logica y Computabilidad. Se cursa los Lunes, Miercoles y Jueves.

Programa

  • Introducción.
  • Lenguajes y gramaticas
  • 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.
  • 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.


Trabajos Prácticos Viejos

2006 - 1er Cuatrimestre TP

Enlaces externos

Pagina Oficial de la Materia