DIPARTIMENTO   DI   INFORMATICA
Università di Torino

Corso di: Linguaggi e Ambienti di Programmazione (CFU 6) 

Laurea Triennale in Informatica: percorso Sistemi e Reti

Anno accademico: 2006-2007

Docente: Maddalena Zacchi

INDICE

Obiettivi del corso

Scopo del corso è introdurre la teoria dei linguaggi formali e illustrarne l'applicazione nella traduzione dei linguaggi di programmazione.

Prerequisiti

Si presuppone che lo studente conosca i concetti base dell'informatica e abbia un po' di esperienza di programmazione.
Eventuali corsi propedeutici:  Programmazione I e II

Modalità d'esame

L'esame consiste in una prova scritta.

Libri di testo

  • [1]  "Linguaggi Formali e Compilazione", Stefano Crespi Reghizzi, Pitagora Editrice Bologna, 2006.
  • [2]  "Compilers", Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Addison Wesley, 1986.

Programma del corso

DEFINIZIONE SINTATTICA DEI LINGUAGGI
(cap.2 e 3 di [1], tranne 2.7.3 e 2.7.4)
  • Teoria dei linguaggi formali: alfabeto e linguaggio, operazioni sulle stringhe, operazioni sui linguaggi.
  • Espressioni e linguaggi regolari: definizione di espressione regolare, derivazioni e linguaggio denotato.
  • Le grammatiche generative libere dal contesto: Sintassi, derivazioni e linguaggio generato. Grammatiche ridotte, ricorsione e infinitezza del linguaggio. Alberi sintattici e derivazioni canoniche. Ambiguità ed equivalenza. Forme normali delle grammatiche. Eliminazione della ricorsione sinistra diretta.
  • Dalle espressioni regolari alle grammatiche libere che generano il linguaggio denotato. Grammatiche lineari.

RICONOSCIMENTO DELLE FRASI: MODELLI FINITI
(cap. 3 di [1] , tranne 3.8.2 e 3.8.3)
  • Automa finito deterministico. Automa finito non deterministico. Eliminazione del non determinismo. Automi finiti e grammatiche lineari.
  • Automi finiti ed espressioni regolari. Automi per il riconoscimento dei linguaggi complemento e intersezione.
  • Automi push-down deterministici e non. Riconoscimento per stato finale e riconoscimento per stack vuoto.
  • Grammatiche libere e riconoscitori predittivi.

ANALISI SINTATTICA DISCENDENTE DETERMINISTICA
(cap.4, $4.4 di [2] , cap.4, $ 4.4.1 e 4.4.2 di [1])
  • Grammatiche LL(1). Definizione e calcolo degli insiemi degli inizi e dei seguiti.
  • Insiemi guida delle produzioni.
  • Parser a discesa ricorsiva.

TRADUZIONE SINTATTICA
(Cap. 5, $5.1, 5.2, 5.3, 5.4, 5.5 di [2])
  • Definizioni guidate dalla sintassi e schemi di traduzione.
  • Grammatiche L-attribuite.
  • Eliminazione della ricorsione sinistra in grammatiche ad attributi.
  • Traduzione a discesa ricorsiva per grammatiche L-attribuite.

Documentazione:

Materiale di complemento alle lezioni
  1.  Introduzione
  2. Algoritmo per l'individuazione degli stati distinguibili in un automa finito deterministico
  3. Grammatiche context-free e automi push-down
  4. Insiemi guida
  5. Analisi sintattica
  6. Traduzione
  7. Esempio: espressioni aritmetiche

Esercitazioni
  1. Esercitazione I
  2. Esercitazione II
  3. Esercitazione III
  4. Esercitazione IV
  5. Prova d'esame (fac simile)
Testi d'esame


[Corso di Studi di Informatica]
Last update: Jul 02, 2007