Register

GO Classes CS Test Series | Mock GATE | Test 4 | Question: 36

• retagged by
2,406 views
27 27 votes
Consider the following grammar:
$$
\begin{aligned}
\text{S} \rightarrow & \text{S} \text { and } \text{S} \\
\mid & \text{S} \text { or } \text{S} \\
\mid & \text{T} \\
\mid & \text { a } \\
\text{T} \rightarrow & \text { a }
\end{aligned}
$$
In this grammar $\text{S}$ and $\text{T}$ are the non-terminals and $\text{S}$ is the start symbol$\text{; "and", "or", }$and $\text{"a"}$ are terminal symbols.
How many parse trees are there for the string: "$\mathrm{a \;and} \;\text{a or a}$"

3 Answers

33 33 votes
16 is the answer

 

12 12 votes
There are $16$ possible parse trees given the above grammar.

First, either $\text{and}$ can have higher precedence than $\text{or}$ or $\text{or}$ can have higher precedence than and. This gives two possible parse trees to produce the $\text{and}$ and $\text{or}.$

What remains is the three $\text{S}$ non-terminals. Each $\text{S}$ non-terminal produce the terminal a via the production $\text{S} \rightarrow \text{a}$ or the production $\text{S} \rightarrow \text{T} \rightarrow \text{a}.$ Each $\text{S}$ non-terminal can choose a production independently from the others so there are $2^3=8$ parses.

In total, we have $2 * 2^3=16$ possible parse trees.
• edited by
1 1 vote
we will be having two parse trees but we can extend it by sometimes putting  S as  T or a ,so for 3 places 2^3 and similar for other tree as well ,

so total 8 + 8 =16
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes CS Test S...Next → · GO Classes CS Test S...
← Previous in category · GO Classes CS Test S...Next in category → · GO Classes CS Test S...
Position:
Show:

Related questions

9 9 votes
1 1 answer
1.2k
1.2k views
GO Classes asked Jan 19, 2023
1,248 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 63
Consider the following $\text{LL(1)}$ grammar.$$\begin{aligned}& \text{S} \rightarrow \text{A} \\& \text{A} \rightarrow \mathbf{a} \text{BE} \\& \text{B} \rightarrow \mat...
21 21 votes
3 3 answers
3.7k
3.7k views
GO Classes asked Jan 19, 2023
3,662 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 64
Consider the following already augmented $\text{LR(1)}$ grammar -$$\begin{aligned}& \text{S}^{\prime} \rightarrow \text{S} \\& \text{S} \rightarrow \text{aAB} \mid \text ...
14 14 votes
3 3 answers
2.2k
2.2k views
GO Classes asked Jan 19, 2023
2,168 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 35
Consider following two states $\text{I}_j$ and $\text{I}_k$ in $\operatorname{SLR}(1)$ parsing. Here $\alpha, \beta$ and $\gamma$ are non empty strings.$$\text{I}_k \boxe...
6 6 votes
2 2 answers
1.3k
1.3k views
GO Classes asked Jan 19, 2023
1,307 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 44
Consider the following tables $\mathrm{R}, \mathrm{S}$ and $\mathrm{T}$ :$$\overset{\textbf{R}}{\begin{array}{|cc|} \hline \mathrm{A} & \mathrm{B} \\\hline 1 & 2 \\3 & 2 ...