GATE CSE 1997 | Question: 1.6

Question

In the following grammar

• $X ::= X \oplus Y \mid Y$
• $Y::= Z * Y \mid Z$
• $Z::= id $

Which of the following is true?

• A. $\text{‘}\oplus\text{’}$ is left associative while $\text{‘}*\text{’}$ is right associative
• B. Both $\text{‘}\oplus\text{’}$ and $\text{‘}*\text{’}$ are left associative
• C. $\text{‘}\oplus\text{’}$ is right associative while $\text{‘}*\text{’}$ is left associative
• D. None of the above

Answer 1

It will be A. For multiple '$\oplus$', the derivation is possible only via '$X$' which is on left side of '$\oplus$' in the production. Hence it is left associative.

For multiple '$*$', the derivation is possible only via '$Y$' which is on the right side of '$*$' in the production. Hence it is right associative.

If both left and right derivations were possible, the grammar would have been ambiguous and we couldn't have given associativity.

Comments

When we create parse tree for the above grammar then  * is computed after x-or. So whether this is correct or not if the answer is 3..

---

A is the most apt answer.
But, * is left associative

https://www.programiz.com/c-programming/precedence-associativity-operators

---

U hav to calculate the associativity on the basis of given grammar  ....

---

understood, thanks :)

---

If both left and right derivations were possible, the grammar would have been ambiguous and we couldn't have given associativity.this is nice point gate keeda

---

What will be the answer A or D.

---

$A)$ is the correct answer.

and precedence$:\ast > \oplus$

---

How to decide the precedence from a given grammar?

---

Intuitively draw parse trees for several small inputs, you will get to see a conclusive pattern.

---

If both left and right derivations were possible, the grammar would have been ambiguous and we couldn't have given associativity.

Anyone please , what does this mean ?

---

@Lakshman Patel RJIT how can u say this ??

Any resources to study this topic.

---

@abir_banerjee Operator derived at the lowest level has the highest precedence.

Associativity and Precedence in CFGs - YouTube: This video will be helpful

---

Thanks @Abhrajyoti00.

Answer 2

Answer is A

Comments

But easily we can check just by seeing if the Grammar is left recursive or Right recursive .