GATE CSE 2011 | Question: 27

Question

Consider two binary operators $\text{‘} \uparrow \text{’}$  and $\text{‘} \downarrow \text{’}$ with the precedence of operator $\downarrow$ being lower than that of the operator $\uparrow$. Operator $\uparrow$ is right associative while operator $\downarrow$ is left associative. Which one of the following represents the parse tree for expression $(7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2)$

• A.
  
• B.
  

   

• C.
  

   

• D.
  

Comments

First one fails because of associativity?

---

@ritiksri8 if u having confusion  instead of taking arrows u can take actual operators and just relpace them  for ($ \uparrow $)  u can use power ^ operator which is right associative and for ($\downarrow$) can use either use $+$ or $-$ why i choose those bcz as we know that power has more priority and $+$ has less, and power is right associative.  

now Your expression will look like this  ($7+(3$^$(4 $^$3 ))+2$)  

so now check all options or u can make its tree or simply in the given diagrams u can update the operators it will be easy to check which will evaluate first and which has more precedance 

So option $A $ $D$ will be wrong as they are giving more priority to dwon arrow bcz its in bottom of the tree now come to $B$ and $C$  if u carefully observe its evaluating 3^4 in bottom which is not in our expression so yeah that's wrong now finally $B$ is Ans.

plz let me know if something wrong here.

 

---

We get:

Option A: If both $\downarrow$ and $\uparrow$ have same precedence & are right-associative.

Option B: Correct answer for the given question.

Option C: If $\uparrow$ has higher precedence than $\downarrow$ ; and $\uparrow$ is left-associative, $\downarrow$ is right-associative.

Option D: If both $\downarrow$ and $\uparrow$ have same precedence & are left-associative.

Answer 1

Answer is B.

To make the parse tree start compiling the identifiers into blocks based on associativity and precedence.

Grouping: $(7 \downarrow (3 \uparrow(4 \uparrow 3)))  \downarrow2 $

Tree can be made by opening inner braces and move towards braces.

Comments

Is 3↑4↑3↑7↓2↓ also possible (assume there exist such a tree) ???????

Answer 2

Higher precedence operator comes at lowest level in the tree.And and if there is left recursion on operator then it is left assosiative ,same if right recursive then it is right associative. Scince tree is given it can be easily seen.As B) is correct.

Answer 3

Higher precedence operators comes at the bottom

↑ has higher precedence so  $3↑4↑3$ will be evaluated first.As ↑ is left associative so $4↑3$ will be evaluated so $4↑3$ should be at last level then 

$3↑(4↑3)$

↓ i this is left associative so left operand i.e & will be evaluated 

$(7↓(3↑(4↑3))$

and then 2 

$((7↓(3↑(4↑3))↓2)$

which gives option (B)

 

Answer 4

answer - B

Comments

How B Explain In your words

---

Since the precedence of ↑ is higher, the sub-expression ([3 ↑ 4 ↑ 3) will be evaluated first. In this sub-expression, 4 ↑ 3 would be evaluated first because ↑ is right to left associative. So the expression is evaluated as ((7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2). Also, note that among the two ↓ operators, first one is evaluated before the second one because the associativity of ↓ is left to right.

---

Right on!