Link to the Team

Link

Slides of the Course

A brief Introduction to the course

Regular Grammars, Deterministic Automata, Non Deterministic Automata

Automata with epsilon transitions, Regular Expressions.

DFA Minimization, Pumping Lemma.

Context free Languages, Pushdown Automata, Chomsky's Hierarchy.

Lexical Analysis

Introduction to Parsing, Precedence and Ambiguity of Grammars

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

Bottom-up parsing

Action and GOTO Table Construction

Context Sensitive Analysis Attribute Grammar

The Procedure Abstraction

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

Code Shape: array, boolean and Control Flow

Optimization: loop unrolling

Data-Flow Analyses: Live Variables

Fixpoint Theory

Data-Flow Analyses: Available Definitions and Reaching Expressions

Static Analysis and Abstract Interpretation

A gentle introduction to abstract interpretation

Abstract interpretation: the formal definitions

Local Register Allocation

Global Register Allocation

Program of the course

• Grammars, automata, regular expressions, equivalences, regular languages, context free languages, Chomsky hierarchy
• Lexical analysis
• Parser
• Contextual analysis
• Intermediate representation
• Code shape
• Optimization
• Dataflow analysis
• More static analyses: Control flow and Abstract interpretation
• Register allocation

The Book

• Engineering a Compiler, Second Edition
  Keith D. Cooper and Linda Torczon Rice University, Houston, Texas
  Published by Morgan Kaufman
   

Suggested material for exploring specific topics

• Introduction to Automata Theory, Languages, And Computation.
  Hopcroft, Motwani, Ullman

• Fondamenti dell'Informatica. Linguaggi formali, calcolabilita' e complessita'.
  Dovier, Giacobazzi
  Bollati Boringhieri

• Principles of Program Analysis.
  Nielson,Nielson, Hankin
  Springer

• Static Inference of Numeric Invariants by Abstract Interpretation a tutorial by Antoine Mine on Abstract interpretation.