Introduction
A recursive-descent parser chooses which rule to apply by looking at the next token. For a hand-written parser that choice is obvious to the programmer, but parser generators must work it out from the grammar alone. Two sets make that possible: FIRST (which tokens can start each construct) and FOLLOW (which tokens can come right after it). They are also how you check that a grammar can be parsed with one token of lookahead.
How it works
The examples use this expression grammar, written without left recursion:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
Nullable. A nonterminal is nullable if it can derive ε. E' and T' are nullable through their ε-rules. A rule makes its left side nullable when every symbol of its body is nullable (an empty body counts).
FIRST of a sequence X1 X2 … Xk: take FIRST(X1); if X1 is nullable, add FIRST(X2); and so on until a symbol that is not nullable. FIRST of a terminal is the terminal itself. A nonterminal's FIRST set is the union over its rules' bodies. By convention ε is listed in FIRST(A) when A is nullable.
FOLLOW. Start with $ (end of input) in FOLLOW of the start symbol. Then, for every rule A → α B β with a nonterminal B:
- add FIRST(β) to FOLLOW(B);
- if β is empty or nullable, also add FOLLOW(A) to FOLLOW(B), because whatever follows A can then follow B.
These rules refer to each other in circles, so they are computed as a fixed point: apply every rule to every production, again and again, until a whole pass changes nothing. Because the sets only grow and are finite, the loop always stops.
Syntax
def first_of(symbols): # FIRST of a sequence, and whether it can be empty
out = set()
for s in symbols:
if s not in grammar: return out | {s}, False
out |= first[s]
if s not in nullable: return out, False
return out, True
Example
grammar = {
"E": [["T", "E'"]],
"E'": [["+", "T", "E'"], []],
"T": [["F", "T'"]],
"T'": [["*", "F", "T'"], []],
"F": [["(", "E", ")"], ["id"]],
}
start = "E"
nullable = set()
first = {a: set() for a in grammar}
follow = {a: set() for a in grammar}
follow[start].add("$")
def first_of(symbols):
out = set()
for s in symbols:
if s not in grammar:
out.add(s)
return out, False
out |= first[s]
if s not in nullable:
return out, False
return out, True
changed = True
while changed:
changed = False
for a, bodies in grammar.items():
for body in bodies:
f, empty = first_of(body)
if not f <= first[a]:
first[a] |= f
changed = True
if empty and a not in nullable:
nullable.add(a)
changed = True
for i, s in enumerate(body):
if s in grammar:
rest_first, rest_empty = first_of(body[i + 1:])
new = rest_first | (follow[a] if rest_empty else set())
if not new <= follow[s]:
follow[s] |= new
changed = True
for a in grammar:
eps = ", ε" if a in nullable else ""
print(f"FIRST({a}) = {{ {', '.join(sorted(first[a]))}{eps} }} FOLLOW({a}) = {{ {', '.join(sorted(follow[a]))} }}")Line by line
- The grammar is a dictionary from each nonterminal to its bodies;
[]is ε. first_ofcomputes FIRST of a sequence and reports whether the whole sequence can vanish.- One
while changedloop updates nullable, FIRST and FOLLOW together, until a full pass changes nothing. - For each nonterminal inside a body, FOLLOW gets FIRST of what comes after it, and FOLLOW of the rule's left side when the rest is nullable.
- The results match the classic textbook values: everything starts with
(orid, and F can be followed by*,+,)or the end.
Expected result
FIRST(E) = { (, id } FOLLOW(E) = { $, ) }
FIRST(E') = { +, ε } FOLLOW(E') = { $, ) }
FIRST(T) = { (, id } FOLLOW(T) = { $, ), + }
FIRST(T') = { *, ε } FOLLOW(T') = { $, ), + }
FIRST(F) = { (, id } FOLLOW(F) = { $, ), *, + }
In the real world
Parser generators such as ANTLR and the LL modes of many tools compute FIRST and FOLLOW to build their tables and to report conflicts in a grammar. The same fixed-point style of computation is used throughout compilers: for liveness of variables, reaching definitions and type inference.
Common mistakes
- Stopping FIRST at the first symbol even when that symbol is nullable.
- Forgetting $ in FOLLOW of the start symbol.
- Putting ε in a FOLLOW set: FOLLOW sets contain only terminals and $.
- Stopping after one pass: the sets depend on each other, so repeat until nothing changes.
Best practices
- Compute nullable, FIRST and FOLLOW in the same fixed-point loop, or in that order.
- Print the sets sorted, so that results are easy to compare with a textbook or a classmate.
- Check each set by hand on a small grammar before trusting the code on a big one.
Summary
Nullable symbols can derive ε. FIRST of a sequence collects the terminals that can begin it, looking past nullable symbols. FOLLOW collects what can come after a nonterminal, starting with $ for the start symbol. All three are computed by repeating simple rules until a fixed point, and together they drive predictive parsing.
Quick check
Key takeaways
- FIRST answers "what can this start with?"; FOLLOW answers "what can come after it?".
- Both are computed by applying a few rules repeatedly until nothing changes.
- They are the input to building an LL(1) parse table.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.