Insegnamento LINGUAGGI FORMALI E COMPILATORI

Corso
Informatica
Codice insegnamento
55067206
Curriculum
Comune a tutti i curricula
Docente
Arturo Carpi
Docenti
  • Arturo Carpi
Ore
  • 42 ore - Arturo Carpi
CFU
6
Regolamento
Coorte 2020
Erogato
2021/22
Attività
Base
Ambito
Formazione informatica di base
Settore
INF/01
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
Condividi su