This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Introduction
|
| Martin Luther King Day
|
(01) Wednesday, 21 January 2004
Getting Started
What is a compiler.
Why study compilers.
How to study compilers.
Administrative Issues.
|
Thursday, 22 January 2004
Lab: Exploring Compilation |
(02) Friday, 23 January 2004
A Quick Introduction to Pascal (1)
A short history of Pascal.
Parts of the language to consider.
Variables and Types.
Basic Operations.
Conditionals.
Assignments:
Homework 1: A Simple Pascal Program.
|
| Week 2: A Sample Compiler
|
(03) Monday, 26 January 2004
A Quick Introduction to Pascal (1)
A short history of Pascal.
Parts of the language to consider.
Variables and Types.
Basic Operations.
Conditionals.
|
(04) Wednesday, 28 January 2004
The Source and Target Languages
Pascal, continued..
This week's focus..
The input language: PAL..
The output language: STUPID..
|
Thursday, 29 January 2004
Lab: Explorations with PAL and STUPID |
(05) Friday, 30 January 2004
Translation
The stages of translation..
Designing the intermediate structures..
Hand-coded tokenizing..
Hand-coded parsing..
Hand-coded translation..
Assignments:
Read chapter 3 of ASU.
Begin Phase 1 of the Project.
|
| Week 3: Representing Tokens
|
(06) Monday, 2 February 2004
Introduction to Lexical Analysis and Regular Expressions
What is a language?.
The process of lexical analysis.
Hand-coding a lexical analyzer.
Lexical analyzer generators.
Regular expressions.
|
(07) Wednesday, 4 February 2004
Regular Expressions, Continued
Simplifying Regular Expressions.
Common Shorthands.
Some Sample Regular Expressions.
Limitations.
Using Regular Expressions for Describing Tokens.
|
Thursday, 5 February 2004
Lab: Regular Expressions |
(08) Friday, 6 February 2004
Finite Automata
Finite automata.
Deterministic Finite Automata.
Examples.
Nondeterministic Finite Automata.
Looking ahead.
|
| Week 4: Lexical Analysis
|
(09) Monday, 9 February 2004
From Specification to Optimal DFA (1)
Review.
From regular expressions to NFAs.
An example.
Due:
Project, Phase 1: Lexer.
Assignments:
Homework 1: Lexical Analysis.
|
(10) Wednesday, 11 February 2004
From Specification to Optimal DFA (2)
From NFA to DFA.
From DFA to optimal DFA.
Lexical analysis using finite automata.
Limitations of regular expressions and finite automata.
|
Thursday, 12 February 2004
Lab: Using Lexical-Analyzer Generators |
(11) Friday, 13 February 2004
Cancelled
|
| Week 5: Representing Structure
|
(12) Monday, 16 February 2004
Introduction to Grammars and Parsing
Limits of regular expressions.
BNF Grammars: Form.
Examples.
Due:
Homework 1.
Assignments:
Project, Phase 2.
|
(13) Wednesday, 18 February 2004
Ambiguous Grammars
Ambiguity..
A Conditional Grammar..
Resolving Ambiguity..
An Expression Grammar..
|
Thursday, 19 February 2004
Lab: Tokenizing with java.io.StreamTokenizer |
(14) Friday, 20 February 2004
Parsing Expressions
A basic expression grammar..
Ambiguity in that grammar..
Adding precedence..
Adding associativity..
|
| Week 6: Syntactic Analysis (1)
|
(15) Monday, 23 February 2004
Predictive Parsing (1)
Introduction to parsing.
Basics of predictive parsing.
An example: Language membership.
Some problems with the technique.
|
(16) Wednesday, 25 February 2004
Predictive Parsing (2)
Helpful tables: First, Follow, and Nullable.
Building the First table..
Building the Nullable table..
Building the Follow table..
|
Thursday, 26 February 2004
Lab: A Sample Parser |
(17) Friday, 27 February 2004
Predictive Parsing (3)
About the tables.
Building the tables and functions.
Using the tables.
|
| Week 7: Syntactic Analysis (2)
|
(18) Monday, 1 March 2004
Predictive Parsing (4)
The Follow table..
The Parse table..
Problems with predictive parsing: Left factoring; Eliminating left recursion..
Problems with predictive parsing, revisited..
|
(19) Wednesday, 3 March 2004
A Sample Parser
Building the parse functions..
An example..
Explaining expressions..
|
Thursday, 4 March 2004
Lab: Parsing Expressions |
(20) Friday, 5 March 2004
Shift-Reduce Parsing (1)
Introduction to shift-reduce parsing.
A shift-reduce parser for a non-predictive language .
A shift-reduce parser for a simple expression language.
LR(0) parsers: Basic shift-reduce parsers.
|
| Week 8: Syntactic Analysis (3)
|
(21) Monday, 8 March 2004
Shift-Reduce Parsing (2)
Building an LR(0) automaton for expressions.
Running the automaton.
Building LR(0) automata.
|
(22) Wednesday, 10 March 2004
Shift-Reduce Parsing (3)
The expression automaton, concluded..
Some potential problems..
Other techniques for computing shift-reduce automata..
|
Thursday, 11 March 2004
Lab: Cancelled |
(23) Friday, 12 March 2004
Class Cancelled
|
| Spring Break
|
| Week 9: Type Checking
|
(24) Monday, 29 March 2004
Semantic Actions
Adding attributes to parse trees.
Example: Evaluating expressions.
Computing the values of attributes.
Example: Typing expressions.
Example: Sequences of assignments.
|
(25) Wednesday, 31 March 2004
Type Checking (1): Introduction
Introduction to Type Checking.
Compile-time vs. Run-time Type Checking.
Common Types.
Assignments:
Homework 2: Lexical Analysis.
|
Thursday, 1 April 2004
Lab: Type Checking a Simple Language |
(26) Friday, 2 April 2004
Type Checking (2): Type Equivalence
Summary of current type knowledge.
Types of types.
Type equivalence.
Assignments:
Project, Phase 3: The Type Checker.
|
| Week 10: Stack Frames
|
(27) Monday, 5 April 2004
Type Checking (3): Conclusion
C's coercion rules..
An example with records..
Type Equivalence, Continued..
|
(28) Wednesday, 7 April 2004
Stack Frames (1)
About the back end.
Where do variables and values go?.
Stacks and stack frames.
Function and procedure calls.
Non-local variables.
|
Thursday, 8 April 2004
Lab: Stack Frames |
(29) Friday, 9 April 2004
Stack Frames (2)
Quiz: Dealing with Scope..
Dealing with Scope, Revisited..
An Example..
|
| Week 11: Type Checking, Revisited
|
(30) Monday, 12 April 2004
A Sample Pascal Parser
Some problems in parsing Pascal..
Some solutions..
Notes on type checking..
|
(31) Wednesday, 14 April 2004
Detour: Type Checking (I)
|
Thursday, 15 April 2004
Lab: No Lab This Week |
(32) Friday, 16 April 2004
Detour: Type Checking (II)
|
| Week 12: Generating Code
|
(33) Monday, 19 April 2004
Translating Declarations and Expressions
Translating assignments.
Translating basic operations.
|
(34) Wednesday, 21 April 2004
Translating Conditionals
Basic issues..
Strict conditionals..
Short-circuit conditionals..
Case statements..
|
Thursday, 22 April 2004
Lab: Exploring Translation |
(35) Friday, 23 April 2004
Translating Conditionals, Continued
Basic issues..
Strict conditionals..
Short-circuit conditionals..
Case statements..
Assignments:
Begin Phase 4 of the project.
|
| Week 13: Generating Code, Continued
|
(36) Monday, 26 April 2004
Translating Loops
While Loops.
Repeat-Until Loops.
For Loops.
|
Class Moved for Funeral |
(37) Thursday, 29 April 2004
Translating Procedure Calls
Format of stack frames..
Allocating space for locals and parameters..
Division of responsibilities..
Function/procedure initialization..
Function/procedure cleanup..
Caller responsibilities..
|
(38) Friday, 30 April 2004
Miscellaneous
|
| Week 14: Miscellaneous
|
(39) Monday, 3 May 2004
Liveness Analysis
Context: Why consider liveness..
The basics of liveness analysis..
Some theoretical issues..
Some practical issues..
Some examples..
|
(40) Wednesday, 5 May 2004
Register Allocation
The Problem of Register Allocation.
A Basic Algorithm.
Detour: NP Completeness.
Graph Coloring.
Coalescing.
The Algorithm, Revisited.
|
(41) Thursday, 6 May 2004
Code Improvement (1)
Why build improvable code?.
Why improve code?.
Analyzing basic blocks..
Variable lifetimes and usage.
Generating better assembly.
Some common optimizations.
|
(42) Friday, 7 May 2004
Wrapup and Evaluation
|
;
Check with Bobby