Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 61 · Context-Free Grammars

FIRST and FOLLOW Sets

Learn how to compute nullable symbols, FIRST and FOLLOW sets for a context-free grammar with a fixed-point algorithm, and run the code in Python.

A parser that reads one token at a time constantly asks the same question: "I am about to expand this nonterminal, and the next token is if. Which production should I use?" To answer it without guessing, the parser needs a small table of facts about the grammar. Those facts are the FIRST and FOLLOW sets. They are computed once, before any program is parsed, and they power both the top-down parsers you will meet next and the bottom-up parsers later in the track.

This lesson defines the sets, explains the single idea that makes them tricky (symbols that can derive the empty string), and then computes them with a short Python program. It builds directly on context-free grammars and works best on grammars that have already been through left-recursion elimination and left factoring.

The grammar we will analyze

We use the classic expression grammar in its non-left-recursive form. Capitalized names are nonterminals, everything else is a terminal, and ε stands for the empty production.

TEXT
E  -> T E2
E2 -> + T E2 | ε
T  -> F T2
T2 -> * F T2 | ε
F  -> ( E ) | id

E2 and T2 are the "tail" rules that replaced left recursion (written E' and T' in many textbooks). They are the interesting ones, because each can vanish: choosing ε consumes no input at all.

Nullable symbols

A nonterminal is nullable if it can derive the empty string. Nullability matters because it lets the parser "see through" a symbol: if A can vanish, then whatever follows A in a production can also be the first thing that appears.

The rules are simple:

  1. A nonterminal with an ε production is nullable.
  2. A nonterminal with a production whose every symbol is nullable is nullable.
  3. Terminals are never nullable.

Rule 2 refers to itself, so you cannot decide everything in one pass. You start with nothing nullable, apply the rules repeatedly, and stop when a full pass changes nothing. That "repeat until nothing changes" loop is called a fixed-point iteration, and all of the algorithms in this lesson use it.

FIRST sets

FIRST(X) is the set of terminals that can appear as the very first token of some string derived from X. For a terminal t, FIRST(t) = {t}. For a nonterminal, you look at each production X -> Y1 Y2 ... Yn:

  • add everything in FIRST(Y1);
  • if Y1 is nullable, also add FIRST(Y2), and so on;
  • keep going until you hit a symbol that cannot vanish, or run out of symbols.

The same walk works for any string of symbols, not just a right-hand side. We will call it first_of_sequence, and you will need it again when building parse tables. By convention the set contains the marker ε when the whole sequence can vanish. In the code below we keep ε out of the stored FIRST sets and track it separately in the nullable set, which keeps the sets purely about terminals.

flowchart LR
    X["X → Y1 Y2 Y3"] --> A["add FIRST(Y1)"]
    A -->|"Y1 nullable?"| B["add FIRST(Y2)"]
    B -->|"Y2 nullable?"| C["add FIRST(Y3)"]
    C -->|"all nullable"| D["X is nullable too"]

The FIRST walk stops at the first symbol that cannot vanish.

FOLLOW sets

FOLLOW(A) is the set of terminals that can appear immediately to the right of A in some sentential form (some partly expanded derivation from the start symbol). It answers a different question from FIRST: not "what can A begin with" but "what can come after A". The end of the input is represented by the special terminal $.

You need FOLLOW because of nullable symbols. If the next token is ) and the parser is looking at E2, no production of E2 starts with ). The only sensible move is to pick E2 -> ε and let the caller deal with the ). The parser can only know that is safe if ) is in FOLLOW(E2).

The rules, for every production A -> α B β (where B is a nonterminal and α, β are any strings of symbols, possibly empty):

  1. Put $ into FOLLOW(S), where S is the start symbol.
  2. Add everything in FIRST(β) to FOLLOW(B).
  3. If β is empty or can vanish entirely, add all of FOLLOW(A) to FOLLOW(B).

Rule 3 is the surprising one. If B can be the last real thing in A, then whatever may follow A may also follow B. Information flows from the left-hand side to the last symbols of the right-hand side.

flowchart LR
    P["A → α B β"] -->|"rule 2: FIRST(β)"| F["FOLLOW(B)"]
    G["FOLLOW(A)"] -->|"rule 3: only if β can vanish"| F

FOLLOW(B) receives the FIRST set of what comes next, plus FOLLOW(A) when nothing real comes next.

Computing the sets in Python

The program below stores a grammar as a dictionary from each nonterminal to a list of alternatives, and each alternative is a list of symbols. Anything that is not a key of the dictionary is a terminal. It prints the FIRST sets after every round, so you can watch the fixed point appear.

Python Nullable, FIRST and FOLLOW for the expression grammar

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace. In round 1 only F, E2 and T2 have anything, because they are the only rules that start directly with a terminal. T has to wait for F, and E has to wait for T, so their sets appear in rounds 2 and 3. Round 4 changes nothing, which is how the loop knows it is done. The order of the rules affects how many rounds you need, never the final answer.

The results match what you would work out by hand. FIRST(E) is { (, id } because an expression starts with a parenthesis or a name. FIRST(E2) is just { + }, and E2 is nullable, so the parser may also choose the empty production. FOLLOW(F) contains *, +, ) and $: a factor can be followed by a * (from T2), by a + (because T2 can vanish and T is followed by E2's +), by a closing parenthesis, or by the end of input.

When you compute FOLLOW by hand, work from the start symbol downward and keep asking "what can come right after this symbol in each production that mentions it?" Rule 3 is the one people forget, so always check whether the symbol sits at the end of a right-hand side.

Tricky grammars and a first LL(1) check

Nullable chains make FIRST and FOLLOW more interesting. In S -> A B c where both A and B can vanish, the first token of S could be a, b or c. The code below packs the three algorithms into a single loop and runs it on three grammars: one with optional parts, a fragment of the toy language's statements from our toy language, and a grammar that is deliberately broken.

After computing the sets, the program does a first check for LL(1). For each nonterminal it collects the tokens that would select each alternative (FIRST of the alternative, plus FOLLOW of the nonterminal when the alternative can vanish). If two alternatives claim the same token, the parser could not choose between them with one token of lookahead, and the program reports a conflict. You will turn this check into a real parse table in LL(1) table-driven parsing.

Python Optional parts, toy statements and a conflict

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Several things are worth noticing in the output. In the first grammar, FOLLOW(A) is { b, c }: after an optional a comes either an optional b or the final c. In the toy statements, Prog is nullable (an empty program is fine), and because blocks end with }, FOLLOW(Prog) contains both $ and }. That is how a parser inside a block knows an empty statement list is correct when it sees }. Finally, S -> a S | a reports a conflict on a: both alternatives begin with the same token. This is exactly the problem that left factoring repairs.

Common mistakes

  • Putting ε into FOLLOW. FOLLOW sets contain only real terminals and $. The empty string is not a token that can appear in the input.
  • Forgetting that FIRST of a sequence depends on nullability. FIRST(A B) includes FIRST(B) only when A is nullable.
  • Stopping after one pass. Rules refer to each other, so you must loop until nothing changes.
  • Forgetting $ for the start symbol. Without it, rule 3 never propagates the end-of-input marker to the right places.
  • Treating FIRST and FOLLOW as the same thing. FIRST looks into a symbol; FOLLOW looks past it.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What does FIRST(X) contain?

    FIRST(X) is about the beginning of strings that X can derive. The tokens that can come after X belong to FOLLOW(X).
  2. 2. Which rule makes FOLLOW(A) flow into FOLLOW(B) for a production A -> α B β?

    If nothing real can follow B inside this production, then B can end A, so whatever may follow A may also follow B.
  3. 3. Why do we repeat the computation until nothing changes?

    Grammar rules refer to one another (for example E needs FIRST(T), which needs FIRST(F)). Sets only grow, and we stop at the fixed point where a full pass adds nothing.
  4. 4. For S -> A B c with A -> a | ε and B -> b | ε, which tokens are in FIRST(S)?

    A can vanish, so B's first tokens are possible; B can vanish too, so c can come first. The marker $ belongs to FOLLOW sets, not FIRST.
  5. 5. Which symbol is always in FOLLOW of the start symbol?

    The start symbol can be followed by the end of the input, so $ is added to FOLLOW(S) by rule 1.

Summary

  • A nonterminal is nullable if it can derive the empty string; this is computed by repeating until nothing changes.
  • FIRST(X) holds the terminals that can begin strings derived from X; the walk through a right-hand side continues past nullable symbols.
  • FOLLOW(A) holds the terminals that can appear right after A; it includes $ for the start symbol, FIRST(β) for what follows, and FOLLOW of the parent when the rest can vanish.
  • All three sets are fixed-point computations and can be written in a few dozen lines of Python.
  • Comparing the sets of alternatives is a first test for LL(1): two alternatives that can start with the same token are a conflict.

Next: Top-Down Parsing Basics