| 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 the 12 lectures from Wednesday February 7
through Monday March 12, starting with user
defined types (variants and records) and defining
functions over them, going through BNF grammars, parse trees,
abstract syntax trees, ambiguous grammars. The following give
examples of the kinds of
questions you are likely to be asked for each topic:
- User-Defined Types
- Be able to define record types and disjoint (variant)
types in OCaml.
- Know the difference between record and disjoint
types, and when each should be used.
- Be able to write OCaml functions over recursive disjoint types.
- 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 semantics
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.
|
|