Descripció
L´objectiu principal de l´assignatura és l´ensenyament del procés de la compilació de llenguatges de programació d´alt nivell. S´estudien les fases d´anàlisi semàntica, generació de codi i optimització d´un compilador i les corresponents tècniques d´implementació. Per l´estudi de cada fase es detallen les característiques específiques de diferents llenguatges de programació imperatius. A la pràctica s´implementen les fases d´anàlisi semàntica i generació de codi d´un compilador d´una sola passada per un llenguatge imperatiu.
Tipus assignatura
Optativa
Semestre
Segon
Crèdits
5.00
Coneixements previs

Estructures de dades, programació imperativa i programació orientada a objectes.
Disseny de llenguatges de programació.

Objectius

Els formalismes de la teoria de la compilació es poden aplicar en altres camps i àrees de la informàtica. L´estudi del procés de compilació requereix un coneixement a fons dels elements que constitueixen un llenguatge de programació. Així, aquesta assignatura ajuda a l´estudiant a reforçar els seus coneixements i a adquirir nous criteris per a la programació, disseny , implementació i avaluació de llenguatges de programació.

Els alumnes que cursen l´assignatura adquireixen els coneixements i desenvolupen les habilitats que s´indiquen a continuació:

1. Coneixements generals bàsics de la teoria de la compilació i coneixements específics en l´análisi semàntica, la generació de codi i l´optimització .
2. Capacitat d´anàlisi i de síntesi.
3. Capacitat d´organització i planificació de la feina a realitzar entre els diferents membres del grup de treball així com de la feina individual de cada alumne.
4. Millora de la comunicació escrita en la llengua utilitzada pels alumnes en les diferents proves presentades al professor i a l´hora de generar l´informe corresponent de cada fase de la pràctica.
5. Coneixements d´eines informàtiques.
6. Capacitat de resolució de problemes.
7. Habilitat de treball en equip.
8. Habilitat de treball en equip mitjançant eines telemàtiques.
9. Desenvolupament d´habilitats interpersonals a l´hora de defensar els arguments propis davant els companys de grup.
10. Capacitat d´aplicar els coneixements de la teoria de la compilació en la realització de la pràctica.
11. Capacitat per generar noves idees a partir dels conceptes teòrics estudiats a classe.
12. Habilitat de treball en entorns telemàtics.
13. Utilització de textos en anglès com a bibliografia bàsica.
14. Capacitat d´autoaprenentatge.
15. Presa de decisions per continuar avançant en el desenvolupament de la pràctica.
16. Disseny i gestió de projectes.

Continguts

1 L´anàlisi semàntica
1.1 L´analitzador semàntic
1.2 Identificadors, atributs i verificacions
1.3 La Taula de símbols
1.4 Anàlisi semàntica de tipus
1.5 Anàlisi semàntica en declaracions
1.6 Anàlisi semàntica d´expressions
1.7 Anàlisi semàntica d´instruccions
1.8 Altres anàlisis semàntiques

2 Generació de codi
2.1 Introducció
2.2 Organització de la memòria
2.3 Representació de les dades
2.4 Generació de codi per les expressions
2.5 Generació de codi per les instruccions simples
2.6 Generació de codi per les instruccions condicionals i llaços
2.7 Generació de codi per funcions i procediments
2.8 Accés a variables

3 Optimització
3.1 Introducció
3.2 Estructura del compilador amb optimització
3.3 Llenguatges intermitjos
3.4 El llenguatge MIR
3.5 De Babel a MIR
3.6 Un exemple
3.7 Tipus de codi i ordre de les optimitzacions
3.8 Etapes d´un optimitzador
3.9 Optimitzacions early
3.10 Transformacions preservant funcionalitat
3.11 Optimització de llaços
3.12 Comptant operacions
3.13 Casos d´estudi

Metodologia

Aquesta assignatura pot cursar-se en dos formats, segons la preferència de l´alumne, presencial i semipresencial. La principal diferència entre les dues modalitats es basa en la diferent assistència física dels alumnes a les aules.

Al llarg del curs es combinen diferents maneres d´impartir l´assignatura:

1. Classes magistrals.

En la modalitat presencial, el professor imparteix al llarg del curs els conceptes teòrics de l´assignatura mitjançant classes magistrals. En aquestes classes el professor també resol exercicis d´aplicació directa dels conceptes explicats. En la modalitat semipresencial, l´alumne pren un paper més actiu en el seu aprenentatge, i disposa dels continguts en el campus virtual, on hi ha una guia d´estudi que: explica breument els conceptes de l´assignatura, dóna referències a la bibliografia on es poden ampliar aquests conceptes, conté enunciats de problemes i conté preguntes autoavaluatives on l´alumne pot tenir una indicació del seu grau d´aprenentatge. En aquest format, també se celebren almenys tres trobades presencials a l´any, on alumnes i professors es reuneixen, per realitzar petites classes magistrals, problemes, o debats.

2. Hores de classe dedicades a resoldre exercicis teòrics, individualment o en grups.

Durant algunes hores de classe el professor planteja exercicis teòrics perquè siguin resolts pels alumnes en aquell moment. Aquests exercicis poden ser resolts individualment o en grup.

3. Exercicis que s´han de resoldre a casa.

A part dels exercicis resolts a classe l´alumne ha de resoldre altres exercicis a casa. La finalitat d´aquests exercicis és la de consolidar les idees teòriques . Els alumnes disposen d´un problemari amb exercicis. Alguns dels exercicis estan resolts.

4. Treball en grup en hores de classe.

Al final de l´assignatura es dediquen 2 hores de classe a l´estudi d´un llenguatge de programació mitjançant la documentació tècnica. L´objectiu és avaluar la seva complexitat a l´hora de la seva implementació.

5. Pràctiques

Al llarg del curs els alumnes implementen parcialment (l´anàlisi semàntica i la generació de codi) un llenguatge de programació (Babel) definit pel professor de l´assignatura amb finalitats acadèmiques. Les classes teòriques s´imparteixen en l´ordre necessari per poder assolir les diferents fases de la pràctica dins les dates de lliurament.

La pràctica es realitza en grups de 2. L´entrega es fa per fases. Cada fase es corregeix, s´informa a l´estudiant dels resultats i se li fan suggeriments per millorar-la. A l´ultima fase es realitza una entrevista personalitzada a cada membre del grup per a què defensin oralment el seu treball.

A continuació es donen les fases en les quals estè dividida la pràctica i l´objetiu principal de cadascuna:

Fase 1. Anàlisi Semàntica del llenguatge BABEL
Implementació d'un analitzador semàntic mitjançant la tècnica de esquemes de traducció amb atributs

Fase 2. Generació De Codi del llenguatge BABEL
Generar codi en llenguatge ensamblador (MIPS) mitjançant la tècnica de traducció dirigida per sintaxi

Avaluació

L´assignatura es divideix en dues parts clarament diferenciades: una part teòrica (40%) i una part pràctica (60%). Cadascuna d´aquestes parts s´avaluen i s´han d´aprovar per separat per poder aprovar l´assignatura.

Si s´aproven les dues parts, la nota final de l´assignatura és la suma aritmètica de la nota de Teoria i de la nota de Pràctiques.

Amb la finalitat d´avaluar si l´alumne ha assolit en un grau adequat els objectius perseguits a l´assignatura es fan servir diferents proves per obtenir dades de l´alumne:

A. Exàmens
Durant el curs es fan exàmens presencials.

B. Exàmens orals
Es realitza un examen oral presencial al final de la pràctica realitzada pels alumnes.

F. Informes corresponents a les pràctiques realitzades en grup.
Per avaluar cada informe de cadascuna de les fases de la pràctica el professor fa servir un formulari on té marcats i quantificats els diferents aspectes que s´han de valorar.

G.Treballs pràctics amb ordinador
La implementació de la pràctica es fa en llenguatge Java. Per cada fase el professor disposa d´un formulari per la seva avaluació.

J. Participació a l´aula o al campus virtual.
El professor de la modalitat presencial disposa d´una llista d´observacions possibles on anota els diferents comportaments i actituds presentades pels alumnes durant la classe. Al sistema semipresencial, aquestes actituds es reflecteixen en l´actuació dels alumnes en els fòrums i en les reunions mitjançant l´aula virtual.

Criteris avaluació

Objectiu 1: Coneixements generals bàsics de la teoria de la compilació.
L´estudiant ha de demostrar que ha adquirit un coneixement adequat dels conceptes estudiats durant el curs. [A, B, C, F].

Objectiu 2: Capacitat d´anàlisi i de síntesi.
L´estudiant ha de ser capaç d´analitzar els problemes amb els quals s´enfronta, i ha de demostrar capacitat de síntesi en la generació de solucions. [A, B, G, J].

Objectiu 3:Capacitat d´organització i planificació de la feina a realitzar entre els diferents membres del grup de treball així com de la feina individual de cada alumne.
L´estudiant ha de planificar i organitzar la seva feina individual, així com la feina a realitzar amb els companys de grup. [G]

Objectiu 4:Millora de la comunicació escrita en la llengua utilitzada pels alumnes en les diferents proves presentades al professor i a l´hora de generar l´informe corresponent a cada fase de la pràctica.
L´estudiant ha de presentar els exàmens i informes sense faltes ortogràfiques i amb l´estil i ordre adequat. [A, F]

Objectiu 5: Coneixements d´eines informàtiques.
L´estudiant ha de demostrar que a adquirit els coneixements necessaris de Java i JavaCC per a la implementació de la pràctica [F, G]

Objectiu 6:Capacitat de resolució de problemes.
L´estudiant ha de demostrar que sap proposar solucions adequades tant pels exercicis teòrics com per a la implementació de les diferents fases de la pràctica. [A, B, F, G]

Objectiu 7:Habilitat de treball en equip.
L´estudiant ha de ser capaç de treballar amb els companys de grup i arribar a proposar solucions als diferents problemes presentats. [F, G]

Objectiu 8:Habilitat de treball en equip mitjançant eines telemàtiques.
Especialment els alumnes semipresencials, i en menor grau, els presencials, han de ser capaços de formar un grup de treball en un entorn virtual, utilitzant els fòrums, utilitzant documents amb diferents versions i dominar les eines de comunicació síncrona remota [G,J]

Objectiu 9:Desenvolupament d´habilitats interpersonals a l´hora de defensar els arguments
propis davant els companys de grup.
L´estudiant ha de mantenir una comunicació fluïda amb els seus companys de grup de pràctica. [F,G]

Objectiu 10:Capacitat d´aplicar els coneixements de la teoria de la compilació en la realització de la pràctica.
L´estudiant ha d´identificar els formalismes i les tècniques adequades de la teoria per implementar les diferents fases de la pràctica amb l´orientació del professor i l´ajuda dels seus companys de grup. [F, G]

Objectiu 11:Capacitat per generar noves idees a partir dels conceptes teòrics estudiats a classe.
L´estudiant ha de demostrar que és capaç d´aplicar en contextos diferents les tècniques de la construcció de compiladors que ha après particularment en la realització de la pràctica. [A, B, F,G]

Objectiu 12:Habilitat de treball en entorns telemàtics.
Tots els alumnes semipresencials basen el seu estudi en diferents eines dins d´un campus virtual. Són competències que queden implícites en els sistemes d´avaluació [A,B,C,G].

Objectiu 13:Utilització de textos en anglès com a bibliografia bàsica.
Alguns dels conceptes de l´assignatura es troben referenciats directament en anglès. Aquests conceptes són avaluats en [A,G]

Objectiu 14:Capacitat d´autoaprenentatge.
L´estudiant ha de demostrar que és capaç d´adquirir coneixement per ell mateix. [A,C ]

Objectiu 15:Presa de decisions per continuar avançant en el desenvolupament de la pràctica.
L´estudiant ha de demostrar que és capaç de decidir quan ha assolit els objectius bàsics de cadascuna de les fases de la pràctica. [F,G]

Objectiu 16:Disseny i gestió de projectes.
L´estudiant ha de demostrar que és capaç de fer un disseny modular de la pràctica i gestionar-la adequadament per poder assolir-la amb garanties i en les dates de lliurament demanades. [F,G]

Bibliografia bàsica

- Aho, Afred V.; Sethi, Ravi; Ullman, Jefrey D. Compilers. Principles, Techniques and Tools. Addison-Wesley Publishing Company, 1985

- Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997

- Elder, John. Compiler Construction. A Recursive Descent Model. Prentice Hall, 1994

- Mozota i Coloma, Maria Antònia. Problemes i Solucions. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Taula de símbols per Babel. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Mozota i Coloma, Maria Antònia. BABEL 2007: Part II. Especificació de la pràctica. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Larus, R. James. Assemblers, Linkers and the SPIM Simulator. Morgan Kaufmann Publishers. Computer Science Departament, University of Wisconsin-Madison, 1998

- Larus, R. James. SPIM S20: A MIPS R2000 SIMULATOR. Computer Science Departament, University of Wisconsin-Madison, 1997

Material complementari

- Pratt, Terrence W.; Zelkowitz, Marvin V.. Lenguajes de Programación. Diseño e Implementación. Prentice Hall, 1998

- Java. Una introducció. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 1999