 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 dryrun for the actual exam.
The exam will cover lecture 11 (Sept 30) which is on Type
Derivation up to and including lecture 22 (Oct 30), the lecture on
Ambiguous Grammars and Recursive Descent Parsing. The following give
examples of the kinds of questions you are likely to be asked for each
topic:
 Polymorphic Types and Type Derivations
 Explain and apply the key terminology of types and
type systems.
 Make proofs of polymorphic type derivations and
polymorphic type inferences using typing rules
 Be able to recognize incorrect versus correct usages of the typing rules
 Polymorphic Type Inferences
 Polymorphic type inferences using polymorphic typing rules, include the
gathering constraints
 Unification
 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
regular expression
 Be able to construct simple Regular Expression or
Regular Gammar
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 semantic actions associated with 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
 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 create a family of data types (abstract
syntax trees) representing the parse trees of a given grammar.
 Demonstrate that a grammar is ambiguous, if it is.
 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.
 Be able to tell whether a grammar in ambiguous.
 Parsers
 Be able to write a recursive descent parser for a given simple
grammar.
