Insegnamento LINGUAGGI FORMALI E COMPILATORI
| Nome del corso di laurea | Informatica |
|---|---|
| Codice insegnamento | 55067206 |
| Curriculum | Comune a tutti i curricula |
| Docente responsabile | Arturo Carpi |
| Docenti |
|
| Ore |
|
| CFU | 6 |
| Regolamento | Coorte 2017 |
| Erogato | Erogato nel 2018/19 |
| Erogato altro regolamento | |
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Anno | 2 |
| Periodo | Secondo Semestre |
| Tipo insegnamento | Obbligatorio (Required) |
| Tipo attività | Attività formativa monodisciplinare |
| Lingua insegnamento | ITALIANO |
| Contenuti | Fasi della compilazione. Automi a stati finiti, linguaggi regolari, grammatiche lineari destre, lemma di iterazione, analizzatori lessicali. Grammatiche non contestuali, grammatiche ambigue, forme normali, automi a pila, algoritmi di parsing. La gerarchia di Chomsky. Analisi semantica: cenni |
| Testi di riferimento | J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson, 2009 A.V. Aho, R. Sethi, J.D. Ullman, Compilers. Principles, Techniques and Tools, Addison Wesley, 1988 D. Grune, C.J.H. Jacobs, Parsing techniques, Springer, 2008 (1. edizione disponibile on line) A. de Luca, F.D'Alessandro, Teoria degli Automi Finiti, Springer, 2013 |
| Obiettivi formativi | Le principali conoscenze fornite riguarderanno - i fondamenti della teoria dei linguaggi formali - la comprensione degli aspetti formali sintattico/semantici dei linguaggi di programmazione - il funzionamento di interpreti e compilatori. L'insegnamento fornirà allo studente la capacità di progettare analizzatori lessicali e analizzatori sintattici per semplici linguaggi di programmazione. |
| Prerequisiti | Per seguire con profitto il corso lo studente dovrebbe conoscere le nozioni fondamentali della Matematica Discreta e, in particolare quelle di funzione, relazione, equivalenza, insieme ordinato, semigruppo, grafo. Risulterà utile inoltre la conoscenza dei più semplici algoritmi su grafi diretti (accessibilità, verifica della connessione, ecc.). |
| Metodi didattici | Lezioni frontali |
| Altre informazioni | - |
| Modalità di verifica dell'apprendimento | L'esame prevede una prova scritta e una prova orale. La prova scritta, di durata non superiore a 90 minuti, consiste nella soluzione di quattro problemi di carattere algoritmico/computazionale. Tale prova ha l'obbiettivo di verificare la capacità di applicare le conoscenze apprese durante il corso alla soluzione di problemi pratici. La prova orale consiste in una discussione della durata di circa 30 minuti con l'obbiettivo di verificare la effettiva comprensione dei contenuti teorici del corso, nonché il livello di conoscenza degli argomenti previsti dal programma. Tale prova consentirà inoltre di verificare la capacità espositiva dello studente, in particolare con l'uso di un adeguato linguaggio tecnico. La prova scritta, una volta superata, conserva la sua validità per 12 mesi. Trascorso tale termine, lo studente che non abbia completato l'esame dovrà sostenere l'intero esame. Gli studenti che lo desiderano, potranno sostenere l'esame in lingua Inglese o Francese. Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa |
| Programma esteso | Generalità sui linguaggi di programmazione e compilatori, esempi, problemi Alfabeto, parole, linguaggi, grammatiche, operazioni tra linguaggi Analisi lessicale: automi a stati finiti, modello deterministico e non deterministico, linguaggi regolari e teorema di Kleene, automa minimo e teorema di Myhill-Nerode, grammatiche lineari destre, lemma di iterazione, analizzatori lessicali, proprietà di chiusura dei linguaggi regolari. Analisi sintattica: grammatiche non contestuali, grammatiche ambigue e linguaggi inerentemente ambigui, lemma di iterazione per linguaggi non contestuali, forme normali di Chomsky e Greibach, automi a pila, riconoscimento per pila vuota e stato finale, caratterizzazione dei linguaggi non contestuali mediante automi a pila, algoritmi di parsing. La gerarchia di Chomsky: linguaggi contestuali e monotoni, linguaggi ricorsivi e ricorsivamente enumerabili. Analisi semantica: cenni |