Bottom-Up Parsing and Derivation Direction: Selecting the Correct Option

Verified Sources

Sep 13, 2026

In context-free grammar parsing, bottom-up parsers (e.g., shift-reduce parsing such as LR parsing) work by recognizing handles and reducing them to nonterminals, effectively building the parse tree from leaves toward the root. This reduction sequence corresponds to the rightmost derivation in reverse of the input sentence.

A helpful way to see this is: bottom-up parsing starts from the given string (the “leaf” form) and applies reductions until it reaches the start symbol. Those reductions mirror a derivation that, if run backward, would be a rightmost derivation.

Key terms:

bottom-up parser
rightmost derivation
handle
shift-reduce parsing

Correct choice: (ii) right most derivation in reverse.

Bottom-Up (Shift-Reduce) Parsing vs Derivations

Why bottom-up parsing matches “rightmost derivation in reverse”

Bottom-up parsing repeatedly:

shifts symbols onto a stack, and then
reduces a handle (a recognizable substring) into a nonterminal, until the stack contains the whole start symbol.

This is equivalent to taking a rightmost derivation and reversing it:

Rightmost derivation forward: $S \Rightarrow^* w$ by expanding the rightmost nonterminal each step.
Bottom-up parsing: starts from $w$ and performs the inverse operations (reductions) to reach $S$ .

So the mapping is specifically rightmost derivation in reverse, not leftmost derivation in reverse.

Linking reductions to a derivation direction

1
Step 1
The parser begins with the sentence $w$ on the tape (conceptually, as the current frontier).
2
Step 2
A handle is the substring that can be reduced next.
3
Step 3
Replacing that handle with the corresponding nonterminal performs one inverse derivation step.
4
Step 4
After a sequence of reductions, the stack contains the start symbol $S$ , completing the reverse derivation.
5
Step 5
Because each reduction corresponds to undoing expansions of the rightmost derivation choices, the overall effect is a rightmost derivation executed in reverse.

Memory trick

Bottom-up builds the tree from leaves → root, so think: derivation forward → root → leaves, hence reverse.

Common confusion: leftmost vs rightmost

The direction “reverse” is right for bottom-up, but the which derivation (leftmost vs rightmost) matters too. Standard results for shift-reduce/bottom-up parsing align with rightmost derivation in reverse.

Derivation direction intuition (forward vs reverse)

Expansion

Rightmost derivation (forward)

Expand the rightmost nonterminal each step until you obtain $w$ ."

Reductions

Bottom-up parsing (reverse)

Start from $w$ and apply reductions that undo those expansions, reaching $S$ ."

Matching parser strategy to derivation form

Which option corresponds to bottom-up parsing?

Quick justification for each option

Knowledge Check

Question 1 of 4

Q1Single choice

A bottom-up parser generates which form of derivation?

(i) right most derivation

(ii) right most derivation in reverse

(iii) right most derivation

(iv) left most derivation in reverse

Explore Related Topics

Lexical Analyzer Output in Compiler Design

In compiler design, the lexical analyzer’s sole output is a stream of tokens derived from the source code character stream.

It scans characters left‑to‑right, grouping them into lexemes that match language patterns.
Each lexeme is classified into a token category (e.g., ID, NUM, PLUS) possibly with attributes.
The token stream is handed to the parser, which builds the parse tree or AST.
Machine code, intermediate code, and parse trees are produced in later compilation phases, not by the lexer.

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

Top-Down Parsing: Choosing the Correct Answer

Browse all research articles