|Below you can find the lecture slides, broken by week, in PDF format.|
|⦿ Please print double-sided.|
⦿ The documents with "-fullscreen" suffix contain one slide per page and include animation steps. Please do not print those.
Week #1: Introduction, Lexical Analysis
|The first hour will be an introduction to the subject and an overview of the course.|
We will learn about lexical analysis (regular expressions, NFA, DFA) in the second hour.
|01-intro.pdf 6.7 MB|
02-lexical.pdf 2 MB
01-intro-fullscreen.pdf 6.7 MB
02-lexical-fullscreen.pdf 2 MB
Week #2: Syntax Analysis - Top-Down Parsing
|Notice that since we covered two topics last week, lecture numbers do not coincide with week numbers.|
So this week's lecture is number 3. This is unfortunate.
This week we will cover the first of two families of parsers, namely top-down parsing: recursive descent and LL(k).
|03-parsing-topdown.pdf 2 MB|
03-parsing-topdown-fullscreen.pdf 2.4 MB
Week #4: Syntax Analysis - Bottom-Up Parsing / Semantic Analysis
|We will see other flavors of LR parsers, namely SLR and LR(1) (slides 60-97 of the presentation in last week's entry; notice that these slides have changed slightly from what was posted, please re-download if you have a local copy).|
We will start looking at the next compiler phase – semantic analysis (slides 1-29 of this week's).
|05-semantic.pdf 1.6 MB|
05-semantic-fullscreen.pdf 3.1 MB
Week #5: Semantic Analysis
|We will continue the lecture on semantic analysis that we started last week (slides 30 onward).|
We'll cover type declarations, coercions, l-values and r-values, subtyping, and attribute grammars (S-attributed and L-attributed).
Week #8: Static Analysis
|We want to generate optimal code, but for that we have to acquaint ourselves with some analysis techniques to understand properties of the code we generate.|
We will study a framework for dataflow analysis, including some mathematical background and formal algorithms.
Among other things, we will see how to perform the live variable analysis, shown in #7, across basic blocks.
|08-analysis.pdf 1.4 MB|
08-analysis-fullscreen.pdf 1.7 MB
Week #9: Optimizations
|To improve the performance of generated code, we will look at a few common automatic optimization techniques that compilers employ.|
We will start with simple techniques: constant propagation, static single-assignment form, and common subexpression elimination.
We will then go on to more advanced optimizations involving loops: code motion and strength reduction.
|09-optimizations.pdf 1.8 MB|
09-optimizations-fullscreen.pdf 2 MB
optimization example - quicksort.pdf 532 KB
Week #10: Activation Records / Memory Management
|So far we have only dealt with single routines.|
We will now show how to generate code for function calls and understand the structure of the runtime stack.
We will start the next topic too: dynamic memory management and garbage collection.
|10-activation.pdf 1.4 MB|
10-activation-fullscreen.pdf 1.6 MB
11-memory.pdf 2 MB
11-memory-fullscreen.pdf 2.1 MB
Week #12: Advanced Static Analysis – Abstract Interpretation
|We present a different view of static analysis through the work on Abstract Interpretation, a mathematical framework for proving program properties.|
In this lecture we will see how it can be used to analyze programs with numerical integer values using the domain of intervals.
|12-analysis-advanced.pdf 2.8 MB|
12-analysis-advanced-fullscreen.pdf 3.1 MB
Class Notes on Abstract Interpretation.pdf 179 KB
|⦿ The class notes can help explain things that were shown on the board but not included in the slides.|
⦿ If you are still confused about the denotational semantics of “while” statements using a fixed point, the explanation was taken from https://www.cs.colorado.edu/~bec/courses/csci5535/reading/densem.pdf , chapter 6. You are encouraged to read it.
Week #13: Advanced Static Analysis / Sum Up
|We will review the foundation of abstract interpretation, and apply static analysis to numerical domains: interval analysis, octagons, and polyhedra.|
Time permitting, we will learn about pointer analysis as well.
These week's slides are based on last week's with some more examples and definitions.
|12-analysis-advanced-rev.pdf 3.8 MB|
12-analysis-advanced-rev-fullscreen.pdf 4.2 MB
Lecture Notes on Static Analysis
|These are more lecture notes from earlier courses on the topic of static analysis, lattices, Galois connection, and abstract interpretation.|
|PA Lecture Notes - Lattices.pdf 330 KB|
PA Lecture Notes - Chaotic Iterations.pdf 1.2 MB
PA Lecture Notes - Galois Connection.pdf 1.3 MB