The GATE Grind

GATE 2020 CS – Question 34

Compiler Design · Parsing and Syntax Analysis · 1 mark · Numerical answer

Consider the following grammar.

$S\to aSB\mid d$

$B\to b$

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 7 to 7

Explanation

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

All Parsing and Syntax Analysis questions →