GATE CSE 2018 | Question: 38

Question

Consider the following parse tree for the expression a#b$\$$c$\$$d#e#f, involving two binary operators $\$$  and #.

Which one of the following is correct for the given parse tree?

• A. $ has higher precedence and is left associative; # is right associative
• B. # has higher precedence and is left associative; $ is right associative
• C. $ has higher precedence and is left associative; # is left associative
• D. $ has higher precedence and is right associative; # is left associative

Comments

How to understand associativity here?

---

More the depth of an operator in tree, earliest it will be evaluated, higher will be it's precedence.

If grammar is left recursive, respective operator is left recursive and if grammar is right recursive then operator is right recursive

---

To understand associativity here: https://gateoverflow.in/204112/gate2018-38#a204270

Answer 1

Inorder $:\{a\#[((b\$c)\$d)\#(e\#f)]\}$ (given in question) 

If we observe, first evaluation is $ b\$c$
So,  (\$) has higher priority.
Therefore, either option (A) or (C) is correct

$\underline{\text{Option A}}$
$\$$ has higher precedence and $\#$ is right associative.

From tree, it is clear that $(e\#f)$ is evaluating first which is to the right side of the root.
Therefore, $\#$ is Right Associative.
So, Option A is correct

$\underline{\text{Option C}}$
$\$$ has higher precedence and $\#$ is left associative.
This is wrong.

Correct Answer: A.

Comments

@Prajna for associativity we need to check if the operator in the grammar is left recursive or right recursive . If left recursive then the operator will be left associative and if the grammar if right recursive then right associative.

---

“From tree, it is clear that (e#f) is evaluating first which is to the right side of the root.
Therefore, # is Right Associative.”

But since the precedence of “Dollar sign” has higher, shouldn’t b$c be evaluated before e#f ?

---

@Yashdeep2000 It is in fact, being evaluated before “e # f”. Find the yield of the given abstract syntax tree, tracing top-down, left-right.Associativity means when one operand is situated amidst two same operators, then which one to associate the operand with at first, left one or the right. In this case, ‘#’ is right associated.So we are associating operand ‘e’ with the # operator succeeding it in the sequence.

Answer 2

We can write the grammar and easily find the associativity.

Option A is correct.

Comments

I found this one the most intuitive

---

nice

---

Best one

Answer 3

$ is the highest precedence with left associative(since evaluated first) and # is right associative.

A is answer

Comments

Easiest question.

Answer 4

In expression tree

• Highest Precedence Operator is at the lowest level in the tree so that it is evaluated first.
• For unambiguous grammar, we can get precedence and associativity directly from production or expression tree.
• Left Associativity => Left Linear Grammar or in expression, tree it should expand on left child for the same operator and vice versa

Here at the lowest level, we have $ so it has the highest precedence.

# is right associative and $ is left associative.

Hence (A) is correct.

Comments

Is it left Linear or left recursive?