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

Ad-hoc syntax directed Translation.

Intermediate Representations

The Procedure Abstraction

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

Code Shape: array, boolean and Control Flow

Optimization: value numbering and loop unrolling

Data-Flow Analyses: Live Variables

Fixpoint Theory

Data-Flow Analyses: Available Definitions and Reaching Expressions

Static Analyses

Abstract Interpretation with widenings (Corrected version with the right abstraction on the sign domain without 0.)

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.