The Gateway to Computer Science Excellence
+16 votes

Consider the parse tree

Assume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. Consider

  1. $2 + a - b$
  2. $2 + a - b * a + b$
  3. $2 + ((a - b) * (a + b)))$
  4. $2 + (a - b) * (a + b)$

The parse tree corresponds to

  1. Expression (i)
  2. Expression (ii)
  3. Expression (iv) only
  4. Expression (ii), (iii), and (iv)
  5. Expression (iii) and (iv) only
in Compiler Design by Boss
edited by | 728 views
there is one  brace extra in option(iii) at end
It took a bit time for me to understand why (E) is the correct option.

Though * has higher precedence than + and -, but brackets always have the highest precedence.

In the given parse tree, (a-b) and (a+b) are evaluated first, then multiplied and added with 2 at last, and the same happening in option iii and iv.

@srestha Ma'am

I don't know whether they expect "most appropriate" answer or not but I think there is no need of choice 3 if choice 4 is sufficient. as "*" has highest precedence then anyhow it wont perform "+" over "*" so no need of parentheses there. Please explain.


"*" has highest precedence then anyhow it wont perform "+" over "*"

that is true, that is why option iv is true

but iii also correct

if both are correct, we need to say both correct. We cannot eliminate one without any reason

There is an extra closing bracket in option iii ?

2 Answers

+13 votes
Best answer

e is correct

Because as the expression evaluated right to left , so in (ii). $2+(a-(b*(a+b)))$ this evaluation performed, which is not a correct evaluation as the parse tree

by Veteran
edited by

Firstly b*a shud perform first becz * has Higher precedence in 2nd part..However it doesn't affect the Final Answer..

Can you elloborate a bit ?
for option (ii)

2+a−(b∗a)+b // * has high precedency

now +,- have same precedency so we will apply right to left associativity

(2+(a−((b∗a)+b))) is the result of option B.
I agree with Rajesh. b*a will be evaluated first.
As given in the question that '*' has higher priority but in the parse tree shown '*' is defined at a level above  '-'. Though the parse tree corresponds to iii) and iv), isn't the priority given wrong here?
$\mathbf *$ should come first that isn't necessary if parenthesis are being used.
+5 votes
Although given answer is correct one can approach in another way if one wants more visualization to this problem

Write the "postfix" expression of given parse tree keeping in mind precedences order & associativity as per question we will get      { 2ab-ab+*+ }

Now write the postfix expressions of options 3 & 4 you will see same and for option 2 you will get different


(E) correct answer
by Loyal
Right approach but when we take infix of tree that match to (ii) option

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
52,215 questions
59,981 answers
94,633 users