retagged by
12,337 views
19 votes
19 votes

Consider the following  grammar.

  • $S \rightarrow aSB \mid d$
  • $B \rightarrow b$

The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is ___________.

retagged by

2 Answers

Best answer
33 votes
33 votes

In parse tree, all the non terminals are reductions. So total 7 reductions.

edited by
28 votes
28 votes
Given string : aaadbbb

 

Bottom-up parsers : rightmost derivation in reverse.

S -> aSB

S -> aSb

S -> aaSBb

S -> aaSbb

S -> aaaSBbb

S -> aaaSbbb

S -> aaadbbb

So, there are 7 steps.
Answer:

Related questions

15 votes
15 votes
5 answers
2
Arjun asked Feb 12, 2020
9,051 views
Let $\mathcal{R}$ be the set of all binary relations on the set $\{1,2,3\}$. Suppose a relation is chosen from $\mathcal{R}$ at random. The probability that the chosen re...
15 votes
15 votes
4 answers
3
Arjun asked Feb 12, 2020
9,065 views
Let $G$ be a group of $35$ elements. Then the largest possible size of a subgroup of $G$ other than $G$ itself is _______.
12 votes
12 votes
2 answers
4