Slides of the Course

Introduzione

Regular Grammars, Deterministic Automata, Non Deterministic Automata

Automata with epsilon transitionas, Regular Expressions, Pumping Lemma, Minimization of a DFA.

DFA Minimization, 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 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, Available Expressions and Reaching Definitions.

Static Analyses: Abstract Interpretation.

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.