retagged by
979 views

2 Answers

1 votes
1 votes

Since it is given that the grammar cannot have:
1) epsilon production
2) production of the form $A->a$

Consider the grammar:
$S->Sa l a$
If we were to derive the string "$aaa$" whose length is $3$ then the number of reduce moves that would have been required are shown below:
$S->Sa$
$S->Saa$

$S->aaa$

This shows us that it has three reduce moves. The string length is $3$ and the number of reduce moves is also $3$. So presence of such kinds of production might give us the answer "$n$" for maximum number of reduce moves. But these productions are not allowed as per the question.Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed "$n$" where “$n$" denotes the length of the string
 

3) No unit productions
Consider the grammar:
$S->A$
$A->B$
$B->C$
$C->a$
If we were to derive the string "$a$" whose length is $1$ then the number of reduce moves that would have been required are shown below:
$S->A$
$A->B$
$B->C$
$C->a$
This shows us that it has four reduce moves. The string length is $1$ and the number of reduce moves is $4$. So presence of such kind of productions might give us the answer "$n+1$" or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.Now keeping in view the above points suppose we want to parse the string "$abcd$". $(n = 4)$ using bottom-up parsing where strings are parsed.finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving rightmost derivations only.We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon- and unit-production (i.e., of type $A->E$ and $A->B$) and no production of the form $A->a$) as follows:

$S->aB$
$B->bC$
$C->cd$

The Right Most Derivation for the above is:
$S->aB (Reduction 3)$
$S->abC(Reduction 2)$
$S->abcd (Reduction 1)$

We can see here the number of reductions present is $3$.
We can get less number of reductions with some other grammar which also doesn't produce unit or epsilon productions or production but in question we want maximum number of reduce move so it will be n-1 .

number of reduce move=$\leqslant n-1$,here $n$ is length of string.

1 votes
1 votes

Option (B)

Take example:

$S \rightarrow AB$
$A \rightarrow aa$
$B \rightarrow bb$

For string of length $n=4$ as $aabb$:

Stack Input Action
$ aabb$ Shift
$a abb$ Shift
$aa bb$ Reduce $A\rightarrow aa$
$A bb$ Shift
$Ab b$ Shift
$Abb $ Reduce $B \rightarrow bb$
$AB $ Reduce $S \rightarrow AB$
$S $ Accept

For 4 tokens, reduce moves are 3 or $n – 1$

Answer:

Related questions

2 votes
2 votes
5 answers
1
admin asked Mar 30, 2020
1,900 views
In a compiler, keywords of a language are recognized duringparsing of the programthe code generationthe lexical analysis of the programdataflow analysis
0 votes
0 votes
1 answer
2
admin asked Mar 30, 2020
742 views
A system program that combines the separately complied modules of a program into a form suitable for executionassemblerlinking loadercross compilerload and go
0 votes
0 votes
0 answers
4
admin asked Mar 30, 2020
1,166 views
Which of the following statements is/are TRUE for an undirected graph?Number of odd degree vertices is evenSum of degrees of all vertices is evenP onlyQ onlyBoth P and QN...