CS 421: Programming Languages and Compilers
Midterm - July 2, 2007
main  ::  policy  ::  lectures  ::  mps  ::  exams  ::  unit project  ::  resources  ::  faq
Midterm Study Guide
Midterm format:
  • 5 written problems, 20 points each
  • 2 additional extra credit written problems, 10 points each
  • Problem topics will include:
    1. OCaml programming
    2. User-defined types
    3. Unification
    4. Type derivation
    5. Regular expressions, NFAs and DFAs
    6. Context free grammars and ambiguities
  • An information sheet will be included with the midterm; other than that, it is a closed-notes exam.
Midterm topics:
  1. OCaml programming
    1. OCaml basics: first MP and earlier problems on second MP
    2. Patterns of recursion:
      • tail recursion
      • map
      • fold_left, fold_right
    3. User-defined types: variant types like 'a option
  2. Type systems
    1. Basic type constructors:
      • atomic types: unit, bool, int, float, string
      • functions: 'a -> 'b
      • lists: 'a list
      • pairs: 'a * 'b
    2. Type derivation rules
    3. Unification
    4. Type inference
  3. Lexing and parsing
    1. Regular expressions, NFAs and DFAs
      • Translating a regular expression to an NFA
      • Translating an NFA to a DFA using the subset construction
      • Derivatives of regular expressions will not be on the midterm.
    2. Context-free grammars
      • Creating grammars
      • Ambiguous grammars and disambiguation
      • LL parsers
      • LR parsers