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 Quiz 3 Learning Goals
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 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?
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.
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?
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?
An activation record is another name for what stack associated term?
Distinguish between the stack-top register and a frame pointer. How are each used in stack and procedure management?
Distinguish the use of data areas: global data, heap allocated data, stack allocated data. When are each used?
What is an object pointer, how is it used in the addressing of variables in modern CPUs?
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 λ"?
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)?
Be able to calculate Closure and Goto for LR Item Sets.
What important property do LR parsers have with respect to the DBL language?
How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing 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.
Other than pure and augmented machine code, what other type of machine code might a compiler generate?
What is augmented machine code? How does it differ from pure machine code?
What is bootstrapping a compiler? Have all compilers been bootstrapped?
What is pure machine code? Be able to cite an example.
What is the difference between absolute binary and relocatable binary forms of machine code?
What is the difference between the target of a compiler and the kind of machine code generated by the compiler?
What other target code format, other than absolute and relocatable is a common output of compilers?
Be able to convert a RE (in the book's notation) to an equivalent NFA.
Be able to process a parse-tree for REs creating a structure for an equivilant 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?
Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).
What features of a language are REs able to describe?
Be able to optimize a DFA to a smaller form by reconciling indistinguishable states.
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.
Be able to compare and contrast two approaches: one symbol table for all scopes and separate symbol table for each scope
What are semantic actions?
What are semantic values?
What is syntax directed translation (SDT)?
How are semantic actions different than syntactic actions?
Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation).
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.
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?