The following is simply a conveniently formatted list of learning goals. More likely than not, some might be hard to assess through a quiz or exam. Students should prioritize their studying based on:
- how much time in lecture was spent discussing or understanding the topic,
- how much the topic was stressed in learning group assignments
- and the student's comfort level with the topic
Assessable Learning Goals covered for Midterm Exam
Be able to identify (seemingly) ambiguous grammars, what demonstrates an ambiguous grammar?
Determine what terminals are in the first set of a grammar sequence.
Determine what terminals are in the follow set of a grammar symbol.
Determine whether a "symbol derives to λ".
Given a grammar, be able to derive a valid sentence of the grammar.
How are left-associative and right-associative connected to recursive production rules?
Know the difference between a leftmost derivation and a rightmost derivation.
Know the notational conventions for CFGs used in the book.
What are terminals, non-terminals, λ, and $ in a CFG?
What is a sentential form?
When might we suspect that a grammar is ambiguous?
Be able to deduce associativity and precedence rules for operators in a CFG.
Be able to design simple languages and grammars with nested productions and recursive rules.
Given a binary operator, △, know how to write its production rule for left or right associativity.
Given two binary operators △ and □ , know how to write a simple grammar to express their relative precedence.
What is a reduced grammar?
Can a BNF grammar represent different languages than a CFG?
What is a parse tree, what characteristics does it have?
What is a regular grammar? What two production rule patterns are associated with regular grammars?
Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream.
How are top-down parsers that don't use LL tables constructed?
How do you build an LL(1) parsing table from a grammar that is LL(1)?
How is a predict set calculated from first sets, follow sets, and "derives to λ"?
How is a predict set calculated from first sets, follow sets, and "derives to λ"?
What do the two Ls and the k stand for in "LL(k)" parsing?
What does a production rule written with left recursion look like?
What is a predict set?
Be able to convert a RE (in the book's notation) to an equivalent NFA.
In what way are REs limited in their description of languages?
What features of a language are REs able to describe?
Be able to optimize a DFA to a smaller form by reconciling indistinguishable states.
Be able to describe an algorithm for removing dead and unreachable states in a DFA.
Cite two ways that a FA (DFA or NFA) may be represented in computer memory. Understand their tradeoffs.
What are dead states and unreachable states in FAs?
What is the difference(s) between a NFA and a DFA?
Be able to convert an NFA to a (unoptimized) DFA.
Be able to construct a RE (in the book's notation) for particular token patterns.
How are the terms regular language, regular set connected to DFAs?
How are the terms regular language, regular set, and regular expression interrelated?
Know the (book's) notation and terminology for regular expressions.
Know the meaning of RE notations: AB, A|B, A∗, A+ and Aκ (κ a constant positive integer)
Know the meaning of λ, single characters s ∈ Σ, and T ⊆ Σ as they relate to the book's RE notation.
What are the three basic operations in REs from which all other operations may be derived.