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

Just a doubt... If the grammar given is not CLR(1) and the string is derivable will it be considered as parsable and sdt would be possible..??

---

@monanshi I did not get why itwill print 231 pls explain

---

@ shweta1920 if you draw parse tree for i/p aab then you will get 

---

I have given question say that used bottom-up parser but I used Top-down parser will get the same answer.

So we can say that SDT(Syntax-Directed Translation) used both parser(either Top-down or Bottom-up parser) give the same answer.

please correct me if I'm wrong?

---

monashi awesome explanation nothing is required to add

---

@Lakshman Patel RJIT yes correct!

---

just a doubt...

When we draw any parse tree, then if any terminal is reducing to some production given, like here, 

S <-- a  as marked by (1), so why can't 2 is printed due to that.

 

---

@PriyankaS

see this, I used TDP (Top-Down Parser)

---

Thank you, I understood it.

But in case of bottom up parser, I am not able to understand what am I doing wrong...

In bottom up parsing, we see reduction, so when a is reducing to S then why are not we printing 2 there [ at (1) ]? Please help me in this.

Thank you.

---

@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