Top Down Parsing Questions and Answers

Answer: A

Correct answer: ordered, so the first successful alternative is taken

In a parsing expression grammar the choice operator is ordered: alternatives are tried in sequence and the first that succeeds is committed to. This makes every PEG unambiguous by construction, since there is exactly one parse - but it also means a rule can silently shadow a later alternative if the order is wrong.

Answer: B

Blank cells outnumber filled ones in a typical table. Reaching one invokes the error routine, which reports the fault and attempts to bring the parser back into step with the input. Good recovery is what distinguishes a usable compiler from a merely correct one.

Answer: C

Synchronising sets are usually built from the FOLLOW sets of the nonterminals on the stack. Skipping to such a token lets the parser resume at a well defined point. The technique is crude but it never loops and it is trivial to implement.

Answer: D

If the lookahead can follow A, then A has evidently been completed or omitted, so popping it is a reasonable repair. The technique costs nothing and improves recovery markedly. Filling the error cells this way is standard practice in generated parsers.

Answer: A

The repair is local and aimed only at continuing. There is a risk of an infinite loop if the correction consumes no input, so implementations guard against that explicitly. A common guard is to require that at least one token be consumed per repair.

Answer: B

Correct answer: A-2, B-4, C-1, D-3

Four strategies of increasing ambition. Panic mode discards tokens until it reaches a synchronising symbol such as a semicolon. Phrase level recovery makes a local repair, inserting or deleting a single symbol. Error productions build the anticipated mistake into the grammar so it can be recognised and reported precisely. And global correction seeks the smallest set of changes making the input legal - theoretically attractive and too costly to use.

Answer: C

Diagnostics can be written for each construct at exactly the point of failure. The cost is that no tool reports conflicts, so the author must verify the grammar properties by hand. A thorough test suite is the usual substitute for that missing static check.

Answer: D

Correct answer: silently accepting a language different from the intended grammar

Nothing checks a hand-written parser against the grammar it was meant to implement, so a mistake in one procedure quietly changes the language accepted. A generated parser at least reports conflicts and is derived from the grammar mechanically - this is the strongest argument for using a tool.

Answer: A

The usual structure is one procedure per nonterminal, so twelve are needed. Terminals are matched inline by a helper rather than by procedures of their own. The correspondence between grammar and code is what makes the style so readable.

Answer: B

One variable suffices for LL(1). Advancing it means calling the scanner for the next token, which is why the two phases are so tightly coupled in this design. Extra lookahead would require buffering tokens the scanner has already produced.