GATE CSE 2016 Set 1 | Question: 46

Question

Consider the following Syntax Directed Translation Scheme $( SDTS )$, with non-terminals $\{S,A \}$ and terminals $\{a,b \}$.

          $S \to aA  \quad \{\text{print }1\}$

          $S \to a    \quad   \{\text{print }2\}$

          $A \to Sb  \quad \{\text{print }3\}$

Using the above $SDTS$ , the output printed by a bottom-up parser, for the input $aab$ is:

• A.  $1 \ 3 \ 2 $ 
• B.  $2 \ 2 \ 3  $ 
• C.  $2 \ 3 \ 1 $ 
• D.  syntax error

Answer 1

$\bf{aab}$ could be derived as follows by the bottom up parser:

$S \rightarrow a$$\color{blue}{\mathbf A}$ prints $\color{blue}{1}$
$\quad \rightarrow a$$\color{blue}{\mathbf S}$$b$ prints $\color{blue}{3}$
$\quad \rightarrow aab$  prints $\color{blue}{2}$
Now since the bottom-up parser will work in reverse of rightmost derivation, so it will print in bottom-up fashion i.e., $231$ which is option C.

Note that this can be easily visualized by drawing the derivation tree.

Comments

@PriyankaS

Okay lets's try and see what happens: Look from bottom to top

Now what, we don't have any Handles to reduce

$SA$

$S\underline{Sb}$

$S\underline{a}b$

$\underline{a}ab$

 

That's why we are not reducing it initially.

---

@Kushagra what is SA here ?

---

@PriyankaS

Initially, we are reducing S to aA, not to S→a.

In your answer, while traversing the tree you are reducing the left subtree using S→a rule (that's why you are printing an extra 2 initially), but the left subtree of the root is only considered when we reduce using S→aA rule.

 

 

Answer 2

Answer is C