Final Exam

The final exam will be held on Monday, November 11th 8-10AM in the usual classrom. It will be closed book, and no calculators or phones are needed. The exam will cover the entire book, and anything from the course project and homeworks is fair game. Expect about six pages, each one covering a different topic.

• Overall structure and purpose of a compiler.
• Scanning:
  • Formal definition of regular expressions.
  • Writing regular expressions to match various tokens.
  • Converting REs into NFAs using Thompson’s construction.
  • Converting NFAs into DFAs using subset construction.
• Context Free Grammars:
  • Identifying and removing ambiguity from CFGs.
  • Top-Down Parsing
  • Bottom-Up Parsing
  • Chomsky Hierarchy
• Parsing in Practice
  • Writing Grammars with Bison
  • Interpreting While Parsing
  • Constructing the AST
• Abstract Syntax Tree Understand all the parts of language grammar:
  • Declarations
  • Statements
  • Expressions
  • Types
  • Parameters vs Arguments
  • Symbols
• Type Checking Aspects of type systems: - Static vs Dynamic - Safe vs Unsafe - Explicit vs Implicit - Data conversions Methods of checking types in B-minor: - Computing Expression Types - Type Constraints in Statements - Type Constraints in Declarations
• Memory Organization
  • General Code Organization
  • Methods of Heap Management
  • Methods of Stack Management
  • Calling Conventions
• Code Generation
  • Expressions
  • Statements
  • Declarations
• Optimization
  • Understand inherent inefficiencies that arise from our simple code generation method.

Coding Expectations:

• Expect to write some small quantities of C, B-minor, or assembly code.
• You should have deep familiarity with the implementation of your own compiler in the C language, including the structure and contents of the Abstract Syntax Tree.
• You should know the core of X86 assembly language that is used to implement the code generator.