edited by
32,845 views
83 votes
83 votes

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?

  1. $n/2$
  2. $n-1$
  3. $2n-1$
  4. $2^{n}$
edited by

13 Answers

Best answer
82 votes
82 votes

Ans will be B

  • $A \rightarrow BC$
  • $B \rightarrow aa$
  • $C \rightarrow bb$

Now suppose string is $aabb.$ Then

$A \rightarrow BC$ (reduction $3$)
$\quad \rightarrow aaC$ (reduction $2$)
$\quad \rightarrow aabb$ (reduction $1$)

$n = 4$ and number of reductions is $3.$ So, $n-1$

edited by
33 votes
33 votes

Answer B option.

To get maximum number of Reduce moves, we should make sure than in each sentential form only one terminal is reduced. Since there is no unit production, so last 2 tokens will take only 1 move.

So To Reduce input string of n tokens, first Reduce n-2 tokens using n-2 reduce moves and then Reduce last 2 tokens using production which has . So total of n-2+1 = n-1 Reduce moves.


Example for this could be :

S-->aA

A-->bB

B-->cC

C->de


Generate string of 5 tokens as

S-->aA

  -->abB

  -->abcC

  -->abcde

So first we take 3 steps to reduce ' abc ' and then take 1 step to produce ' de '. So total (5-2) + 1 = 4 Reduction moves

6 votes
6 votes
The answer is C.

Take,

S-->AB

A-->a

B-->b.

Derive ab. you'll have 3 reduce moves.
2 votes
2 votes
Input length = n;

From backward 1st level reduce move = n/2;

2nd level reduce move = n/4;

3rd level reduce move = n/8;

and so on....

so total no of reduce move: n/2+n/4+n/8+n/18+......+1

which is equal to ~=n-1
Answer:

Related questions