The Gateway to Computer Science Excellence
+19 votes

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$?

in Compiler Design by Boss (30.8k points)
edited by | 767 views

4 Answers

+19 votes
Best answer

Answer is option B.

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

by Loyal (7.4k points)
edited by
I think, Ans should be option D.

1. How did you decide the priority of + is greater than -. ?
both have same priority but they are right associative so + evalute first
Yes,(y).. My bad... Thank you @sonam :)
+ 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.



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

I don't think your logic is fully correct.

+3 votes


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


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.
by Boss (23.9k points)
+2 votes

Answer will be (B) 

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

by Veteran (119k points)
0 votes

$*$ 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.
by Loyal (6.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,909 users