Indice degli argomenti

  • Materiale Didattico

    Il testo adottato dal corso è il 'Dragon Book':

    A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman
    Compilatori
    Principi, tecniche e strumenti
    seconda edizione
    Pearson Education Italia, 2009

    Il corso utilizza inoltre un forum elettronico diviso in tre sezioni per lo scambio tra gli studenti ed il docente di informazioni tecniche, didattiche ed amministrative
  • Lezione 1

    Giovedì 09 marzo (ore 14:30-16:30)

    Presentazione del corso

    • Obiettivi, prerequisiti e materiale
    • Informazioni amministrative

    Introduzione alla teoria dei compilatori

    • Traduzone: compilatori e interpreti
    • Fasi della compilazione
    • Cenni storici

    Materiale

    • Aho et al., cap. 1
  • Lezione 2

    Venerdì 10 marzo (ore 12:30-14:30)

    Analisi lessicale

    • Token e lessemi
    • Espressioni regolari
    • Definizioni regolari
    • Diagrammi a transizioni

    Materiale

    • Aho et al., cap. 3
  • Lezione 3

    Giovedì 16 marzo (ore 14:30-16:30)

    Analisi lessicale

    • Diagrammi a transizioni
    • Parole chiave e identificatori
    • Architetture per l'analizzatore lessicale

    Materiale

    • Aho et al., cap. 3
    • Lezione 4

      Venerdì 17 marzo (ore 12:30-14:30)

      Analisi lessicale

      • Flex: teoria e esercizi

      Materiale

      • Aho et al., cap. 3
    • Lezione 5

      Lunedì 20 marzo (ore 14:30-16:30)

      Analisi lessicale

      • Automi a stati finiti
      • Simulazione di un automa deterministico su parola singola
      • Combinazione di più automi: maximal match e regole di precedenza
      • Simulazione di un automa nondeterministico su parola singola e su stream di caratteri
      • Implementazione della tabella delle transizioni

      Materiale

      • Aho et al., cap. 3
    • Lezione 6

      Giovedì 23 marzo (ore 14:30-16:30)

      Analisi sintattica

      • Grammatiche context-free
      • Derivazioni e alberi di parsing
      • Ambiguità sintattica
      • Automi a pila
      • Parsing top-down e parsing bottom-up

      Materiale

      • Aho et al., cap. 4
    • Lezione 7

      Venerdì 24 marzo (ore 12:30-14:30)

      Bison

      • Introduzione al programma Bison
      • Formato file
      • Esempi
      • Gestione di grammatiche ambigue

      Materiale

      • Aho et al., cap. 4
    • Lezione 8

      Giovedì 30 marzo (ore 14:30-16:30)

      Bison

      • Uso combinato di Bison e Flex
      • Gestione di grammatiche ambigue

      Analisi sintattica

      • Rimozione ambiguità sintattica
      • Eliminazione della ricorsione sinistra immediata in una CFG

      Materiale

      • Aho et al., cap. 4
    • Lezione 9

      Venerdì 31 marzo (ore 12:30-14:30)

      Analisi sintattica

      • Eliminazione della ricorsione sinistra in una CFG: algoritmo e motivazione
      • Fattorizzazione di una CFG
      • Parsing top-down e recursive descent
      • Parsing e backtracking

      Materiale

      • Aho et al., cap. 4
      • Lezione 10

        Giovedì 06 aprile (ore 14:30-16:30)

        Bison

        • Uso combinato di Bison e Flex
        • Gestione della dichiarazione %union

        Analisi sintattica

        • Funzioni FIRST() e FOLLOW()
        • Grammatiche LL(1)
        • Tabella per il parser LL(1)
        • Gestione degli errori per il parser LL(1)

        Materiale

        • Aho et al., cap. 4
        • Lezione 11

          Venerdì 07 aprile (ore 12:30-14:30)

          Bison

          • Esercizi: Gestione della symbol table

          Analisi sintattica

          • Bottom-up parsing e nozione di handle
          • Shift-Reduce parsing
          • Conflitti: shift-reduce e reduce-reduce
          • Esempi

          Materiale

          • Aho et al., cap. 4
        • Lezione 12

          Giovedì 13 aprile (ore 14:30-16:30)

          Analisi sintattica

          • Sentential form in una rightmost derivation e taglio verticale dell'albero di derivazione
          • Viable prefixes per una CFG come linguaggio regolare
          • NFA per il linguaggio dei viable prefixes: LR items come stati e specifica delle transizioni
          • Riconoscimento delle handles e parser LR

          Materiale

          • Appunti dalla lezione
          • Video disponibile sul post 'Handles and valid prefixes' del Forum
          • Lezione 13

            Giovedì 20 aprile (ore 14:30-16:30)

            Analisi sintattica

            • Viable prefixes
            • LR parsing: items e stati
            • Funzioni closure() e goto()
            • SLR parsing
            • Costruzione tabella SLR
            • Ambiguità e gestione degli errori nel parsing LR

            Materiale

            • Aho et al., cap. 4
          • Lezione 14

            Venerdì 21 aprile (ore 12:30-14:30)

            Traduzione

            • Traduzione guidata dalla sintassi
            • Attributi sintetizzati ed ereditati
            • Il formalismo Syntax-Directed Definition (SDD, definizione guidata dalla sintassi)
            • Esempi di traduzione con attributi sintetizzati ed ereditati

            Materiale

            • Aho et al., cap. 5
          • Lezione 15

            Giovedì 27 aprile (ore 14:30-16:30)

            Traduzione

            • Grafo delle dipendenze e ordine di valutazione
            • S-attribuited SDD e L-attribuited SDD
            • Alberi sintattici astratti ed esempi di traduzione
            • Struttura dei tipi ed esempi di traduzione

            Materiale

            • Aho et al., cap. 5
            • Lezione 16

              Venerdì 28 aprile (ore 12:30-14:30)

              Discussione Progetto

              • Traduzione in 3-address code

              Traduzione

              • Il formalismo Syntaxt-Directed Translation Schemata (SDT, Schemi di traduzione guidati dalla sintassi)
              • Esempi di SDT
              • Trasformazione da S-attributed SDD a Postfix SDT

              Materiale

              • Aho et al., cap. 5
            • Lezione 17

              Giovedì 04 maggio (ore 14:30-16:30)

              Traduzione

              • Trasformazione da L-attributed SDD a SDT
              • Esempio: istruzione di dichiarazione variabili
              • Esempio: Istruzione iterazione while
              • Implementazione (L-attributed) SDT mediante parser recursive descent
              • Implementazione (L-attributed) SDT mediante parser recursive descent con generazione incrementale del codice

              Materiale

              • Aho et al., cap. 5
            • Lezione 18

              Venerdì 05 maggio (ore 12:30-14:30)

              Traduzione

              • Implementazione (L-attributed) SDT mediante parser LL
              • Implementazione (L-attributed) SDT mediante parser LR

              Bison

              • Tecniche per l'implementazione in Bison di attributi ereditati
              • Tecniche per l'emulazione in Bison di attributi ereditati
              • Azioni infisse in Bison

              Materiale

              • Aho et al., cap. 5
              • Lucidi del corso (sezione 05, parte III)
              • Lezione 19

                Giovedì 11 maggio (ore 14:30-16:30)

                Generazione codice intermedio

                • Rappresentazioni intermedie: AST, DAG, value-number
                • Codice a tre indirizzi; definizione, quadruple, triple, triple indirette
                • Traduzione espressioni aritmetiche

                Discussione Progetto

                • Traduzione in 3-address code

                Materiale

                • Aho et al., cap. 6
                • Lucidi della lezione
              • Lezione 20

                Venerdì 12 maggio (ore 12:30-14:30)

                Generazione codice intermedio

                • Tabelle dei simboli e campo di visibilità
                • Traduzione espressioni booleane
                • Lazy evaluation
                • Traduzione di istruzioni di controllo di flusso

                Materiale

                • Aho et al., cap. 2
                • Aho et al., cap. 6
              • Lezione 21

                Giovedì 18 maggio (ore 14:30-16:30)

                Discussione Progetto

                • Attributi inherited e parser LR
                • Nonterminali di tipo marker

                Generazione codice intermedio

                • Espressioni per i tipi, rappresentazione a grafo
                • Equivalenza per tipi: name equivalence e structural equivalence
                • Esempio array: traduzione di dichiarazioni in espressione di tipo e occupazione di memoria

                Materiale

                • Aho et al., cap. 6
                • Lezione 22

                  Venerdì 19 maggio (ore 12:30-14:30)

                  Discussione Progetto

                  • Gestione attributi inherited
                  • Gestione symbol table in 3AC

                  Generazione codice intermedio

                  • Record e class: traduzione di dichiarazioni in espressione di tipo e occupazione di memoria
                  • Organizzazione in memoria per un array a k dimensioni
                  • Indirizzamento degli elementi di un array e address polynomial

                  Materiale

                  • Aho et al., cap. 6
                • Lezione 23

                  Giovedì 25 maggio (ore 14:30-16:30)

                  Generazione codice intermedio

                  • Indirizzamento per array: implementazione tramite SDT
                  • Type system e inferenza
                  • Introduzione al type system: notazione basata su sistemi di Post
                  • Type system: regole per espressioni aritmetiche e Booleane

                  Materiale

                  • Aho et al., cap. 6
                  • Lucidi della lezione
                  • Lezione 24

                    Venerdì 26 maggio (ore 12:30-14:30)

                    Generazione codice intermedio

                    • Type system: regole per istruzioni più comuni
                    • Conversioni di tipo
                    • Backpatching per espressioni Booleane
                    • Backpatching per istruzioni di controllo di flusso

                    Materiale

                    • Aho et al., cap. 6
                    • Lucidi della lezione

                    Materiale

                    • Aho et al., cap. 4
                    • Programma corso

                      Il programma del corso è basato sul libro di testo adottato. Alcuni argomenti segnalati esplicitamente nel programma devono essere integrati con i lucidi delle lezioni, disponibili su questo sito.
                    • Temi d'esame

                      In questa box vengono pubblicati i temi d'esame degli appelli svolti nello scorso anno accademico.

                      Tenete presente che nell'anno accademico in corso ho spiegato in maggiore dettaglio le SDD e SDT, e ciò si rifletterà nelle consegne degli appelli.