| 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 lecture 10 which is Type Systems & Type Derivations, up to and including the
lecture on LR Parsing. The following give examples of
the kinds of questions you are likely to be asked for each topic:
- Types and Type Derivations
- Explain and apply the key terminology of types and
type systems.
- Make proofs of type derivations and type inferences
using typing rules
- 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 & DFAs
- Be able to tell when a string is in the language of a
regular expression or DFA
- Be able to construct simple DFAs/Regular Expression
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.
|
|