in Compiler Design edited by
12,504 views
39 votes
39 votes

Consider the translation scheme shown below.

  • $S \rightarrow T\;R$
  • $R \rightarrow + T \{\text{print}(‘+’);\} R\mid \varepsilon$
  • $T  \rightarrow$ num $\{\text{print}$(num.val)$;\}$

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘$9 + 5 + 2$’, this translation scheme will print

  1. $9 + 5 + 2$
  2. $9 \ 5 + 2 +$
  3. $9 \ 5 \ 2 + +$
  4. $+ + 9 \ 5 \ 2$
in Compiler Design edited by
12.5k views

2 Comments

edited by

Similar question: GATE2006-59

2
2

The catch here is right the parse table  along with the print statements and print  when you encounter print(‘+’)

or print(num.val)

Don't print the +  that is in the start of    + T  R 

 Here don't get  into confusion of printing the first plus before T 

we have to print  +  that is given as semantic rule after we processed T then     we have to print this  {print(‘+’);} 

 

not the intial +  before T

0
0

4 Answers

56 votes
56 votes
Best answer

Correct Option: B
$9\ 5+2+$

edited by

4 Comments

Could someone explain this solution in words a little bit ?
Im having trouble in understainding how

9+5 prints 95+ ?

9+5+2

  • T+5+2  ( T-> num  output : 9 )
  •  

Im stuck at here , How to proceed ?

0
0
in L attribute we evaluate the node first time when we visit it.

so according to this answer should be 9+5+2 ???
1
1
Correct me if I am wrong .. Since given SDT is L-attributed SDT,we gotta evaluate it depth first left to right traversal of the parse tree 🌲 ??
0
0
Nice
0
0
25 votes
25 votes
InputTranslationOutput
9 + 5 + 2S → T R 
9 + 5 + 2T  → num {print(num.val);}9
+ 5 + 2R → + T {print(‘+’);} R (the + is simply consumed as there is no print corresponding to it)
5 + 2T  → num {print(num.val);}5+
+ 2 R → + T {print(‘+’);} R 
2T  → num {print(num.val);}2+

So, output 95+2+. Option B.

by

4 Comments

edited by

@amarVashishth 

while creation of parse tree, are we supposed to place the semantic actions in the parse tree in the same order they appear in the grammar?

I was considering the semantic action after complete reduction of +TR into R and hence getting 952++ .

Could you please confirm if my understanding regarding placement of semantic actions is now correct?

 

Another query : is depth first, left to right traversal the same as top down parsing?

0
0

No the question is not ambiguous. In case of bottom up parsing, see here the semantic rule is present between T and R.

R → + T {print(‘+’);} R∣ε

so while traversing through the parse tree, you need to evaluate between T and R and thus take the semantics action given.

 

0
0

Well explained @Arjun sir

0
0
3 votes
3 votes

Reduce the Expression Rightmost in Reverse:- (Seeing the first matching reducible symbol)
9 + 5 + 2ε  (Print 9 and reduced to T)
> T + 5 + 2ε  (Print 5 and Reduced to T)
> T + T  + 2ε (+T print + and can't be reduced)
> T + T + Tε   (Print 2 and reduced to T)
> T + T +Tε (+T print + and can't be reduced)
> T + T +TR (ε Reduced to R)
> T +TR (+TR reduced to R)

>TR (+TR reduced to R)

>S (TR reduced to S)

9 5 + 2 +

1 comment

what is the 3rd step +T print + and can’t be reduced? you cannot call a half production…. call a complete or dont call at all.

0
0
1 vote
1 vote

Answer is B

Answer:

Related questions