Top Down Parsing Questions and Answers

Answer: C

Correct answer: 2 - 4 - 1 - 3

The transformations must come before the analysis, since they change the grammar the sets are computed from. Left recursion is removed first, then common prefixes are factored out, then FIRST and FOLLOW are computed on the resulting grammar, and only then can the table be filled from those sets.

Answer: D

The marker records that the symbol may vanish entirely, which is what forces the parser to look at FOLLOW instead. Whether epsilon propagates through a whole right side depends on every symbol in it being able to vanish, and tracking that is the part most often got wrong when the sets are computed by hand.

Answer: A

Whatever can follow the left side can equally follow the last symbol of any of its right sides, so the whole set is copied across. The same rule applies to a symbol whose successors can all derive the empty string, which is where the computation most often goes astray when it is worked through by hand.

Answer: B

Correct answer: the start symbol of the grammar

The end of input marker can follow the start symbol and nothing else at the outermost level, so it is placed in FOLLOW of the start symbol and propagates from there to whatever can appear at the end of a sentence. It is not added to every nonterminal, though many will acquire it through propagation.

Answer: C

A appears in the right side aAb followed immediately by the terminal b, so FIRST of what follows A is simply b. Nothing else can follow A anywhere in this grammar. Small grammars like this one are worth working through by hand until the rule is automatic.

Answer: D

S begins with A, which contributes a. Because A can also derive epsilon, FIRST of B contributes b as well. Epsilon is not included since S itself cannot derive the empty string. Tracking when epsilon propagates is the part most often got wrong by hand.

Answer: A

Correct answer: 40

The rows are the nonterminals and the columns the terminals together with the end of input marker: \[ 5 \times (7 + 1) = 40. \] Forgetting the marker gives 35, which is the trap here - the column for the end of input is what allows the parser to accept, and to reduce by an epsilon production at the end of the input.

Answer: B

Correct answer: whichever rule fits when A heads the stack and a is in hand

The cell holds the production to apply when the nonterminal A is on top of the stack and the lookahead is the terminal a. An empty cell means no production applies and the parser reports an error. A cell with two entries means the grammar is not LL(1).

Answer: C

The two clauses cover the ordinary case and the epsilon case. Applying them to every production of every nonterminal fills the whole table mechanically. No judgement is involved, which is why the construction can be automated entirely.

Answer: D

A conflict means one token of lookahead is not enough to decide. The grammar may still be fixable by factoring or by removing left recursion, or it may need more lookahead. The generator reports the offending cell, which usually identifies the cause.