Compilers (CS362 2004S)

CS362 2004S At A Glance

This is an abbreviated course syllabus. Like everything else in this course, it is likely to change.

Weeks: 1, 2, 3, 4, 5, 6, 7, 8, break, 9, 10, 11, 12, 13, 14.

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
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
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
(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
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



This document is automatically generated from a number of other documents. Hence, I may not always remember to update the history.

Friday, 12 January 2001 [Samuel A. Rebelsky]

Tuesday, 7 Janaury 2003 [Samuel A. Rebelsky]

Tuesday, 14 January 2003 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:46:22 2004.
The source to the document was last modified on Wed May 5 11:45:49 2004.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,