Predicitve Parser LL(1) condition

Question

Lets say we use the predictive parser LL(1). Why is it necessary that

$FIRST(\alpha) \cap FIRST(\beta) = \emptyset$,

for all $\alpha, \beta$ right side of alternative productions i.e., productions associated to the same non-terminal. Why is this condition necessary?

Answer 1

Here's an intuitive explanation:

It follows essentially from the nature of LL(1) parsers: LL(1) parsers build a LL(1) parsing table. The rows of the table are nonterminals, and the columns are terminals. We can think about LL(1) parsing as doing LL(1) table lookups upon encountering each symbol in the input: we look at the entry determined by the current nonterminal and the input terminal, and apply a corresponding production rule. Thus, the LL(1) table cannot contain multiple production rules at each entry, otherwise, the parser cannot decide which rule to apply.

If the right hand side of a production $\alpha$, $\beta$ have intersecting FIRST sets, then we'd have multiple rules at a single entry in the LL(1) table (i.e. duplicate/conflicting entries) --- having nontrivial intersection of FIRST sets essentially prevents us from constructing the LL(1) parsing table.

If you're still unclear about why this condition is necessary, I suggest you construct an example with intersecting FIRST sets on the right hand side of a production, and then try to manually construct an LL(1) parsing table or use one of the online visualization tools; you'll immediately find a conflict.