Studying for this exam

[top]

• 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.

Syllabus

[top]

The exam will cover lecture 15 (Mar 5), 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, Ambiguous Grammars and disambiguation, lecture 22 (Apr 4). You should fully understand and be able to do exercises like those in MP6: A Unification-Based Type Inferencer, WA6: Incremental Unification Algorithm, MP7: Unification Algorithm, WA7: Regular Expressions, MP8: A Lexer for PicoML, and WA8: Parse Trees. You willnot be expected to write an ocamlyacc file as in MP9: A Parser for PicoML, but you are responsible for understanding the concept of an ambiguous grammar, be able to identify speific causes of ambiguity in a specific grammar, and analyze an attempt at disambiguation.

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 demonstrate that a grammar is ambiguous, if it is.
  • Be able to analyze an attempt at disambiguating a grammar for whether is generates the same language as the original, and for whether it is unambiguous.
  • Be able to give a unambiguous grammar generating the same language as a given ambiguous, for sources of ambiguity arising from infixed operators, respecting any specification of precedence or associativity.