Università degli Studi di Perugia

Prova scritta e orale

n.d.

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

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

Lezioni frontali

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

Conoscere le basi della teoria dei linguaggi formali e del parsing. Comprensione degli aspetti formali sintattico/semantici dei linguaggi di programmazione e del funzionamento di interpreti e compilatori.

1/03/2012 - 15/06/2012

n.d.

facoltativa

Dipartimento di Matematica e Informatica

Giovedì ore 16-18

Venerdì ore 11-13

Dipartimento di Matematica e Informatica, 2. piano