CS445/CS545 Compiler Construction
Lectures: Tue-Thu 9:30-10:45am, Science Center 342 (or 334 ITL
Office hours: SC373, Tue-Thu
Pre-requisites: CS344 Data Structures and
Algorithms, CS345 Automata Theory and Formal Languages
SYLLABUS: A study of compiler design. Overview of the compilation
process. Formal definition of syntax, lexical scanning, parsing including LL and
LR grammars, run-time structures, intermediate code generation, and storage
allocation. Students are expected to develop a compiler for a substantial subset
of a high-level language using compiler tools such as lex and yacc.
GRADING Project 50%; Exams 50%
- Required: Alfred V. Aho, Monica Lam, Ravi Sethi and Jeffrey D.
Ullman. "Compilers: Principles, Techniques, and Tools," 2nd edition,
- Brian W. Kernighan and Dennis M. Ritchie, "The C Programming Language,"
2nd edition, Prentice-Hall (1988) (on reserve)
- John Levine, Tony Mason, and Jason Brown, "lex & yacc," 2nd edition,
O'Reilly (1992) (on reserve)
- Language translation. Compilation. Overview.
- Lexical Analysis. Regular expressions.
- Syntax Analysis. Theory of Parsing: top-down LL(1); bottom-up SLR(1),
LR(1) (and LALR(1)).
- Semantic Analysis. Parse trees. Syntax-directed translation. Type
- Code generation. Runtime environments.
The objective of this course is to learn the
fundamentals of compiler theory and its application in constructing a real
working compiler. The specific outcomes are:
- Proficiency in C.
- Knowledge of standard UNIX tools for software design and compiler
- Knowledge of assembly language and its run-time environment relevant for
- Ability to build a small and functional compiler in a UNIX programming
Although attendance is not mandatory, students are responsible
for all course materials covered in lectures and any exams given during class
periods. Students that need to make up missing course work must follow the
official Clarkson policies regarding these matters. All students must submit
their own work; the exchange of ideas are encouraged but ultimately the
submitted work must be the student's own. Please refer to the Clarkson
University Regulations for more guidelines on academic integrity and related
- Introduction: read Chapter 1 [Dragon]
Phases: lexical analysis, syntax
analysis, semantic analysis, intermediate code generation, code optimization,
- Course project: Appendix A [Dragon, 1st ed]
Source language: Pascal;
target language: Intel assembly. Implementation language + tools: C + lex
- Syntax-directed translation: read Chapter 2 [Dragon]
parsing (top down). LL(1) grammars.
- Parsing techniques: read Chapter 4 [Dragon]
LL(1); bottom-up SLR(1); LR(1) and LALR(1) (yacc)
- Symbol Table: hashing (see Chapter 7 [Dragon])
- Semantic analysis: read Chapter 5 and 6 [Dragon]
building syntax trees;
- Code generation: Chapter 8 [Dragon].
Run-time environments Chapter 7