Topic outline

  • 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

    Martedì 01 marzo (ore 08:30-10: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

    Giovedì 03 marzo (ore 12:30-14:30)

    Analisi lessicale

    • Token e lessemi
    • Espressioni regolari

    Materiale

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

    Martedì 08 marzo (ore 08:30-10:30)

    Analisi lessicale

    • Definizioni regolari
    • Diagrammi a transizioni

    Materiale

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

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

      Analisi lessicale

      • Flex

      Materiale

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

      Martedì 15 marzo (ore 08:30-10:30)

      Analisi lessicale

      • Automi a stati finiti
      • Nondeterminismo e determinismo
      • Simulazione di un automa deterministico
      • Costruzione di un automa nondeterministico a partire da una espressione regolare
      • Combinazione di più automi: maximal match e regole di precedenza

      Materiale

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

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

      Analisi lessicale

      • Le funzioni epsilon-closure() e move()
      • Simulazione di un automa nondeterministico
      • Costruzione di un automa deterministico a partire da un automa nondeterministico
      • Implementazione della tabella delle transizioni

      Materiale

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

        Martedì 22 marzo (ore 08:30-10:30)

        Analisi sintattica

        • Parsing
        • Grammatiche context-free
        • Derivazioni e alberi di parsing
        • Ambiguità sintattica

        Materiale

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

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

        Analisi sintattica

        • Rimozione ambiguità sintattica
        • Eliminazione della ricorsione sinistra in una CFG: algoritmo e motivazione
        • Fattorizzazione di una CFG

        Materiale

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

          Martedì 05 aprile (ore 08:30-10:30)

          Analisi sintattica

          • Parsing top-down e recursive descent
          • Parsing e backtracking

          Materiale

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

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

          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

            Martedì 12 aprile (ore 08:30-10:30)

            Bison

            • Introduzione al programma Bison
            • Formato file
            • Esempi
            • Gestione di grammatiche ambigue
            • Uso combinato di Bison e Flex

            Materiale

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

            Giovedì 14 aprile (ore 12:30-14:30)

            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 13

            Martedì 19 aprile (ore 08:30-10:30)

            Analisi sintattica

            • LR parsing: items e stati
            • Esempi
            • Funzione closure()
            • Stati kernel e non-kernel
            • Funzione goto()

            Materiale

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

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

              Analisi sintattica

              • Grammatiche LR(0) e automa deterministico delle azioni
              • Esempi
              • SLR parsing
              • Costruzione tabella SLR
              • Esempi

              Materiale

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

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

                Analisi sintattica

                • Cenni sulle tecniche di parsing LR(1) e LALR(1)
                • Compressione delle tabelle di parsing LR
                • Ambiguità e gestione degli errori nel parsing LR

                Traduzione

                • Traduzione guidata dalla sintassi
                • Attributi sintetizzati ed ereditati

                Materiale

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

                Martedì 03 maggio (ore 08:30-10:30)

                Traduzione

                • Il formalismo Syntax-Directed Definition (SDD, definizione guidata dalla sintassi)
                • Esempi di traduzione con attributi sintetizzati ed ereditati
                • Grafo delle dipendenze e ordine di valutazione
                • S-attribuited SDD e L-attribuited SDD

                Materiale

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

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

                  Traduzione

                  • Alberi sintattici astratti ed esempi di traduzione
                  • Struttura dei tipi ed esempi di 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 18

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

                  Traduzione

                  • Trasformazione da S-attributed SDD a Postfix SDT
                  • Trasformazione da L-attributed SDD a SDT
                  • Esempio: istruzione di dichiarazione variabili
                  • Esempio: Istruzione iterazione while
                  • Implementazione (L-attributed) SDT mediante parser recursive descent

                  Materiale

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

                    Martedì 17 maggio (ore 08:30-10:30)

                    Traduzione

                    • Implementazione (L-attributed) SDT mediante parser recursive descent con generazione incrementale del codice
                    • Implementazione (L-attributed) SDT mediante parser LL
                    • Implementazione (L-attributed) SDT mediante parser LR
                    • Conversione attributi ereditati in attributi sintetizzati

                    Materiale

                    • Aho et al., cap. 5
                    • Lucidi del corso
                  • Lezione 20

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

                    Traduzione

                    • Emulazione attributi ereditati in Bison
                    • Azioni infisse in Bison

                    Generazione codice intermedio

                    • Rappresentazioni intermedie: AST, DAG, value-number
                    • Codice a tre indirizzi; definizione, quadruple, triple, triple indirette
                    • Espressioni per i tipi, rappresentazione a grafo, nozioni di equivalenza
                    • Esempio: traduzione di dichiarazioni in espressione di tipo e occupazione di memoria

                    Materiale

                    • Aho et al., cap. 6
                    • Lucidi del corso
                  • Lezione 21

                    Martedì 24 maggio (ore 08:30-10:30)

                    Generazione codice intermedio

                    • Traduzione di espressioni aritmetiche
                    • Indirizzamento degli elementi di un array

                    Materiale

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

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

                    Generazione codice intermedio

                    • Controllo statico dei tipi
                    • Introduzione al type system: notazione basata su sistemi di Post
                    • Type system: regole per espressioni aritmetiche e Booleane
                    • Type system: regole per istruzioni più comuni
                    • Conversioni di tipo

                    Materiale

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

                      Martedì 31 maggio (ore 08:30-10:30)

                      Generazione codice intermedio

                      • Tabelle dei simboli e campo di visibilità
                      • Traduzione di istruzioni di controllo di flusso

                      Materiale

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

                      Martedì 07 giugno (ore 08:30-10:30)

                      Generazione codice intermedio

                      • Backpatching per espressioni Booleane
                      • Backpatching per istruzioni di controllo di flusso

                      Esercizi

                      • Esercizi stile esame

                      Materiale

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

                      In questo argomento pubblicherò le slides con alcuni esercizi risolti, mano a mano che i rispettivi argomenti verranno svolti a lezione.
                      Il file con gli esercizi Flex era già stato distribuito sul forum. Nel file con gli esercizi su top-down parsing, l'esercizio V è stato svolto da uno studente dello scorso anno e non è ancora stato validati da me. Se trovate degli errori, vi prego di segnalarli usando il forum, così tutti vedono.
                    • 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 alcuni temi d'esame degli appelli svolti negli scorsi anni accademici.