[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
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 Translation The stages of translation.. Designing the intermediate structures.. Handcoded tokenizing.. Handcoded parsing.. Handcoded 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. Handcoding 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 LexicalAnalyzer 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 ShiftReduce Parsing (1) Introduction to shiftreduce parsing. A shiftreduce parser for a nonpredictive language . A shiftreduce parser for a simple expression language. LR(0) parsers: Basic shiftreduce parsers. 
Week 8: Syntactic Analysis (3)  
(21) Monday, 8 March 2004 ShiftReduce Parsing (2) Building an LR(0) automaton for expressions. Running the automaton. Building LR(0) automata. 
(22) Wednesday, 10 March 2004 ShiftReduce Parsing (3) The expression automaton, concluded.. Some potential problems.. Other techniques for computing shiftreduce 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. Compiletime vs. Runtime 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. Nonlocal 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.. Shortcircuit conditionals.. Case statements.. 
Thursday, 22 April 2004 Lab: Exploring Translation 
(35) Friday, 23 April 2004 Translating Conditionals, Continued Basic issues.. Strict conditionals.. Shortcircuit conditionals.. Case statements.. Assignments: Begin Phase 4 of the project. 
Week 13: Generating Code, Continued  
(36) Monday, 26 April 2004 Translating Loops While Loops. RepeatUntil 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 
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]
Course at a Glanceform.
Tuesday, 7 Janaury 2003 [Samuel A. Rebelsky]
Tuesday, 14 January 2003 [Samuel A. Rebelsky]
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
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 http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Handouts/glance.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu