CS445/CS545 Compiler Construction
Lectures: TR 9:30-10:45am, Science Center 342
hours: TR 10:45-12:00, 2:15-3:30, Science Center
Pre-requisites: CS344, CS345.
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 (tentative) Project and Assignments 60%; Exams 40%
- 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:
- Proficient in C programming.
- Knowledge of standard UNIX tools for software design and compiler
- Knowledge of assembly language and its run-time environment relevant for
- Ability to craft 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
- Part 1 :
Implement the symbol table module.
- Part 2:
Implement the lex scanner and yacc parser
for the specified programming language. Mix the symbol table in with the yacc
parser and test scoping rules.
- Part 3:
Implement the syntax tree module for most grammar
rules: start with expressions. As for other modules, do scaffold testing of
the tree module before incorporating it into the yacc parser. Beware of memory
leaks; use GNU profiler "gprof" to help look for hotspots.
- Part 4:
Implement the semantic analyzer; use ideas
related to attributed grammars. Build trees for rules on statements, variable
- Part 5:
Implement the code generator.
Use an algorithm
that converts parse trees for expressions to assembly sequences. Then, extend
this to statements.
- Arrange an online demo of your compiler (during the last 2 weeks of the
- Send a compressed tar source by email.
- Submit a hardcopy of your source files and a documentation.
documentation should include a user manual, a status report (caveats and
bugs), testing report, and a brief design document.