Corso di Automi, Linguaggi e Traduttori.  Laurea on-line.

Anno Accademico 2005-2006.

Dipartimento di Informatica, Sistemi e Produzione. Computer Science Department.

Docente: Alberto Pettorossi. You can talk to the teacher by appointment.
To get in contact with the teacher:
you can also send email messages to pettorossi@info.uniroma2.it.
 with subject: ALTonline2005-06 NomeCognome NumeroDiMatricola

Informazioni aggiornate circa le lezioni, gli esami, il programma, le domande
d'esame e le modalità d'esame sono riportate nel sito del corso di
Automi, Linguaggi e Traduttori della laurea NON on-line:
      http://www.iasi.cnr.it/~adp/ProgramCorsoALT05-06.html

Links to:
  1. Automi, Linguaggi e Traduttori Laurea NON on-line:
      http://www.iasi.cnr.it/~adp/ProgramCorsoALT05-06.html
  2. Ingegneria On line (password required)
  3. Ingegneria On line: Automi, Linguaggi e Traduttori (password required)

---------------------------------
Per l'esame occorre 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 puo` prenotare per entrambi gli appelli.
Nella prenotazione indicare: Laurea online.

Inviare entro sette giorni dalla data dell'appello a:
corsoalt2006@tiscali.it e a pettorossi@info.uniroma2.it
un messaggio con oggetto: altonline2006_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 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 con i nomi:
           altonline2006_CognomeNome_Matricola_Membership1
           altonline2006_CognomeNome_Matricola_Parsing2
--> Non si includano screenshots e ci si attenga a queste indicazioni, per cortesia.
--> Si invii il messaggio con i due allegati, anche se cio` e` stato fatto per un appello precedente.
---------------------------------

Obiettivo del corso.
Introduzione alla gerarchia dei linguaggi formali e degli automi con
particolare riferimento ai linguaggi regolari, ai linguaggi liberi
dal contesto, agli automi finiti e agli automi pushdown. Introduzione alle
tecniche fondamentali per l'analisi sintattica e la compilazione dei
linguaggi di programmazione.

Programma del corso:
Preliminari matematici. Gerarchia di Chomsky. Linguaggi regolari,
espressioni regolari, automi finiti. Parsing dei linguaggi regolari.
Linguaggi liberi dal contesto e automi pushdown. Parsing dei linguaggi
liberi dal contesto: Cocke-Younger-Kasami parser, chop-expand parser,
LL-parsers, LR-parsers. LALR(1) parsers.

Prerequisiti: Elementi di programmazione in C++ o in Java.
Uso di arrays, liste, puntatori e ricorsione.
Elementi di Algebra e di Calcolo dei Predicati. 

Prove in itinere
Programma dettagliato del corso e domande d'esame
Modalità di esame: 
Presentazione e discussione degli esercizi delle prove in itinere (da svolgere individualmente).
Scritto e orale.
Si ricorda che possono sostenere l'esame solo gli studenti che:
(i) nell'anno accademico 2005-06 sono iscritti al secondo anno ripetente o al terzo anno o
    al terzo anno ripetente, e
(ii) nel loro piano di studi per l'anno 2005-06 hanno il corso di Automi, Linguaggi e Traduttori, e
(iii) se iscritti per l'anno accademico 2005-06 al secondo anno ripetente, allora hanno richiesto nel piano
   di studi di anticipare il corso di Automi, Linguaggi e Traduttori al secondo anno, e
(iv) hanno avuto il piano di studi approvato.

Norme generali di accesso agli esami:
1) Non è possibile sostenere un esame che, per conflitto col piano di studi o con l'anno di iscrizione,
non possa esser sostenuto dallo studente nell'anno in corso.
2) Lo studente dovrà presentarsi all'esame con il libretto di iscrizione e con una copia approvata del proprio piano
di studi (autentica rilasciata dalla segreteria studenti).
---------------------------------------------------------------------------------------------------------------------

Testi consigliati.
1. J. E. Hopcroft, R. Motwani, J.D. Ullman: "Automi, Linguaggi e Calcolabilità", Addison-Wesley,
    Pearson Education Italia, 1997.
Alcune sezioni dei seguenti testi:
2. Pettorossi, A.: Quaderni di Informatica Parte I. (2nd Edition) (2004).
3. Pettorossi, A.: Theory of Computation II.  (2nd Edition) Aracne (1993).
4. A.V. Aho, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools.
   Chapter 4. Addison-Wesley 1986 (It is the so-called Dragon Book)
-------------------------------------------------------------