Compiladors

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Compiladors
Crèdits
6
Tipus
Complementària d'especialitat (Computació)
Requisits
  • Prerequisit: TC
Departament
CS
Web
https://www.cs.upc.edu/~cl
La interacció persona-màquina sovint es realitza mitjançant llenguatges de programació i darrera de cada llenguatge hi ha eines de traducció i/o interpretació que permeten executar els programes. Els exemples d'eines més coneguts són els compiladors i intèrprets. En aquesta assignatura ens endinsarem dins de l'estructura d'aquestes eines per conèixer com fan l'anàlisi del llenguatge, la seva traducció a instruccions de la màquina i l'optimització d'aquestes instruccions.

L'assignatura també es fixarà en traductors de llenguatges que van mes enllà de l'àmbit dels compiladors. Una part important de l'assignatura serà un projecte de disseny d'un traductor i intèrpret d'un llenguatge. Es permetrà que l'estudiant proposi el seu propi projecte: un intèrpret de comandes d'un robot, un llenguatge per descriure partitures musicals, un llenguatge per visualitzar animacions, un llenguatge per descriure circuits digitals, etc. La pràctica serà en grups de dues persones i no es descarta que es pugui combinar amb el projecte d'una altra assignatura si existeix una sinèrgia que ho permeti fer.

Professorat

Responsable

  • Jose Miguel Rivero Almeida ( )

Altres

  • Lluis Padro Cirera ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Transversals

Treball en equip

  • G5 [Avaluable] - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.
    • G5.3 - Identificar els rols, les habilitats i les carències dels diferents membres del grup. Proposar millores en l'estructura del grup. Interactuar amb eficàcia i professionalitat. Negociar i gestionar conflictes en el grup. Reconèixer i donar suport o assumir el paper de líder en el grup de treball. Avaluar i presentar els resultats del treball de grup. Representar el grup en negociacions amb terceres persones. Capacitat de col·laborar en un entorn multidisciplinar. Conèixer i saber aplicar les tècniques per a promoure la creativitat.

Competències Tècniques

Competències tècniques comunes

  • CT1 - Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
    • CT1.2C - Interpretar, seleccionar i valorar conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica i la seva aplicació a partir dels fonaments matemàtics, estadístics i físics necessaris. CEFB3. Capacitat per a comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per al tractament automàtic de la informació mitjançant sistemes computacionals i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
  • CT4 - Demostrar coneixement i capacitat d'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i la complexitat dels algorismes
    • CT4.1 - Identificar les solucions algorísmiques més adequades per a resoldre problemes de dificultat mitjana.

Competències Tècniques de cada especialitat

Especialitat computació

  • CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
    • CCO1.2 - Demostrar coneixement dels fonaments teòrics dels llenguatges de programació i les tècniques de processament lèxic, sintàctic i semàntic associades, i saber aplicar-les per a la creació, el disseny i el processament de llenguatges.
  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.3 - Desenvolupar i avaluar sistemes interactius i de presentació d'informació complexa, i la seva aplicació a la resolució de problemes de disseny d'interacció persona computador.

Objectius

  1. Conèixer l'estructura general dels compiladors i intèrprets de llenguatges de programació.
    Competències relacionades: CCO1.2,
  2. Conèixer les tècniques d'anàlisi lèxic i els mètodes per a generar analitzadors lèxics
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  3. Conèixer les tècniques d'anàlisi sintàctica i els mètodes per a generar analitzadors sintàctics.
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  4. Conèixer les tècniques d'anàlisi semàntica d'un llenguatge de programació.
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  5. Conèixer l'estructura d'un intèrpret i els conceptes bàsics de màquines virtuals.
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  6. Conèixer les tècniques de generació de codi d'un compilador.
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  7. Conèixer les tècniques d'optimització de codi d'un compilador.
    Competències relacionades: CCO1.2, CT1.2C, CT4.1,
  8. Aprendre a organitzar un grup de treball per a realitzar una tasca de mitjana complexitat.
    Competències relacionades: G5.3,
  9. Aprendre a dissenyar llenguatges de programació per a aplicacions en diversos àmbits de la Informàtica.
    Competències relacionades: CCO1.2, CT1.2C, G5.3, CCO2.3, CT4.1,
  10. Aprendre a desenvolupar un projecte de mitjana complexitat de disseny i traducció/interpretació d'un llenguatge de programació.
    Competències relacionades: CT1.2C, G5.3, CCO2.3, CT4.1,

Continguts

  1. Introducció.
    Elements d'un llenguatge de programació. Compiladors i intèrprets: concepte i diferències. Estructura i fases d'un compilador i un intèrpret.
  2. Anàlisi lèxica.
    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àlisi sintàctica.
    Objectius de l'anàlisi sintàctica. Revisió de la teoria de llenguatges lliures de context 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. Arbres sintàctics.
    Arbres sintàctics concrets i abstractes. Construcció d'arbres sintàctics. Informació emmagatzemada en els arbres sintàctics.
  5. Anàlisi semàntica.
    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. Comprovacions de tipus.
  6. Intèrprets i màquines virtuals.
    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ó de codi.
    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. Optimització de codi.
    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ó.

Activitats

Activitat Acte avaluatiu


Prova de laboratori


Objectius: 3 7
Setmana: 12
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Projecte


Objectius: 9 10 8
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen de teoria
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

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.
Objectius: 3 7 9
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Examen de teoria


Objectius: 3 7 9
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen de teoria
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

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.
Objectius: 2
Continguts:
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

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.
Objectius: 3
Continguts:
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 3
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 3 4
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 4
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
3h

Aprenentatge 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.
Objectius: 5
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

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

L'alumne assistirà a classe per adquirir els coneixements sobre el tema. Addicionalment haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objectius: 6
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 7
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 3 9
Continguts:
Teoria
0h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
1h

Ampliació d'un intèrpret d'un llenguatge 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.
Objectius: 3 9 10 1 2 5
Continguts:
Teoria
0h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 3 9
Continguts:
Teoria
0h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
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.
Objectius: 9 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
17h
Aprenentatge dirigit
0h
Aprenentatge autònom
16h

Metodologia docent

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ètode d'avaluació

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.

Bibliografia

Bàsica:

Complementaria:

Capacitats prèvies

Per a seguir l'assignatura de Compiladors, és necessari que l'estudiant arribi amb uns coneixements adequats de teoria de llenguatges formals (llenguatges regulars i lliures de contexte) i autòmats (finits i de piles). També és necessari tenir coneixements d'estructures de dades (llistes, arbres, grafs) i d'algorismes bàsics sobre aquestes estructures (recorreguts, cerques, recursivitat). Finalment, calen coneixements bàsics de llenguatge màquina i assemblador.

Per les raons abans esmentades, convé que l'estudiant hagi realitzat les assignatures d'Algorísmia, Teoria de la Computació i Estructura de Computadors.