Compiladores

Usted está aquí

Créditos
6
Tipos
Complementaria de especialidad (Computación)
Requisitos
  • Prerrequisito: TC
Departamento
CS
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.

Profesores

Responsable

  • Jordi Cortadella Fortuny ( )

Otros

  • Jose Miguel Rivero Almeida ( )
  • Lluis Padro Cirera ( )

Horas semanales

Teoría
2
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0.4
Aprendizaje autónomo
5.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.
    Objectius de l'anàlisi lèxica. Revisió de la teoria de llenguatges regulars i autòmats finits. Construcció d'analitzadors lèxics a partir d'autòmats indeterministes.Eines d'anàlisi lèxica.
  3. Análisis sintáctico.
    Objectius de l'anàlisi sintàctica. Revisió de la teoria de llenguatges lliures de contexte i autòmats de pila. Gramàtiques ambigües i recursivitat per la dreta i per l'esquerra. Construcció d'analitzadors sintàctics descendents. Construcció d'analitzadors sintàctics ascendents.
  4. Árboles sintácticos.
    Arbres sintàctics concrets i abstractes. Construcció d'arbres sintàctics. Informació emmagatzemada en els arbres sintàctics.
  5. Análisis semántico.
    Noms i objectes en un llenguatge de programació. Vida dels objectes. Visibilitat de noms estàtica i dinàmica.Bloc d'activació d'una funció.Taules de símbols.Comprobacions de tipus.
  6. Intérpretes y máquinas virtuales.
    Interpretació d'un llenguatge de programació. Concepte de màquina virtual. Tipus d'intèrprets. Fases d'un intèrpret. Representacions internes i intermitges: en arbre, codi de tres direccions, codi per a màquines de piles. Accés a noms locals i no locals. Exemples de màquines virtuals.
  7. Generación de código.
    Codi intermig. Generació de codi per a expressions aritmètiques i booleanes. Generació de codi per a instruccions: assignació, instrucció condicional, instrucció iterativa. Funcions: blocs d'activació, pas de paràmetres i retorn de resultats. Accés a estructures de dades.
  8. Optimización de código.
    Blocs bàsics i optimitzacions locals. Graf de control de flux. Anàlisi de flux per a optimitzacions globals. Vida i ús/definició de variables.Optimitzacions globals: subexpressions comunes, codi mort, propagació de constants i propagació de còpies. Optimitzacions en bucles: invariants i variables d'inducció.

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 final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
1h
Aprendizaje autónomo
2h

Aprenentage de conceptes generals sobre llenguatges, compiladors i intèrprets.

L'activitat bàsica és la de assitir a classe per adquirir els coneixements d'aquest tema i tenir una visió global del curs. L'estudiant podrà consultar llibres especialitzats en el cas que vulgui aprofondir en algun aspecte determinat.
Objetivos: 3 7 9
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
2h

Aprenentatge sobre la teoria i tècniques d'anàlisi lèxica.

L'estudiant assistirà a les classes teòriques i dedicarà temps a estudiar la teoria sobre anàlisis lèxic i realitzar exercicis proposats pel professor. Una part dels coneixements adquirits hauran de ser aplicats al projecte de l'assignatura.
Objetivos: 2
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Examen de teoría


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

Aprenentatge sobre la teoria i tècniques de disseny d'analitzadors sintàctics descendents.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i amb la resolució dels problemes proposats a classe. Una part dels coneixements adquirits seran utilitzats en el projecte.
Objetivos: 3
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprenentatge sobre la teoria i tècniques de disseny d'analitzadors sintàctics ascendents.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i amb la resolució dels problemes proposats a classe.
Objetivos: 3
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprenentage sobre la construcció d'arbres abstractes de sintaxi.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objetivos: 3 4
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprenentatge de teoria i tècniques d'anàlisi semàntica

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objetivos: 4
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Aprenentage sobre el disseny d'intèrprets i màquines virtuals

L'alumne assistirà a classe per adquirir els coneixements sobre el tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe. Els coneixements adquirits a classe seran posteriorment utilitzats en el projecte del curs.
Objetivos: 5
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Aprenentage sobre la teoria i tècniques de generació de codi

L'alumne assistirà a classe per adquirir els coneixements sobre el tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objetivos: 6
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprenentatge sobre la teoria i tècniques d'optimització de codi

L'alumne assistirà a classe per adquirir els coneixements del tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objetivos: 7
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Introducció a l'eina ANTLR: disseny d'un avaluador d'expressions.

L'alumne realitzarà una modificació de l'exemple proposat pel professor a la classe de laboratori. Durant la classe, utilitzarà l'eina ANTLR, que serà la mateixa amb la que es realitzarà el projecte del curs.
Objetivos: 3 9
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
1h

Ampliació d'un intèrpret d'un lleguatge de programació.

L'alumne haurà de realitzar la modificació de l'intèrpret proposat pel professor durant les hores de laboratori i d'estudi personal. Finalment haurà de construir un jocs de proves que validin la correctesa de les modificacions realitzades.
Objetivos: 3 9 10 1 2 5
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Disseny d'un llenguatge de programació i el seu analitzador sintàctic.

L'activitat consistirà en dissenyar un llenguatge de programació senzill orientat a un tipus específic d'aplicacions. En aquesta activitat es permetrà que el propi estudiant proposi el llenguatge i l'àmbit d'aplicació. Altrament, l'estudiant podrà optar per realitzar el projecte proposat pel professor de l'assignatura. Alguns exemples de llenguatges de programació que es podrien proposar: (1) un llenguatge per a la creació i visualització d'animacions d'objectes senzills, (2) un llenguatge de programació del control d'un Lego-Robot, (3) un llenguatge per a generar patrons Escher, (4) un llenguatge per a generar partitures de música, (5) un llenguatge per a definir i manipular funcions matemàtiques, etc. Una vegada triat el llenguatge, l'alumne haurà de realitzar l'analitzador lèxic i sintàctic utilitzants les eines del curs.
Objetivos: 3 9
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
4h
Aprendizaje dirigido
1h
Aprendizaje autónomo
16h

Disseny de la fase d'interpretació d'un llenguatge de programació.

L'alumne haurà de construir l'analitzador semàntic i intèrpret del llenguatge utilitzant les eines del curs durant les classes de laboratori i les hores de treball personal. Finalment haurà de construir uns jocs de prova i una documentació a nivell d'usuari per tal que el projecte pugui ser avaluat.
Objetivos: 9 10
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
17h
Aprendizaje dirigido
1h
Aprendizaje autónomo
16h

Metodología docente

Els continguts teòrics de l'assignatura s'imparteixen a les classes de teoria. Aquestes classes es complementen amb exemples pràctics i problemes que els estudiants han de resoldre en les hores d'Aprenentatge Autònom. Durant les classes de teoria i esporàdicament en algunes classes de laboratori es resoldran alguns dels exercicis mes representatius del curs.

En les sessions de laboratori s'imparteixen aquells coneixements que han de donar suport a la realització del projecte de l'assignatura. En les primeres sessions es revisaran exemples senzills en els que els estudiants hauran de fer modificacions per familiaritzar-se amb les solucions proposades. Després d'unes sessions introductòries, els estudiants centraran els seus esforços en el projecte del curs. Durant les classes de laboratori, el professor anirà introduint noves tècniques i deixarà una part important de la classe per tal que els estudiants treballin amb el seu projecte amb l'ajut del professor quan sigui necessari.En aquesta fase serà imprescindible la utilització de les hores d'Aprenentatge Autònom assignades al projecte.

El projecte de laboratori es farà en grups de 2 o 3 persones, depenent de la complexitat del problema. S'espera que els estudiants organitzin el seu grup de manera que les tasques siguin distribuïdes i sincronitzades. Cada estudiant haurà de tenir una responsabilitat important i individual en el projecte.

Método de evaluación

El mètode té com a objectiu avaluar els coneixements tant teòrics com pràctics de l'estudiant.

L'avaluació consistirà en tres actes avaluatius. El primer d'ells (L1) té com a objectiu avaluar coneixements pràctics del curs i consistirà en una prova de laboratori on l'estudiant haurà de fer petites modificacions a un compilador existent per afegir-hi nova funcionalitat. Amb aquesta prova s'avaluarà el coneixement que l'estudiant té de l'estructura d'un compilador i la seva capacitat d'implementar nous conceptes de llenguatges de programació i expressar-los en una gramàtica. L'avaluació es realitzarà mitjançant la validació de la implementació amb jocs de proves prèviament preparats.

El segon acte avaluatiu (L2) es basarà en el desenvolupament de l'anàlisi semàntica i generació de codi del compilador proposat a l'assignatura. Aquest treball es farà en grup. L'acte avaluatiu consistirà en una prova de laboratori on caldrà executar uns jocs de proves per validar el compilador i les extensions proposades a la mateixa prova. En aquest acte s'avaluarà la capacitat de l'estudiant per aplicar els conceptes adquirits durant el curs i el coneixement del treball realitzat en grup.

Finalment, el tercer acte consistirà en una prova escrita on s'avaluaran els coneixements teòrics impartits durant el curs.

La nota final del curs (F) es calcularà amb una suma ponderada de les dues proves de laboratori (L1 i L2) i la prova de coneixements teòrics (T):

F = 0.2 L1 + 0.35 L2 + 0.45 T

Amb el projecte de laboratori també s'avaluarà la capacitat de treball en grup. El projecte haurà de ser realitzat per grups de dos estudiants. Per a cada estudiant, s'avaluarà la seva implicació en el grup, el repartiment de responsabilitats, el compliment dels acords d'implementació establerts al principi del projecte, la gestió dels conflictes entre els membres del grup, el coneixement global del projecte i la presentació dels resultats.

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.

Adenda

Contenidos

No hi ha modificacions.

Metodología docente

No hi ha modificacions.

Método de evaluación

No hi ha modificacions.

Plan de contingencia

En cas de semi-presencialitat, les classes de teoria es faran remotament, combinant vídeos i classes on-line. En cas que la situació sanitària ho demani, les classes de pràctiques també seran realitzades on-line, utilitzant els mateixos recursos informàtics que s'utilitzen en les classes convencionals.