Link to the Team

Link

Slides of the Course

A brief Introduction to the course

Regular Grammars, Deterministic Automata, Non Deterministic Automata

Lexical Analysis

Introduction to Parsing, Precedence and Ambiguity of Grammars (Corrected Version with Exercise)

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

Bottom-up parsing

Action and GOTO Table Construction (revised version 22 Nov 11:15)

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 (Revised version 2 Dic)

Fixpoint Theory

Data-Flow Analyses: Available Definitions and Reaching Expressions

Static Analysis and Abstract Interpretation

Abstract Interpretation

Local Register Allocation

Global Register Allocation

Program of the course

Introduction to the Course

• Overview and objectives of the course.

Formal Languages and Automata Theory

• Regular Grammars.
• Deterministic and Non-Deterministic Automata.
• Automata with Epsilon Transitions.
• Regular Expressions and their Equivalences.
• Finite Automata and Language Properties
• DFA Minimization
• Pumping Lemma for Regular Languages

Context-Free Languages and Parsing

• Pushdown Automata
• Chomsky's Hierarchy

Lexical Analysis

• Techniques and tools for lexical analysis

Parsing Techniques

• Introduction to Parsing
• Precedence and Ambiguity in Grammars
• Predictive Parsing
• LL(k) Grammars
• Computation of First() and Follow() Sets
• Bottom-Up Parsing
• Construction of LR Tables

Attribute Grammars and Translation

• Attribute Grammars
• Ad-hoc Directed Translation
• Procedure Abstraction

Code Generation

• Introduction to Code Generation
• Code Shape: Expressions, Case Commands, Arrays, Booleans, and Control Flow

Optimization and Dataflow Analysis

• Optimization Techniques
• Dataflow Analysis: Live Variables
• Reaching Definitions
• Available Expressions

Abstract Interpretation

• Introduction to Abstract Interpretation
• Theory of Abstract Interpretation v

  Register Allocation

• Local Register Allocation
• Global 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.