CST 8152 - Pre-Final Exam Review Material
Numbers in parentheses refer to the course text chapter
This is a quick combination of several sets of review
questions; there is much redundant material:
- Be familiar with the notational conventions for
context-free grammars (4.2).
- Error handling: Aho p. 11; and section 4.1
- Symbol table routines: Aho p. 11; 72, 77 (insert,
lookup); early parts of section 7.6 discuss
implementation and efficiency issues.
- Postfix Converter (as an example of embedding action
symbols in a grammar): Aho section 2.3, p.33; example
2.8, section 2.5
- Aho sections 2.1, 2.2: parsing, syntax definition,
context free grammars, parse trees, ambiguity,
- 2.4: top-down parsing, predictive parsing, function of
lookahead, FIRST sets, designing a predictive parser
- Recursive Descent parsing functions: Fig 2.24, 2.27, 2.28
- Matching statements by using reserved words: Fig 2.34
- 4.1: role of the parser, error recovery, nature of syntax
- Parts of section 4.2: Context Free Grammars, terminology
and notation, ambiguity
- Parts of section 4.3: how are grammars built?
- Parts of section 4.4: recursive-descent parsing,
predictive parsers, transition diagrams
- Error handling: Aho p. 11 and section 4.1
- What is an ambiguous grammar? Show that a grammar is
- List and describe various types of error recovery in a
- Write a function that implements panic mode error
recovery in a language that uses ';' to separate
- Modify the panic() function to stop on commas as well as
- What are Aho's three goals of an error handler in a
- Of what use are reserved words to a predictive parser?
- What are the four components of a Context Free Grammar?
- Show how parse trees for left- and right-associative
grammars differ. (2.2)
- Write a parse tree for a given sentence and grammar.
- What is a parse tree? (2.2)
- Why not use a CFG to define the lexical syntax of a
language, instead of using regular expressions? (4.3)
- Describe some methods of error repair and recovery.
- Describe four error recovery strategies. (4.2)
- Given a Grammar (possibly one you have never seen),
construct a Parse Tree that shows how a sentence in the
language is recognized (2.2, 4.2, 4.4), e.g. 3 * A + 7 *
B + 9
- Given a Grammar (possibly one you have never seen), and a
Scanner that returned the next Token, derive the simple C
Language functions for a recursive descent parser that
would recognize each of the production rules in the
grammar, e.g. functions similar to statement(),
assignment(), print(), dump(), expression(), factor(),
- Define briefly (4.2,4.5): handle, leftmost (rightmost)
derivation, shift, reduce, ambiguous grammar, left
(right) recursion, a sentential form, a sentence
- Given a grammar and a sentence in the language defined by
the grammar, show the rightmost and leftmost derivations
of the sentence. Show the parse trees corresponding to
the two derivations.
- What is meant by an "LL" parser? What is an
- Is top-down parsing LL or LR? What about bottom-up
- Can a top-down parser handle: (1) left-recursive
grammars? (2) right-recursive grammars?
- Know how to recognize left recursion in a grammar (2.4,
4.3). Know how to eliminate immediate left
recursion from a grammar (p.176). Why would one want to
- Why use a stack to locate handles in shift-reduce
- Define briefly (8.1, 9.1, 9.2): intermediate
representation, target language, quadruple notation,
triple notation (p.470)
- How are constants handled in a compiler if only addresses
or names can be pushed on the value stack?
- Why use an Intermediate Representation (IR)? Why not
generate the target language (machine code) directly?
- Name the three forms of IR described in class.
- With respect to code generation , why must the symbol
table contain both the type and the address of a name?
Why is the type necessary?
- Given the following expression, show the IR quadruples
that might be generated when the code is compiled.
Variables i,j,k are
integer; x is
i = j * k + j * x
- What changes are needed in the data structures of your
interpreter to turn it into a compiler?
- How do the semantic functions (e.g. execute(op))
differ between an interpreter and a compiler?
- Define briefly: backtracking, predictive parsing,
recursive-descent parsing, grammar production, terminal
symbol, non-terminal symbol, top-down parsing, bottom-up
parsing, semantic action symbols, translation scheme,
token, look ahead token, white space, lexeme, value
stack, panic-mode recovery, phrase-level recovery, error
productions, unary minus.
- Why cant a recursive-decent parsing function be
written for the following grammar rule?
<expr> --> <expr> +
<term> (Hint: Try to write the function.)
- Define and document a C language data structure that
would hold one element of the symbol table needed for
- Define and document a C language data structure
implementing the global data returned by the scanner() in
- What are three goals of the error handler in a parser?
- Describe four levels at which errors may occur in a
program. Which level has been given the most attention by
compiler writers and why?
- Statistically, are the errors that occur in real programs
simple or moderately complex?
- What is the difference between error recovery and error
repair in a parser?
- Why not quit the parser upon finding the first error?
- Briefly describe three error recovery methods for a
- How can a parser distinguish between different statement
types in a language, e.g. between for() and while()
- Draw a block diagram showing the difference between an
interpreter and a compiler.
- List some advantages of an interpreter over a compiler.
- List some disadvantages of interpreters.
- Why are loops so difficult for interpreters?
- How can the scanner differentiate between subtract
and unary minus?
- How can the parser differentiate between subtract
and unary minus?
- Write a recursive descent parsing function that
implements any of the grammar productions in the Toy
Grammar from the notes. No semantic actions are required;
the functions need only recognize the input.
- Write pseudocode functions that show what code is needed
to write a recursive descent parser, with semantic
actions, for the following simple grammar of assignment
<stmt> -> ID = <item> ;
<item> -> ID