| Syllabus and Study Guide for the final |
|
- Understand the lecture slides and discussions thoroughly.
- Revisit the MPs, and WAs 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 all the lectures in the course. It is a
comprehansive exam. Listed here are topics not previously listed
in midterm1.syllabus.html,
midterm2.syllabus.html,
or midterm3.syllabus.html. They
writing parsers in ocamlyacc,
Natural Semantics and Transition Semantics, Lambda Calculus,
and Axiomatic Semantics. The following give
examples of the kinds of questions you are likely to be asked
for each topic on the exam:
BNF Grammars
- 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 grammar, for common sources of
ambiguity.
Parsers
- Be able to write a simple parser in ocmalyacc by providing an
unambiguous attribute grammar using a tokens type and a family of
types for abstract syntax.
- 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).
- 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 one step of the
the evaluation of an expression in Transition semantics.
- Be able to compare Natural and Transition semantics.
- Understand the evaluation rules in both semantics, and be able to
write evaluation rules for new syntactic constructs.
- Be able to implement Natural and Transition semantics rules as
OCaml programs.
Lambda Calculus (LC)
- Be able to parse a lambda term correctly (e.g. which
variable is bound by which abstraction, which variable is
free, what the scope of an abstraction is, what the grouping
of a series of applications is, which application is outer-most, etc.)
- Describe and know how to apply α-conversions,
α-equivalence and β-reductions.
Axiomatic Semantics
- Be able to prove simple statements in Floyd-Hoare Logic, similar
to the example of {y=a} if x < 0 then y:= y-x else y:= y+x
{y=a+|x|} that was done in class.
- Be able to prove a statement about a simple while loop, as in the
definition of factorial.
|
|