| Syllabus and Study Guide for Midterm 2 |
|
- 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
from the
lecture on Unification (delivered on 4 Octoberber) up to and including
lecture the lecture on Recursive Descent Parsing (delivered on 6
November). I will not ask a question on polymorphic type derivation
or inference on this exam, but you should expect something on the final.
The following give examples of the kinds of questions you are likely
to be asked for each topic:
- Unification
- Solve simple unification problems such as the
ones in the lecture slides.
- 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 by providing semantic
actions associated with corresponding regular expressions
- Be able to write mutually recursive lexers, 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.
- Parsers
- Be able to write a recursive descent parser for a given simple
grammar.
- Know how Action and Goto tables are used to implement an LR
parser (we did not cover, and you are not responsible for how to
generate these tables from a grammar).
- 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.
|
|