Top Down Parsing Questions and Answers

Answer: A

Correct answer: starting at the root and working toward the leaves

A top down parser begins with the start symbol and repeatedly expands nonterminals until the leaves match the input, which is why it is also called predictive: it must guess which production to apply before seeing what that production will derive. Bottom up parsing works the other way, from the leaves inward.

Answer: B

Correct answer: a leftmost derivation of the input string

Since the parser always expands the leftmost unexpanded nonterminal, the sequence of productions it applies is exactly a leftmost derivation, produced in order. Bottom up parsing produces a rightmost derivation, and produces it backwards - which is the essential contrast between the two families.

Answer: C

Correct answer: a procedure whose body mirrors the productions for that nonterminal

Each nonterminal becomes a procedure, each alternative a branch within it, each terminal in a right side a call to match, and each nonterminal a call to the corresponding procedure. The correspondence between grammar and code is close enough to read one from the other, which is why the method is so easy to write by hand.

Answer: D

Correct answer: the call stack of the host programming language

There is no explicit stack of grammar symbols: the recursion of the procedures does the work, and the partly expanded grammar symbols are held in the sequence of active calls. This is what makes the method so compact, and it is also its limitation - a deeply nested input can exhaust the call stack.

Answer: A

Correct answer: tries alternatives in turn and undoes work when one fails

With backtracking the parser attempts each alternative in turn, and on failure restores the input position and tries the next. It handles a larger class of grammars than a predictive parser, but it can take exponential time and it makes semantic actions awkward, since work already done may have to be undone.

Answer: B

Retrying alternatives repeatedly rescans the same input and any action already executed must be reversed. Predictive parsing avoids both at the price of requiring an LL(1) grammar. That price is normally paid gladly, since the transformations are mechanical.

Answer: C

One token of lookahead determines the alternative uniquely, so no alternative is ever retried. This is what makes predictive parsing linear in the length of the input. Each token is examined once and each stack symbol is pushed and popped once.

Answer: D

Filling the table from the FIRST and FOLLOW sets and finding every cell single valued is the operational test. A doubly occupied cell names the nonterminal and the token at which one symbol of lookahead proved insufficient, which usually identifies the offending pair of alternatives immediately.

Answer: A

Correct answer: 1 and 2 only

Statements 1 and 2 are precisely the LL(1) conditions: the alternatives must be distinguishable on one token of lookahead, and where one derives epsilon the others must avoid whatever may follow the nonterminal. Statement 3 confuses this with a normal form - the length of a right side has nothing to do with whether the grammar is LL(1).

Answer: B

Left recursion, common prefixes and ambiguity each create a table conflict. Right recursion is perfectly acceptable and is in fact what left recursion elimination produces. Bottom up parsers by contrast prefer left recursion for exactly the opposite reason.