Definition

FIRST and FOLLOW are sets of terminals computed from a grammar, used to build predictive (LL) parsing tables and to construct parsers without backtracking.

Key Points

• FIRST(α): the set of terminals that can begin any string derived from α. If α can derive ε (empty string), ε ∈ FIRST(α).
• FOLLOW(A): the set of terminals that can appear immediately to the right of non-terminal A in some derivation. $ (end marker) is included in FOLLOW(start symbol).
• Computation rules (simplified):
  • FIRST(terminal) = itself
  • FIRST(A) where A → Y1 Y2...Yn: add FIRST(Y1) minus ε; if Y1 can be ε, also add FIRST(Y2), and so on
  • FOLLOW(S) always contains $
  • If A → αBβ, everything in FIRST(β) (except ε) is in FOLLOW(B); if β is empty or nullable, FOLLOW(A) ⊆ FOLLOW(B)

Example

Grammar: E → T E', E' → + T E' | ε, T → id

• FIRST(E) = FIRST(T) = {id}
• FOLLOW(E) = {$, )}
• FOLLOW(E') = FOLLOW(E) = {$, )}

📌 CSS Frequency: High — "compute FIRST and FOLLOW for the given grammar" is a classic numeric question.

Model Answer (short)

"FIRST(α) is the set of terminals that can start a string derived from α, while FOLLOW(A) is the set of terminals that can immediately follow A in some sentential form. Both are computed by systematically applying the grammar's production rules, and together they are used to build the LL(1) parsing table, which decides which production to apply for a given non-terminal and lookahead symbol."