Statement of Course Outcomes

Course Number: CS 516

Course Name: Compiler Design

Course Coordinator: David Klappholz

Graduate or Undergraduate Equivalent: CS 494

 

Catalog Description: Lexical analysis; syntax analysis; symbol table construction; semantic analysis; syntax-directed translation; dataflow analysis; liveness analysis; and register allocation. The emphasis in this course is on the integration of the various parts of a compiler. Each student writes a complete compiler for a small, but substantial, language. Prerequisite: CS 510 or equivalent.

Course Outcomes

Each course outcome is followed in parentheses by the Program Outcome to which it relates.

CS 516 Compilers

 

Goals: Students who successfully complete this course will:

• be able to design and implement a program of significant size and complexity without being given complete details as to data structures and algorithms to be used
• understand how a compiler works

 

Objectives: Students who successfully complete this course will be able to:

 

1. [parse tree construction] construct a parse tree, or explain why no parse tree exists, given a BNF grammar and a string over the appropriate alphabet (cs-discrete-math)(is-discrete-math)(cys-discrete-math)

 

2. [lexical analyzer implementation] implement a lexical analyzer from a specification of a language’s lexical rules (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

3. [eliminate square and curly brackets] translate a BNF grammar that uses “[ ]” notation and “{ }” notation into an equivalent grammar with no such notation (cs-discrete-math)(is-discrete-math)(cys-discrete-math)

 

4. [compute FIRST set] compute the FIRST set for a BNF grammar (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

5. [compute follow set] compute the FOLLOW set for a BNF grammar (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

6. [determine FIRST intersect FIRST constraint satisfaction] determine if a BNF grammar satisfies the constraint on intersection of FIRST sets required for single-symbol-lookahead, top-down, lookahead parsing (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

7. [determine FIRST intersect FOLLOW constraint satisfaction] determine if a BNF grammar satisfies the constraint on intersection of FIRST and FOLLOW sets required for single-symbol-lookahead, top-down, lookahead parsing (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

8. [check for left recursion] determine if a BNF grammar satisfies the constraint on left recursion for single-symbol-lookahead, top-down, lookahead parsing (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

9. [fix simple constraint violations] fix simple violations of constraints that preclude single-symbol-lookahead, top-down, lookahead parsing (cs-discrete-math, cs-problem-solving)(is-discrete-math, is-problem-solving)(cys-discrete-math, cys-problem-solving)

 

10. [construct parser] design and implement a single-symbol-lookahead, top-down, lookahead parser from a BNF grammar (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

11. [design symbol table] design a symbol table format for the language defined by a BNF grammar (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

12. [implement symbol table construction] enhance the parser to construct a symbol table as it parses an input (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

13. [formulate semantic tests] determine the specific semantic tests, e.g., type analysis, to perform on an input to the parser for a BNF grammar and enhance the parser to perform that analysis (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

14. [implement semantic testing] enhance the parser to perform semantic tests as it parses an input (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

15. [design code generator] design a syntax-oriented translation, into a specified intermediate code language, for the high-level language defined by a BNF grammar, and enhance the grammar’s parser to perform that translation. (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

 

16. [implement code generator] enhance the parser to perform translation into the intermediate code language as it parses an input. N.B. the code generator need not generate target code from source code containing procedure/function calls as that has been found to be too much for a single-semester course, (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)

17. [construct dynamic run-time stack] draw the dynamic structure of the run-time stack when target code containing procedure/function calls is executed. (cs-runtime)(cys-runtime)

 

18. [Apply code optimizations] apply simple intermediate code optimizations (as time permits) , (cs-problem-solving, cs-requirements)(is-problem-solving, is-requirements)(cys-problem-solving, cys-requirements)