Datos Identificativos 2012/13
Asignatura (*) Compiladores Código 614451111
Titulación
Mestrado Universitario en Enxeñaría de Sistemas Informáticos
Descriptores Ciclo Período Curso Tipo Créditos
Mestrado Oficial Anual
 Primeiro Obrigatoria 5
Idioma
Castelán
Galego
Prerrequisitos
Departamento Tecnoloxías da Información e as Comunicacións
Coordinación
Dafonte Vazquez, Jose Carlos
 Correo electrónico
carlos.dafonte@udc.es
Profesorado
Dafonte Vazquez, Jose Carlos
 Correo electrónico
carlos.dafonte@udc.es
Web http://lia2.tic.udc.es/compiladores
Descrición xeral Compiladores;cc traductores e intérpretes; etapas de un compilador; optimización de código; macroprocesadores.
O obxectivo é familiarizar ó alumno co funcionamento dos compiladores, o entorno no que traballan así coma algunhas ferramentas software para a construcción dos mesmos.Asumir a característica interdisciplinar da asignatura. Adquirir os coñecementos necesarios para deseñar e implementar as diferentes etapas necesarias para o desenvolvemento dun compilador: análise (léxico, sintáctico e semántico) e síntese (xeración de código intermedio, optimización de código e xeración de código obxeto).

Competencias do título
Código Competencias da titulación
A2 Arquitectura de computadores.
A5 Capacidade para entender e avaliar especificacións internas e externas.
A7 Dirección, planificación e xestión de proxectos.
A8 Deseño e arquitectura de Sistemas de Información.
A9 Documentación técnica.
A11 Enxeñería do software.
A12 Integración de sistemas.
B1 Capacidade de análise e síntese.
B2 Capacidade de organización e planificación de proxectos informáticos.
B3 Capacidade de xestión da información.
B4 Capacidade de resolución de problemas.
B5 Toma de decisións.
B6 Traballo en equipo.
B7 Habilidades nas relacións interpersoais e interdisciplinares.
B8 Razoamento crítico.
B10 Aprendizaxe autónoma.
B11 Adaptación a novas situacións.
B12 Creatividade.
B15 Motivación pola calidade.
C1 Expresarse correctamente, tanto de forma oral coma escrita, nas linguas oficiais da comunidade autónoma.
C3 Utilizar as ferramentas básicas das tecnoloxías da información e as comunicacións (TIC) necesarias para o exercicio da súa profesión e para a aprendizaxe ao longo da súa vida.
C6 Valorar criticamente o coñecemento, a tecnoloxía e a información dispoñible para resolver os problemas cos que deben enfrontarse.
C7 Asumir como profesional e cidadán a importancia da aprendizaxe ao longo da vida.
C8 Valorar a importancia que ten a investigación, a innovación e o desenvolvemento tecnolóxico no avance socioeconómico e cultural da sociedade.

Resultados de aprendizaxe
Competencias de materia (Resultados de aprendizaxe) Competencias da titulación
Coñecer e comprender as técnicas utilizadas para o deseño de compiladores. Deseñar e implementar as diferentes fases necesarias para o deseño dun compilador. Coñecer e manexar algunhas das ferramentas máis habituais neste campo. AP2
AP5
AP7
AP8
AP9
AP11
AP12
 BP1
BP2
BP3
BP4
BP5
BP6
BP7
BP8
BP10
BP11
BP12
BP15
 CM1
CM3
CM6
CM7
CM8

Contidos
Temas Subtemas
Tema I. Introducción 1.1 Estructura de un compilador.
1.2 Ejemplo de las fases de un compilador.
Tema II. Lenguajes y Gramáticas 2.1 Notación de Chomsky.
2.2 Clasificación de Chomsky.
2.3 Gramáticas de contexto libre (GCL).
2.4 Diagramas de Conway.
2.5 Reglas BNF.
2.6 Problemas en las GCL.
2.7 Simplificación de gramáticas.
2.8 Gramática limpia.
2.9 Forma normal de Chomsky (FNC).
2.10 Resumen.
2.11 Ejercicios.
Tema III. Análisis Léxico 3.1 Tipos de máquinas reconocedoras o autómatas.
3.2 Autómatas Finitos.
3.3 Conversión de una Gramática Regular en un Autómata finito.
3.4 Expresión regular.
3.5 Algoritmo de Thompson.
3.6 Transformación de un AFND-lambda en un AFD.
3.7 Traductores finitos (TF).
3.8 Implementación de autómatas.
3.8.1 Tabla compacta.
3.8.2 Autómata programado.
3.9 Ejemplo. Scanner para números reales sin signo en Pascal.
3.10 Acciones semánticas.
3.11 Generador LEX.
Tema IV. Análisis sintáctico (Parsing) 4.1 Máquinas teóricas, mecanismos con retroceso
4.1.1 Autómatas con pila (AP).
4.1.2 Esquemas de traducción (EDT).
4.1.3 Traductores con pila (TP).
4.2 Algoritmos sin retroceso.
4.2.1 Análisis sintáctico ascendente por precedencia simple.
4.2.2 Análisis sintáctico ascendente por precedencia de operadores.
4.2.3 Analizadores descendentes LL(K).
4.2.4 Analizadores ascendentes LR(k).
4.2.5 Generador de analizadores sintácticos YACC.
Tema V. Análisis semántico 5.1 Definiciones dirigidas por la sintáxis.
5.2 Esquema de traducción.
5.3 Comprobaciones en tiempo de compilación.
Tema VI. Generación de código 6.1 Lenguajes intermedios.
6.2 Generación de código intermedio.
6.3 Generación de código desde lenguaje intermedio.
Tema VII. Optimización de código 7.1 Algoritmo de Nakata.
7.2 Un ejemplo de optimización manual.
7.3 Lazos en los grafos de flujo.
7.4 Análisis global del flujo de datos.
7.5 Solución iterativa de las ecuaciones de flujo de datos.
Tema VIII. Errores 8.1 Tipos de errores.
8.2 Recuperación de errores léxico-gráficos.
Tema IX. Intérpretes y complementos 9.1 Estructura de un intérprete actual.
9.2 Arquitectura neutral de java.

Planificación
Metodoloxías / probas Horas presenciais Horas non presenciais / traballo autónomo Horas totais
Sesión maxistral 40 40 80
Proba obxectiva 3 3 6
Prácticas de laboratorio 15 15 30
 
Atención personalizada 9 0 9
 
*Os datos que aparecen na táboa de planificación son de carácter orientativo, considerando a heteroxeneidade do alumnado

Metodoloxías
Metodoloxías Descrición
Sesión maxistral Sesións maxistrais coincidentes entre a asignatura do Master e en Enxeñería Informática. O axuste de horas non é exacto pero, de cara a facilitar o desenvolvemento do proxecto, no segundo cuatrimestre dispoñerase dunha reducción de horas maxistrais a tal efecto, igualando o esquema de docencia entre ambas.
Proba obxectiva Faranse dous exames, un en febreiro/marzo sobre o contido do primeiro cuatrimestre e outro en xuño do contido do segundo cuatrimestre. Neste último tamén haberá unha segunda oportunidade para recuperar, se é necesario, a materia do primeiro cuatrimestre.
Prácticas de laboratorio Realizaranse varias pequenas prácticas hasta xaneiro e a partir de ahí haberá que desenvolver un proxecto que involucre a maior parte das fases dun compilador. Este proxecto será proposto polo estudante.

Atención personalizada
Metodoloxías
Prácticas de laboratorio
Descrición
Especialmente no caso do proxecto a desenvolver polo alumno, realizarase un seguimento semanal dos traballos.

Avaliación
Metodoloxías Descrición Cualificación
Proba obxectiva Duas probas (febreiro/marzo e xuño) que aportarán cada únha un 50% da nota neste apartado (será condición imprescindible ter presentadas as pequenas prácticas iniciais). 60
Prácticas de laboratorio Proxecto a propoñer e desenvolver polo alumno durante o segundo cuatrimestre 40
 
Observacións avaliación

En calquera caso, é preciso aprobar as dúas parte. No caso contrario, a máxima nota que se poderá acadar é un 4.5.


Fontes de información
Bibliografía básica

Bibliografía complementaria

"Compiladores: Principios, técnicas y herramientas", Aho, A.V.; Lam M.; Sethi, R. ; Ullman, J.D., Addison-Wesley, Reading, Massachussetts 2008.

"Construcción de compiladores. Principios y Práctica", Louden D. K., Paraninfo Thomson Learning, 2004.

Garrido, A. ; Iñesta J.M. ; Moreno F. ; Pérez J.A. [2004] Diseño de compiladores, Publicaciones Universidad de Alicante.

"Compiladores, teoría y construcción", Sanchis, F.J.; Galán, J.A., Ed. Paraninfo, 1987.

"The theory of parsing, translation and compiling" (I y II), Aho, A.V.; Ullman, J.D., Prentice-Hall, 1972.

"Principles of compiler design", Aho, A.V.; Ullman J.D., Addison-Wesley, 1977.

"Introducción a la teoría de autómatas, lenguajes y computación", Hopcroff, J.E. ; Motwani R. ; Ullman, J. D. [2002] I, Addison-Wesley, 2002

"Compiler design in C", Allen I.; Holub, Prentice-Hall, 1991.

"Compiladores e Intérpretes", Sánchez, G.; Valverde J.A., Ed. Díaz de Santos, 1984.

“Languages and machines”, Sudkamp T.A., Addison-Wesley, 1994

Recomendacións
Materias que se recomenda ter cursado previamente

Materias que se recomenda cursar simultaneamente
Deseño de Sistemas Operativos/614407114
Enxeñería do Software/614407115

Materias que continúan o temario
Linguaxes Naturais/614407220

Observacións
A asignatura troncal de Enxeñería Informática e Enxeñería Técnica en Informática de Sistemas "Teoría de autómatas e linguaxes formais" é de gran utilidade para a comprensión da asignatura de Compiladores.


(*)A Guía docente é o documento onde se visualiza a proposta académica da UDC. Este documento é público e non se pode modificar, salvo casos excepcionais baixo a revisión do órgano competente dacordo coa normativa vixente que establece o proceso de elaboración de guías