Determine LL(1) Grammar - Oya-Learning-Notes/Compilers GitHub Wiki

To check if a grammar is LL(1) grammar, we need to:

  1. Eliminate Left Recursion.
  2. Calculate First Set.
  3. Calculate Follow Set.
  4. Calculate Select Set.

The first three steps are discussed in detail in other articles of this Wiki. Checkout NavBar at the right for more info.

Select Set

For a production, the select set is only related to RHS.

Consider $A \to \alpha, \quad \alpha \in V^*$

$$ select(A \to \alpha) = first(\alpha) $$

If $\varepsilon \in fisrt(\alpha)$:

$$ select(A \to \alpha) = (first(\alpha) - \varepsilon) \cup follow(A) $$

Note in this case, the $follow(LHS)$ is used, not using RHS sequence $\alpha$