GATE 2020 CS Q.24: solution and answer

GATE 2020 · CSQ.24 · 1 mark · NAT

Consider the following grammar.

$S \to a S B ∣ d$
$B \to b$

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The parser takes 7 reduction steps to accept aaadbbb.

Official answer: 7Source: Official answer key, GATE 2020 CS (IIT Delhi)

A bottom-up parser traces a rightmost derivation in reverse. Each reduction undoes one production use, so the number of reductions equals the number of steps in the rightmost derivation.
Rightmost derivation of aaadbbb: $S \Rightarrow a S B \Rightarrow a S b \Rightarrow aa S B b \Rightarrow aa S bb \Rightarrow aaa S B bb \Rightarrow aaa S bbb \Rightarrow aaa d bbb$ Each step rewrites the rightmost nonterminal, and the final string is aaadbbb.
Count the productions used: $S \to a S B$ three times (one for each leading a), $B \to b$ three times (one for each trailing b), and $S \to d$ once.
Parser run: shift aaad, then reduce $S \leftarrow d$ (1 reduction). The stack is aaaS. Shift b, reduce $B \leftarrow b$ , then reduce $S \leftarrow a S B$ . Repeat this shift and two reductions for each of the three bs. The stack ends as S with the input empty, so the string is accepted.
Total reductions: $1 + 3 \times 2 = 7$ .

KEY IDEA

The number of reductions equals the number of production applications in the rightmost derivation. Here that is 3 uses of S -> aSB, 1 use of S -> d and 3 uses of B -> b.

WATCH OUT FOR

Counting only the reductions by S -> aSB and S -> d, which gives 4, and forgetting the three B -> b reductions. Another slip is counting shift moves as steps.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

GATE 2020 CS Q.24: solution and answer

Answer and solution

More Parsing questions