Question

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar 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ⁿ

Answer 1

Correct Answer - Option 2 : n – 1

Explanation:

Grammar with no epsilon- and unit-production

S → PQ

P → pp

Q → qq

Derive String: ppqq

S → PQ

S → ppQ

S → pppqq

String length = 4

Production needed = 4 – 1 = 3.