FIRST and FOLLOW Sets for LL(1) Grammars

The Parser's Dilemma: Which Rule to Choose?

Imagine a parser is trying to analyze a piece of code. It has a non-terminal symbol, let's say A, that it needs to expand. The grammar gives it several options:
A → α | β | γ

How does the parser decide whether to replace A with α, β, or γ? A naive approach would be to try one, and if it leads to a dead end, backtrack and try another. This is inefficient. A predictive parser, specifically an LL(1) parser, avoids this by making an informed choice based on the single next input token, called the lookahead symbol.

To make this choice, it needs answers to two questions:

1. What are the possible first terminals that can be derived from α, β, and γ?
2. If a rule can derive an empty string (ε), what are the terminals that are allowed to follow A in a valid sentence?

The FIRST and FOLLOW sets provide the precise, algorithmically-computed answers to these questions.

Computing the FIRST Set

The FIRST set of a non-terminal X, denoted $\text{FIRST}(X)$, is the set of terminals that can appear as the first symbol in any string derived from X. If X can derive the empty string, ε, then ε is also in $\text{FIRST}(X)$.

Here are the rules to compute the FIRST sets for all non-terminals in a grammar:

1. For a terminal a: $\text{FIRST}(a)=\{a\}$.
2. For a non-terminal X:
   • If there is a production X → ε, add ε to $\text{FIRST}(X)$.
   • If there is a production X → aα (where a is a terminal), add a to $\text{FIRST}(X)$.
   • If there is a production X → Y₁Y₂...Yk (where Y₁ is a non-terminal), add everything in $\text{FIRST}(Y_1)$ (except ε) to $\text{FIRST}(X)$.
   • If $\text{FIRST}(Y_1)$ contains ε, then also add everything in $\text{FIRST}(Y_2)$ (except ε) to $\text{FIRST}(X)$. Continue this process. If ε is in $\text{FIRST}(Y_i)$ for all $i=1,...,k$, then add ε to $\text{FIRST}(X)$.

Computing the FOLLOW Set

The FOLLOW set of a non-terminal A, denoted $\text{FOLLOW}(A)$, is the set of terminals that can appear immediately to the right of A in some sentential form. We also use a special symbol, $, to denote the end of the input string.

Here are the rules to compute the FOLLOW sets:

1. Place $ in $\text{FOLLOW}(S)$, where S is the start symbol.
2. If there is a production A → αBβ:
   • Add everything in $\text{FIRST}(\beta )$, except ε, to $\text{FOLLOW}(B)$.
   • If $\text{FIRST}(\beta )$ contains ε (or if β is empty), then everything in $\text{FOLLOW}(A)$ must be in $\text{FOLLOW}(B)$.
3. If there is a production A → αB, then everything in $\text{FOLLOW}(A)$ is in $\text{FOLLOW}(B)$.

These rules are applied iteratively until no new terminals can be added to any FOLLOW set.

Let's see these rules applied to GATE-style problems. The following video systematically calculates FIRST and FOLLOW sets for several grammars.

The LL(1) Condition

Now that we can compute these sets, we can define an LL(1) grammar. The name stands for Left-to-right scan of the input, Leftmost derivation, and 1 symbol of lookahead. A grammar is LL(1) if and only if for every non-terminal A with two or more distinct productions, say A → α and A → β, the following conditions hold:

1. Disjoint FIRST sets: The FIRST sets of the right-hand sides must be disjoint. Formally, $\text{FIRST}(\alpha )\cap \text{FIRST}(\beta )=\varnothing$. This ensures that if the lookahead symbol is t, it can belong to the FIRST set of at most one of the possible expansions.

2. Handling Epsilon: At most one production can derive ε. If one production can derive ε (say, α →* ε), then its FIRST set will contain ε. In this case, the FIRST set of any other production β must not contain any symbol that is in the FOLLOW set of A. Formally, if ε is in $\text{FIRST}(\alpha )$, then $\text{FIRST}(\beta )\cap \text{FOLLOW}(A)=\varnothing$. This prevents confusion: if the lookahead symbol is in $\text{FOLLOW}(A)$, the parser knows to apply the A → α (which will eventually become ε) rule. If it's in $\text{FIRST}(\beta )$, it applies A → β. There cannot be an overlap.

If either of these conditions is violated for any non-terminal, the grammar is not LL(1). The parser would face a conflict, meaning it wouldn't know which production to choose based on the lookahead, and would have to guess or backtrack.

Let's apply this test to some grammars.

The conflicts highlighted in the video—multiple entries in a single cell of the parsing table—are the direct result of violating one of the two LL(1) conditions we discussed. For GATE, being able to quickly compute these sets and check for these conflict conditions is a key problem-solving skill.

Conclusion

In this lesson, we moved from the what of syntax (tokens) to the how of parsing (prediction). You've learned the algorithms for computing FIRST and FOLLOW sets, which are the cornerstones of predictive parsing.

Here are the key takeaways:

• FIRST(X) is the set of terminals (plus potentially ε) that can begin strings derived from X.
• FOLLOW(A) is the set of terminals (plus potentially $) that can appear immediately after A in a valid derivation.
• A grammar is LL(1) if, for any non-terminal, the parser can uniquely determine which production to apply by looking at only the next input symbol.
• This uniqueness is guaranteed if the LL(1) conditions are met: disjoint FIRST sets for alternative productions, and if one production yields ε, its FOLLOW set must be disjoint from the other productions' FIRST sets.

We've now established the theoretical basis for building a predictive parser. You can determine if a grammar is "good enough" for this simple, efficient parsing method. In our next lesson, we will put this theory into practice. We'll learn how to construct the complete LL(1) parsing table and use it with a stack-based algorithm to parse an input string, tracing the entire process from start to finish.