GATE CS 1997 Q1.6 — Parsing (LL, LR)

To determine the associativity of the operators $\oplus$ and $*$, we analyze the recursive structure of the grammar rules:

1. Operator $\oplus$: The production rule is: $$X \to X \oplus Y \mid Y$$ Since the non-terminal $X$ on the left-hand side appears as the leftmost symbol on the right-hand side of the production ($X \to X \oplus Y$), this is a left-recursive production. Left-recursion implies that the operator $\oplus$ is left-associative.
   Example: For the expression $id \oplus id \oplus id$, the parse tree groups the leftmost operation first: $((id \oplus id) \oplus id)$.
2. Operator $*$: The production rule is: $$Y \to Z * Y \mid Z$$ Since the non-terminal $Y$ on the left-hand side appears as the rightmost symbol on the right-hand side of the production ($Y \to Z * Y$), this is a right-recursive production. Right-recursion implies that the operator $*$ is right-associative.
   Example: For the expression $id * id * id$, the parse tree groups the rightmost operation first: $(id * (id * id))$.

Therefore, $\oplus$ is left-associative and $*$ is right-associative, which matches Option A.