What is the maximum number of reduce moves that can be taken

Home » Compiler Design » Compiler design miscellaneous » Question

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammer with no epsilon-and unit-production (i.e. of type A → ε and A → a) to parse a string with n tokens?

1. n / 2
2. n – 1
3. 2n – 1
4. 2ⁿ

Correct Option: B

Let the grammar is:
A → BC
B → aa
C → bb
now let the string w = aabb then
A → BC(reduction 3)
→ aaC (reduction 2)
→ aabb (reduction 1)
n = 4 and number of productions are 3 so n - 1