Top Down Parsing Questions and Answers

Answer: A

Without the epsilon alternative the new nonterminal could never be discharged and the repetition would be obliged to continue for ever. The epsilon alternative is precisely what converts unbounded left recursion into a loop that the parser can leave, and it is also why FOLLOW must be consulted when the table is filled

Answer: B

The standard algorithm orders the nonterminals and substitutes earlier ones into later ones, exposing the recursion as immediate. Only then is the usual transformation applied. The algorithm terminates because each substitution reduces the remaining cycles.

Answer: C

A shared prefix makes the FIRST sets overlap, so one token of lookahead cannot choose. Factoring the prefix out lets the parser commit to it and postpone the choice. Several rounds of factoring may be needed when alternatives share nested prefixes.

Answer: D

The shared prefix is parsed once and the optional else becomes a two way choice in the auxiliary nonterminal. Nothing is removed from the language and nothing about recursion changes; only the moment at which the parser must commit has been moved later, which is exactly what one token of lookahead requires.

Answer: A

Correct answer: False

The two transformations remove two specific obstacles, but a grammar can fail the LL(1) conditions for other reasons - overlapping FIRST sets that no factoring reveals, or an inherent ambiguity. Some languages have no LL(1) grammar at all, so no sequence of transformations could produce one.

Answer: B

Two parse trees for one sentence means two applicable productions at some point. That is precisely a table conflict, so ambiguity and the LL(1) property are incompatible. Removing the ambiguity is therefore the first task when a conflict appears.

Answer: C

Both continuing the inner statement and returning to the outer one are possible when else is the lookahead. The usual convention attaches the else to the nearest unmatched if. Languages with an explicit end keyword sidestep the whole difficulty.

Answer: D

Taking the else greedily in the procedure for the if statement realises the nearest if rule directly. This is one of the places where a hand written parser is simpler than a table. The greedy consumption is a single line of code in the if statement procedure.

Answer: A

Larger k accepts more grammars, but the table grows roughly exponentially in k. Most practical tools use one token, sometimes with special handling for a few awkward constructs. The special cases are usually documented alongside the grammar itself.

Answer: B

Both are true and the reason gives the mechanism, and there is a further consideration. Most language constructs can be brought within one token of lookahead by modest grammar changes, so the extra machinery earns little.