GATE CSE 2020 | Question: 24

Question

Consider the following  grammar.

• $S \rightarrow aSB \mid d$
• $B \rightarrow b$

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

Comments

| Stack   | Input | Action           |
| ------- | ----- | ---------------- |
| $aaad   | bbb$  |                  |
| $aaaS   | bbb$  | reduction S->d   |
| $aaaSb  | bb$   | reduction B->b   |
| $aaaSB  | bb$   | reduction S->aSB |
| $aaSb   | b$    | reduction B->b   |
| $aaSB   | b$    | reduction S->aSB |
| $aSb    | $     | reduction B->b   |
| $S      | $     | reduction S->aSB |

Note : Skipped shift steps. 

---

Nice question

Answer 1

In parse tree, all the non terminals are reductions. So total 7 reductions.

Comments

Can’t we take the string and try to reach to the initial symbol? That is how bottom up works right?

---

Yes, you can use that approach as well.

---

can we think of the idea from Gribeck Normal form

Answer 2

Given string : aaadbbb

 

Bottom-up parsers : rightmost derivation in reverse.

S -> aSB

S -> aSb

S -> aaSBb

S -> aaSbb

S -> aaaSBbb

S -> aaaSbbb

S -> aaadbbb

So, there are 7 steps.