Bottom-Up Parsing and LR(0) MCQs: 10 Solved Questions with Explanations

Remembering that LR means bottom-up is easy. The trouble starts when a question mixes input direction with derivation order, asks for the exact handle rather than any reducible substring, or expects you to count a CLOSURE or GOTO set without missing an item. Those three demands decide most of the marks on this topic, and the ten questions below take them in that order, with every step written out. Each question title opens the same question on its solved practice page. If top-down and bottom-up still feel mixed together, read Parsing in Compiler Design: Top-Down and Bottom-Up Explained first as a concept refresher.

Bottom-Up Parsing and LR(0): the minimum concept set

A bottom-up parser starts with the input and reduces it towards the grammar's start symbol. An LR parser reads left to right while reversing a rightmost derivation, so input direction and derivation order are separate.

A handle is the production RHS occurrence chosen for the next reduction, including its position in the right-sentential form. An LR(0) item places a dot in a production to show parsing progress.

For every item-set problem, use one working rule: build the kernel first, apply CLOSURE until no new item appears, and count distinct items only.

Bottom-up parser basics, derivations, and reduction count

Question 1: identify bottom-up parser families

Which of the following is/are Bottom-Up Parser(s)?

A. Shift-reduce Parser
B. Predictive Parser
C. LL(1) Parser
D. LR Parser

Answer: A and D. A shift-reduce parser reduces input towards the start symbol, and LR is its systematic form. Predictive and LL(1) parsers expand from the start symbol, making B and C top-down methods.

Question 2: connect LR parsing to the correct derivation

Which one of the following kinds of derivation is used by LR parsers?

A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse

Answer: D. LR reads left to right, but each reduction undoes one step of a rightmost derivation. Option A confuses input direction with derivation order.

Question 3: count bottom-up reductions for aaadbbb

Consider the following grammar.
S → aSB | d
B → b
The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ________ .

Answer: 7. First write the forward derivation:

S => aSB => aaSBB => aaaSBBB => aaadBBB => aaadbBB => aaadbbB => aaadbbb

The derivation applies S -> aSB three times, S -> d once, and B -> b three times. That is 3 + 1 + 3 = 7 production applications. Bottom-up parsing reverses all seven applications, so it takes seven reductions.

Handles and right-sentential forms

Question 4: choose the complete definition of a handle

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

A. It is the position in a sentential form where the next shift or reduce operation will occur
B. It is non-terminal whose production will be used for reduction in the next step
C. It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur
D. It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

Answer: D. A handle identifies the production for the next reduction and the position of its RHS. A gives only a position, B only a non-terminal, and C changes the required next reduction into a possible future one.

Question 5: trace handles for n + n × n

Consider the grammar
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are

A. n, E + n and E + n × n
B. n, E + n and E + E × n
C. n, n + n and n + n × n
D. n, E + n and E × n

Answer: D. Start with the rightmost derivation:

E => E × n => E + n × n => n + n × n

Reverse it for bottom-up parsing:

n + n × n -> E + n × n -> E × n -> E

The handles are n, then E + n, then E × n. Only the RHS occurrence required by the next reverse step qualifies, not the whole unreduced input.

LR(0) CLOSURE and GOTO counts

Question 6: compute goto(closure(I0), +)

Consider the augmented grammar with {+, *, (, ), id} as the set of terminals.
S′ → S
S → S + R | R
R → R * P | P
P → (S) | id
If I0 is the set of two LR(0) items {[S′ → S.], [S → S. + R]}, then goto(closure(I0), +) contains exactly ________ items.

Answer: 5. Moving the dot over + creates the kernel [S -> S + .R]. Because the dot is before R, CLOSURE gives the complete set:

1. [S -> S + .R]

2. [R -> .R * P]

3. [R -> .P]

4. [P -> .(S)]

5. [P -> .id]

The item [S′ -> S.] cannot move on +, so it is not copied into the new set.

Question 7: count a nested GOTO on <

Consider the following augmented grammar with { #, @, <, >, a, b, c } as the set of terminals.
S′ → S
S → S # cS
S → SS
S → S @
S → < S >
S → a
S → b
S → c
Let I0 = CLOSURE({[S′ → •S]}). The number of items in the set GOTO(GOTO(I0, <), <) is ___________.

Answer: 8. Moving over the first < creates the kernel [S -> < .S >]. Since the dot is before S, CLOSURE adds one dot-at-start item for each of the seven S productions, giving 1 + 7 = 8 distinct items. That closed set contains [S -> .<S>]; moving over the second < recreates the kernel and the same seven closure items. The nested GOTO therefore also has eight items.

Question 8: compute GOTO(I0, 〈)

Consider the augmented grammar given below:
S' → S
S → 〈L〉 | id
L → L,S | S
Let I0 = CLOSURE ({[S' → •S]}). The number of items in the set GOTO (I0 , 〈 ) is: ________.

Answer: 5. Shifting 〈 produces the kernel [S -> 〈 .L 〉]. CLOSURE adds [L -> .L,S] and [L -> .S]; the dot before S then adds [S -> .〈L〉] and [S -> .id]. The distinct-item count is 1 + 2 + 2 = 5.

LR(0) canonical item sets

Question 9: decide which items share a canonical set

Consider the following grammar.
S -> S * E
S -> E
E -> F + E
E -> F
F -> id
Consider the following LR(0) items corresponding to the grammar above.
(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> F + .E
Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

A. (i) and (ii)
B. (ii) and (iii)
C. (i) and (iii)
D. None of the above

Answer: D. Shifting * from [S -> S . * E] reaches item (i); its closure adds dot-at-start E and F items, not (ii) or (iii). Shifting F reaches item (ii), while shifting + from (ii) reaches item (iii). Their kernels differ, so no listed pair shares a set.

Compiler phase connections that appear beside parsing

Question 10: match compiler tasks to their foundations

Match the following:
(P) Lexical analysis
(i) Leftmost derivation
(Q) Top down parsing
(ii) Type checking
(R)Semantic analysis
(iii) Regular expressions
(S) Runtime environments
(iv) Activation records

A. P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii
B. P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv
C. P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv
D. P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii

Answer: B. Map each task before looking at the combinations: lexical analysis uses regular expressions, top-down parsing constructs a leftmost derivation, semantic analysis includes type checking, and runtime environments use activation records. Those four matches select B and give a reusable elimination method.

How bottom-up parsing and LR(0) are tested

The questions fall into four recurring demand types:

• Classification: Questions 1, 2, and 10 separate related compiler ideas.

• Reverse-production counting: Question 3 counts grammar applications before reversing them.

• Handles: Questions 4 and 5 test the definition and a reduction trace.

• Item-set construction: Questions 6 to 9 demand dot movement, closure, and state comparison. A written method prevents guesswork.

For LR(0) item sets, revise with the same checklist every time:

1. Augment the grammar.

2. Write the kernel.

3. Close every non-terminal after a dot.

4. Remove duplicate items.

5. Count only after the set stops growing.

LR(0) has no lookahead or FOLLOW filtering, while SLR(1) uses FOLLOW sets to decide where completed-item reductions are valid. For another mixed set, work through Parsing MCQs: 12 Solved GATE Questions and Answers. The Compiler Design MCQs hub is the broader subject-level practice route.

LR(0) MCQs: the short version and next step

Bottom-up means rightmost derivation in reverse. A handle is the next RHS occurrence to reduce. GOTO moves the dot first, CLOSURE expands afterwards, and LR(0) never consults lookahead.

Now retry Questions 3, 6, 7, 8, and 9 without viewing the explanations. Their answers are 7, 5, 8, 5, D in order, but the real test is whether your written steps reproduce them. Use the GATE Test Series when you want structured practice, or explore GATE CS Exam Preparation when you need broader subject coverage.