GATE CSE 2013 | Question: 9

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 \rightarrow \epsilon$ and $A \rightarrow a$) to parse a string with $n$ tokens?

• A. $n/2$
• B. $n-1$
• C. $2n-1$
• D. $2^{n}$

Comments

For the sake of simplicity we also take it as:

in a worst case  (because they asked only maximum )

A->a

B->b

C->c

D->d

E-> e

F->f

for n=6 token stream we takes abcdef

so for a,b,c,d,e we got 5 reduce moves and , last one for f we got accepted state thats not a reduced move so finally we got 6-1=>n-1 reduced moves.

if may be they asked about minimum then :

we can take production like  A-> abcdef

there is no reduced move only accepted state. (however there will be more shift moves...)

it is going to be 0.

---

@Aks9639 I think there is something wrong in the worst case example, u need to add one more production S->ABCDEF to get desired input string, hence accepted state 'ABCDEF' reduced to S. One more doubt, why you hadn't count accepted state move as a reduced move?

---

@Nitesh Singh 2 You are right but if in the it says A->a is unit production then you assume it and then find answer on behalves of this ,and right answer id n-1 by taking A->a as unit production.

Answer 1

Take a+b*c ==5 tokens

                       *

                 /            \

          +                   c

     /          \

a               b

 

4 reductions

 

Hene answer is (B) n-1