Compiler Design FIRST and FOLLOW: 6 Solved Problems with LL(1) Parsing Tables
FIRST tells you which terminal can start a derived string. It also contains ε when the string can vanish. FOLLOW tells you which terminal can occur immediately after a nonterminal in a sentential form, plus $ when it can end the input. The LL(1) table must choose at most one production for each nonterminal/lookahead pair.
This worksheet has six solved Compiler Design problems and three self-tests. Every set and table below was computed by a program, then written here. These are general BTech CSE practice questions, not an official university paper or prediction. Related practice: Exam Numericals Hub, time complexity problems and semester-wise exam notes.
1. The rules in short
- FIRST of a terminal is the terminal itself. If A -> ε is a rule, ε is in FIRST(A).
- FIRST(X1 X2 ...): take FIRST(X1) without ε. If X1 can vanish (ε in FIRST(X1)), also add FIRST(X2), and so on. Add ε only if every symbol can vanish.
- FOLLOW(start) contains $. For A -> α B β, add FIRST(β) without ε to FOLLOW(B). If β can vanish or is empty, add FOLLOW(A) to FOLLOW(B).
- LL(1) table: for rule A -> α, put it in M[A, t] for each t in FIRST(α). If ε is in FIRST(α), put it in M[A, t] for each t in FOLLOW(A).
1A. Three questions, three different sets
| Object | Question it answers | Includes ε? |
|---|---|---|
| FIRST(α) | What can begin a string derived from α? | Yes, if α can vanish |
| FOLLOW(A) | What can occur immediately after A in context? | Never; $ is the endmarker |
| SELECT(A -> α) | Which lookaheads select this exact production? | Never; use FIRST(α) without ε, plus FOLLOW(A) if α is nullable |
LL(1) means read input left to right, construct a leftmost derivation, and choose with one lookahead token. Here id is one token, not two letters. ε is an empty right-hand side, not an input token; $ marks the end, not part of the source program.
Nullable-prefix diagram
S -> A B C
| | |
a b c possible leading terminals
| | |
ε ε c A and B may vanish; C cannot
FIRST(ABC) = {a, b, c}, not {a} and not {a, b, c, ε}
Stop adding later FIRST sets at the first non-nullable symbol. FOLLOW propagation diagram
A -> α B β
|
+-- FIRST(β) without ε ------> FOLLOW(B)
|
+-- if β can vanish --------> FOLLOW(A) also flows to B
Empty β counts as nullable. Repeat until no set grows. Why one pass fails: for S -> A, A -> B, B -> c | ε, scanning S then A then B starts with empty sets. c and ε reach B first, then A, then S on later passes. FIRST(S)=FIRST(A)=FIRST(B)={c, ε}; all three FOLLOW sets are {$}. A fixed point means another complete pass adds nothing.
2. Six solved problems
Problem 1: FIRST and FOLLOW for the expression grammar
Grammar (E′ is written E', T′ is T'):
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
| Non-terminal | FIRST | FOLLOW |
|---|---|---|
| E | {(, id} | {), $} |
| E' | {+, ε} | {), $} |
| T | {(, id} | {), +, $} |
| T' | {*, ε} | {), +, $} |
| F | {(, id} | {), *, +, $} |
Why: FIRST(F) is { (, id } because F starts with ( or id, and T and E start with F. E' and T' can vanish, so FOLLOW(T) gets FIRST(E') without ε, which is +, plus FOLLOW(E), which is ) and $.
Problem 2: a grammar where a symbol vanishes
S -> A B
A -> a A | ε
B -> b B | c
| Non-terminal | FIRST | FOLLOW |
|---|---|---|
| S | {a, b, c} | {$} |
| A | {a, ε} | {b, c} |
| B | {b, c} | {$} |
Why: A can vanish, so FIRST(AB) = (FIRST(A) without ε) plus FIRST(B) = {a, b, c}. FOLLOW(A) is FIRST(B) = {b, c}.
Problem 3: LL(1) parsing table for Problem 1's grammar
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| E | E -> T E' | E -> T E' | ||||
| E' | E' -> + T E' | E' -> ε | E' -> ε | |||
| T | T -> F T' | T -> F T' | ||||
| T' | T' -> ε | T' -> * F T' | T' -> ε | T' -> ε | ||
| F | F -> id | F -> ( E ) |
Result: no cell has two rules, so the grammar is LL(1). Empty cells are errors. Notice E' -> ε appears under ) and $ because those are in FOLLOW(E').
Problem 4: parse id + id * id with that table
| Stack (top at left) | Input | Action |
|---|---|---|
| E $ | id + id * id $ | E -> T E' |
| T E' $ | id + id * id $ | T -> F T' |
| F T' E' $ | id + id * id $ | F -> id |
| id T' E' $ | id + id * id $ | match id |
| T' E' $ | + id * id $ | T' -> ε |
| E' $ | + id * id $ | E' -> + T E' |
| + T E' $ | + id * id $ | match + |
| T E' $ | id * id $ | T -> F T' |
| F T' E' $ | id * id $ | F -> id |
| id T' E' $ | id * id $ | match id |
| T' E' $ | * id $ | T' -> * F T' |
| * F T' E' $ | * id $ | match * |
| F T' E' $ | id $ | F -> id |
| id T' E' $ | id $ | match id |
| T' E' $ | $ | T' -> ε |
| E' $ | $ | E' -> ε |
| $ | $ | accept |
Result: the parser reaches $ on both stack and input. There are 17 table rows: 11 production expansions, 5 terminal matches and 1 accept check. Epsilon expansions pop a nonterminal without consuming input.
Problem 5: the dangling-else grammar is not LL(1)
S -> i E t S S' | a
S' -> e S | ε
E -> b
| Non-terminal | FIRST | FOLLOW |
|---|---|---|
| S | {a, i} | {e, $} |
| S' | {e, ε} | {e, $} |
| E | {b} | {t} |
Conflict: S' has the rules S' -> e S and S' -> ε. FIRST(e S) contains e, and FOLLOW(S') also contains e, so M[S', e] gets both rules. Choosing the nonempty rule on e implements the nearest-if convention, but it does not make this grammar LL(1). It is an extra disambiguation policy. Do not erase the conflict when checking the grammar.
Read the conflict as two reasons for one lookahead
S' -> e S : e belongs to FIRST(e S) -> M[S', e]
S' -> ε : e belongs to FOLLOW(S') -> M[S', e]
^
two rules, same cell
Self-test A -> B a : FIRST(B a) = {b, a}
Self-test A -> ε : FOLLOW(A) = {b, $}
Shared b -> conflict at M[A, b].Problem 6: is S -> a S b | ε LL(1)?
FIRST(S) = {a, ε} and FOLLOW(S) = {b, $}. The rule S -> a S b goes under a. The rule S -> ε goes under b and $. No cell is shared.
Answer: yes, it is LL(1) (conflicts found by program: 0).
3. Common mistakes
- Putting ε into FOLLOW. FOLLOW never contains ε. It contains $ and real terminals only.
- Forgetting to add FOLLOW(A) to FOLLOW(B) when what comes after B can vanish.
- Using FOLLOW for a rule that cannot vanish. For a rule with no ε in FIRST(α), use only FIRST(α).
- Calling a grammar LL(1) after checking one rule. Check every cell of the table.
4. Three self-tests
Test 1. Grammar: S -> A B, A -> B a | ε, B -> b | ε. Find FIRST and FOLLOW of S, A and B.
Test 2. Is the grammar in Test 1 LL(1)? Name the cell if not.
Test 3. In Problem 1, which cell holds T' -> ε entries? List the terminals.
Answers
Test 1: S: FIRST {a, b, ε}, FOLLOW {$}; A: FIRST {a, b, ε}, FOLLOW {b, $}; B: FIRST {b, ε}, FOLLOW {a, $}.
Test 2: not LL(1). Cell M[A, b] gets both A -> B a and A -> ε.
Test 3: T' -> ε is under +, ), $.
Test 2: not LL(1). Cell M[A, b] gets both A -> B a and A -> ε.
Test 3: T' -> ε is under +, ), $.
5. Five-minute revision
- FIRST: what can start. FOLLOW: what can come next.
- ε is in FIRST, never in FOLLOW. $ is in FOLLOW of the start symbol.
- Table rule: FIRST(α) for the rule, plus FOLLOW(A) if α can vanish.
- Two rules in one cell means not LL(1).
6. Run the set, table and parser proof lab
Copy this complete Python 3 block. No packages are needed. Empty tuples represent ε; output spells it eps. Grammar keys are nonterminals and other RHS symbols are terminals. The start symbol is stated explicitly. This teaching lab assumes well-formed, reachable grammars and keeps all candidate productions rather than overwriting a conflict.
It checks all sets for the expression, nullable-prefix, dangling-else, balanced a/b and self-test grammars; checks the 17-row expression trace; rejects four malformed expressions; accepts a parenthesized expression; accepts eleven anbn strings including empty input and rejects four malformed a/b strings. A reversed chain checks that repeated propagation works.
# Python 3. Empty tuple () means epsilon; $ is end of input.
from collections import defaultdict
EPS = 'eps'
def analyse(g, start):
first = {a: set() for a in g}
follow = {a: set() for a in g}
follow[start].add('$')
def seq(rhs):
out = set()
for x in rhs:
f = first[x] if x in g else {x}
out |= f - {EPS}
if EPS not in f:
return out
return out | {EPS}
changed = True
while changed:
changed = False
for a, rules in g.items():
for rhs in rules:
old = len(first[a])
first[a] |= seq(rhs)
changed |= len(first[a]) != old
changed = True
while changed:
changed = False
for a, rules in g.items():
for rhs in rules:
for i, b in enumerate(rhs):
if b not in g:
continue
tail = seq(rhs[i + 1:])
add = tail - {EPS}
if EPS in tail:
add |= follow[a]
old = len(follow[b])
follow[b] |= add
changed |= len(follow[b]) != old
table = defaultdict(list)
for a, rules in g.items():
for rhs in rules:
f = seq(rhs)
look = (f - {EPS}) | (follow[a] if EPS in f else set())
for t in look:
if rhs not in table[a, t]:
table[a, t].append(rhs)
conflicts = sorted(k for k, v in table.items() if len(v) > 1)
return first, follow, table, conflicts
def parse(g, table, start, tokens):
# Reject conflicted tables rather than silently picking a rule.
if any(len(v) > 1 for v in table.values()):
return False, []
stack, inp, i, trace = [start, '$'], tokens + ['$'], 0, []
while stack:
top, look = stack[0], inp[i]
if top == '$':
action = 'accept' if look == '$' else 'error'
trace.append((' '.join(stack), ' '.join(inp[i:]), action))
return look == '$', trace
if top not in g:
action = 'match ' + top if top == look else 'error'
trace.append((' '.join(stack), ' '.join(inp[i:]), action))
if top != look:
return False, trace
stack.pop(0)
i += 1
else:
choices = table.get((top, look), [])
if len(choices) != 1:
trace.append((' '.join(stack), ' '.join(inp[i:]), 'error'))
return False, trace
rhs = choices[0]
action = top + ' -> ' + (' '.join(rhs) if rhs else 'eps')
trace.append((' '.join(stack), ' '.join(inp[i:]), action))
stack = list(rhs) + stack[1:]
return False, trace
G = {'E': [('T', "E'")], "E'": [('+', 'T', "E'"), ()],
'T': [('F', "T'")], "T'": [('*', 'F', "T'"), ()],
'F': [('(', 'E', ')'), ('id',)]}
N = {'S': [('A', 'B')], 'A': [('a', 'A'), ()],
'B': [('b', 'B'), ('c',)]}
D = {'S': [('i', 'E', 't', 'S', "S'"), ('a',)],
"S'": [('e', 'S'), ()], 'E': [('b',)]}
B = {'S': [('a', 'S', 'b'), ()]}
Q = {'S': [('A', 'B')], 'A': [('B', 'a'), ()], 'B': [('b',), ()]}
def show(name, g):
f, h, table, conflicts = analyse(g, next(iter(g)))
print(name)
for a in g:
print(' ', a, 'FIRST=', sorted(f[a]), 'FOLLOW=', sorted(h[a]))
print(' conflicts:', conflicts)
assert all(EPS not in v for v in h.values())
return f, h, table, conflicts
f, h, table, c = show('Expression grammar', G)
assert f == {'E': {'(', 'id'}, "E'": {'+', EPS}, 'T': {'(', 'id'},
"T'": {'*', EPS}, 'F': {'(', 'id'}}
assert h == {'E': {')', '$'}, "E'": {')', '$'}, 'T': {')', '+', '$'},
"T'": {')', '+', '$'}, 'F': {')', '*', '+', '$'}}
assert not c
ok, trace = parse(G, table, 'E', ['id', '+', 'id', '*', 'id'])
print('Expression parse:', ok, '; steps including accept:', len(trace))
assert ok and len(trace) == 17
for tokens in [[], ['id', '+'], ['id', '*', '*', 'id'], ['(', 'id']]:
assert not parse(G, table, 'E', tokens)[0]
assert parse(G, table, 'E', ['(', 'id', '+', 'id', ')', '*', 'id'])[0]
f, h, _, c = show('Nullable-prefix grammar', N)
assert f == {'S': {'a', 'b', 'c'}, 'A': {'a', EPS}, 'B': {'b', 'c'}}
assert h == {'S': {'$'}, 'A': {'b', 'c'}, 'B': {'$'}} and not c
f, h, _, c = show('Dangling else', D)
assert f == {'S': {'i', 'a'}, "S'": {'e', EPS}, 'E': {'b'}}
assert h == {'S': {'e', '$'}, "S'": {'e', '$'}, 'E': {'t'}}
assert c == [("S'", 'e')]
f, h, bt, c = show('Balanced a/b grammar', B)
assert f == {'S': {'a', EPS}} and h == {'S': {'b', '$'}} and not c
for n in range(11):
assert parse(B, bt, 'S', ['a'] * n + ['b'] * n)[0]
for tokens in [['a'], ['b'], ['a', 'b', 'b'], ['a', 'b', 'a', 'b']]:
assert not parse(B, bt, 'S', tokens)[0]
f, h, _, c = show('Self-test grammar', Q)
assert f == {'S': {'a', 'b', EPS}, 'A': {'a', 'b', EPS}, 'B': {'b', EPS}}
assert h == {'S': {'$'}, 'A': {'b', '$'}, 'B': {'a', '$'}}
assert c == [('A', 'b')]
# Deliberately reversed chain order: one pass is not enough.
C = {'S': [('A',)], 'A': [('B',)], 'B': [('c',), ()]}
f, h, _, c = analyse(C, 'S')
assert all(v == {'c', EPS} for v in f.values())
assert all(v == {'$'} for v in h.values()) and not c
print('All set/table/parser assertions passed; malformed inputs rejected.')
Actual output
Expression grammar
E FIRST= ['(', 'id'] FOLLOW= ['$', ')']
E' FIRST= ['+', 'eps'] FOLLOW= ['$', ')']
T FIRST= ['(', 'id'] FOLLOW= ['$', ')', '+']
T' FIRST= ['*', 'eps'] FOLLOW= ['$', ')', '+']
F FIRST= ['(', 'id'] FOLLOW= ['$', ')', '*', '+']
conflicts: []
Expression parse: True ; steps including accept: 17
Nullable-prefix grammar
S FIRST= ['a', 'b', 'c'] FOLLOW= ['$']
A FIRST= ['a', 'eps'] FOLLOW= ['b', 'c']
B FIRST= ['b', 'c'] FOLLOW= ['$']
conflicts: []
Dangling else
S FIRST= ['a', 'i'] FOLLOW= ['$', 'e']
S' FIRST= ['e', 'eps'] FOLLOW= ['$', 'e']
E FIRST= ['b'] FOLLOW= ['t']
conflicts: [("S'", 'e')]
Balanced a/b grammar
S FIRST= ['a', 'eps'] FOLLOW= ['$', 'b']
conflicts: []
Self-test grammar
S FIRST= ['a', 'b', 'eps'] FOLLOW= ['$']
A FIRST= ['a', 'b', 'eps'] FOLLOW= ['$', 'b']
B FIRST= ['b', 'eps'] FOLLOW= ['$', 'a']
conflicts: [('A', 'b')]
All set/table/parser assertions passed; malformed inputs rejected.
7. Boundary questions with answers
| Question | Answer and reason |
|---|---|
| Must every symbol in the suffix be nullable? | Yes, before FOLLOW(left-hand side) can flow through the whole suffix. A nullable first suffix symbol alone is not enough. |
| Can ε be placed in an input column? | No. It is not a lookahead token. Nullable productions use FOLLOW columns, which may include $. |
| Can a FOLLOW set contain + even when the nonterminal cannot start with +? | Yes. FIRST and FOLLOW answer different questions; expression T starts with id or (, but may be followed by +. |
| Does resolving a double cell prove LL(1)? | No. A preferred-rule policy can define behavior, but the grammar still has an LL(1) conflict. |
| Does left factoring guarantee LL(1)? | No. It removes a shared prefix, but nullable/FOLLOW conflicts may remain. Rebuild every cell. |
| Does an empty table cell mean accept? | No. It is a syntax error. Acceptance requires both stack and remaining input at $. |
| Is the 17-step parse count universal? | No. This trace counts every expansion, terminal match and final accept check. Implementations that count only expansions or omit accept report a different number. |
| Is this a lexer or a full compiler? | Neither. The lab takes an already tokenized list and implements a small predictive-parser demonstration; it has no lexer, error recovery or semantic actions. |
References
Concepts follow standard compiler lecture notes: JHU Compilers, Lecture 9: LL(1) parsing and Columbia COMS W4115, Lecture 9: Predictive Top-Down Parsers. The grammars, sets, tables and traces on this page were written and computed for TechVani. Topic order differs by university; check your own syllabus.
Additional checks: JHU LL(1), FIRST+ and stack algorithm; Calgary nullable and fixed-point propagation; Cornell dangling-else and grammar transformations; Washington LL(1) property; CMU parsing and FOLLOW definitions. This page uses ε inside FIRST sets; some notes instead store a separate nullable flag. The two representations describe the same empty-string property.
Comments
Post a Comment