CS445/CS545 Compiler Construction

SPRING 2009

• Required: Alfred V. Aho, Monica Lam, Ravi Sethi and Jeffrey D. Ullman. "Compilers: Principles, Techniques, and Tools," 2nd edition, Addison-Wesley (2006).
• 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)

1. Language translation. Compilation. Overview.
2. Lexical Analysis. Regular expressions.
3. Syntax Analysis. Theory of Parsing: top-down LL(1); bottom-up SLR(1), LR(1) (and LALR(1)).
4. Semantic Analysis. Parse trees. Syntax-directed translation. Type checking.
5. Code generation. Runtime environments.

• Proficiency in C.
• Knowledge of standard UNIX tools for software design and compiler construction.
• Knowledge of assembly language and its run-time environment relevant for compilers.
• Ability to build a small and functional compiler in a UNIX programming environment.

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 matters.

• Introduction: read Chapter 1 [Dragon]
  Phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, code generation.
• Course project: Appendix A [Dragon, 1st ed]
  Source language: Pascal; target language: IA32. Implementation language and tools: C and lex & yacc.
• Syntax-directed translation: read Chapter 2 [Dragon]
  Recursive-descent parsing (top down). LL(1) grammars.
• Parsing techniques: read Chapter 4 [Dragon]
  Top-down (stack-based) LL(1); bottom-up SLR(1); LR(1) and LALR(1) (yacc)
• Symbol Table: hashing (see Chapter 7 [Dragon]) with P.J. Weinberger's hashpjw function.
• Semantic analysis: read Chapter 5 and 6 [Dragon]
  building syntax trees; simple type systems.
• Code generation: Chapter 9 [Dragon].
  Run-time environments Chapter 7 [Dragon]; access to nonlocal names. The gencode algorithm (9.10) and its labeling algorithm (c.f.: Ershov numbers).

DRAGON PROJECT

• Arrange an online demo of your compiler (30min).
• Send a self-contained compressed tar source of your compiler by email.
• Submit a hardcopy of your compiler documentation: design document, user manual, testing report, status report (limitations, caveats, or bugs), and Dragon haiku. Indicate clearly in your report an extra feature that is unique to your compiler (choose one of the bonus options in the check-list below).

Note: Bonus (optional for all), Team (required for groups of more than one), Grad (required for CS545)

(1.0) Lexical Analysis

1. line numbering
2. comments [style: (* .. *)]
3. Bonus: allow two styles of comments [(* .. *) and {..}]
4. Bonus: scientific notation for floating point values

(1.5) Syntax Analysis: grammar additions

1. nested subprograms
2. array access as both L-value and R-value
3. Team/Grad: FOR statement

(2.0) Symbol Table

1. Bonus: statistics of hashpjw
2. Bonus: memory leak handler

(2.5) Syntax Tree (Intermediate Code Generation)

1. visual print
2. Bonus: memory leak handler

(3.0) Semantic Analysis

1. Clear the check list
2. error reporting
3. Bonus: error recovery

(4.0) Code Generation

1. Input/Output
2. simple expressions (arithmetic and relational): gencode
3. statements (assignment, conditional, loop)
4. nonlocal names: base frame pointer (static scope parent)
5. recursive routines (GCD test)
6. Team/Grad: complex expressions (register spilling)
7. Grad: arrays (L-value, R-value, parameters, nonlocal)
8. Bonus: floating-point support