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

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