GATE CS 2004 Q8 — Parsing (LL, LR)

An operator grammar is a context-free grammar that satisfies the following two conditions for all its production rules:

1. No production has $\varepsilon$ (the empty string) on the right-hand side.
2. No production has two adjacent non-terminals on the right-hand side.

Let's analyze the given grammar rules (where $P, Q, R$ are non-terminals and $r, s, t$ are terminals):

• Rule I ($P \rightarrow QR$): Violates the requirements because the non-terminals $Q$ and $R$ are adjacent.
• Rule II ($P \rightarrow Q s R$): Valid because the non-terminals $Q$ and $R$ are separated by the terminal $s$.
• Rule III ($P \rightarrow \varepsilon$): Violates the requirements because it is an $\varepsilon$-production.
• Rule IV ($P \rightarrow Q t R r$): Valid because no two non-terminals are adjacent, and there is no $\varepsilon$ on the right-hand side.

Therefore, rules (I) and (III) only violate the requirements of an operator grammar.