GATE CS Mastery
Cheat sheets

GATE CS 2020 · Compiler Design

Question 34

NATPrinted as CS Q.241 markNo negative markingEasy (estimate)

Question

Consider the following grammar.

S→aSB∣dB→b\begin{aligned} S &\to a S B \mid d \\ B &\to b \end{aligned}

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

Official answer and solution
Official answer
7
From
Official GATE 2020 answer key

Solution

Trace the bottom-up shift-reduce parse steps (reverse rightmost derivation) for the string aaadbbb.

Given grammar:

  1. S→aSBS \to a S B
  2. S→dS \to d
  3. B→bB \to b

A bottom-up parser reconstructs the rightmost derivation in reverse:

  1. aaadbbb  ⟹  aaaSbbba a a d b b b \implies a a a S b b b (Reduction 1: using S→dS \to d)
  2. aaaSbbb  ⟹  aaaSBbba a a S b b b \implies a a a S B b b (Reduction 2: using B→bB \to b)
  3. aaaSBbb  ⟹  aaSbba a a S B b b \implies a a S b b (Reduction 3: using S→aSBS \to a S B)
  4. aaSbb  ⟹  aaSBba a S b b \implies a a S B b (Reduction 4: using B→bB \to b)
  5. aaSBb  ⟹  aSba a S B b \implies a S b (Reduction 5: using S→aSBS \to a S B)
  6. aSb  ⟹  aSBa S b \implies a S B (Reduction 6: using B→bB \to b)
  7. aSB  ⟹  Sa S B \implies S (Reduction 7: using S→aSBS \to a S B)

Counting the reduction steps:

  • 1 reduction for d→Sd \to S
  • 3 reductions for b→Bb \to B
  • 3 reductions for aSB→Sa S B \to S
  • Total reduction steps = 1+3+3=71 + 3 + 3 = 7.
Final answer

7

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2020 Computer Science and Information Technology (CS)
Question
34 of 65, printed as CS Q.24
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.