MadeEasy Subject Test: Compiler Design - Syntax Directed Translation

Question

$\begin{align*} &E\rightarrow E+E \qquad {\color{red}{\text{E.val} = \text{E}_1\text{.val} { \;\;\large + \;\; } \text{E}_2\text{.val}}} \\ &E\rightarrow E*E \; \qquad {\color{red}{\text{E.val} = \text{E}_1\text{.val} { \;\;\large - \;\; } \text{E}_2\text{.val}}} \\ &E\rightarrow E - E \qquad {\color{red}{\text{E.val} = \text{E}_1\text{.val} { \;\;\large * \;\; } \text{E}_2\text{.val}}} \\ &E\rightarrow \left ( E \right ) \;\;\; \; \qquad {\color{red}{\text{E.val} = \text{E}_1\text{.val}}} \\ &E\rightarrow \text{id} \;\;\; \; \;\;\; \qquad {\color{red}{\text{E.val} = \text{id}\text{.val}}} \\ \\ &\text{What is that value of the attribute comupted at the root when the expression} \\ &{\large\color{blue}{\left [ \left ( 3*3 \right )+\left ( 3*5 \right ) - 6 \right ]+7}} \quad \text{is evaluated using above SDT ?} \\ \end{align*}$

Comments

answer is coming out to be -5

---

vaishali jhalani please check for any typo ...QS updated !

Answer 1

$\begin{align*} &\text{Operator priority order } \\ &\rightarrow 1st \quad {\large \color{blue}{-}} \\ &\rightarrow 2nd \quad {\large \color{blue}{*}} \\ &\rightarrow 3rd \quad {\large \color{blue}{+}} \\ \\ \hline \\ &\text{While reducing to a production corresponding SDT is evaluated} \\ \\ &\Rightarrow \left ( {\color{red}{\left ( 3*3 \right )}}+{\color{red}{\left ( 3*5 \right )}} - 6 \right )+7 \\\\ &\Rightarrow \left ( 0 \;\;{\large \color{blue}{+}} \;\; {\color{red}{(- 2) \;\;{\large \color{red}{-}}\;\; 6}} \right ) + 7 \\\\ &\Rightarrow \left ( 0 \;\;{\large \color{blue}{+}} \;\; (-12) \right ) + 7 \\ \\ &\Rightarrow \left ( -12 \right ) + 7 \\ \\ &\Rightarrow -5 \\ \end{align*}$

Comments

The grammar seems ambiguous, so how is the priority/precedence decided here?

---

yes grammar is ambiguous so priority couldnt be decided(in general case)
but here they have explicitly mentioned that we have to evaluate the expression ..so we have 2 choices either give priority urself or use their gramamar and decide(this is what we have to do..see their levels )....if they would have mentioned everything in one line like  E→E+E / E∗E / E−E / (E) / id..then there was a confusion which was having higher priority...but again they have given grammar in levels..saying treat lowest with highest priority..

NOTE:for ambiguous grammars precednce is nt defined..we can play with it according our needs or according to their needs...this question is about satisfying their worries..!

---

Okay!! so its a trick. thanks @sudsho

Answer 2

see this one..little bit messy though..!

Comments

This is the sdt tree..

---

"precedence is from left to right" We do not say that.

We say - Associativity is from left-to-right.

---

yes..sorry..associativity it is