Bottom Up Parsing Questions and Answers

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.

Answer: C

Correct answer: True

LR parsing is incremental: actions run as reductions occur, so a translator can emit code, build tree fragments or write output long before the end of the input is reached. This is what makes single-pass compilation possible and why an LR parser can be used on a stream.

Answer: D

The parser may shift several times in a row or reduce several times in a row. There is no required alternation, and the counts of the two actions are generally different. The shift count equals the token count while the reduction count does not.