GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
171 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 (5.4k points)  
edited by | 171 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 (36.8k 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 (10.3k 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 Jan 2017
  1. Debashish Deka

    8968 Points

  2. sudsho

    5326 Points

  3. Habibkhan

    4798 Points

  4. Bikram

    4532 Points

  5. Vijay Thakur

    4486 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4196 Points

  8. santhoshdevulapally

    3808 Points

  9. Sushant Gokhale

    3596 Points

  10. Kapil

    3486 Points

Monthly Topper: Rs. 500 gift card

19,212 questions
24,104 answers
53,150 comments
20,319 users