Testbook Test Series: Compiler Design - Syntax Directed Translation

Question

Let Grammar be with these transitions:

S -> a{print "0"}A

A -> b{print "1"}B

A -> c{print "2"}

A -> ε{print "-"}

B -> d{print "1"}A

B -> ε{print "0"}

What is the output produced for input string  abdbdc using Bottom-Up Parsing with above translations:

A) 0211-10

B) 0211110

C) 0111-20

D) 0111012

Comments

This is an L-attributes SDT but they mentioned to do Bottom Up parsing So,

ans should be 211110...close to B

and b if second production of will be $A\rightarrow c\{print\ "2" \}B$

---

As soon as you encounter the symbol semantic action has to be performed,  so answer should be 011112.

---

bottom up is mentioned ..semantic action is performed after reduction

---

How does Bottom Up changes the question ? what if I parse the final tree in Preorder manner ?

---

if you do preorder then you will get 011112 as ans

---

@Lokesh. I think its bottom-up, left-right where left to right is given precedence. So, even I think 011112 should be the answer.

---

@Lokesh. This is the right reason.

S

-> aA

->abB

->abdA

->abdbB

->abdbdA

->abdbdc

 

Now, we trace the derivation in reverse. So, 'c' gets reduced to A. So, 2 should get printed.

Next, dA must get reduced to B. But before A, "print 1" should have got executed.

 

So, till this output is 12.

 

And so on.

Answer 1

Ans is option b

Answer 2

For bottom up we used to make right most derivation .so if we parse from bottom to top after creation of anoted parse tree the closest answer we got is as option b

 

          s = aA = abB = abdA = abdbB = abdbdA = abdbdc i have make use of RMD so by going bottom to top if u see the c is patches to firstly A at that u should look the semantic rule given just use that while deriving so it will print 2 and after dA is patches  to  B so use semantic rule i says print 1 likewise u should go till the end the result u will found that 211110 which is closer to 0211110 i dont know why they have given 0211110 the correct answer is even 211110. so option B is correct.