Università degli Studi di Urbino Carlo Bo / Portale Web di Ateneo


LINGUAGGI DI PROGRAMMAZIONE E COMPILATORI

Linguaggi di Programmazione e Compilatori

A.A. CFU
2011/2012 12
Docente Mail Ricevimento studenti
Alessandro Aldini mercoledì 10:00-13:00

Assegnato al Corso di Studio

Giorno Orario Aula

Obiettivi Formativi

Il Corso ha l'obiettivo di introdurre i concetti di base relativi alla sintassi e alla semantica dei linguaggi di programmazione e le loro applicazioni allo sviluppo dei compilatori.

English version: The objective is to illustrate the main concepts related to the syntax and semantics of programming languages, and their applications for the development of compilers.

Programma

01. Introduzione alla compilazione:
  01.01 Architettura e fasi di un compilatore.
  01.02 Grammatiche a struttura di frase, linguaggi formali, classificazione di Chomsky.

02. Linguaggi regolari:
  02.01 Automi a stati finiti deterministici.
  02.02 Automi a stati finiti non deterministici.
  02.03 Automi a stati finiti con ε-transizioni.
  02.04 Grammatiche lineari destre.
  02.05 Proprietà di chiusura dei linguaggi regolari.
  02.06 Espressioni regolari.
  02.07 Relazione tra espressioni regolari e automi a stati finiti.
  02.08 Pumping lemma per linguaggi regolari.
  02.09 Minimizzazione di automi a stati finiti.

03. Linguaggi liberi:
  03.01 Grammatiche libere e alberi sintattici.
  03.02 Semplificazione delle grammatiche libere, forma normale di Chomsky.
  03.03 Pumping lemma per linguaggi liberi, proprietà di chiusura dei linguaggi liberi.
  03.04 Automi a pila non deterministici.
  03.05 Relazione tra grammatiche libere e automi a pila non deterministici.

04. Analisi sintattica:
  04.01 Parsing top-down, parser e grammatiche LL(1).
  04.02 Parsing bottom-up.
  04.03 Parser e grammatiche SLR.
  04.04 Parser e grammatiche LR(1) e LALR(1).

05. Analisi semantica:
  05.01 Alberi attribuiti, alberi di sintassi astratta.
  05.02 Nomi e regole di scoping.
  05.03 Tipi di dato e type checking.

06. Generazione del codice:
  06.01 Organizzazione della memoria e passaggio dei parametri.
  06.02 Generazione del codice intermedio.
  06.03 Compilazione di espressioni aritmetiche.
  06.04 Compilazione di espressioni booleane.
  06.05 Compilazione di comandi e costrutti di controllo.

07. Semantica operazionale:
  07.01 Semantica operazionale naturale di un semplice linguaggio imperativo (While).
  07.02 Semantica operazionale di While con procedure (scoping statico e dinamico).

08. Semantica denotazionale:
  08.01 Semantica denotazionale di While.
  08.02 Semantica denotazionale di While con procedure (call-by-value e call-by-reference).

09. Programmazione funzionale in Haskell:
  09.01 Introduzione al linguaggio Haskell: espressioni, valori, tipi di dato primitivi.
  09.02 Funzioni e ricorsione.
  09.03 Polimorfismo.
  09.04 Coppie, tuple e liste.
  09.05 Funzioni di ordine superiore, specializzazione e currying.
  09.06 Definizione di tipi di dato: alias di tipo e tipi algebrici.
  09.07 Moduli.
  09.08 Monadi e input/output.

10. Attività di laboratorio:
  10.01 Esercizi di base su espressioni, valori e tipi.
  10.02 Esercizi su funzioni e ricorsione.
  10.03 Esercizi su coppie, tuple e liste.
  10.04 Esercizi su funzioni di ordine superiore.
  10.05 Esercizi su tipi algebrici.
  10.05 Esercizi su input/output in Haskell.
  10.06 Analisi lessicale in Haskell.

  10.07 Analisi sintattica in Haskell.

English version:

01. Introduction to compiling:
  01.01 Architecture and phases of a compiler.
  01.02 Grammars, formal languages, Chomsky hierarchy.

02. Regular languages:
  02.01 Deterministic finite-state automata.
  02.02 Non-deterministic finite-state automata.
  02.03 Finite-state automata with ε-transitions.
  02.04 Right-linear grammars.
  02.05 Closure properties of regular languages.
  02.06 Regular expressions.
  02.07 Regular expressions and finite-state automata.
  02.08 Pumping lemma for regular languages.
  02.09 Minimization of finite-state automata.

03. Context-free languages:
  03.01 Context-free grammars.
  03.02 Simplification of context-free grammars, Chomsky normal form.
  03.03 Pumping theorem for context-free languages, closure properties of context-free languages.
  03.04 Non-deterministic push-down automata.
  03.05 Context-free grammars and non-deterministic push-down automata.

04. Syntax analysis:
  04.01 Top-down parsing, LL(1) parsers and grammars.
  04.02 Bottom-up parsing.
  04.03 SLR parsers e grammars.
  06.04 LR(1) and LALR(1) parsers and grammars.

05. Semantic analysis:
  05.01 Attributed syntax trees, abstract syntax trees.
  05.02 Names, scope rules, management of the symbol table.
  05.03 Data types and type checking.

06. Code generation:
  06.01 Run-time environments.
  06.02 Intermediate code generation.
  06.03 Compilation of arithmetic expressions.
  06.04 Compilation of boolean expressions.
  06.05 Compilation of statements and control structures.

07. Operational semantics:
  07.01 Natural operational semantics for a simple imperative language (While).
  07.02 Operational semantics for While with procedure (static and dynamic scope).

08. Denotational semantics:
  08.01 Denotational semantics for While.
  08.02 Denotational semantics for While with procedures (call-by-value and call-by-reference).

09. Functional programming in Haskell:
  09.01 Introduction to Haskell: expressions, values, primitive data types.
  09.02 Functions, recursion, and polymorphism.
  09.03 Pairs, tuples, and lists.
  09.04 Higher-order functions.
  09.05 Datatypes.
  09.06 Modules.
  09.07 Monads and input/output.

10. Laboratory activity:
  10.01 Practice on expressions, values, primitive data types.
  10.02 Practice on functions and recursion.
  10.03 Practice on pairs, tuples, and lists.
  10.04 Practice on higher-order functions.
  10.05 Practice on datatypes.
  10.06 Practice on input/output.

Eventuali Propedeuticità

Logica Matematica, Programmazione degli Elaboratori, Architettura degli Elaboratori, Algoritmi e Strutture Dati.

Modalità Didattiche, Obblighi, Testi di Studio e Modalità di Accertamento

Modalità didattiche

Lezioni teoriche ed esercitazioni di laboratorio, sia in presenza che a distanza.

English version: Theory lectures and laboratory exercises, both face-to face and on-line.

Obblighi

Nessuno.

Testi di studio

Hopcroft, Motwani, Ullman, "Automi, Linguaggi e Calcolabilità", Addison-Wesley, 2009

Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, 2007

Aho, Lam, Sethi, Ullman, "Compilers: Principles, Techniques, and Tools", Addison-Wesley, 2007

Nielson, Nielson, "Semantics with Applications: An Appetizer", Springer, 2007

Thompson, "The Craft of Functional Programming", Addison-Wesley, 1999.

Hutton, "Programming in Haskell", Cambridge University Press, 2007.

Modalità di
accertamento

Prova scritta, prova al terminale e prova orale.

English version: Written exam, lab exam, and oral exam.

Note

L'insegnamento è erogato sia in presenza che a distanza nel Corso di Laurea in Informatica Applicata.

English version: The course is offered both face-to-face and on-line within the Laurea Degree Program in Applied Computer Science.

« torna indietro Ultimo aggiornamento: 22/12/11


Condividi


Questo contenuto ha risposto alla tua domanda?


Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

Il tuo 5x1000 per sostenere le attività di ricerca

L'Università di Urbino destina tutte le risorse che deriveranno da questa iniziativa alla ricerca scientifica ed al sostegno di giovani ricercatori.

numero verde

800 46 24 46

Richiesta informazioni

informazioni@uniurb.it

Posta elettronica certificata

amministrazione@uniurb.legalmail.it

Social

Performance della pagina

Università degli Studi di Urbino Carlo Bo
Via Aurelio Saffi, 2 – 61029 Urbino PU – IT
Partita IVA 00448830414 – Codice Fiscale 82002850418
2019 © Tutti i diritti sono riservati

Top