CO 424 Syllabus of Record
I. Catalog
Description
CO 424 Compiler Construction 3c-0l-3sh
Prerequisites: CO 300 and CO 310
Relates the
formal concepts of automata and language theory to
the practicality of constructing a high-level language
translator. The
structures and techniques used in lexical
analysis, parsing, syntax directed translation, intermediate
and object code generation, and optimization are emphasized.
II. Course
Objectives
Upon
successful completion of this course, the student will be
able to
A. Describe in detail the phases of
compilation.
B. Use finite automata to write a lexical
analyzer for a
given language.
C. Write a grammar for a programming language.
D. Describe shift-reduce parsing and various
ways to
manipulate grammars.
E. Construct a syntax directed translator based
on an SLR(1)
parse table.
F. Write a program to generate object code for
a specified
machine.
G. Describe various compiler optimization
techniques.
III. Detailed Course Outline
A. Overview of the Compilation Process (3 hrs)
1. Phases and passes
2. Lexical analysis
3. Syntax analysis
4. Semantic analysis
5. Intermediate code generation
6. Code generation
7. Optimization
8. Compiler development tools
B. Introduction to Grammars and Their Uses (2 hrs)
1. Context-free grammars
2. Describing programming language features
3. Handling attributes (meaning)
C. Lexical Analysis (3 hrs)
1. Recognizing lexemes
2. Representing tokens
3. Scanning techniques
4. Regular expressions
5. Available tools
D. Symbol and Literal Tables (1 hr)
1. Organization and access
2. Entry fields
E. Finite
Automata (2
hrs)
1.
Nondeterministic FA
2. Conversion to deterministic FA
3. Minimizing states
F. Error Handling
(1 hr)
1. Reporting the error
2. Recovery techniques
G. Context-free Grammars (3 hrs)
1. Productions, alphabets and sentential forms
2. Derivations and reductions
3. Ambiguity
4. Representing precedence
5. Influence of semantics
6. Influence of intermediate code form
7. Methods of modifying grammars
H. Parsing
(3 hrs)
1. Top-down and bottom-up
2. Shift-reduce approach
3. LR parser
4. Parse table use
5. Driver routine
6.
Parse table construction
7. FIRST and FOLLOW functions
8. Handling conflicts in the grammar
9. Parse table generators
I. Syntax Directed Translation (4 hrs)
1. Grammar requirements
2. Token-terminal association
3. Synthesized and inherited attributes
4. Parsing stack manipulation
5. Type checking and coercion
6. Semantic checking
7. Overloading operators
J. Intermediate Code Generation (4 hrs)
1. Three-address code
2. Quadruple operations
3. Condition handling
4. Using temporaries
5. Handling declaration statements
6. Backpatching
forward references
7. Array references
K. Storage Allocation (1
hr)
1. Program code
2. Identifiers (symbols)
3. Literals
4. Temporaries
L. Code Generation (4
hrs)
1. Object code form
2. Register use
3. Addressing modes
4. Macro approach to generation
5. Details of target machine
6. Inefficiencies in the macro approach
7. Backpatching
forward references
M. Compilation of Procedures (2 hrs)
1. Symbol tables for block structure
2. Call and argument quadruples
3. Storage allocation for arguments
4. Activation records and stacks
5. Argument access
N. Optimization
(6 hrs)
1. Placement of optimizing routines
2. Peephole techniques
3. Basic block analysis
4. Flow graph representation
5.
6. Induction variables
7. Next use and liveness
of variables
8. Code transformations
9. DAG representation of basic blocks
10. Detecting common subexpressions
11. Programming situations that cause
optimization
problems
IV. Evaluation
Methods
50% Examinations. Two mid-term exams and the final exam each
count equally toward the 50%. Examinations consist of
short-answer, analysis, and what-if questions.
50% Project. The project is to write a compiler for a
simple
programming language; it is in four parts or stages -
lexical analyzer, grammar writing, syntax-directed
translator, and object code generator. The project is
assigned groups of two or three students with group
membership changing after stages 1 and 3.