|
- 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 29 September) up to and including
lecture the lecture on Transition Semantics (delivered on 3 November).
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
- Creating 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 the limitations and consequences of recursive descent
parsing, be able to calculate FIRST sets and know what their use is.
- 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.
- Operational Semantics
- Be able to derive the proof tree for the evaluation of an expression in Natural semantics.
- Be able to derive the proof tree for the evaluation of an expression in Transitional semantics.
- Be able to compare Natural and Transitional semantics.
- Understand the evaluation rules in both semantics, and be able to write evaluation rules for new syntactic constructs.
|