 Understand the lecture slides and discussions thoroughly. Revisit the MPs and HWs and make sure you understand the solutions
thoroughly. Repeat any you are not comfortable with.
 Take the sample exam as a check on your
understanding of material for the actual exam.
The exam will cover lecture 15 (Oct 10 ), which is on Polymorphic
Type Inference, Unification, followed by Language Translation,
Syntax, Regular Expressions, Right Regular Grammars, ocamllex
Regular Expressions, using OCamllex to produce a lexer, BNF
Grammars, Parse Trees, LR Parsing, Action & Goto
Tables, Ambiguous Grammars and disambiguation, lecture 22 (Nov 2).
You should fully understand and be able to do exercises like those
in MP6: A UnificationBased Type Inferencer, WA6: Incremental
Unification Algorithm, MP7: Unification Algorithm, WA7: Regular
Expressions, MP8: A Lexer for PicoML, WA8: Parse Trees, MP9: A
Parser for PicoML.
The following give examples of the kinds of questions you are likely
to be asked for each topic:
 Polymorphic Type Inferences

Implement polymorphic type inferences using polymorphic
typing rules, including the gathering constraints
 Unification
 Be able to implement the unfication algorithim and
auxilliary functions for substitution and occurs checking
 Solve simple unification problems such as the
ones in the lecture slides.
 Recognize correct versus incorrect applications of
steps in the unification algorithm.
 Know how unification is used for pattern matching,
type checking, and type inference.
 Regular Expressions & Regular languages
 Be able to tell when a string is in the language of a
given regular expression
 Be able to construct simple Regular Expression or
Right Regular Grammar given a description of the strings they
should accept.
 Lexing
 Be able to describe lexical items using regular
expressions
 Be able to write a simple lexer in ocamllex by
providing regular expressions for recognizing leximes
(stings translated to tkens) AND semantic actions associated
with the corresponding regular expressions
 Be able to write mutually recursive lexers in
ocamllex, and use arguments to lexers to be able to
implement different kinds of comments, and accumulate
information
 BNF Grammars
 Be able to create a grammar that generates a given language (set of
strings) described in English
 Be able to build a parse tree for a string in the
language of a grammar, or say none exists if the string is
not in the language.
 Be able to give a unambiguous grammar generating the
same language as a given ambiguous, for common sources of
ambiguity, respecting any specification of precedence or associativity.
