Studying for this exam

[top]

• Understand the lecture slides and discussions thoroughly.
• Revisit the MPs and make sure you understand the solutions thoroughly. Repeat any you are not comfortable with.
• Do the sample exam questions as a dry-run for the actual exam.

Syllabus

[top]

The exam will cover the material through lecture slide set 13. The following give examples of the kinds of questions you are likely to be asked for each topic:

• Basic OCaml
  • Know the basic constructs (e.g., match, fun, let, let rec, ::) like the back of your hand.
  • Be able to evaluate OCaml expressions
  • Be able to determine the type of OCaml expressions
  • Be able to use pattern matching
  • Work with lists and tuples
• Recursion
  • Be able to write recursive functions, possibly tail-recursive.
  • Be able to recognize whether a function is tail-recursive, and when a recursive call is in tail call position
  • Understand the performance benefits of tail recursion.
  • Define mutually-recursive functions
• User-Defined Types
  • Be able to define unions and disjoint (variant) types in OCaml.
  • Be able to write OCaml functions over recursive disjoint types.
• Regular Expressions and DFAs
  • Be able to tell when a string is in the language of a regular expresion or DFA
  • Be able to construct simple DFAs/Regular Expression given a description of the strings they should accept.
• Lexing
  • Be able to construct a simple lexer given a description of the language
  • Given a lexer definition and an input string, be able to specify the list of tokens that will be generated by the lexer
  • Write elements of a lexer in ocamllex syntax
• Context-Free Grammars and Parsing
  • Given a description of the language, be able to construct a context-free grammar for the language
  • Given a context-free grammar and an input string, illustrate left-most and right-most (canonical) derivations
  • Given a context-free grammar and an input string, show a parse tree, possibly constrainted by a certain derivation order
  • Be able to say whether a given grammar is ambiguous, including showing multiple parse trees to illustrate the ambiguity
  • Construct a shift-reduce parse for a sentence of a grammar
  • Write parse rules in ocamlyacc syntax
• Compiler Structure and Code Generation
  • Identify the major components of the compiler, and their relationship
  • Analyze or write IR code generators for statements and expressions, including contextual and short-circuit evaluation