Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Compiladores (CL)

Créditos Dept. Tipo Requisitos
9.0 (7.2 ECTS) CS
  • Obligatoria para la EI
  • Optativa para la ETIG
  • Optativa para la ETIS
ALCC - Prerequisito para la ETIS
EC1 - Prerequisito para la EI , ETIG , ETIS
PRED - Prerequisito para la EI , ETIG
PS - Prerequisito para la ETIS
TC - Prerequisito para la EI , ETIG

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

Cubrir los contenidos especificados en la troncalidad de procesadores del lenguaje, y los siguientes objetivos específicos.

Objectivos Específicos

Conocimientos

  1. Técnicas y herramientas generales, flexibles y eficientes para la compilación de lenguajes de programación y para otras aplicaciones, como los formateadores de texto (LaTeX, nroff), lenguajes gráficos (postscript, CIF, GIF, JPEG), lenguajes de descripción de hardware (VDHL, Verilog), lenguajes de simulación (simscript, GPs), intérpretes de querys y comandos, o los compiladores de silicio.
  2. Una aplicación en la que se utilizan y consolidan multitud de conceptos aprendidos previamente: lenguajes formales y autómatas, programación estructurada y recursiva, tipos abstractos de datos, etc.

Habilidades

  1. Ser capaz de desarrollar aplicaciones prácticas de las técnicas y herramientas estudiadas (por ejemplo, transformaciones de datos, o sencillos intérpretes).
  2. Ser capaz de completar algún módulo de un compilador modular moderno, como aplicación en la que son imprescindibles la robustez (ausencia de errores de ejecución) y la corrección (del código objeto producido).

Competencias

  1. Ser mejores programadores a través de un mejor conocimiento de los lenguajes de programación, en su sintaxis, semántica, e implementación eficiente.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Introducción y motivación
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
Estructura y fases de un compilador.
¿Por qué estudiar compiladores?
El porqué de la organización de la asignatura.

2. Análisis léxico
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 0 2,0 0 2,0 6,0 0 13,0
Definición del problema. Repaso de lenguajes regulares y autómatas finitos, varios algoritmos y sus costes. Tratamiento de errores, la herramienta PCCTS, otras aplicaciones.
  • Laboratorio:
    Manejo de la herramienta PCCTS y otras aplicaciones similares.
  • Actividades de laboratorio adicionales:
    Lectura, comprensión y análisis de la hoja de laboratorio correspondiente a la sesión.

3. Análisis sintáctico
T      P      L      Alt    L Ext. Est    O. Ext. Total 
12,0 0 4,0 0 4,0 12,0 0 32,0
Repaso de gramáticas de contexto libre y autómatas de pila.
Árboles de sintaxis concreta y abstracta, técnicas de parsing descendente y ascendente, la herramienta PCCTS, otras aplicaciones.
  • Laboratorio:
    Manejo de la herramienta PCCTS y otras aplicaciones.
  • Actividades de laboratorio adicionales:
    Lectura, comprensión y análisis de las hojas de laboratorio correspondientes a la sesión.

4. Análisis semántico
T      P      L      Alt    L Ext. Est    O. Ext. Total 
8,0 0 12,0 0 12,0 8,0 0 40,0
Lenguajes con estructura de bloques, paso de parámetros, comprobación de tipos, equivalencias de tipos, conversión explícita e implícita de tipos. Otros paradigmas de programación.
  • Laboratorio:
    Implementación de la primera parte de la práctica que corresponde a las fases de análisis léxico, sintáctico y semántico. Evaluación de esta primera parte de la práctica

  • Actividades de laboratorio adicionales:
    Lectura del documento que presenta la práctica de la asignatura en lo que corresponde a las fases de análisis léxico, sintáctico y semántico. Comprensión del mismo, y diseño interno de los módulos que compondrán esta primera parte de la práctica.

5. Intérpretes, representaciones intermedias y máquinas virtuales
T      P      L      Alt    L Ext. Est    O. Ext. Total 
9,0 0 0 0 0 9,0 0 18,0
Interpretes como herramienta útil y definidora de la semántica del lenguaje.
Representaciones internas e intermedias: en árbol, código de tres direcciones, código para máquinas de pila. Máquinas virtuales: ventajas e inconvenientes. La Q-machine. Acceso a nombres locales y no-locales: cadenas estáticas y displays.

6. Generación de código intermedio
T      P      L      Alt    L Ext. Est    O. Ext. Total 
14,0 0 10,0 0 10,0 14,0 0 48,0
Código para instrucciones sencillas. Compilación de expresiones booleanas, tipos estructurados, arrays estáticos y dinámicos, procedimientos y funciones como parámetros.
Adaptación para orientación a objetos.
  • Laboratorio:
    Implementación de la segunda parte de la práctica, correspondiente a la fase de generación de código.
    Evaluación de la práctica, donde sobre todo se evalúa esta segunda parte de la misma.
  • Actividades de laboratorio adicionales:
    Lectura del documento que presenta la práctica de la asignatura en lo que corresponde a la fase de generación de código. Comprensión del mismo, y diseño interno de los módulos que compondrán esta segunda parte de la práctica.

7. Optimizaciones independientes de la arquitectura
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 0 0 0 0 6,0 0 12,0
Bloques básicos, grafo de control de flujo, vida de variables, uso y definiciones de variables, ejemplos de optimización (subexpresiones comunes, código muerto, propagación de constantes, invariantes y variables de inducción en bucles).


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
54,0 0 28,0 0 28,0 57,0 0 167,0
Horas adicionales dedicadas a la evaluación 3,0
Total horas de trabajo para el estudiante 170,0

Metodología docente

Se persiguen los objetivos expuestos estimulando el trabajo personal del estudiante. Así, las clases de laboratorio están destinadas a la realización de la práctica por parte del alumno, conjuntamente con consultas y discusiones acerca de la misma.Para las primeras prácticas con la herramienta PCCTS existe la correspondiente "hoja de laboratorio" con las explicaciones y ejercicios a realizar. Para las demás existe abundante material para la realización del compilador.



No se distingue entre clases de teoría y de problemas, debido a que éstos últimos se concentran sólo en ciertos periodos del curso, y sería demasiado rígido tener que dedicarles un número fijo de horas semanales.



Existen diversas listas de problemas, y el estudiante sabe con antelación cuándo en clase se van a resolver cuáles de ellos. De esta manera debería intentar resolverlos primero por su cuenta.

Además existe muy abundante material disponible en las páginas web de la asignatura: apuntes, transparencias, módulos y enunciados para las prácticas, exámenes anteriores resueltos y sin resolver, listas de preguntas frecuentes, etc.



El material ofrecido por la asignatura permite al estudiante realizar un seguimiento de la asignatura, tanto del modo habitual, asistiendo a clase y estudiando según el ritmo que marca la planificación propuesta, como de una forma independiente por propia planificación del alumno, en base a sus otras obligaciones o restricciones.

Método de evaluación

Habrá un examen escrito de teoría (T), con ejercicios y preguntas cortas de tipo teórico. La nota de la práctica (P) provendrá de dos ejercicios prácticos P1 y P2. Ambos consistirán en realizar modificaciones de la práctica hecha por el propio estudiante, con el fin de valorar su dominio y comprensión de la misma. P1 se llevará a cabo a mitad de curso, y P2 durante las últimas semanas de curso.

La nota P se obtendrá así:

P=max( P2,((P1+P2)/2) ).

En el caso de que, por motivos técnicos, no se pudieran realizar estas pruebas por este medio, alternativamente, se realizaria un examen escrito sobre la práctica.

La nota final Fin se determina en funcion de T y P de la siguiente manera que fomenta un esfuerzo equilibrado en ambas partes:

Fin := 0.6*T + 0.4*P

Bibliografía básica

  • Reinhard Wilhelm, Dieter Maurer Compiler design;, Addison-Wesley, 1995.
  • Andrew W. Appel, with Maia Ginsburg Modern compiler implementation in C, Cambridge University press, 1998.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman Compilers : principles, techniques, and tools, Addison-Wesley, 1986.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman; Compiladores : principios, técnicas y herramientas, Addison-Wesley Iberoamericana [etc.], 1990.
  • V. Paxson Flex - fast lexical analyzer generator, ftp://ftp.ee.lbl.gov/flex-2.5.3.tar.gz, 1995.
  • Charles Donnelly and Richard Stallman Bison : the YACC-compatible parser generator : september 2003 Bison version 1.875, GNU, 2003.
  • Richard M. Stallman Using and porting GNU CC : last updated 26 november 1995 for version 2.7.2, Free Software Foundation, 1996.
  • T.J. Parr, the designer and author of PCCTS Language Translation Using PCCTS and C, ISBN:0-9627488-5-4 , disponible en http://www.polhode.com/pccts.html, .

Bibliografía complementaria

  • N. Wirth Compiler Construction, Addison-Wesley, 1996.
  • Steven S. Muchnick Advanced compiler design implementation, Morgan Kaufmann, 1997.
  • C.N. Fischer and R.J. LeBlanc Crafting a Compiler, Benjamin/Cummings, 1988.
  • A.W. Appel Modern Compiler Implementation in ML, Cambridge University Press, 1998.
  • A.W. Appel Modern Compiler Implementation in Java, Cambridge University Press, 1998.
  • Alfred V. Aho, Jeffrey D. Ullman The Theory of parsing translation and compiling, Prentice-Hall, 1972.

Enlaces web

  1. http://www.lsi.upc.es/~rivero/CL


Capacidades previas

Conocimientos de técnicas de programación estructurada y estructuras de datos y algoritmos; lenguajes, autómatas y gramáticas formales; estructura de computadores.


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil