TIFR CSE 2015 | Part B | Question: 15

Question

Consider the following grammar (the start symbol is $E$) for generating expressions.

• $E \rightarrow T - E \mid T + E \mid T$
• $T \rightarrow T * F \mid F$
• $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$

With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?

• A.
• B.
• C.
• D.
• E.

Answer 1

Answer is option B.

The corresponding parse tree is drawn for the given expression according to the given grammar.

Comments

+ is right associate  ( ie right most + will be solve among all +) , - is also right associative ( ie right most - will be solve among all -) , but how to decide associativity between + and -  ??

---

@tsvkp1  As, both + and - are generated by same LHS so, both have the same precedence, Now the question is which one to evaluate first, So, When Precedence fails we go for associativity of the operator as + and - are right associative so the operator which is in Rightmost (+) will be evaluated first hence + will be evaluated first among + and -.

I hope now it is clear.

---

@ShiveshRoy

But $\mathbf +$ and $\mathbf -$ have the same associativity. 

I don't think your logic is fully correct.

Answer 2

#TheQuickApproach

Here we know 

* has high priority (Left to Right Associativity)

+,- (Right to Left associativity)

Now if we evaluate the given expression using above data then it will give us

2∗3∗4−5∗6+7=-13

Now due to * has high priority with Left to right associativity 2*3 should done first.

which is done by Option B and D only. so except this 2 remaining options are eliminated.

Now Option B only gives result -13 and D gives 1 as result of Expression tree evaluation.

Hence Option B is Ans.

Answer 3

Answer will be (B) 

Evaluation will be ((2*3)*4)-((5*6)+7)

Answer 4

$*$ has the highest precedence and is left associative. So, $((2*3)*4)...$ is done first.

Options A, C and E are eliminated.

 

After that, $5*6$ should be done.

B and D comply to that.

 

Now, $+$ and $-$ have equal priority, so treat them as same symbol: $((2∗3)∗4)<symbol>(5∗6)<symbol>7$

And they both are right associative.

So, treat the right symbol first.

=> Do addition first, then subtraction.

 

Hence, Option B is correct, and D is incorrect.