Question

Consider the following grammer:
S $\to$ aSB|d
B $\to$ b

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

• A. 6
• B. 7
• C. 5
• D. 8

Answer 1

The correct option is B 7

Given string, aaadbbb
Bottom-up parser: rightmost derivation in reverse.
1. aaaSbbb {S$\to$ d}
2. aaaSBbb {B$\to$ b}
3. aaSBb {S$\to$ aSB}
4. aaSBb {B$\to$ b}
5. aSb {S$\to$ aSB}
6. aSB {B$\to$ b}
7. S {S$\to$ aSB}

Therefore, total 7 steps required.