Slides of the Course

Introduzione

Regular Grammars, Deterministic Automata, Non Deterministic Automata, Automata with Epsilon Transitions and Equivalences. Part of the material of these and next lesson slides are taken from the course of Languages of Prof. Isabella Mastroeni, Universita' di Verona (Thanks! ;) ).

Regular Expressions, Pumping Lemma, Minimization of a DFA, Context Free Languages, Push-Down Automata.

Lexical Analysis

Introduction to Parsing, Precedence and Ambiguity of Grammars

Predictive Parsing, LL(k) Grammars, Cpmputation of the set Fist() and Follow()

Bottom-up parsing

Action and GOTO Table Construction

Context Sensitive Analysis Attrinute Grammar

Context Sensitive Analysis Ad hoc Syntax Directed Translation

Intermediate Representations

The Procedure Abstraction I and II

Introduction to Code generation and Code shape: Expression and case startments

Code Shape: array, boolean and Control Flow

Optimization: value numbering and loop unrolling

Data-Flow Analyses: live Variables. Part of the material of these and next lesson slides are taken from the course of Prof. Francesco Ranzato, Universita' di Padova, (Thanks! ;) ).

Some Fixpoint theory concepts.

The computation of Live variable data-flow analysis.

Data-flow analyses: Reaching Definitions and Available Expressions.

Static Analyses: Control Flow and type Annotated type systems.

Static Analyses: Abstract Interpretation.Thanks to David Smiths, Francesco Ranzato, Roberto Bagnara, Patrik Cousot.

Local Register Allocation

Global Register Allocation

Presentations

Shape Analysis by Valeria Montagna

L'uso dei puntatori è un ostacolo per la comprensione, il debugging e l'ottimizzazione di un programma. La Shape Analysis permette di analizzare staticamente un programma, in modo da estrapolare informazioni sulle strutture dati allocabili sullo heap che il programma manipola. I risultati di questa analisi permettono di comprendere e di verificare proprietà del programma. In questo seminario ci focalizzeremo sulle informazioni ottenibili dall'uso delle espressioni a puntatore, determinanti per il debug, l'impiego del garbage collector e la parallelizzazione del codice.

Instruction Scheduling by Pasquale Pulieri

Le macchine moderne permettono di eseguire più operazioni indipendenti in parallelo, inoltre alcune istruzioni, caratterizzate da una latenza più lunga, possono impattare pesantemente sul tempo di esecuzione del codice compilato. Introdurrò nella mia presentazione l'Istruction Scheduler, che ha il compito di riordinare le istruzioni, cercando di minimizzare il tempo di esecuzione del codice, mantenendo il suo significato originale. In particolare, mi focalizzerò sul paradigma dominante per risolvere questo problema e alcune sue estensioni.

Non-Strict Semantics with Abstract Machines by Andrea Laretto

Rispetto ai linguaggi di programmazione standard, il concetto di linguaggio non-strict costituisce un'interessante variazione in cui la valutazione delle espressioni viene ritardata ed eseguita solo quando necessaria. In questo seminario introdurremo le nozioni alla base delle semantiche non-strict e lazy, partendo dai concetti di closure, thunk e trattando gli ordini di valutazione nel contesto formale del λ-calcolo. Dopo aver introdotto il concetto di macchina astratta, ci concentreremo in particolare su interpretazione e compilazione del λ-calcolo per macchine astratte con semantica call-by-name, presentando come esempio principale la Krivine machine e una sua variante call-by-need.

Program of the course