GATE2013_9

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?

(A) n/2

(B) n−1

(C) 2n−1

(D) 2n

Answer:- (B)
Exp:-
      A->BC
      B->bb
      C->cc
now suppose string is bbcc
A->BC  (reduction 3)
->aaC  (reduction 2)
->aabb (reduction 1)
n = 4
and number of reductions are 3 so n-1 

0Comment