Bottom Up Parsing Questions and Answers

Answer: A

The three listed components are all present at run time. FIRST sets are used when building canonical LR lookaheads but are not consulted while the parser is actually running. Everything the parser needs at run time has been folded into the tables.

Answer: B

Implementations often store only the states, since the symbols can be recovered from them. The semantic values live on a parallel stack of their own. Keeping the two stacks in step is the responsibility of the generated driver.

Answer: C

Correct answer: each state determines the grammar symbol that led into it

Every transition into a given state is on the same symbol, so the symbol is recoverable from the state and need not be stored separately. Implementations therefore push states alone, halving the stack, and reconstruct the symbols only when something - an error message, say - actually needs them.

Answer: D

Default reductions, row equivalence and displacement schemes all cut the space substantially. The cost is a slightly more expensive lookup at run time. For a table of several hundred states the trade is usually worth making.

Answer: A

Correct answer: reducing on any lookahead not explicitly listed for the state

Where a state has one reduction dominating its row, the individual lookahead entries can be replaced by a single default, which compresses the table considerably. The parser then reduces on a token that should have been an error, but since a reduction consumes no input the error is caught a moment later, before any token is shifted.

Answer: B

Both are true and the reason gives the mechanism, and this is the standard justification for the compression. The only visible cost is that the reported error position may be a reduction or two later than it would otherwise be.

Answer: C

Correct answer: default reductions used to compress the parsing tables

With default reductions the parser may perform one or more reductions on an erroneous lookahead before discovering there is no shift for it, so detection is no longer at the very first impossible token. Nothing incorrect is ever shifted, so the error is still reported before any bad input is consumed - the property is delayed rather than lost.

Answer: D

Merging states with equal cores can create a reduce-reduce conflict. Such grammars can be constructed deliberately but seldom arise when describing an actual programming language. This is why LALR has been an acceptable default for so long.

Answer: A

Most conflicts come from an ambiguity or an accidental overlap that is easy to fix once identified. Reaching for a more powerful parser should be a last resort rather than a first. Most conflicts point at a genuine ambiguity worth removing anyway.

Answer: B

Real grammars produce a few hundred states for a language of moderate size. The exponential worst case exists in theory but is not approached by practical grammars. Grammar size rather than pathological structure is what drives the count.