Log In
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
edited by
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
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

4 votes
1 answer
$Q_1 \Rightarrow$ For synthesized attribute, value is only computed when symbol is on the _____ side of production. For inherited attribute, value is computed in productions where symbol is on the _____ side. $1.$ Left, Right $2.$ Right, Right $3.$ Right, Left $4.$ Left, ... $b).$ Search where the function is called $c).$ Refers to global variable $d).$ None of these
asked Nov 11, 2016 in Compiler Design mcjoshi 431 views
3 votes
1 answer
Consider the following grammar and their Syntax Directed Translation (SDT) rules. (Here id represent a integer and id.val is value of that integer) S1: Given SDT is L-attributed and using L-attributed evaluation the value of the expression 4 * 6 + 3 * 7 is 84. S2: ... to the above SDT.? My doubt here: Is there any difference in the way of evaluation of L-attributed SDT and S-attributed SDT ?
asked Jan 7, 2019 in Compiler Design Shivam Kasat 593 views