I.  Overall Compiler Organization

• what's in the front/back end
• what the job of each phase is

II.  Lexical Analysis

• Terminology

  • token, pattern

• Regular expressions

  • the notation
  • how you build them, concrete examples
  • advantages
  • limitations
  • naming them

• Scanners

  • Regular expressions and DFAs. You are not responsible for the details of the RE -> NFA -> DFA construction.

III.  Syntactic Analysis

• Context-free grammar

  • BNF: terminals, nonterminals, productions
  • how you build them, concrete examples
  • advantages
  • limitations

• Derivations

  • abstract vs. concrete (parse) syntax trees

• Parsing algorithms

• top-down vs. bottom-up
• predictive parsing
• table-driven & recursive descent implementations

• LL(1) grammars

  • LL(k) property - disjoint FIRST sets
  • ambiguity & fixes
    • meta-rules (code/precedence tables)
    • rewrite grammar
    • change language
  • common prefixes (left factoring)
  • left recursion

• Bottom Up LR(0) Parsing

• Building a LR(0) DFA
• Building a LR(0) parse table
• Shift-reduce parsing using an LR(0) parse table
• Dealing with shift-redue and reduce-reduce conflicts.
• FIRST, FOLLOW, and NULLABLE
• SLR(1) vs LR(0)
• Using ambiguous grammars and precedence rules in parser generators

IV.  Semantic Analysis

• Type checking basics

  • examples
  • type checking algorithm

• Symbol table

  • typical information recorded for names
  • scopes: when created, how used, why have them
  • handling procedures
  • handling records

• Strong, weak, static, dynamic typing

• Type equivalence

  • structural vs name