Compilatori 2002/2003

docente: Fausto Spoto
fausto.spoto@univr.it
Dispense in linea:
  • prima versione (gennaio) postscript, pdf
  • seconda versione (febbraio) postscript, pdf
  • solo la differenza fra la seconda e la prima versione postscript, pdf
    Progetto (versione finale)
    Esempi di programmi in Object Tiger
    Testi d'esame:
  • 24 giugno 2002 postscript, pdf
  • 3 luglio 2002 postscript, pdf
  • 6 settembre 2002 postscript, pdf
  • 20 dicembre 2002 postscript, pdf
  • 2 aprile 2003 postscript, pdf
  • 23 giugno 2003 postscript, pdf
  • 25 luglio 2003 postscript, pdf
  • 24 settembre 2003 postscript, pdf
  • 10 ottobre 2003 postscript, pdf
  • 12 dicembre 2003 postscript, pdf
    Lezione 1 (9 gennaio 2003)
  • compilatori, fasi di compilazione.
  • esempio di programma Tiger
  • analisi lessicale
  • token, valore lessicale
  • alfabeto, linguaggio, espressioni regolari
  • lista di regole, trasformazione in automa a stati finiti
  • risoluzione dell'ambiguità: longest match e priorità sulle regole

    Lezione 2 (10 gennaio 2003)

  • analisi lessicale di Tiger
  • l'interfaccia Parse/Lexer.java
  • i token java_cup/runtime/Symbol.java
  • il package ErrorMsg
  • le espressioni regolari: Parse/Tiger.lex
  • modalità JLex: commenti e stringhe con escape
  • il makefile

    Laboratorio 1 (10 gennaio 2003)

  • istallazione e compilazione dell'analizzatore lessicale per Tiger
  • aggiunta dei token class, method, extends e new all'analizzatore lessicale per Tiger
  • file modificati: Parse/Tiger.lex, Parse/sym.java e Parse/Main_lexical.java

    Lezione 3 (22 gennaio 2003)

  • grammatiche libere dal contesto, terminali, non terminali, derivazioni, alberi di derivazione, ambiguità
  • parsing a discesa ricorsiva
  • insiemi NULLABLE, FIRST e FOLLOW e loro calcolo iterativo
  • costruzione della tabella di parsing LL(1)
  • ogni grammatica LL(k) è non ambigua

    Lezione 4 (23 gennaio 2003)

  • esercizi sulle grammatiche LL(1)

    Lezione 5 (27 gennaio 2003)

  • automi a pila, operazioni shift, reduce, goto e accept
  • items LR(0), chiusura di un insieme di items LR(0)
  • costruzione dell'automa e della tabella LR(0)
  • costruzione dell'automa e della tabella SLR

    Lezione 6 (29 gennaio 2003)

  • items LR(1), chiusura di un insieme di items LR(1)
  • costruzione dell'automa e della tabella LR(1)
  • costruzione della tabella LALR(1)
  • la gerarchia delle grammatiche
  • parsing in presenza di grammatiche ambigue

    Lezione 7 (30 gennaio 2003)

  • esercizi sul parsing LR(1)
  • esercizi sul parsing LR(1) in presenza di grammatiche ambigue: uso di priorità e associatività

    Lezione 8 (3 febbraio 2003)

  • il generatore di analizzatori sintattici JavaCup
  • precedenze e risoluzione dei conflitti in JavaCup
  • sintassi astratta
  • generazione dell'albero astratto durante il parsing LL(1)
  • generazione dell'albero astratto durante il parsing LR(1): azioni semantiche
  • sintassi astratta per Tiger
  • azioni semantiche per Tiger

    Lezione 9 (5 febbraio 2003)

  • esempi di traduzione del codice Tiger in semantica astratta
  • fusione degli alberi astratti di dichiarazioni mutuamente ricorsive di tipi e funzioni
  • identificatore unico per i simboli: la classe Symbol/Symbol.java

    Laboratorio 2 (5 febbraio 2003)

  • aggiunta delle produzioni di grammatica concreta per dichiarazioni di classi, creazione dinamica di oggetti e chiamate di metodo per il linguaggio Tiger
  • file modificati: Parse/Grm.cup

    Laboratorio 3 (6 febbraio 2003)

  • individuazione e implementazione delle classi di sintassi astratta Absyn/NewExp.java, Absyn/MethodCallExp.java, Absyn/MethodDec.java e Absyn/ClassDec.java
  • aggiunta delle azioni semantiche alla grammatica concreta per Tiger, come modificata nel Laboratorio 2
  • file modificati: Parse/Grm.cup

    Lezione 10 (10 febbraio 2003)

  • tabelle di simboli (ambienti)
  • gestione degli scope
  • implementazione funzionale e imperativa delle tabelle di simboli
  • classe Symbol/Table.java

    Laboratorio 4 (12 febbraio 2003)

  • modifica della classe di stampa degli alberi astratti Tiger in modo da gestire le quattro nuove classi astratte aggiunte durante il laboratorio 3
  • file modificati: Absyn/Print.java

    Lezione 11 (13 febbraio 2003)

  • ambiente delle variabili e ambiente dei tipi
  • uguaglianza strutturale e nominale dei tipi
  • la classe Types/Type.java e le sue sottoclassi
  • la classe Semant/Env.java

    Lezione 12 (17 febbraio 2003)

  • dichiarazioni di tipo semplici
  • dichiarazioni di tipo ricorsive
  • compatibilità fra tipi Tiger
  • dichiarazioni di variabile

    Lezione 13 (19 febbraio 2003)

  • dichiarazioni ricorsive di funzioni
  • controllo dei tipi per i leftvalue
  • controllo dei tipi per le espressioni

    Lezione 14 (20 febbraio 2003)

  • controllo della posizione dei break
  • esercitazione sull'analisi semantica

    Lezione 15 (24 febbraio 2003)

  • analisi semantica delle dichiarazioni di classe: problemi e possibili soluzioni

    Laboratorio 5 (24 febbraio 2003)

  • implementazione della classe Types/CLASS.java che rappresenta il tipo classe. Dovrà avere fra i suoi campi il tipo della superclasse e un ambiente locale per memorizzare i campi e i metodi locali della classe
  • implementazione della classe Semant/MethodEntry.java per denotare i simboli di metodo. Dovrà memorizzare la segnatura del metodo e l'etichetta Temp/Label.java a partire dalla quale si deve generare il codice per il metodo

    Laboratorio 6 (26 febbraio 2003)

  • discussione e impostazione del controllo dei tipi per le dichiarazioni di classe (dentro Semant/Semant.java): sia b un blocco di dichiarazioni di classe contigue:
    1. si controlla che b non contenga la definizione di due classi con lo stesso nome
    2. si assegnano delle Types/NAME.java ai nomi delle classi definite in b
    3. si chiama un metodo transClass(Absyn.ClassDec) che trasforma un albero astratto per una dichiarazione di classe in una istanza di Types/CLASS.java. Questo metodo viene richiamato su tutti gli alberi astratti legati nel blocco b tramite il campo next. Esso deve dare errore se la superclasse non è definita (ma può tranquillamente essere una Types/NAME.java)
    4. si cerca iterativamente di legare ogni Types/NAME.java inserita due passi prima al Types/CLASS.java calcolato da transClass per l'albero astratto corrispondente. Il legame si effettua solo se la superclasse è già stata legata, altrimenti si attende. Se si effettuano più iterazioni del numero di classi dichiarate in b si dà errore a causa di una ereditarietà circolare
    5. si scorrono tutti gli inizializzatori di campi e i corpi dei metodi e si controlla che i loro tipi siano corretti e compatibili coi tipi di dichiarazione
  • osservazioni/suggerimenti:
    1. occorre espandere la transExp con i casi per una Absyn/NewExp.java e una Absyn/MethodCallExp.java
    2. il corpo dei metodi può utilizzare l'identificatore this
    3. il metodo checkCompatible deve essere aggiornato per tenere conto della relazione di sottoclasse
    4. idem per il metodo checkUnifiable (facoltativo!)
    5. l'identificatore Object deve esistere nell'ambiente, legato a un Types/CLASS.java con superclasse null e ambiente locale vuoto. Si lavori a questa modifica dentro a Semant/Env.java. Il legame deve essere diretto o tramite una Types/NAME.java ? Si ricordi che Object deve essere usabile come superclasse!
    6. un metodo può essere ridefinito solo se il numero e il tipo dei parametri non cambia (facoltativo!)
  • file modificati: Semant/Semant.java, Semant/Env.java

    Lezione 16 (27 febbraio 2003)

  • introduzione al linguaggio intermedio per la compilazione di Tiger
  • stack di attivazione: problema di accesso agli identificatori esterni in presenza di scope statico (come in Tiger)

    Lezione 17 (3 marzo 2003)

  • costruzione della catena statica: regola figlio-fratello-antenato
  • coordinate di accesso per le variabili
  • classi Java per la gestione degli stack di attivazione di Tiger

    Lezione 18 (5 marzo 2003)

  • modalità di compilazione
  • compilazione delle dichiarazioni di tipo e di variabile
  • compilazione delle costanti intere e di null
  • compilazione dell'assegnamento

    Lezione 19 (6 marzo 2003)

  • compilazione delle espressioni condizionali
  • compilazione dell'espressione break
  • compilazione della chiamata di funzione: implementazione della regola figlio-fratello-antenato

    Lezione 20 (10 marzo 2003)

  • compilazione dei leftvalue
  • esempi di compilazione dei leftvalue
  • cenni ai frammenti di compilazione

    Laboratorio 7 (10 marzo 2003)

  • implementazione della compilazione di una RecordExp dentro la classe Translate/Translate.java
  • file modificati: Translate/Translate.java e Semant/Semant.java (se si modifica l'interfaccia di RecordExp dentro Translate/Translate.java)

    Lezione 21 (12 marzo 2003)

  • esercizi sulla generazione del codice
  • esercizi da tema d'esame

    Lezione 22 (13 marzo 2003)

  • esercizi sulla compilazione del codice per i linguaggi a oggetti