GATE CSE 2006 | Question: 59

Question

Consider the following translation scheme. 

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

Here $id$ is a token that represents an integer and $id.value$ represents the corresponding integer value. For an input $\text{‘}2 * 3 + 4\text{’},$  this translation scheme prints 

• A. $2 * 3 + 4$
• B. $2 * +3 \ 4$
• C. $2 \ 3 * 4 +$
• D. $2 \ 3 \ 4+*$

Comments

What will be the Tree Of the above Grammar

---

i think D. is ans since + having higher precedency over * ...In ur tree * having higher precedence than + ...

---

The precedence is enforced by grammar, so if I am able to draw the tree using the grammar shouldn't that be correct?
My understanding is that if + has higher precedence than * then using that using no tree should give higher precedence to *. Is that wrong to assume?

---

Yes we should not assume that

---

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

---

This converts the infix expression to postfix, where the + has more priority than *.

---

Similar question: GATE2003-58

Answer 1

Correct Option: D

Make a tree and perform post order evaluation.

Comments

@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.so 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?

---

@Manu Thakur

​​​​​​i think this syntax tree will not work as it uses the production F->(S). this production adds parenthesis to the final outcome , which is not given in the required expression

 

Let me know if my understanding is wrong

Answer 2

This grammer is actually left recursive removed grammer of S-->E*E|E  E-->F+E|F and so on. So + have highest precedence than * . So although the grammer give two parse tree for the given i/p string.. The correct ans should be which allow + have higher precedence than * .. i.e Option D.

Answer 3

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.

Answer 4

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