Corso di Automi, Linguaggi e Traduttori (Corso frontale e Corso on-line)
Anno Accademico 2007-2008.
Dipartimento di Informatica, Sistemi
e Produzione. Computer Science Department.
Link to: Automi, Linguaggi e Traduttori.
(Corso on-line) (username and password required)
Docente: Alberto
Pettorossi. You can talk to the teacher after the lectures or by
appointment.
You can send email messages to the
teacher. In your messages, please,
use the subject: alt2008_CognomeNome_Matricola or
if you are an online
student: alt2008online_CognomeNome_Matricola
Lectures: from 10.12.07 to 15.02.08
(No lectures from 22.12.07 to 06.01.08)
Tuesday 11:30-13:15 Room 2 PP2
Thursday 11:30-13:15 Room 2 PP2
Friday
14:00-15:45 Room 4 PP2
Exams:
Tuesday 19.02.08 16:00 (Room 04 n.e.) Seminario
didattico-scientifico in preparazione all'esame
Friday 22.02.08 16:00
(Room 02 n.e.) Primo appello
(*)
Tuesday 26.02.08 16:00 (Room 02 n.e.) Secondo appello (*)
Tuesday 09.09.08 16:00
(Room 06 n.e.) Seminario didattico-scientifico in preparazione all'esame
Thursday 11.09.08 15:30 (Room 02 n.e.) Primo
appello (*)
Tuesday 16.09.08 15:30 (Room 02 n.e.) Secondo
appello (*)
---------------------------------
(*) Prenotarsi nel foglio predisposto all'ingresso
dell'edificio
di Ingegneria dell'Informazione (Via
del Politecnico 1, 00133 Roma)
entro sette
giorni dalla data dell'appello.
--> Non ci si può prenotare a
entrambi gli appelli.
Se si è studenti "online"
nella prenotazione indicare: online.
Inviare entro sette giorni dalla data dell'appello a:
alt@iasi.cnr.it e a pettorossi@info.uniroma2.it
un messaggio con
oggetto:
alt2008_CognomeNome_Matricola
con testo: Invio in allegato i miei elaborati relativi alle
due prove in itinere che ho fatto da solo. Nome
Cognome
e con allegati due
file di tipo testo (.cpp oppure .java oppure .txt) con i programmi documentati,
con indicazioni per
la loro compilazione ed esecuzione, e
con alcune prove di
esecuzione riportate come commenti nel codice,
fatti dallo
studente, relativi alle prove in itinere. I nomi dei due file siano:
alt2008_CognomeNome_Matricola_ Parsing1
alt2008_CognomeNome_Matricola_ Membership2
Se si e` studenti
"online":
altonline2008_CognomeNome_Matricola_Parsing1
altonline2008_CognomeNome_Matricola_Membership2
Non si includano
screenshots e ci si attenga a queste indicazioni, per cortesia.
Si invii il messaggio con i due
allegati, anche se ciò è stato fatto per un appello
precedente.
---------------------------------
Obiettivo del
corso.
Introduzione ai linguaggi
formali e agli automi con particolare riferimento
ai linguaggi regolari, ai
linguaggi liberi dal contesto, agli automi finiti e
agli automi pushdown.
Introduzione alla teoria della computabilità.
Introduzione alle
tecniche fondamentali per l'analisi sintattica e
la compilazione dei
linguaggi di programmazione.
Programma del corso:
Preliminari matematici:
relazioni, funzioni. Gerarchia di Chomsky. Linguaggi regolari,
espressioni regolari,
automi finiti deterministici e nondeterministici. Parsing dei linguaggi
regolari.
Linguaggi context-free e
automi pushdown deterministici e nondeterministici.
Parsing dei linguaggi
context-free: Cocke-Younger-Kasami parser, chop-expand parser,
Earley parser
(facoltativo), LL(1) parsers, LR(0) parsers, LR(1) parsers, LALR(1) parsers.
Macchina di Turing e
grammatiche di tipo 0 e 1. Problemi decidibili e semidecidibili.
KMP pattern
matcher. Knuth-Morris-Pratt pattern matcher.
Triple di Hoare per la
correttezza parziale.
Programma
dettagliato del corso e domande d'esame.
Previous Exam
Questions.
Dispense:
1. Visiting Trees
While Looking for Good Nodes 1.bis Depth First Visit of Trees 2. Chop-Expand Parser in Java
3.
Chop-Expand Parser in Prolog (facoltativo) 4.
LL(1) Parsing 5. Theorem Prover in Java
6. Knuth-Morris-Pratt algorithm in Java 1.5
7. Quantifiers 8. Dijkstra's SSSP (facoltativo) 8.bis Paths in
Graphs
9.
DistributedTermination (facoltativo) 10. LALR(1) parsing using Bison 11.
HsiangTheoremProver (facoltativo)
Prerequisiti: Fondamenti di Informatica. Elementi di programmazione
in C++ oppure Java.
Uso di arrays, liste, puntatori e
ricorsione. Elementi di Algebra e di Calcolo dei Predicati.
Modalità di
esame:
Presentazione e discussione degli
esercizi delle prove in itinere (da svolgere da soli!). Scritto e orale.
Lo studente dovrà presentarsi all'esame
con il libretto di iscrizione.
------------------------------------------------------------------------------------------------------------
Testi consigliati.
1. Pettorossi, A.: Automata Theory
and Formal Languages.
Aracne, 2007.
Escluse le sezioni: 1.6, 2.7, 2.11, 3.13.2, 3.14,
3.15, 3.16, 6.2, 6.3, 6.4, 7.1, 7.2, 7.6.
e le prove dei teoremi dei capitoli 4, 5 e della
sezione 6.1
2. A.V. Aho, R. Sethi, J.D. Ullman: Compilers:
Principles, Techniques, and Tools.
Addison-Wesley, 1986. This book is known as
"The Dragon Book".
The following sections only:
4.4 (Top-Down Parsing), 4.5 (Bottom-Up Parsing),
4.7 (LR-Parsers). Handouts are available for this part
of the course.
Errata Corrige of Books
--------
Tra i tanti testi disponibili ove
approfondire alcuni argomenti del corso, si segnalano i seguenti:
3. J. E. Hopcroft, R. Motwani,
J.D. Ullman: "Automi, Linguaggi e Calcolabilità", Addison-Wesley,
Pearson Education Italia, 1997. In Inglese:
"Introduction to Automata Theory, Languages,
and Computation, Addison-Wesley Pub. Co., 2001
(Revised Edition).
4. Pettorossi, A.: Quaderni
di Informatica Parte I. 2nd
Edition, Aracne, 2004. In particular, Chapters 1 and 8.
-------------------------------------------------------------