| 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 topics starting from the
June 20 lecture on DFAs and lexing up to and including
the July 9 lecture on small-step semantics.
The following give examples of the kinds of questions you are likely
to be asked for each topic:
- 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 expressions
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 lexing rules, and use
arguments to rules 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 that none exists if the string is
not in the language.
- Be able to create a family of variant 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 (i.e., precedence and associativity).
- Parsers
- Be able to write a recursive descent parser for a given simple
grammar.
- Know the limitations of recursive descent
parsing, and be able to calculate FIRST sets and apply the Pairwise Disjointness Test.
- Be able to write an ocamlyacc specification generate a parser for a given language.
- Know what shift/reduce and reduce/reduce conflicts are, why
they happen, and some ways of resolving them.
- Operational Semantics
- Be able to build a proof tree for the evaluation of an expression in Natural (big-step) Semantics.
- Be able to build proof trees for the evaluation of an expression in Structural Operational (small-step) Semantics.
- Be able to compare Natural and Structural Operational Semantics.
- Understand the evaluation rules in both semantics, and be able to write evaluation rules for new syntactic constructs.
|
|