Linguaggi e Traduttori
A.A. 2011-2012

Argomenti delle lezioni

---

In questa pagina sono elencati gli argomenti trattati in ogni lezione. E' inoltre segnalato un riferimento ai due libri di testo principali a cui si fa riferimento con le iniziali degli autori.
E' talvolta anche presente un riferimento a dei lucidi preparati da collaboratori del Prof. Crespi Reghizzi. Attenzione: tali lucidi non corrispondono esattamente alle lezioni (contengono sia argomenti in piu' che in meno).

---

• Lezione del 7 ottobre
  [ ALSU cap. 1 sez. 1.1, 1.2]
  Introduzione al corso: programma, libri i testo, modalita' d'esame.
  Contesto e fasi di un compilatore. Analisi lessicale, sintattica e semantica di una frase. Introduzione generale alle fasi del front-end di un compilatore.

• Lezione del 11 ottobre
  [CR cap. 2 sez. 2.1, 2.2 - Lucidi Serie 01]
  Introduzione ai linguaggi formali. Notazioni, definizioni ed esempi. Operazioni tra parole e tra linguaggi.

• Lezione del 14 ottobre
  [CR cap. 2 sez. 2.3, 2.4 - Lucidi Serie 02]
  Espressioni regolari e linguaggi regolari. Definizioni ed esempi. Derivazioni. Linguaggio di una espressione regolare. Ambiguita'. Espressioni regolari estese. Proprieta' di chiusura della famiglia REG.

• Lezione del 17 ottobre
  [CR cap. 2 sez. 2.5.1 - 2.5.6 - Lucidi Serie 03]
  Grammatiche context-free. Definizioni. Esempi: linguaggio dei palindromi, linguaggio delle espressioni regolari. Notazioni e tipi di regole in base alla forma delle parti sinistre e destre. Derivazioni e linguaggio generato.
  Proprietą di ricorsione e infinitezza del linguaggio. Esempio: linguaggio delle espressioni aritmentiche.

• Lezione del 21 ottobre
  [CR cap. 2 sez. 2.5.7- 2.5.10 - Lucidi Serie 04]
  Alberi sintattici e derivazioni canoniche (sinistre o destre). Linguaggio di Dyck. Esempi. Composizioni regolari di linguaggi liberi. Chiusura rispetto all'operazione di unione insiemistica.
  Ambiguitą sintattica. Gradi di ambiguitą. Esempi.

• Lezione del 24 ottobre
  [CR cap. 2 sez. 2.5.11 , 2.6.1-2.6.2 Lucidi Serie 04, 06]
  Catalogo di forme ambigue nelle grammatiche ed eventuali rimedi. Ambiguitą nella ricorsione bilaterale. Ambiguitą derivata dall'operazione di unione. Linguaggi inerentemente ambigui. Esempi. Ambiguitą derivata dall'operazione di concatenazione. Esempi. Ambiguitą delle frasi condizionali: problema dell' "else appeso".
  Grammatiche per linguaggi regolari: grammatiche lineari destre o sinistre. Esempi. Calcolo di una grammatica lineare destra (o sinistra) a partire da una espressione regolare.
  Linguaggi non context-free.

• Lezione del 25 ottobre
  Esercizi su espressioni regolari e grammatiche context-free.

• Lezione del 4 novembre
  [CR cap. 2 sez. 2.8 , cap. 3 sez. 3.1-3.4 Lucidi Serie 07, 08]
  Classificazione dei linguaggi secondo Chomsky.
  Automi a stati finiti come algoritmi per il riconoscimento dei linguaggi regolari. Definizioni ed esempi. Automa minimale. Passaggio da un automa finito ad una grammatica lineare destra.

• Lezione del 7 novembre
  [CR cap. 3 sez.3.5-3.7 Lucidi Serie 09]
  Automi non deterministici: motivazioni per il non determinismo. Riconoscimento con automi non deterministici. Determinizzazione di automi. Calcolo dell'automa deterministico definendo soltanto gli stati raggiungibili. Riconoscimento su automa non deterministico per simulazione dell'automa deterministico. Trasformazioni di una grammatica unilineare in automa non deterministico.

• Lezione del 8 novembre
  [CR cap. 3 sez. 3-8 Lucidi Serie 10]
  Dall'espressione regolare all'automa finito: metodo di Thompson, metodo di Glushkov, Mc Naugthon e Yamada e metodo di Berry e Sethi.
  Esercizio 1: implementare in C l'algoritmo di passaggio da RE ad NFA e quello di passaggio diretto a un DFA.
  Esercizio 2: Trasformare le seguenti RE in NFA, applicare poi l'algoritmo di determinizzazione. Trasformare poi direttamente le seguenti RE in DFA per confrontare gli automi ottenuti.
  i) (a|b)*
  ii) (a*|b*)*
  iii) ((ε |a) b*)*
  iv) (a|b)*abb(a|b)*
  Gli esercizi possono essere spediti per mail al docente.

• Lezione del 11 novembre
  ALSU cap. 3 sez. 3.1, 3.3.4, 3.4
  Definizioni regolari. Schema di progetto di un analizzatore lessicale: token, pattern e lessemi. Definizione dei token per un frammento di codice.

• Lezione del 14 novembre
  [CR cap. 4 sez. 4.1-4.2 Lucidi Serie 11]
  Algoritmi di riconoscimento per linguaggi context-free: automi a pila.
  Trasformazione di una grammatica in un automa a pila con un solo stato. Determinismo e non-ambiguitą.

• Lezione del 15 novembre
  ALSU cap. 4 sez. 4.3.3, 4.3.4, 4.4.1. (Si consiglia lettura sez. 4.1 e 4.2).
  Parsing a discesa ricorsiva. Eliminazione della ricorsione sinistra e della fattorizzazione sinistra di una grammatica.

• Lezione del 18 novembre
  ALSU cap. 4 sez. 4.4.2- 4.4.3
  Costruzione di una tabella di parsing predittivo. Funzioni First e Follow . Esempi.

• Lezione del 21 novembre
  ALSU cap. 4 sez. 4.4.3 - 4.4.4.
  Grammatiche LL(1):costruzione della tabella di parsing. Algoritmo di parsing predittivo non ricorsivo aiutato da tabella. Gestione degli errori.
  Esempio 1: Dire se la grammatica seguente e' LL1 (costruire la tabella di parsing).
  S -> aSb | ε
  Esempio 2: Dire se la grammatica seguente e' LL1 (costruire la tabella di parsing).
  S -> +SS | *SS | id
  Esempio 3: Dire se la grammatica seguente e' LL1 (costruire la tabella di parsing).
  S -> aSb | aSc | ε
  

Lezione del 22 novembre
ALSU cap. 4 sez. 4.5 , 4.6.1-4.6.2
Parser ascendenti. Schema e descrizione intuitiva di un parser shift-reduce (SR).
Possibili conflitti in un parser SR. Parser LR(0): LR(0)-item : funzioni "closure" e "goto". Costruzione dell'automa LR(0).

Lezione del 28 novembre
ALSU cap. 4 sez. 4.6.3, 4.6.4
Algoritmo di parsing LR.
Esempio di grammatica non LR(0). Parsing SLR: costruzione della tabella per l'esempio precedente.
Esempio di grammatica non SLR. Esempi di conflitti shift-reduce e reduce-reduce in tabelle SRL.

• Lezione del 29 novembre
  ALSU cap. 4 sez. 4.6.4, 4.7
  Parsing SLR: costruzione della tabella per l'esempio precedente.
  Esempio di grammatica non SLR. Esempi di conflitti shift-reduce e reduce-reduce in tabelle SRL.
  Parsing LR(1): item LR(1) , funzioni closure e goto relative. Costruzione della tabella. Riduzione dell'automa LR(1) e parser LALR.

  Esercizio 1: Dire se la seguenti grammatica e' LR0 e/o SLR e costruire le relative tabelle.
  E -> E + n | n
  Esercizio 2: Dire se la seguenti grammatica e' LR0 e/o SLR e costruire le relative tabelle.
  S -> (S) S | e
  Esercizio 3: Dire se la seguenti grammatica e' LR0 e/o SLR e costruire le relative tabelle.
  E -> T | E + T
  T -> (E) | k
  Esercizio 4: Creare la tabella LR(1) per la grammatica:
  S -> L=R
  S -> R
  L -> *R
  L -> id
  R -> L
  

• Lezione del 5 dicembre
  Esercitazione su parsing LR.

• Lezione del 12 dicembre
  [CR cap. 5 sez.5.1-5.4 Lucidi Serie 15]
  Traduzioni: frontiera tra sintassi e semantica. Relazione e funzione di traduzione. Translitterazioni.
  Traduzioni regolari e automa traduttore. Traduttore sequenziale.

• Lezione del 16 dicembre
  [CR cap. 5 sez.5.5-5.5.1 Lucidi Serie 15; ALSU cap.5 sez 5.1-5.2 (cenni)]
  Traduzioni sintattiche e schemi di traduzioni. Esempio: uno schema di traduzione dal linguaggio delle espressioni aritmetiche infisse a quelle in forma polacca prefissa.
  Traduzioni semantiche: perche' si usano e come si implementano. Grammatiche con attributi.
  Esempio di grammatica con attibuti per il linguaggio di stringhe che rappresentano numeri binari. Albero di parsing con il calcolo degli attributi.
  Esempio di grammatica con attibuti per il linguaggio di stringhe che rappresentano numeri binari o ternari.
  Esercizio: Calcolare l'albero di parsing con gli attributi per la parola 212t.
  

---