The Gateway to Computer Science Excellence
+2 votes

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

in Compiler Design by Junior (537 points)
edited by | 359 views
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.


-> aA







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.

2 Answers

0 votes
Ans is option b
by Junior (627 points)
0 votes

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.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,131 answers
93,303 users