| Syllabus and Study Guide for Midterm 3 |
|
- 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.
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.
|
|