Bottom Up Parsing Questions and Answers

Answer: A

Correct answer: 2 - 4 - 1 - 3

The order is fixed by what each step needs from the last. The action table, indexed by the state on top and the lookahead, says which production to reduce by; the right side symbols and their states are then popped, exposing the state beneath; the goto table is consulted with that exposed state and the left side; and the left side with its new state is pushed. The input pointer never moves.

Answer: B

Ignoring the lookahead makes LR(0) conflict on almost every real grammar. The construction matters chiefly as the foundation on which SLR and the later methods build. Understanding it makes the later constructions much easier to follow.

Answer: C

The parser cannot tell whether to extend the current construct or to complete it. The dangling else is the classic instance, and generators usually resolve it by preferring the shift. The report should still be read, since a genuine grammar fault looks identical.

Answer: D

Correct answer: a genuine problem in the grammar that needs restructuring

A shift-reduce conflict often reflects a real ambiguity with a conventional resolution - the dangling else being the standard case - and shifting handles it correctly. A reduce-reduce conflict means the parser cannot tell which of two constructs it has just seen, which almost always indicates the grammar itself is at fault.

Answer: A

Correct answer: to shift, which realises the nearest if rule for the dangling else

Generators resolve shift-reduce conflicts in favour of shifting and usually report the count without stopping. For the dangling else this gives exactly the conventional interpretation, binding each else to the nearest unmatched if - which is why languages with this ambiguity are parsed successfully by generated parsers every day.

Answer: B

Correct answer: comparing the precedence of the rule with that of the lookahead token

A production takes the precedence of its rightmost terminal unless one is assigned explicitly, and the conflict is settled by comparing that against the precedence of the lookahead. Higher rule precedence means reduce, higher token precedence means shift, and equal precedence is settled by the associativity declaration.

Answer: C

Correct answer: reduce rather than shift when precedences are equal

Reducing on equal precedence closes off the expression already on the stack before the new operator is considered, so a − b − c groups as (a − b) − c. Shifting instead would defer the reduction and give right association, which is the declaration used for exponentiation and assignment.

Answer: D

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

Four declarations and four behaviours on equal precedence. Left associativity reduces, closing the left operand first; right associativity shifts, deferring the reduction; non-associativity reports an error, which is how a construct like a < b < c is forbidden outright; and with no declaration at all there is nothing to settle the conflict, so the generator reports it.

Answer: A

Correct answer: a smaller table and fewer single production reductions at run time

The layered grammar encodes precedence in its structure through chains such as E to T to F, and every level costs a unit reduction at parse time as well as extra states. An ambiguous grammar with precedence declarations expresses the same language with fewer productions, so the table is smaller and the parse does less work.

Answer: B

Correct answer: it costs a reduction that accomplishes no useful work

A unit production replaces one symbol by another with no structural change and no semantic content, yet the parser must still pop, consult the goto table and push. In a layered expression grammar these reductions can be a substantial fraction of the total, which is why generators offer to eliminate them and why precedence declarations are preferred.