GATE CSE 2004 | Question: 45

Question

Consider the grammar with the following translation rules and $E$ as the start symbol$$\begin{array}{lll}
E \rightarrow   E_ 1\# \: T & \qquad\left\{E.value = E_1.value * T.value\right\}\\
\qquad\mid T & \qquad \{E.value = T.value\}\\
T \rightarrow  T_1 \& \: F &\qquad \{T.value = T_1.value + F.value\}\\
\qquad\mid F&\qquad \{T.value = F.value\}\\
F \rightarrow \text{num}&\qquad \{F.value=num.value\}
\end{array}$$

Compute $E.value$ for the root of the parse tree for the expression:$2$ # $3$ & $5$ # $6$ & $4$

• A. $200$
• B. $180$
• C. $160$
• D. $40$

Comments

C   will   be ans.

---

GATE 2004_45
 original  question was :

Consider the grammar with the following translation rules and E as the start symbol

E→ E1 # T       {E.value=E1.value ∗ T.value}
        | T             {E.value=T.value}
T→T1 & F        {T.value=T1.value + F.value}
       | F               {T.value=F.value}
F→num            {F.value=num.value}

---

please draw parse tree?

---

Parse tree for this, please. I don’t know how to use E1 and T1 in the tree.

---

C

---

Solve without parse tree

---

While creating parse tree for this problem if you are confused whether to take which rule just see how much inorder traversal you have done from the given expression.

---

All questions related to Syntax Directed Translation Scheme(SDTS):

Compiler Design: GATE CSE 1995 | Question: 2.10

Compiler Design: GATE CSE 1996 | Question: 20

Compiler Design: GATE CSE 2000 | Question: 19

Compiler Design: GATE CSE 2016 Set 1 | Question: 46

Compiler Design: GATE CSE 2021 Set 1 | Question: 26

Compiler Design: GATE CSE 2022 | Question: 55

Compiler Design: GATE CSE 2023 | Question: 50

Compiler Design: GATE CSE 2003 | Question: 58

Compiler Design: GATE CSE 2004 | Question: 45

Compiler Design: GATE CSE 2006 | Question: 59

Answer 1

Here # is multiplication and & is addition by semantics rules given in the question.
By observation of productions,

1. here &(+) is higher precedence than #(*), because & is far from starting symbol
2. both &,# are left associative

So, we can solve the expression as $((2*(3+5))*(6+4)) =160$

Answer is (C).

Comments

@Sachin+Mittal+1

Sachin sir ,

So everytime ..to decide precedence and asscociativity operator relation table constructed using Lead and Trails is needed ??

Can't we answer it using this argument 

"Operator which is at lower level in the grammar is termed to have higher precedence."

---

@Sachin Mittal 1

can you explain a bit more about trailing and leading method.. Or are there any good references for it?

---

Rackson  No they are symbolically categorized to differentiate the one on left hand side and the one right hand side if they are different then we would never be able to determine the string 

Answer 2

syntax tree with SDT