Traductores e Interpretadores (CI-3725)

Si estoy enseñado la teoría

Bibliografía

El curso estará basado sobre el libro

   Sudkamp, Thomas
   Languages and Machines
   Addison-Wesley Publishing
   ISB 0-321-32221-5
   QA267.3.S83

Pueden usar la Tercera Edición (tapa verde, como el que muestro el primer día de clase) o la Segunda Edición (tapa roja) por igual. En los cronogramas y material de apoyo hago referencia a la tercera edición de ese libro como [Sudkamp]. La numeración de los capítulos cambió entre la segunda y tercera edición, de modo que si Ud. tiene la segunda edición verifique el contenido.

Para el estudio de Gramáticas de Atributos y Analizadores utilizaré el libro

    Aho, Sethi & Ullman
    Compilers: Principles, Techniques and Tools
    Addison-Wesley Publishing
    ISB 0-201-10088-6
    QA76.76.C65A37

conocido como «el dragón» por la imagen que tiene en la portada. Pueden usar la Primera Edición (tapa blanca) o la Segunda Edición (tapa morada) por igual. En los cronogramas hago referencia a este libro como [ASU].

Un complemento muy bueno para la teoría y fuente de excelentes ejercicios es el libro

   Hopcroft & Ullman
   Introduction to Automata Theory, Languages and Compuation
   Addison-Wesley Publishing
   ISBN 0-201-02988-X
   QA267.H56

conocido como «la costurera» por la imagen que tiene en la portada. Es particularmente útil para la discusión sobre Máquinas de Turing. En los cronogramas hago referencia a este libro como [HU].

Evaluación

La evaluación consiste en tres (3) exámenes escritos presenciales, que representan respectivamente el veinte (20%), veinticinco (25%) y veinticinco (25%) de la calificación total. Consulte la página correspondiente al trimestre en curso para saber las fechas en que serán presentados, y las calificaciones resultantes.

Los exámenes deberán ser tomados en las fechas indicadas en el cronograma de clases. Para ser excusado de un examen es indispensable obtener todas las autorizaciones y documentación por escrito que exige el Departamento, y en ese caso el estudiante presentará un examen diferente pero equivalente al efectuado en la fecha original.

Copiar durante el examen desde el libro, notas de clase, otro compañero o cualquier otra fuente de información, será sancionado con el aplazamiento de la materia con uno (1) y una amonestación en la Coordinación de la carrera que puede llevar a la expulsión de la Universidad.

Durante cualquier examen estará terminantemente prohibido tener en su escritorio otra cosa que no sea el papel del examen, las hojas para escribir sus respuestas y los implementos para escribir. Cualquier otra pertenencia personal deberá estar guardada en su morral, bolso, maletín o debajo de su pupitre; esto incluye calculadoras, computadores portátiles, computadores de mano, reproductores de música y teléfonos celulares. Estos últimos en particular deben estar apagados (si suena su celular, usted pierde un punto en el examen).

Cronograma Habitual

Semana 1

  • Introducción — [Sudkamp] 2.1 a 2.3

    • Compilación, traducción e interpretación.
    • Lenguajes y su especificación finita.
    • Ejercicios

  • Conjuntos Regulares — [Sudkamp] 2.3 y 2.4, [HU] 2.5 y 2.8

    • Notación inductiva de conjuntos.
    • Expresiones Regulares («regex»).
    • Aplicación práctica en programación.
    • Ejercicios [Sudkamp] 2.14 hasta 2.41

Semana 2

  • Máquinas de Estado — [Sudkamp] 5.2-5.5, [HU] 2.2-2.4

    • Autómatas Finitos Determinísticos (DFA).
    • Autómatas Finitos No-Determinísticos (NFA).
    • λ-transiciones (λ-NFA).
    • Ejercicios [Sudkamp] 5.1 hasta 5.35

  • Equivalencias — [Sudkamp] 6.1 y 5.6, [HU] 2.5

    • Equivalencia entre regex y λ-NFA.
    • Equivalencia entre λ-NFA y DFA.
    • Equivalencia entre DFA y regex.
    • Ejercicios [Sudkamp] 5.36 hasta 5.42 y 6.1 hasta 6.3

Semana 3

  • Equivalencias — [Sudkamp] 6.2 y 5.7

    • Minimización de DFA.
    • Aplicación al Análisis Lexicográfico.
    • Ejercicios [Sudkamp] 5.43 y 5.45

  • Propiedades de los Conjuntos Regulares — [Sudkamp] 7.4 y 7.6, [HU] 3.1 y 3.2

    • Propiedades de Clausura.
    • Lema de Bombeo para Lenguajes Regulares.
    • Ejercicios [Sudkamp] 6.11, 6.12 y 6.14

Semana 4

  • Primer Examen

  • Lenguajes Libres de Contexto — [Sudkamp] 3.1-3.5, [HU] 4.2 y 4.3

    • Gramáticas Libres de Contexto (CFG).
    • Derivaciones y Arboles de Derivación.
    • Lenguaje Generado por una Gramática.

Semana 5

  • Transformación de Gramáticas — [Sudkamp] 4.1-4.8

    • Transformaciones varias.
    • Forma Normal de Chomsky.
    • Forma Normal de Greibach.

  • Autómatas de Pila y Variaciones — [Sudkamp] 7.1-7.3, [HU] 5.1-5.3

  • Propiedades de CFG y PDA — [Sudkamp] 7.4-7.5, [HU] 6.1-6.2

    • Equivalencia entre CFG y PDA.
    • Propiedades de Clausura.
    • Lema de Bombeo para Lenguajes Libres de Contexto.

Semana 6

  • Gramática de Atributos — [ASU] 5.1-5.5

    • Aplicación al Análisis de Contexto.
    • Aplicación a la Traducción Dirigida por Sintaxis.

  • Reconocedor Descendente — [Sudkamp] 19.2-19.8 y [ASU] 4.4

    • Lookahead.
    • Cálculo de FIRST y FOLLOW.
    • Gramática Fuertemente LL(1).

Semana 7

  • Reconocedor Descendente — [Sudkamp] 19.2-19.8 y [ASU] 4.4

    • Reconocedor no-recursivo por tablas.
    • Construcción de Tablas LL(1).
    • Reconocedor recursivo descendente.

  • Segundo Examen

Semana 8

  • Reconocedor Ascendente — [Sudkamp] 20.1-20.3 y [ASU] 4.5

    • Asas (handles) y Prefijos Viables.
    • Items de una Producción y su Clausura.
    • Autómata de Prefijos Viables.

  • Reconocedor Ascendente — [ASU] 4.7 y 4.8

    • Construcción de Tablas LR(0) y SLR(1).
    • Reconocedor LR.

Semana 9

  • Máquinas de Turing — [Sudkamp] 8.1-8.7, [HU] 7.1-7.5

    • Máquinas de Turing como calculadora.
    • Máquinas de Turing cmo aceptadora.
    • Discusión informal de las variaciones.

  • Máquinas de Turing — [Sudkamp] 8.8, [HU] 7.7

    • Máquina de Turing como enumeradora.
    • Lenguajes Recursivos (REC).
    • Lenguajes Recursivamente Enumerables (RE).

Semana 10

  • Propiedades de Clausura — [Sudkamp] 11.5 y 12.1, [HU] 8.2-8.3

    • Propiedades de Clausura REC.
    • Propiedades de Clausura RE.
    • Máquina Universal.
    • Problema de la Parada.
    • Existencia de lenguajes no-REC y no-RE.

  • Decidibilidad — [Sudkamp] 11.1-11.4 y 12.2-12.4, [HU] 8.2-8.3

    • Problemas de Decisión.
    • Reducción.
    • Teorema de Rice.

Semana 11

  • Complejidad — [Sudkamp] 11.3-11.5 y 12.1, [HU] 8.2-8.3

    • Complejidad en Tiempo.
    • Complejidad en Espacio.

  • Tercer Examen

Si estoy en el laboratorio

...es porque soy el coordinador del laboratorio.

Evaluación

La evaluación consiste en un (1) proyecto de programación dividido en cuatro (4) entregas parciales, que representan respectivamente el cinco (5%), seis (4%), siete (9%) y diez (10%) de la calificación total. Consulte la página correspondiente al trimestre en curso para saber las fechas en que serán entregadas y las calificaciones.

La complejidad de las entregas aumenta notablemente en cada etapa, por lo cual es recomendable que trabaje sobre cada una de ellas tan pronto como le sea posible. Si bien las dos primeras entregas suelen ser muy fácil y rápida de desarrollar, es improbable que pueda hacer la tercera entrega en menos de cuatro días de trabajo, ni la última en menos de una semana y media de trabajo. Han sido advertidos.

Puesto que se trata de un proyecto por partes, para la segunda parte deberá corregir cualquier cosa que haya faltado en la primera; y para la tercera parte deberá corregir cualquier cosa que haya faltado en la segunda; y para la cuarta parte deberá corregir cualquier cosa que haya faltado en la tercera. Considere que el grueso de la evaluación final está basado en la corrida correcta y completa del interpretador.

Equipos

Los equipos son de dos (2) personas. Para la tercera semana debo haber recibido de ustedes un mensaje de correo con la constitución de los equipos; caso contrario los asignaré al azar.

Copiar el proyecto de otro compañero será sancionado con el aplazamiento del proyecto, y el desenlace de la materia dependerá de la opinión del Profesor que coordine la asignatura. Independientemente de eso recibirán una amonestación en la Coordinación de la carrera que puede llevar a la expulsión de la Universidad.

Si encuentran en biblioteca, hemeroteca o Internet un artículo, fragmento o aplicación que resuelva total o parcialmente sus proyectos, es válido utilizarlo siempre y cuando cumpla con dos condiciones simultáneamente:

  • Cite completa y correctamente el origen del trabajo (dónde lo encontró y quién lo escribió originalmente).

  • Prepárese a explicarlo completamente en revisión personal.

Resolver problemas apoyándose en soluciones de otros es perfectamente válido, siempre y cuando se tenga el coraje académico de reconocerlo.

Herramientas de Programación

Usaremos los lenguajes de programación Haskell o Ruby para desarrollar las soluciones a los proyectos propuestos en clase. Deben escoger un lenguaje para su proyecto al iniciar, y mantenerlo durante todo el trimestre; esto es, no pueden cambiar de lenguaje una vez hecha la Primera Entrega.

Si escoge trabajar con Haskell:

  • Este curso no es para aprender Haskell — si Ud. ya conoce Haskell y sus herramientas, tiene libertad de usarlas. Si es la primera vez que va a utilizar Haskell, el aprendizaje del lenguaje, el estilo funcional, y las librerías, corre por su cuenta.

  • Debe utilizar GHC 7.6 o 7.8 con la Plataforma Haskell estándar.

  • Debe utilizar Alex como generador de analizadores lexicográficos.

  • Debe utilizar Happy como generador de analizadores sintácticos LALR.

  • Solamente puede utilizar librerías provistas por Haskell Platform estándar — no puede instalar librerías de terceros.

Si escoge trabajar con Ruby:

  • Este curso no es para aprender Ruby. Si es la primera vez que va a utilizar Ruby, el estilo orientado a objetos no es un inconveniente, pero el tiempo para explorar la librería estándar, corre por su cuenta.

  • Debe utilizar expresiones regulares nativas de Ruby para construir el analizador lexicográfico.

  • Debe utilizar Racc como generador de analizadores sintácticos LALR.

  • Solamente puede utilizar librerías estándar provistas en la base Ruby — no puede emplear gemas ni librerías de terceros.

¿Haskell o Ruby?

Usar Haskell hará que los tres primeros proyectos sean sumamente simples en comparación con sus equivalentes en Ruby, en virtud de lo poderoso del lenguaje propiamente, de Alex y Happy. Sin embargo, la implantación de la última etapa puede tornarse sumamente complicada, en particular si Ud. no domina Monads para manipular estado mutable.

Usar Ruby hará que los dos primeros proyectos sean algo más largos de escribir en comparación con sus equivalentes en Haskell, por la necesidad de construir manualmente cosas que podrían generarse automáticamente, además de la necesidad de modelar jerarquías de clases para tokens y un árbol de amplitud arbitraria. La implantación de la última etapa será un ejercicio en recorrido de árboles con un objeto mutable.

Cronograma y Material de Apoyo

El cronograma del laboratorio es cambiante, pues depende de la relación entre los días de clase de teoría con el de laboratorio.

Los ejercicios a resolver en el laboratorio también varían. Aquí encontrará algunos ejercicios resueltos, que ni son suficientes, ni necesariamente aplican para todas las versiones del laboratorio.

Ediciones Pasadas