**Primary:**
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]

**Sets:**
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]

**ECA:**
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]

**Miscellaneous:**
[2001S]
[98F]
[SamR]
[Glimmer Labs]

*This is a highly approximate syllabus. Expect
topics, assignments, ordering, and almost everything else to change.*

- Week One: Introduction
- Week Two: Lexical Analysis with Finite Automata
- Week Three: Syntactic Analysis
- Week Four: Syntactic Analysis
- Week Five: Syntactic Analysis, Continued
- Week Six: From Parsing to Type Checking
- Week Seven: Type Checking
- Week Eight: Stack Frames
- Break
- Week Nine: Generating Code
- Week Ten: Generating Code, Continued
- Week Eleven: Putting it Together
- Week Twelve: Assembly Language Programming
- Week Thirteen: Code Improvement
- Week Fourteen: Wrapup

Class 01
(Friday, August 30, 2002)
**Getting Started**

**Assignments**

- Fill out the introductory survey.
- Read Chaper 1 of ASU.

- Background
- What is a compiler?
- Why study compilers?
- How to study compilers

- Administrative Issues

Class 02
(Monday, September 2, 2002)
**Compilation Steps**

**Assignments**

- Write a few small Pascal programs that we can use for testing.
- Fill out the introductory survey.
- Scan chapter 2 of ASU.
- Read chapter 3 of ASU.

- The steps of compilation
- Sample programs
- Lexical analysis
- Syntactic analysis
- Generating intermediate representation trees
- Semantic analysis
- Generating assembly code
- Optimization

Class 03
(Wednesday, September 4, 2002)
**Introduction to Lexical Analysis and Regular Expressions**

**Due**

- Sample Pascal programs.
- Sections 3.1-3.4 of ASU.

- What is a language?
- The process of lexical analysis
- Hand-coding a lexical analyzer
- Lexical analyzer generators
- Regular expressions

Class 04
(Friday, September 6, 2002)
**Regular Expressions, Continued**

- Simplifying Regular Expressions
- Common Shorthands
- Some Sample Regular Expressions
- Limitations
- Using Regular Expressions for Describing Tokens

Class 05
(Monday, September 9, 2002)
**Finite Automata**

**Due**

- Regular expression for
strings that are not 'if'

(orstrings that are not 'while'

) (orstrings that are neither 'if' nor 'while'

).

- Finite automata
- Deterministic Finite Automata
- Examples
- Nondeterministic Finite Automata
- Looking ahead

Class 06
(Wednesday, September 11, 2002)
**From Specification to Optimal DFA**

**Assignments**

- Do Homework 1 (Due Wednesday, September 17, 2002)

- From regular expressions to NFAs
- An example
- From NFAs to DFAs
- Example continued

Class 07
(Friday, September 13, 2002)
**From Specification to Optimal DFA, Continued**

- From NFA to DFA
- From DFA to optimal DFA
- Reminder: Lexical analysis using automata

Class 08
(Monday, September 16, 2002)
**Introduction to Grammars and Parsing**

**Assignments**

- Project Phase 1: Lexical Analyzer

- Limits of regular expressions
- BNF Grammars
- Form
- Some examples

- Context-Free Grammars

Class 09
(Wednesday, September 17, 2002)
**Context-Free and Context-Sensistive Grammars**

**Due**

- Context-Free Grammars
- Parse Trees
- Context-Sensitive Grammars

Class 10
(Friday, September 20, 2002)
**Ambiguous Grammars**

- Ambiguity
- A Conditional Grammar
- Resolving Ambiguity
- An Expression Grammar

Class 11
(Monday, September 23, 2002)
**Parsing Expressions**

- A basic expression grammar
- Ambiguity in that grammar
- Adding precedence
- Adding associativity

Class 12
(Wednesday, September 25, 2002)
**Predictive Parsing**

- Introduction to parsing
- Basics of predictive parsing
- An example
- Language membership
- Deriving the parse tree

- Some problems with the technique

Class 13
(Friday, September 27, 2002)
**Predictive Parsing, Continued**

**Due**

**Assignments**

- Helpful tables: First, Follow, and Nullable
- Building the
`First`

table. - Building the
`Nullable`

table. - Building the
`Follow`

table.

Class 14
(Monday, September 30, 2002)
**Even More Predictive Parsing**

- Building the tables and functions
- The
`First`

table and`first`

function - The
`Nullable`

table and`nullable`

function - The
`Follow`

table

- The
- Using the tables

Class 15
(Wednesday, October 2, 2002)
**Predictive Parsing, Concluded**

- Using an explicit stack in predictive parsing
- An extended expression example
- Problems with predictive parsing, revisited

Class 16
(Friday, October 4, 2002)
**Shift-Reduce Parsing**

**Due**

- Introduction to shift-reduce parsing
- Sample shift-reduce parsers
- A non-predictive language
- A simple expression

- LR(0) parsers: Basic shift-reduce parsers

Class 17
(Monday, October 7, 2002)
**Shift-Reduce Parsing, Continued**

**Assignments**

- Building LR(0) automata
- Example

Class 18
(Wednesday, October 9, 2002)
**Shift-Reduce Parsing, Concluded**

**Assignments**

- Some potential problems
- Other tehcniques for computing shift-reduce automata

Class 19
(Friday, October 11, 2002)
**Semantic Actions**

- Adding attributes to parse trees
- Computing the values of attributes
- Examples:
- Evaluating expressions
- Typing expressions
- Sequences of assignments

Class 20
(Monday, October 14, 2002)
**Introduction to Type Checking**

- The problem of type checking
- How it's used
- Two issues: determining types and using types

- Examples from Pascal

Class 21
(Wednesday, October 16, 2002)
**Type Equivalence**

- Summary of current type knowledge
- Other types
- Type coercion

- Type equivalence

Class 22
(Friday, October 18, 2002)
**Type Checking, Concluded**

- C's coercion rules
- Type Equivalence, Continued
- Records
- Two common forms
- Arrays
- Constants

- More Fun with C

Class 23
(Monday, October 28, 2002)
**Coding Style**

- The problems with
The Hammer Strategy

- Comments
- General strategies
- Javadoc

- Code formatting
- Coding strategies

Class 24
(Wednesday, October 30, 2002)
**Stack Frames**

- About the back end
- Where do variables and values go?
- Stacks and stack frames
- Function and procedure calls
- Non-local variables

Break runs from 5:00 p.m. on Friday, March 17, 1998 to 8:00 a.m. on Monday, April 3.

Class 25
(Friday, November 1, 2002)
**More Stack Frames**

Class 26
(Monday, November 4, 2002)
**Symbol Tables**

- Background: Associating attributes with symbols
- Sample attributes
- The implementation of symbol tables

Class 27
(Wednesday, November 6, 2002)
**Symbol Tables, Continued**

- Notes on translation
- Symbol tables, revisited

Class 28
(Friday, November 8, 2002)
**Translating Declarations and Expressions**

- Translating ...
- Assignments
- Basic Operations

Class 29
(Monday, November 11, 2002)
**Translating Conditionals**

- Basic issues
- Strict conditionals
- Short-circuit conditionals
- Case statements

Class 30
(Wednesday, November 13, 2002)
**Translating Loops**

- While Loops
- Repeat-Until Loops
- For Loops

Class 31
(Friday, November 15, 2002)
**Translating Procedure Calls**

Class 32
(Monday, November 18, 2002)
**Liveness Analysis**

- Context: Why consider liveness
- The basics of liveness analysis
- Some theoretical issues
- Some practical issues
- Some examples

Class 33
(Wednesday, November 20, 2002)
**Register Allocation**

- The Problem of Register Allocation
- A Basic Algorithm
- Detour: NP Completeness
- Graph Coloring
- Coalescing
- The Algorithm, Revisited

Class 34
(Friday, November 22, 2002)
**Class Canceleld**

Class 35
(Monday, November 25, 2002)
**Steps in Compilation, Revisited**

- A sample program
- Lexing and parsing (elided)
- Translation to intermediate code

Class 36
(Wednesday, November 27, 2002)
**Steps in Compilation, Continued**

- What we've done so far.
- Procedure initialization and cleanup
- Factorial
- Helper

Class 37
(Monday, December 2, 2002)
**General Improvement Techniques**

- Why build improvable code?
- Why improve code?
- Basic analyses:
- Basic blocks
- Variable lifetimes and usage

- Generating better assembly
- Some common optimizations

Class 38
(Wednesday, December 4, 2002)
**Additional Improvement Techniques**

- Improvement, reviewed
- Loop optimization
- An example

Class 39
(Friday, December 6, 2002)
**Student Presentations (1)**

Not yet available

*Attendance is particularly important this week.*

Class 40
(Monday, December 9, 2002)
**Student Presentations (2)**

Not yet available

Class 41
(Wednesday, December 11, 2002)
**Student Presentations (3)**

Not yet available

Class 42
(Friday, December 13, 2002)
**Evaluation**

*The history will not include small changes to the summaries of
individual classes or perhaps even on the arrangement of courses.
You can find more information on such changes
in the individual outlines.*

Thursday, 29 August 2002

- First generic version, based on summaries of years past.

**Primary:**
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]

**Sets:**
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]

**ECA:**
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]

**Miscellaneous:**
[2001S]
[98F]
[SamR]
[Glimmer Labs]

**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 Fri Nov 15 10:30:28 2002.

The source to the document was last modified on Thu Aug 29 15:27:30 2002.

This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Handouts/syllabus.html`

.

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

Glimmer Labs: The Grinnell Laboratory for Interactive Multimedia Experimentation & Researchglimmer@grinnell.edu