The Gateway to Computer Science Excellence
+21 votes

Consider the following translation scheme. 

  • $ S\rightarrow ER$
  • $ R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon $
  • $ E\rightarrow F+E\left \{ print('+'); \right \}\mid F $
  • $ F\rightarrow (S)\mid id \left \{ print(id.value); \right \} $

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '$2 * 3 + 4$',  this translation scheme prints 

  1. $2 * 3 + 4$
  2. $2 * +3 \ 4$
  3. $2 \ 3 * 4 +$
  4. $2 \ 3 \ 4+*$
in Compiler Design by Active (3.3k points)
edited by | 2.6k views
What will be the Tree Of the above Grammar
what is ans now ??
Top-down parsing and bottom-up parsing yield different answers to this question. Can anybody confirm which one is to be followed?
@Vishal Top down and BU parser should always give the same result

3 Answers

+30 votes
Best answer

It will be D. Make a tree and perform post order evaluation.

by Boss (19.9k points)
edited by
The grammar also has print statements in it how to make a tree of that ??
I am getting C as answer.
+ is having higher precedence so it need to resolved first, so (d) .

in option (c) * is having higher precedence which is wrong
c will not be as you have to complete the E before printing *,and to complete E you have to print the plus from F+E{print +}

Why to perform perform post order evaluation ??

@Gabbar ,Here We need to perform left to right DFS instead of post order traversal bcz it is L-attributed SDT.

Correct Me !!!
I think if you go through L to R also gives the same ans....

But here { } are evaluated after  left and Right has been processed...Left right root post order...
@gabbar r u sure ?
one thing i know that ...action can be placed at any position and it executed immediately when all its left hand side symbols processed when actions are inside the production body.

when all actions are end of production body simply do post order ....

if you know than tell us ! i know this much !

I think in order traversal is performed means when we first time visit the node then associated value with node will be printed


If we evaluate it from Left to Right we get C as answer, i believe there is some ambiguity in question. Here is parse tree

@Arjun sir, I am not finding any method to implement this SDT during any kind of parsing.

1) given grammer is not $LL(1)$ because of this production $E->F+E | F$, so top down parsing is not possible.

2) given grammar is $L$ attributed grammar and Only for the $L$ attributed grammar made from $LL(1)$ we can always gurantee BUP is also not possible.

because of this reason, @stblue I think, we are getting two different trees for this.
As can be seen in the screenshot of pdf attached by saurabh, it is confirmed that its L attributed (as semantic actions are placed anywhere). L attributed SDT is parsed in depth first form. But I am not sure how it should evaluate the semantic actions. Should it be evaluated in postfix order or prefix order? Postfix indeed gives option d. However why we should resort to postfix order ? Can anyone summarize the whole solution?
0 votes
clearly here {} is present in between the variables in r.h.s hence we will go for top down parsing as it is L-attributed. Now refer the best answer for the figure.
by Active (1.8k points)
–3 votes

My Guesstimation: ..Usuallhy in this typ of question we perform top down left to right... but here  { } is given in this is S-attributed grammer(use bottom up parsing)

by Active (1.9k points)

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,647 questions
56,461 answers
100,242 users