Bottom Up Parsing Questions and Answers

Answer: A

This invariant is what the whole method rests on. Each reduction moves backward one step along a rightmost derivation, so the concatenation of stack and input is always a right sentential form until the start symbol alone remains.

Answer: B

Correct answer: the steps of a rightmost derivation taken backwards

A bottom up parser starts from the input and works towards the start symbol, so the reductions it performs are the derivation steps run in reverse. Because the handle is always the leftmost complete right side available, the derivation being reversed is specifically the rightmost one - which is why the method is also called LR, for left-to-right scan of a rightmost derivation in reverse.

Answer: C

Correct answer: shift, which pushes a token, and reduce, which replaces a right side

Shift moves the next input token onto the stack; reduce pops the symbols of a right side and pushes the corresponding left side. Accept and error are the two remaining table entries, but they terminate the parse rather than advance it. Predict and match belong to top down parsing.

Answer: D

Correct answer: a right side whose reduction at that position reverses a derivation step

The definition has two parts and both matter: the symbols must form the right side of some production, and reducing them at that particular position must correspond to undoing a step of the rightmost derivation. A string may match a right side without being a handle, and reducing it then leads the parse astray.

Answer: A

Correct answer: at the top of the stack, never buried below other symbols

This is the property that makes the whole method work with a stack rather than a general data structure. Because handles never appear buried, a reduction only ever needs to pop from the top, and the parser never has to reach inside the stack to find what to reduce.

Answer: B

Viable prefixes are exactly the stack contents reachable during a correct parse. The LR(0) automaton is precisely a machine recognising the viable prefixes of the grammar. That the set is regular is what allows a finite table to drive the parse.

Answer: C

Both are true and the reason gives the mechanism, and this is why the set of viable prefixes is a regular language even though the language itself is not. The stack contents form a regular set, which is the deep reason a finite table suffices.

Answer: D

The dot divides what has already been pushed from what the parser still expects. Sets of such items become the states of the automaton that drives the parse. Constructing those sets is the mechanical heart of every LR table generator.

Answer: A

A complete item means the entire right side is on the stack. Whether the parser actually reduces depends on the lookahead and on the particular LR construction being used. LR(0) reduces regardless while the later constructions consult the lookahead.

Answer: B

Closure adds an item for every production of whatever nonterminal follows a dot, so any two states expecting the same nonterminal share those items. The kernels differ, which is why the states remain distinct, but a great deal of the content is duplicated across the collection.