• 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 dry-run for the actual exam.

Syllabus

[top]

The exam will cover lecture 22 (Mar 8 ), which is on Unification, followed by Language Translation, Syntax, Regular Expressions, Right Regular Grammars, ocamllex Regular Expressions, OCamllex, OCamllex example, BNF Grammars, Parse Trees, Ambiguous Grammars, Ocamlyacc, LR Parsing, Action & Goto Tables, lecture 32 (Apr 7). The following give examples of the kinds of questions you are likely to be asked for each topic:

• 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.
• Parsers
  • Be able to write an attribute grammar suitable for processing by ocamlyacc to generate a parser for a given language.
  • Know what shift/reduce and reduce/reduce conflicts are, why they happen, and how they can be resolved.
  • Know how Action and Goto tables are used to implement an LR parser.