Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Compiladors (CL)

Crèdits Dept.
9.0 (7.2 ECTS) CS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

Cobrir els continguts especificats a la troncalitat de processadores del llenguatge i els següents objectius específics.

Objectius Específics

Coneixements

  1. Tècniques i eines generals, flexibles, i eficients per a la compilació de llenguatges de programació i per a altres aplicacions, com els formatadors de text (LaTeX, nroff), llenguatges gràfics (postscript, CIF, GIF, JPEG), llenguatges de descripció de hardware (VDHL, Verilog), llenguatges de simulació (simscript, GPSS), intèrprets de querys i comandes, o els compiladores de silici.
  2. Una aplicació en la que s'utilitzen i consoliden molts conceptes apresos prèviament: llenguatges formals i autòmats, programació estructurada i recursiva, tipus abstractes de dades, etc.

Habilitats

  1. Ser capaç de desenvolupar aplicacions pràctiques de les tècniques i eines estudiades (per exemple, transformacions de dades, o senzills intèrprets).
  2. Ser capaç de completar algun mòdul d"un compilador modular modern, com a aplicació a la que són imprescindibles la robustesa (absència d"errors d"execució) i la correctesa (del codi objecte produït).

Competències

  1. Ser millors programadors a través d"un millor coneixement dels llenguatges de programació, a la seva sintaxi, semàntica i implementació eficient.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Introducció i motivació
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
Estructura i fases d'un compilador.
Per què estudiar compiladors?
El perquè de la organització de lassignatura.

2. Anàlisi lèxic
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 0 2,0 0 2,0 6,0 0 13,0
Definició del problema. Repàs de llenguatges regulars i autòmats finits, diversos algoritmes i els seus costos. Tractament d'errors, l'eina PCCTS, altres aplicacions.

  • Laboratori:
    Ús de l'eina PCCTS i altres aplicacions similars.



  • Activitats de laboratori addicionals:
    Lectura, comprensió i anàlisi de la fulla de laboratori corresponent a la sessió.

3. Anàlisi sintàctic
T      P      L      Alt    L Ext. Est    A Ext. Total 
12,0 0 4,0 0 4,0 12,0 0 32,0
Repàs de gramàtiques de context lliure i autòmats de pila. Arbres de sintaxi concreta i abstracta, tècniques de parsing descendent i ascendent, l'eina PCCTS, altres aplicacions.
  • Laboratori:
    Ús de l'eina PCCTS i altres aplicacions.

  • Activitats de laboratori addicionals:
    Lectura, comprensió i anàlisi de les fulles de laboratori corresponents a la sessió.

4. Anàlisi semàntic
T      P      L      Alt    L Ext. Est    A Ext. Total 
8,0 0 12,0 0 12,0 8,0 0 40,0
Llenguatges amb estructura de blocs, pas de paràmetres, comprovació de tipus, equivalències de tipus, conversió explícita i implícita de tipus. Altres paradigmes de programació.
  • Laboratori:
    Implementació de la primera part de la pràctica que correspon a les fases d'anàlisi lèxic, sintàctic i semàntic. Avaluació d"aquesta primera part de la pràctica
  • Activitats de laboratori addicionals:
    Lectura del document que presenta la pràctica de l'assignatura pel que correspon a les fases d'anàlisi lèxic, sintàctic i semàntic. Comprensió del mateix, i disseny intern dels mòduls que composaran aquesta primera part de la pràctica.

5. Intèrprets, representacions intermitges i màquines virtuals
T      P      L      Alt    L Ext. Est    A Ext. Total 
9,0 0 0 0 0 9,0 0 18,0
Intèrprets com a eina útil i definidora de la semàntica del llenguatge. Representacions internes i intermitges: en arbre, codi de tres direccions, codi per a màquines de pila. Màquines virtuals: avantatges i inconvenients. La Q-machine. Accés a noms locals i no-locals: cadenes estàtiques, i displays.

6. Generació de codi intermedi
T      P      L      Alt    L Ext. Est    A Ext. Total 
14,0 0 10,0 0 10,0 14,0 0 48,0
Codi per a instruccions senzilles. Compilació d'expressions booleanes, tipus estructurats, arrays estàtics i dinàmics, procediments i funcions com a paràmetres. Adaptació per a orientació a objectes.
  • Laboratori:
    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.
  • Activitats de laboratori addicionals:
    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. Optimitzacions independents de l'arquitectura
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 0 0 0 0 6,0 0 12,0
Blocs bàsics, graf de control de flux, vida de variables, ús i definicions de variables, exemples d'optimització (subexpressions comunes, codi mort, propagació de constants, invariants i variables d'inducció a bucles).


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
54,0 0 28,0 0 28,0 57,0 0 167,0
Hores addicionals dedicades a l'avaluació 3,0
Total hores de treball per l'estudiant 170,0

Metodologia docent

Es persegueixen els objectius exposats estimulant el treball personal de l'estudiant. Així, les classes de laboratori estan destinades a la realització de la pràctica per part de l'alumne, conjuntament amb consultes i discussions sobre la mateixa. Per a les primeres pràctiques amb l'eina PCCTS existeix la corresponent "fulla de laboratori" amb les explicacions i exercicis a realitzar. Per a les altres existeix abundant material per a la realització del compilador.

No es distingeix entre classes de teoria i de problemes, degut al fet de que aquestes últimes es concentren només en certs períodes del curs, i seria massa rígid haver-les de dedicar un nombre fix d"hores setmanals.

Existeixen diverses llistes de problemes, i l'estudiant sap amb antelació quan a classe es resoldran quines d'elles. D'aquesta manera hauria d'intentar resoldre'ls primer pel seu compte. A més existeix abundant material disponible a les pàgines web de l'assignatura: apunts, transparències, mòduls i enunciats per a les pràctiques, examens anteriors resolts i sense resoldre, llistes de preguntes freqüents, etc.

El material ofert per l"assignatura permet a l'estudiant realitzar un seguiment de l'assignatura, tant de la manera habitual, assistint a classe i estudiant segons el ritme que marca la planificació proposada, com d'una forma independent per pròpia planificació de l"alumne, en base a les seves altres obligacions o restriccions.

Mètode d'avaluació

Hi haurà un examen escrit de teoria (T), amb exercicis i preguntes curtes de tipus teòric. La nota de la pràctica (P) provindrà de dos exercicis pràctics P1 i P2. Ambdós consistiran a realitzar modificacions de la pràctica feta pel propi estudiant, amb la finalitat de valorar el seu domini i comprensió de la mateixa. P1 es realitzarà a la meitat del curs, i P2 durant les últimes setmanes de curs.

La nota P s'obtindrà així:

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

En el caso de que, por motius tècnics, no es poguessin realitzar aquestes proves per aquest mitjà, alternativament, es realitzaria un examen escrit sobre la pràctica.

La nota final Fin es determina en funció de T i P de la següent manera que fomenta un esforç equilibrat en ambdues parts:

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 complementària

  • 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.

Enllaços web

  1. http://www.lsi.upc.es/~rivero/CL
    Página de la asignatura


Capacitats prèvies

Coneixements de tècniques de programació estructurada i estructures de dades i algoritmes; llenguatges, autòmats i gramàtiques formals; estructura de computadors.


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil