Grammar: $S\to aSB\mid d$, $B\to b$. The string $aaadbbb$ is derived as $S\Rightarrow aSB\Rightarrow aaSBB\Rightarrow aaaSBBB\Rightarrow aaadBBB\Rightarrow aaadbbb$ (rightmost derivation: replace $B\to b$ for each).
A bottom-up parser performs the **reverse** of the rightmost derivation. The reductions are: 1. $d\to S$ (1 reduction). 2. Three times $b\to B$ (3 reductions), one for each `b`. 3. Three times $aSB\to S$ (3 reductions).
Total $=1+3+3=\mathbf7$.
More Parsing and Syntax Analysis questions
GATE 2019 CS Q13– Which one of the following kinds of derivation is used by LR parsers?
GATE 2019 CS Q29– Consider the grammar given below: S → Aa A → BD B → b ε D → d ε Let a, b, d, and 36 be…
GATE 2019 CS Q53– Consider the augmented grammar given below: S' → S S → ⟨L⟩ id L → L,S S Let I…
GATE 2018 CS Q48– Consider the following parse tree for the expression a\#b36c36d\#e\#f, involving two…
GATE 2015 CS (CS1) Q18– Which one of the following is TRUE at any valid state in shift-reduce parsing?
GATE 2016 CS (CS1) Q55– The attributes of three arithmetic operators in some programming language are given below.…