Skip to content
GATETECH
Official PYQ · 2020Q24Parsing (LL, LR)NAT1 mark

GATE CS 2020 Q24 — Parsing (LL, LR)

Explain with AI

Consider the following  grammar.

  • S→aSB∣dS \rightarrow aSB \mid d
  • B→bB \rightarrow b

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbbaaadbbb is ___________.

View worked solution

Answer: 7

A bottom-up parser performs reductions in the exact reverse order of a rightmost derivation.

Let us find the rightmost derivation for the string aaadbbbaaadbbb using the grammar:

  1. S→aSBS \rightarrow aSB
  2. S→dS \rightarrow d
  3. B→bB \rightarrow b

Rightmost Derivation:

S⇒aSB‾⇒aSb‾(using B→b)⇒a(aSB‾)b=aaSB‾b(using S→aSB)⇒aaSb‾b(using B→b)⇒aa(aSB‾)bb=aaaSB‾bb(using S→aSB)⇒aaaS‾bbb(using B→b)⇒aaadbbb(using S→d)\begin{align*} S &\Rightarrow a S \underline{B} \\ &\Rightarrow a S \underline{b} & (\text{using } B \rightarrow b) \\ &\Rightarrow a (a S \underline{B}) b = aaS\underline{B}b & (\text{using } S \rightarrow aSB) \\ &\Rightarrow aaS\underline{b}b & (\text{using } B \rightarrow b) \\ &\Rightarrow aa(aS\underline{B})bb = aaaS\underline{B}bb & (\text{using } S \rightarrow aSB) \\ &\Rightarrow aaa\underline{S}bbb & (\text{using } B \rightarrow b) \\ &\Rightarrow aaadbbb & (\text{using } S \rightarrow d) \end{align*}

The total number of production steps in the derivation is 77. Since each production step corresponds to exactly one reduction step in the bottom-up parser, the number of reduction steps is 7.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Parsing (LL, LR) questions