The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
333 views

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

asked in Compiler Design by Junior (517 points)
retagged by | 333 views
0
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$
0
As soon as you encounter the symbol semantic action has to be performed,  so answer should be 011112.
0
bottom up is mentioned ..semantic action is performed after reduction
0
How does Bottom Up changes the question ? what if I parse the final tree in Preorder manner ?
0
if you do preorder then you will get 011112 as ans
0
@Lokesh. I think its bottom-up, left-right where left to right is given precedence. So, even I think 011112 should be the answer.
0
@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.

2 Answers

0 votes
Ans is option b
answered by Junior (837 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.

answered by

Related questions

0 votes
0 answers
2
0 votes
0 answers
3
0 votes
0 answers
5


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

43,964 questions
49,519 answers
162,503 comments
65,759 users