menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

TIFR2015-B-15

22 votes
1.3k views

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
edited by 1.3k views

5 Answers

21 votes
 
Best answer

Answer is option B.

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


edited by
0
I think, Ans should be option D.

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

@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.

0

@ShiveshRoy

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

I don't think your logic is fully correct.

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

Answer will be (B) 

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

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.
0 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=6*4-30+7=24-30+7=-6+7=1

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 D is Ans.
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

5 votes
2 answers
1
417 views
TIFR2015-A-15
Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the second set is $\mu_{B}$; let the corresponding variances be $v_{A}$ and $v_{B}$ ... $p.v_{A}+ (1 - p). v_{B} + (\mu_{A}- \mu_{B})^{2}$
Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the second set is $\mu_{B}$; let the corresponding variances be $v_{A}$ and $v_{B}$ respectively. If the average of the elements in $A \cup B$ ... $p.v_{A}+ (1 - p). v_{B} + (\mu_{A}- \mu_{B})^{2}$
asked Dec 5, 2015 in Quantitative Aptitude makhdoom ghaya 417 views
14 votes
3 answers
2
1.2k views
TIFR2015-B-14
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of $x$ ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$
asked Dec 8, 2015 in Operating System makhdoom ghaya 1.2k views
4 votes
2 answers
3
317 views
TIFR2015-B-13
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. ... ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the ... (ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
asked Dec 8, 2015 in Algorithms makhdoom ghaya 317 views
8 votes
2 answers
4
662 views
TIFR2015-B-12
Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n > 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statements are true: (i) There exists three successive triangular numbers whose product is a perfect square. (ii) If ... $(i)$ only. $(ii)$ only. $(iii)$ only. All of the above. None of the above.
Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n > 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statements are true: (i) There exists three successive triangular numbers whose product is a perfect square. (ii) If the triangular ... $(i)$ only. $(ii)$ only. $(iii)$ only. All of the above. None of the above.
asked Dec 8, 2015 in Quantitative Aptitude makhdoom ghaya 662 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...