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 Final Exam
The author suggests an AST node have access to what collection of other "nearby" nodes?
What is the common AST node structure associated with a sequence or block of statements?
What is the common AST node structure associated with a repeat-until or repeat-while post-test loop?
What is the common AST node structure associated with a while-do-done pre-test loop?
What is the common AST node structure associated with an if-then or if-then-else structure?
What is the common AST node structure associated with a switch or if-elif-elif-elif-else multi-way branch?
What is the difference between a concrete syntax tree and an abstract syntax tree (AST)?
Be able to identify (seemingly) ambiguous grammars, what demonstrates an ambiguous grammar?
Be able to write a non-trivial grammar with recursive rules.
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?
What is a parse tree, what characteristics does it have?
Cite two pieces of information stored as control information in a stack frame.
How is the location of local variables in a function determined? How are these addresses accessed in modern CPUs?
Know the difference between procedure level and block level frame allocation.
What function specific information is commonly stored in the symbol table? Why is the symbol table the ideal structure?
What is a dynamic link of a stack frame? Why is it dynamic?
What is a frame or stack frame? What language construct implies the use of stack frames?
What is a local variablle? Where in memory is a local variable typically stored?
What is the difference between callee and caller saved registers? Which might not exist for a function and why?
Be able to eliminate left recursion from a grammar in order to make it LL(1)
Be able to factor out common prefixes in order to make an LL(1) grammar.
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?
How are Item Follow Sets formed?
If a LR(k) parsing table can be formed from a grammar G that generates or defines language L, what ambiguity conclusion can be made about L?
In terms of deciding which production rule to use, what is the fundamental advantage of LR parsers over LL parsers?
Know what an Item Set and its Progress Marker represent.
Understand the shift-reduce parsing algorithm (given a LR parsing table or a simple grammar).
What do to the L, R, and k stand for in LR(k) parsing?
What is a reduce-reduce conflict in an LR table construction algorithm?
What is a shift-reduce conflict in LR table construction?
What type of derivation do "bottom-up" parsers use (generate)?
How are Follow Sets used in SLR to resolve reduce-reduce or shift-reduce conflicts in LR(0) tables?
What property of it's predict sets make a grammar not LL(1)?
A context free grammar defines what particular facet of a programming language? What does a CFG guarantee?
Complete the following: "CFGs confirm a program has valid ----, static semantics confirm a program is ---.
What are static semantics? Cite examples.
Be able to convert a RE (in the book's notation) to an equivalent NFA.
How are left recursive rules refactored so that a grammar might be processed with an LL(1) parser?
How are grammars with common prefixes that create intersecting predict sets refactored to become LL(1) languages?
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.
What are semantic actions?
What are semantic values?
What is syntax directed translation (SDT)?
Be able to express semantic actions in the context of an LL parse where a node's parent, descendents, and left-hand siblings are known.
Know the (limited) capabilities of semantic actions in a simply implemented LR parser.
Describe a common simple data structure for maintaining a compiler's namespace.
What information is associated with a symbol? Name 3 distinct items.
What is the namespace of a compiler? What does the namespace store?
What special properties of names suggest a relatively simple namespace data structure can be used?
What are active scopes?
What is a shadowed identifier?
What is the current scope?
What is the downside to implementing a full blown symbol table for each scope vs one global table?
What operations (API) is required of a symbol table implementation?