The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
3.7k views

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}$
asked in Compiler Design by Veteran (342k points)
edited by | 3.7k views
0
But the grammar with unit production is of Form A-->B. i.e. a non terminal on the RHS.
0
This is straight from GATE paper :P
0
sir a/c to question we dont have to use either unit production or  A->a type production?
+2
Question ask for number of reduce move. for bottom up parsing number of reduce move is equal to the number of internal node. answer does not change for A > a or A > aa is present in production.
+2
If we have A-->B in the grammar, then more than (n-1) reductions are possible.
+1

@vishalshrm539 yes exactly ... I think they should have also given that A->B type productions are not there in the grammar ... 

4 Answers

+38 votes
Best answer

Ans will be B

$A \rightarrow BC$

$B \rightarrow aa$

$C \rightarrow bb$

now suppose string is $aabb$

then

$A \rightarrow BC$ (reduction $3$)

    $\rightarrow aaC$ (reduction $2$)

    $\rightarrow aabb$ (reduction $1$)

$n = 4$

and number of reductions are $3$ so $n-1$

answered by Junior (805 points)
edited by
0
Just for the sake of knowledge. It is in CNF. and you must know how many steps does it take. Its 2n-1.
+48
Here, in this question we are not supposed to have A -> a, even though that is not a unit production. Obviously a mistake in question, but we must follow what is written in question. Answer to this question is n-1, as given by GATE key. So, if similar thing happens in GATE, follow the question word by word and never try to correct the question.
+6
ITS NOT CNF
+3
@arjun sir since the question defines unit production as A→a we can use any number of productions of form A→B
+4
@arjun sir,

I have same doubt if we use question data we can use as many productions of type  A->B, the number of reduce moves won't be n-1, I guess.
0
@rahulkr

I think the approach u are using is not correct. Consider the following example:

A->BC

B->aaa

C->bbb

now suppose string is aaabbb

then

A->BC(reduction 3)

->aaaC(reduction 2)

->aaabbb (reduction 1)

n = 6

and number of reductions are 3 which is not n-1
+4
@anchit

max number of reductions is asked

so in ur example in a single sttep you are reducing more than 1 terminal which cannot give max value

only one terminal should be reduced in each step only then u get max number of reductions
+13 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

answered by Active (1.6k points)
+3 votes
The answer is C.

Take,

S-->AB

A-->a

B-->b.

Derive ab. you'll have 3 reduce moves.
answered by Boss (19.7k points)
0

How do you come to the conclusion that this is the maximum possible number of reduce moves?

+3

You take any Grammar of this form. The answer will be 2n-1.

+3

but in the question it is given that production of the form Aa  is not allow.

+4
see my comment on the question. That's a mistake actually.

Unit productions are of type

A-->B. there shouldn't be any terminal on the RHS.
+2
thanks #GateKeeda :)
0

here  i m taken each possible case.   case1-> A->epsilon(Null prod) and A-> B (Unit prod.) not allowed then for 'n' length token how many maximum reduce move required .  lets take example -  for string 'ab'  S->AB : A->a , B->b then here required 3 reduced moves . lets take other string  ex- abc for that i do S->AB , A->DE , D->a , E->b ,B->c so it is 5  so we can say in general answer will be 2n-1 

case 2 . if  A-> epsilon(Null prod) and A-> a  are not allowed  but unit production allowed then for that if i  take string 'ab' then for that S->A , A->B, C->D, D->E and so on ..at last producion i write like as K->ab  so here for that we can't write a general form . 

case3. if A-> epsilon(Null prod) and A-> a  are not allowed  and also unit production not allowed then take string 'ab' for that you can write only S->ab for that required 1 reduce  and for string 'abcd' we can write S->AB , A->ab ,C->cd  so required 3  so in general required 'n-1' reduce . then  according to arjun sir no need to be change the question so i m going wid "n-1"

0
If grammar is S->BAC ,A->aa ,B->bb and C->cc then for generating aabbcc we need 4 steps.

is grammar should be in cnf?
+1

@vaishali    here they are not mention wheather we follow CNF or not just simply think that maximum how many step can we take to genearte a string without using any production A->a and unit production(A->B) and null production

S->AB

B->CD

C->bb

D->cc

A->aa so 5 steps required to generate 'aabbcc'

 

0
Thank you, I get it.
0 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
answered by Active (2.4k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,527 questions
42,803 answers
121,619 comments
42,166 users