retagged by
2,982 views
25 votes
25 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$?

retagged by

5 Answers

Best answer
23 votes
23 votes

Answer is option B.

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

edited by
5 votes
5 votes

#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.
3 votes
3 votes

Answer will be (B) 

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

1 votes
1 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.
Answer:

Related questions