Compiladores

Usted está aquí

Inicio » Estudios » Grados » Grado en Ingeniería Informática » Plan de estudios » Asignaturas » Compiladores
Créditos
6
Tipos
Complementaria de especialidad (Computación)
Requisitos
  • Prerrequisito: TC
Departamento
CS
Web
https://www.cs.upc.edu/~cl
La interacción persona-máquina se realiza frecuentemente mediante lenguajes de programación y detrás de cada lenguaje existen herramientas de traducción y/o interpretación que permiten ejecutar los programas. Los ejemplos de herramientas mas conocidos son los compiladores y los intérpretes. En esta asignatura nos adentraremos en la estructura de estas herramientas para conocer como se realiza el análisis del lenguaje, su traducción a instrucciones de la máquina y la optimización de estas instrucciones.

La asignatura también se centrará en traductores de lenguajes que van más allá del ámbito de los compiladores. Una parte importante de la asignatura será un proyecto de diseño de un traductor e intérprete de un lenguaje. Se permitirá que el estudiante proponga su propio proyecto: un intérprete de comandos de un robot, un lenguaje para describir partituras musicales, un lenguaje para visualizar animaciones, un lenguaje para describir circuitos digitales, etc. La práctica será en grupos de dos personas y no se descarta que se pueda combinar con el proyecto de otra asignatura si existe una sinergia que lo permita.

Profesorado

Responsable

  • Jose Miguel Rivero Almeida ( )

Otros

  • Lluis Padro Cirera ( )

Horas semanales

Teoría
2
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Competencias Transversales

Trabajo en equipo

  • G5 [Avaluable] - Ser capaz de trabajar como miembro de un equipo, ya sea como un miembro más, o realizando tareas de dirección con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.
    • G5.3 - Identificar los papeles, habilitados y carencias de los diferentes miembros del grupo. Proponer mejoras en la estructura del grupo. Interactuar con eficacia y de forma profesional. Negociar y gestionar conflictos en el grupo. Reconocer y dar soporte o asumir el papel de líder en el grupo de trabajo. Evaluar y presentar los resultados del trabajo de grupo. Representar al grupo en negociaciones con terceros. Capacidad de colaborar en un entorno multidisciplinar. Conocer y saber aplicar las técnicas para promover la creatividad.

Competencias Técnicas

Competencias técnicas comunes

  • CT1 - Demostrar conocimiento y comprensión de hechos esenciales, conceptos, principios y teorías relativas a la informática y a sus disciplinas de referencia.
    • CT1.2C - Interpretar, seleccionar y valorar conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática y su aplicación a partir de los fundamentos matemáticos, estadísticos y físicos necesarios. CEFB1: Capacidad para la resolución de los problemas matemáticos que puedan plantarse en la ingeniería. Aptitud para aplicar los conocimientos sobre: algebra, cálculo diferencial e integral i métodos numéricos; estadística y optimización.
  • CT4 - Demostrar conocimiento y capacidad de aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y la complejidad de los algoritmos
    • CT4.1 - Identificar las soluciones algorítmicas más adecuadas para resolver problemas de dificultad mediana.

Competencias Técnicas de cada especialidad

Especialidad de computación

  • CCO1 - Tener un conocimiento profundo de los principios fundamentales y de los modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
    • CCO1.2 - Demostrar conocimiento de los fundamentos teóricos de los lenguajes de programación y las técnicas de procesamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, el diseño y el procesamiento de lenguajes.
  • CCO2 - Desarrollar de forma efectiva y eficiente los algoritmos y el software apropiados para resolver problemas complejos de computación.
    • CCO2.3 - Desarrollar y evaluar sistemas interactivos y de presentación de información compleja, y su aplicación a la resolución de problemas de diseño de interacción persona computadora.

Objetivos

  1. Conocer la estructura general de los compiladores e intérpretes de lenguajes de programación.
    Competencias relacionadas: CCO1.2,
  2. Conocer las técnicas de análisis léxico y los métodos para generar analizadores léxicos
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  3. Conocer las técnicas de análisis sintáctico y los métodos para generar analizadores sintácticos.
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  4. Conocer las técnicas de análisis semántico de un lenguaje de programación.
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  5. Conocer la estructura de un intérprete y los conceptos básicos de máquinas virtuales.
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  6. Conocer las técnicas de generación de código de un compilador.
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  7. Conocer las técnicas de optimización de código de un compilador.
    Competencias relacionadas: CCO1.2, CT1.2C, CT4.1,
  8. Aprender a organizar un grupo de trabajo para realizar una tarea de mediana complejidad.
    Competencias relacionadas: G5.3,
  9. Aprender a diseñar lenguajes de programación para aplicaciones en diversos ámbitos de la Informática.
    Competencias relacionadas: CCO1.2, CT1.2C, G5.3, CCO2.3, CT4.1,
  10. Aprender a desarrollar un proyecto de mediana complejidad de diseño y traducción/interpretación de un lenguaje de programación.
    Competencias relacionadas: CT1.2C, G5.3, CCO2.3, CT4.1,

Contenidos

  1. Introducción.
    Elementos de un lenguaje de programación. Compiladores e intérpretes: concepto y diferencias. Estructura y fases de un compilador y un intérprete.
  2. Análisis léxico.
    Objetivos del análisis léxico. Revisión de la teoría de lenguajes regulares y autómatas finitos. Construcción de analizadores léxicos a partir de autómatas indeterministas. Herramientas de análisis léxico.
  3. Análisis sintáctico.
    Objetivos del análisis sintáctico. Revisión de la teoría de lenguajes libres de contexto y autómatas de pila. Gramáticas ambiguas y recursivitat por la derecha y por la izquierda. Construcción de analizadores sintácticos descendentes. Construcción de analizadores sintácticos ascendentes.
  4. Árboles sintácticos.
    Árboles sintácticos concretos y abstractos. Construcción de árboles sintácticos. Información almacenada en los árboles sintácticos.
  5. Análisis semántico.
    Nombres y objetos en un lenguaje de programación. Vida de los objetos. Visibilidad de nombres estática y dinámica. Bloc de activación de una función.Tablas de símbolos. Comprobaciones de tipos.
  6. Intérpretes y máquinas virtuales.
    Interpretación de un lenguaje de programación. Concepto de máquina virtual. Tipos de intérpretes. Fases de un intérprete. Representaciones internas e intermedias: en árbol, código de tres direcciones, código para máquinas de pilas. Acceso a nombres locales y no locales. Ejemplos de máquinas virtuales.
  7. Generación de código.
    Código intermedio. Generación de código para expresiones aritméticas y booleanas. Generación de código para instrucciones: asignación, instrucción condicional, instrucción iterativa. Funciones: bloques de activación, de parámetros y retorno de resultados. Acceso a estructuras de datos.
  8. Optimización de código.
    Bloques básicos y optimizaciones locales. Grafo de control de flujo. Análisis de flujo para optimizaciones globales. Vida y uso/definición de variables. Optimizaciones globales: subexpressions comunes, código muerto, propagación de constantes y propagación de copias. Optimizaciones en bucles: invariantes y variables de inducción.

Actividades

Actividad Acto evaluativo


Prueba de laboratorio


Objetivos: 3 7
Semana: 12
Tipo: examen de laboratorio
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
2h

Proyecto


Objetivos: 9 10 8
Semana: 15 (Fuera de horario lectivo)
Tipo: examen de teoría
Teoría
1h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje de conceptos generales sobre lenguajes, compiladores e intérpretes.

La actividad básica es la de assitir a clase para adquirir los conocimientos de este tema y tener una visión global del curso. El estudiante podrá consultar libros especializados en el supuesto de que quiera aprofondir en algún aspecto determinado.
Objetivos: 3 7 9
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
2h

Examen de teoría


Objetivos: 3 7 9
Semana: 15 (Fuera de horario lectivo)
Tipo: examen de teoría
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje sobre la teoría y técnicas de análisis léxico.

El estudiante asistirá en las clases teóricas y dedicará tiempos a estudiar la teoría sobre análisis léxico y realizar ejercicios propuestos por el profesor. Una parte de los conocimientos adquiridos tendrán que ser aplicados al proyecto de la asignatura.
Objetivos: 2
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Aprendizaje sobre la teoría y técnicas de diseño de analizadores sintácticos descendentes.

El alumno asistirá en clase para adquirir los conocimientos teóricos. Addicionalement tendrá que consolidar estos conceptos con su estudio personal y con la resolución de los problemas propuestos a clase. Una parte de los conocimientos adquiridos serán utilizados en el proyecto.
Objetivos: 3
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje sobre la teoría y técnicas de diseño de analizadores sintácticos ascendentes.

El alumno asistirá en clase para adquirir los conocimientos teóricos. Addicionalement tendrá que consolidar estos conceptos con su estudio personal y con la resolución de los problemas propuestos a clase.
Objetivos: 3
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprendizaje sobre la construcción de árboles de sintaxis abstractos.

El alumno asistirá en clase para adquirir los conocimientos teóricos. Además tendrá que consolidar estos conceptos con su estudio personal y la resolución de los problemas propuestos a clase.
Objetivos: 3 4
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprendizaje de teoría y técnicas de análisis semántico

El alumno asistirá en clase para adquirir los conocimientos teóricos. Adicionalmente tendrá que consolidar estos conceptos con su estudio personal y la resolución de los problemas propuestos a clase.
Objetivos: 4
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprendizaje sobre el diseño de intérpretes y máquinas virtuales

El alumno asistirá en clase para adquirir los conocimientos sobre el tema. Addicionalement tendrá que consolidar estos conceptos con su estudio personal y la resolución de los problemas propuestos a clase. Los conocimientos adquiridos a clase serán posteriormente utilizados en el proyecto del curso.
Objetivos: 5
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Aprendizaje sobre la teoría y técnicas de generación de código

El alumno asistirá en clase para adquirir los conocimientos sobre el tema. Adicionalmente tendrá que consolidar estos conceptos con su estudio personal y la resolución de los problemas propuestos a clase.
Objetivos: 6
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje sobre la teoría y técnicas de optimización de código

El alumno asistirá en clase para adquirir los conocimientos del tema. Addicionalement tendrá que consolidar estos conceptos con su estudio personal y la resolución de los problemas propuestos a clase.
Objetivos: 7
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Introducción a la herramienta ANTLR: diseño de un evaluador de expresiones.

El alumno realizará una modificación del ejemplo propuesto por el profesor a la clase de laboratorio. Durante la clase, utilizará la herramienta ANTLR, que será la misma con la que se realizará el proyecto del curso.
Objetivos: 3 9
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
1h

Ampliación de un intérprete de un lenguaje de programación.

El alumno tendrá que realizar la modificación del intérprete propuesto por el profesor durante las horas de laboratorio y de estudio personal. Finalmente tendrá que construir un juegos de pruebas que validen la correctesa de las modificaciones realizadas.
Objetivos: 3 9 10 1 2 5
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Diseño de un lenguaje de programación y su analizador sintáctico.

La actividad consistirá al diseñar un lenguaje de programación sencillo orientado a un tipo específico de aplicaciones. En esta actividad se permitirá que el propio estudiante proponga el lenguaje y el ámbito de aplicación. De lo contrario, el estudiante podrá optar para realizar el proyecto propuesto por el profesor de la asignatura. Algunos ejemplos de lenguajes de programación que se podrían proponer: (1) un lenguaje para la creación y visualización de animaciones de objetos sencillos, (2) un lenguaje de programación del control de un Lego-Robot, (3) un lenguaje para generar patrones Escher, (4) un lenguaje para generar partituras de música, (5) un lenguaje para definir y manipular funciones matemáticas, etc. Una vez elegido el lenguaje, el alumno tendrá que realizar el analizador léxico y sintáctico utilitzants las herramientas del curso.
Objetivos: 3 9
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16h

Diseño de la fase de interpretación de un lenguaje de programación.

El alumno tendrá que construir el analizador semántico e intérprete del lenguaje utilizando las herramientas del curso durante las clases de laboratorio y las horas de trabajo personal. Finalmente tendrá que construir unos juegos de prueba y una documentación a nivel de usuario para que el proyecto pueda ser evaluado.
Objetivos: 9 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
17h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16h

Metodología docente

Los contenidos teóricos de la asignatura se imparten en las clases de teoría. Estas clases se complementan con ejemplos prácticos y problemas que los estudiantes tienen que resolver en las horas de Aprendizaje Autónomo. Durante las clases de teoría y esporádicamente en algunas clases de laboratorio se resolverán algunos de los ejercicios mas representativos del curso.

En las sesiones de laboratorio se imparten aquellos conocimientos que tienen que apoyar a la realización del proyecto de la asignatura. En las primeras sesiones se revisarán ejemplos sencillos en los que los estudiantes tendrán que hacer modificaciones para familiarizarse con las soluciones propuestas. Después de unas sesiones introductorias, los estudiantes centrarán sus esfuerzos en el proyecto del curso. Durante las clases de laboratorio, el profesor irá introduciendo nuevas técnicas y dejará una parte importante de la clase para que los estudiantes trabajen con su proyecto con la ayuda del profesor cuando sea necesario. En esta fase será imprescindible la utilización de las horas de Aprendizaje Autónomo asignadas al proyecto.

El proyecto de laboratorio se hará en grupos de 2 o 3 personas, dependiendo de la complejidad del problema. Se espera que los estudiantes organicen su grupo de forma que las tareas sean distribuidas y sincronizadas. Cada estudiante tendrá que tener una responsabilidad importante e individual en el proyecto.

Método de evaluación

El método tiene como objetivo evaluar los conocimientos tanto teóricos como prácticos del estudiante.

La evaluación consistirá en tres actos evaluativos. El primero de ellos (L1) tiene como objetivo evaluar conocimientos prácticos del curso y consistirá en una prueba de laboratorio donde el estudiante tendrá que hacer pequeñas modificaciones a un compilador existente para añadir nueva funcionalidad. Con esta prueba se evaluará el conocimiento que el estudiante tiene de la estructura de un compilador y su capacidad de implementar nuevos conceptos de lenguajes de programación y expresarlos en una gramática. La evaluación se realizará mediante la validación de la implementación con juegos de pruebas previamente preparados.

El segundo acto evaluativo (L2) se basará en el desarrollo del análisis semántico y generación de código del compilador propuesto en la asignatura. Este trabajo se hará en grupo. El acto evaluativo consistirá en una prueba de laboratorio donde habrá que ejecutar unos juegos de pruebas para validar el compilador y las extensiones propuestas a la misma prueba. En este acto se evaluará la capacidad del estudiante para aplicar los conceptos adquiridos durante el curso y el conocimiento del trabajo realizado en grupo.

Finalmente, el tercer acto consistirá en una prueba escrita donde se evaluarán los conocimientos teóricos impartidos durante el curso.

La nota final del curso (F) se calculará con una suma ponderada de las dos pruebas de laboratorio (L1 y L2) y la prueba de conocimientos teóricos (T):

Bibliografía

Básica:

Complementaria:

Capacidades previas

Para seguir la asignatura de Compiladores, es necesario que el estudiante llegue con un conocimiento adecuado de teoría de lenguajes formales (lenguajes regulares y libres de contexto) y autómatas (finitos y de pilas). También es necesario tener conocimientos de estructuras de datos (listas, árboles, grafos) y de algoritmos básicos sobre estas estructuras (recorridos, búsquedas, recursividad). Finalmente, se necesitan conocimientos básicos de lenguaje máquina y ensamblador. Por las razones antes mencionadas, conviene que el estudiante haya realizado las asignaturas de Algorítmica, Teoría de la Computación y Estructura de Computadores.