SSC IMD SA Mock 02 – Question 158

In compiler design, what is the primary condition that must be satisfied by a grammar to be parsed by an \(LL(1)\) predictive top-down parser without backtracking?

• For every production \(A \rightarrow \alpha \mid \beta\), \(\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset\) and if \(\beta \Rightarrow^* \epsilon\), then \(\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset\)
• The grammar must contain left recursion
• The grammar must be inherently ambiguous
• Every non-terminal must derive the empty string \(\epsilon\)

A grammar is LL(1) if and only if for every pair of alternate productions \(A \rightarrow \alpha \mid \beta\): 1. \(\text{FIRST}(\alpha)\) and \(\text{FIRST}(\beta)\) are disjoint. 2. At most one of \(\alpha, \beta\) can derive \(\epsilon\). 3. If \(\beta \Rightarrow^* \epsilon\), then \(\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset\).