GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
223 views
$\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*}$
asked in Compiler Design by Boss (6.1k points)  
retagged by | 223 views
answer is coming out to be -5

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

2 Answers

+3 votes
Best answer
$\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*}$
answered by Veteran (50.9k points)  
selected by
That is what..i was saying
I used word "priority" in the same sense as @arkriti is saying "precedence"
I have a doubt. Do the operators really have priority here?

The grammar seems to be E→E+E / E∗E / E−E / (E) / id

All the operators are at same level. So how is the priority decided? Shouldn't they all have equal priority?
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
+1 vote

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

answered by Veteran (13.2k points)  
@Akriti... - has more priority than + so it should come at lower level..
who said - has more priority than +.both have same priority but precedence is from left to right(As far as i know)
[(3*3) + (3*3) -6]---in this expression,both - and + have same priority
but + before 7 has the lowest priority among all,thats why it is at the highest
and [] has more precedence than any operator,so obviously it will be at lower level
Ya after that + ans - ,
In SDT that one is farthest from the start has high priority.
So - has more priority than +
did'nt get you..can u show ur SDT?whats ur answer??

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


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users