CS445/545 Compiler Construction (Spring 2023)

Instructor: Christino Tamon
Class: TR 3:00-4:15 (SC342)
Office hours: TR 9:15-11:00, 2-3 (SC373)

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. The goal is to develop a compiler for a high-level programming language using standard compiler tools.

Grading:

• Project (Dragon, solo/duo): 40%
• Project (Free Will, group): 10%
• Tests (x2): 50%

The following texts are also highly recommended:

• B. Kernighan, D. Ritchie, "The C Programming Language", 2nd edition, Prentice-Hall, 1988.
• J. Levine, T. Mason, J. Brown, "lex & yacc", 2nd edition, O'Reilly, 1992.

Objective: to understand the fundamentals of compiler theory and its application in constructing a real working compiler.

Specific outcomes:

• Knowledge of standard UNIX tools for software design and compiler construction.
• Knowledge of 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 provide the required Clarkson official exempt form. 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.

All chapter references are for the Dragon book (1986 edition).

• Chapter 1: Introduction
  Translation phases: (front end) lexical analysis, syntax analysis, semantic analysis;
  (back end) intermediate code generation, code optimization, code generation.

• Chapter 2: Syntax-directed translation
  Recursive-Descent parsing (top down).
  Example: operator languages (calculator).

  Little Dragon project

  Appendix A: Compiler Dragon project [Dragon One]
  Source language: Pascal(-like); target language: IA32.
  Implementation language and tools: C/C++ and lex&yacc.

• Chapter 3: Lexical analysis
  Theory: Finite Automata (DFA and NFA), Regular Expressions.
  Practice: pattern matching, automata-based matching; lex (by Mike Lesk and Eric Schmidt).

  Thompson construction (RE to NFA), Subset construction (NFA to DFA), shortcut construction (RE to DFA),
  two-stack simulation of NFA, DFA minimization algorithm (half of Myhill-Nerode theorem),
  Knuth-Morris-Pratt algorithm, Aho-Corasick algorithm.

• Chapter 4: Syntax Analysis
  Theory: Push-Down Automata (PDA), Context-Free Grammars.
  More Theory: deterministic parsing methods => top-down LL(1); bottom-up SLR(1); LR(1) and LALR(1);
  Practice: yacc (Steven C. Johnson)

• Chapter 5 & 6: Semantic Analysis and Type Checking
  Theory: Syntax Trees (intermediate code), Attribute Grammars, Attribute evaluation; Recursive type systems.
  Practice: standard data structures.

• Chapter 7: Scoping Issues and Run-Time Environments
  Theory: Symbol (hash) Table. Activation records.
  Practice: hashpjw (by P.J. Weinberger). Assembly calling-sequences.

• Chapter 9: Code Generation
  Theory: gencode algorithm and its labeling scheme; register allocation (NP-complete). Basic blocks; flow graphs; static analysis.
  Practice: Assembly rules and conventions.

Schedule (tentative)

Project: DRAGON

• Arrange an in-person demo of your compiler during Finals week (15min).
• Send a self-contained compressed tar source of your compiler by email. Your compiler must run on polaris (Clarkson Linux server).
• Submit a hardcopy of your compiler documentation: design document, user manual, testing report, status report (limitations, caveats, or bugs), and a "dragon" haiku. Indicate clearly in your report an extra feature that is unique to your compiler.

(1.0) Lexical Analysis

1. Line numbering
2. Two styles of comments
3. (optional) Scientific notation

(1.5) Syntax Analysis: grammar adjustments

1. Unlimited nesting of subprograms
2. Array access on both sides of assignment
3. Allow for statements.
4. (optional) Another loop construct
5. (optional) Multidimensional arrays
6. (optional) Records and pointers

(2.0) Symbol Table

1. Memory-leak handler
2. (optional) Statistical analysis of hashpjw

(2.5) Syntax Tree (Intermediate Code Generation)

1. Visual print
2. Memory-leak handler

(3.0) Semantic Analysis & Type Checking

1. Check list
2. Error reporting
3. (optional) Error recovery

(4.0) Code Generation

1. Input/Output statements
2. Simple expressions (arithmetic and relational): gencode
3. Statements (assignment, conditional, loop)
4. Nonlocal names: base frame pointer (static scope parent)
5. Recursive routines (example: GCD program)
6. Complex expressions (register spilling)
7. (optional) Arrays (L-value, R-value, parameters, nonlocal)
8. (optional) Floating-point support

Extra Trails (under construction)

• Lambda or Objects.
• Code generator for IA64 or SPARC (RISC architecture).
• Code optimization.

• Lexical analysis:
  • A. Aho, M. Corasick, "Efficient string matching: an aid to bibliographic search," Communications of the ACM 18(6):333-340, 1975. [pdf]
  • The Knuth-Morris-Pratt algorithm: explanation by D. Eppstein.
• Syntax analysis:
  Top-down LL(1) parsing (Chapter 4: Dragon1, Sections 4.2-4.4, p165-195 (Dragon2: p197-228), Algorithms 4.1, 4.2, 4.3 & 4.4 and related material). [table + trace p188; FIRST & FOLLOW sets p189];
  Bottom-up SLR(1) and LR(1) parsing (Chapter 4: Dragon1), LALR(1) parsing.
  • A. Aho, S. Johnson, "LR Parsing," Computing Surveys 6(2):99-124, 1974. [pdf].
• Semantics:
  • D. Knuth, "Semantics of Context-Free Languages." [pdf].
  • R. Merkle, "Evaluators for Attribute Grammars." [pdf].
• Code generation:
  Chapter 9: Dragon1, Section 9.10, p557-565. [pseudocode p564, trace p565]; basic blocks and control flow graphs (next-use and live analysis).
  
  • Compiler Explorer (courtesy of Josh Gordon).
  • CSAPP3: web asides.
  • x86: wiki; guide.
• Other:
  • B. Kernighan, "Why Pascal is Not My Favorite Programming Language," 1981. [link].

• Code a "bean counter" from scratch (no tools, just KnR).
• Grow trees.
• Summon the tree-walker in NineTen.
• Jump into IA100000 (five zeros for now).
• Read Wirth's grammar.
• (F)lex the Bison (formerly known as Yacc).
• stack(hash(list)) with one of AWK.
• The Meaning of ...
• Secret flag: -fno-asynchronous-unwind-tables -m32

• Best RE-to-DFA transformation?
• DetCFL is weaker than CFL?
• Declare-before-Use is not context-free.
• AMBIGUITY is undecidable?
• Coexisting left-plus and right-minus?
• Quantum: projects.