Compiladores e Interpretes

1
ASIGNATURA: COMPILADORES E INTERPRETES

Cód.: 31-403
Horas reloj semanales: 4
Horas prácticas: 30
Horas teóricas: 30
Horas totales: 60
Carrera: Sistemas
Año del programa 2016
FUNDAMENTOS:
Esta asignatura es el punto de entrada en el mundo de la Informática Teórica en el sentido de

disciplina que crea y explora fundamentos teóricos en busca de ideas que permitan el posterior
desarrollo de los sistemas informáticos. Tradicionalmente se distinguen dos grandes campos dentro de
la Informática Teórica: la Teoría de Lenguajes Formales y las Teorías de Computabilidad y
Complejidad. Aquí presentamos una introducción al primer campo, la Teoría de Lenguajes Formales.
La problemática que se estudia en esta asignatura tiene dos vertientes. Por un lado, veremos cómo se
puede describir el conjunto de palabras que forman un lenguaje determinado. Esta problemática
aparece, por ejemplo, al intentar describir un lenguaje de programación o un idioma determinado. Se
presentan dos mecanismos para describir lenguajes, las expresiones regulares y las gramáticas
incontextuales. Por otro lado, nos interesa que un ordenador sea capaz de distinguir las palabras que
siguen las reglas de un lenguaje de las que no las siguen. Cualquier aplicación que reciba una entrada
en un cierto formato, ya sea código en un cierto lenguaje de programación o un comando en lenguaje
natural, deberá ser capaz de comprobar si dicha entrada es correcta. Se presentan dos mecanismos para
reconocer las palabras de un lenguaje: los autómatas finitos y los autómatas con pila.
OBJETIVOS:
Al finalizar el curso, el estudiante habrá adquirido las habilidades necesarias y suficientes para
comprender los fundamentos básicos de los lenguajes formales, sus propiedades y mecanismos de
representación. Entender el funcionamiento de las gramáticas como generadores de lenguajes y
diferenciar sus tipos. Destacar el papel de los autómatas en el reconocimiento de lenguajes y distinguir
entre los diferentes tipos de autómatas. Relacionar tipos de lenguajes con autómatas y gramáticas,
sobre todo para lenguajes regulares y libres de contexto. Introducir herramientas avanzadas de
representación de lenguajes. Comprender y analizar algoritmos básicos en el contexto de lenguajes
formales.
CONTENIDOS MÍNIMOS:
- Unidad I: Introducción a los Lenguajes Formales y autómatas. Minimización de Autómatas.

Jerarquía de Chomsky. Gramáticas e Isomorfismos. Intérpretes y compiladores. Semántica formal.
- Unidad II: Lenguajes Regulares.
- Unidad III: Lenguajes Libres de Contexto.
- Unidad IV: Máquina de Turing. Expresiones regulares. Teoría de la Computabilidad y Complejidad
PROGRAMA ANALÍTICO:
Unidad I: Introducción a los Lenguajes Formales.

2
Concepto de Lenguaje. Símbolo. Alfabeto. Cadena. Operaciones con lenguajes. La Jerarquía de

Chomsky. Gramáticas e Isomorfismos. Concepto de Intérpretes y compiladores. Nociones básicas de
semántica formal.
Unidad II: Lenguajes Regulares.

Autómatas finitos: funcionamiento. Definición formal. Métodos de diseño. Equivalencia de autómatas
finitos. Simplificación de autómatas finitos. Autómatas finitos con salida: Máquina de Moore y
máquina de Mealy. Autómatas finitos no deterministas. Definición formal de lenguajes regulares.
Expresiones regulares: significado de las expresiones regulares. Metodología de diseño de las
expresiones regulares. Equivalencias de las expresiones regulares. Equivalencia de expresiones
regulares y autómatas finitos. Gramáticas regulares. Autómatas finitos y gramáticas regulares.
Limitaciones de los lenguajes regulares.
Unidad III: Lenguajes Libres de Contexto.

Lenguajes y gramáticas libres de contexto. Formalización de las gramáticas libres de contexto. Diseño
de las gramáticas libres de contexto. Árboles de derivación. Ambigüedad en gramáticas libres de
contexto. Gramáticas libres y sensitivas al contexto. Limitaciones de los lenguajes libres de contexto.
Autómatas de pila: Diseño de autómatas de pila. Formalización de los autómatas de pila. Relación
entre autómatas finitos y autómatas de pila. Compiladores LL y LR
Unidad IV: Máquina de Turing.

Funcionamiento de la Máquina de Turing. Formalización de las Máquinas de Turing. Máquinas de
Turing para el cálculo de funciones. Límites de las Máquinas de Turing. Máquinas de Turing en la
jerarquía de Chomsky. Conceptos Básicos de la Teoría de la Computabilidad y Complejidad.
Problemas computables y no computables: problemas tratables e intratables. Funciones Recursivas
METODOLOGIAS DE ENSEÑANZA Y APRENDIZAJE:
La duración del curso es de quince semanas de cuatro horas (teoría 2 horas y práctica 2 horas) de
duración, con una asistencia mínima del 75% y examen final. El desarrollo de las temáticas se hará en
forma teórico práctica.
EVALUACION:
Durante la cursada se evaluará al estudiante a través de:

• Breve consulta escrita sobre un tema tratado.
• Evaluación parcial sobre tópicos conceptuales.
• Parcial resolutivo de ejercicios prácticos.
• Opinión formada por el docente.
CRONOGRAMA:
Unidad I: 4 clases.
Unidad II: 3 clases.
Unidad III: 4 clases.
Unidad IV: 4 clases.
BIBLIOGRAFIA:
 Ebook Vázquez Juan y otros, Lenguajes Formales Y Teoria De Autómatas, Editorial

AlfaOmega 2015, IBSN 9786076224670
3
 Ebook Ruiz, E., Compiladores: Teoría E Implementación , ISBN 9786076220320
 Ebook Mandado, E. y otros Autómatas Programables, , Editorial AlfaOmega, 2009, ISBN

9786077072867
 Ebook Mandado, E. y otros Autómatas Programables Y Sistemas de automatización , Editorial

AlfaOmega, 2009, ISBN 9786077074854
Planeamiento Educativo
GdePlaneamiento@kennedy.edu.ar
4

Compiladores e Interpretes

Cargado por

Copyright:

Formatos disponibles

Compiladores e Interpretes

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Compiladores e Interpretes

Cargado por

Copyright:

Formatos disponibles

1

ASIGNATURA: COMPILADORES E INTERPRETES

Esta asignatura es el punto de entrada en el mundo de la Informática Teórica en el sentido de

- Unidad I: Introducción a los Lenguajes Formales y autómatas. Minimización de Autómatas.

Unidad I: Introducción a los Lenguajes Formales.

Concepto de Lenguaje. Símbolo. Alfabeto. Cadena. Operaciones con lenguajes. La Jerarquía de

Unidad II: Lenguajes Regulares.

Unidad III: Lenguajes Libres de Contexto.

Unidad IV: Máquina de Turing.

METODOLOGIAS DE ENSEÑANZA Y APRENDIZAJE:

Durante la cursada se evaluará al estudiante a través de:

 Ebook Vázquez Juan y otros, Lenguajes Formales Y Teoria De Autómatas, Editorial

 Ebook Ruiz, E., Compiladores: Teoría E Implementación , ISBN 9786076220320

 Ebook Mandado, E. y otros Autómatas Programables, , Editorial AlfaOmega, 2009, ISBN

 Ebook Mandado, E. y otros Autómatas Programables Y Sistemas de automatización , Editorial

También podría gustarte