Review: FIRST and FOLLOW Sets
3
FIRST(α):
For some α ∈ ( T ∪ NT ∪ EOF ∪ ε)*, define FIRST (α) as the set
of tokens that appear as the first symbol in some string that derives
from α.
FIRST set is defined over the strings of grammar symbols
( T ∪ NT ∪ EOF ∪ ε)*
That is, x ∈ FIRST(α) iff α ⇒∗ xγ for some γ
T: terminals NT: non-terminals
First Set Example
4
Start ::= S eof
S ::= a S b | ε FIRST(ε) =
{a}
{ε}
{a, ε}
S can be rewritten as the following:
ab
aaabbb
aabb
ε
…
FIRST(S) =
aSb can be rewritten as the following:
ab
aabb
…
FIRST(aSb) =
Computing FIRST Sets
5
• FIRST(A) includes FIRST(B1) – ε
• FIRST(A) includes FIRST(B2) – ε if B1 can be rewritten as ε
• FIRST(A) includes FIRST(B3) – ε if both B1 and B2 can derive ε
• …
• FIRST(A) includes FIRST(Bm) – ε if B1B2… Bm-1 can derive ε
For a production A → B1B2 … Bk :
FIRST(A) includes FIRST(B1) … FIRST(Bm) not including ε iff
ε ∈ FIRST(B1), FIRST(B2), FIRST(B3), …, FIRST(Bm-1)
FIRST(A) includes ε iff
ε ∈ FIRST(B1), FIRST(B2), FIRST(B3), …, FIRST(Bk)
First Set Construction
6
• For each X as a terminal, then FIRST(X) is {X}
• If X ::= ε, then ε ∈ FIRST(X)
• For each X as a non-terminal, initialize FIRST(X) to ∅
Build FIRST(X) for all grammar symbols X:
add a to FIRST(X) if a ∈ FIRST(Y1)
add a to FIRST(X) if a ∈ FIRST(Yi) and ε ∈ FIRST(Yj)
for all 1 ≤ j ≤ i-1 and i ≥ 2
add ε to FIRST(X) if ε ∈ FIRST(Yi) for all 1 ≤ i ≤ k
End iterate
• Iterate until no more terminals or ε can be added to any FIRST(X):
For each rule in the grammar of the form X ::= Y1Y2…Yk
EndFor
Filling in the Details: Computing FIRST sets
7
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Initially, set FIRST for each
terminal symbol, EOF and ε
Filling in the Details: Computing FIRST sets
8
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Initialize FIRST of each non-
terminal symbol as empty set
Filling in the Details: Computing FIRST sets
9
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
If any FIRST set changes, it might
affect other FIRST set(s) due to
the inter-dependence relationship.
Filling in the Details: Computing FIRST sets
10
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Check each rule in the
grammar, see if any other
FIRST set needs to be updated.
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Filling in the Details: Computing FIRST sets
11
ε complicates matters
If FIRST(Y1) contains ε, then
we need to add FIRST(Y2) to
rhs, and …
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Filling in the Details: Computing FIRST sets
12
ε complicates matters
If all the rhs symbols can go to
ε, then we add ε to FIRST(lhs)
for each x ∈ ( T ∪ EOF ∪ ε)
FIRST(x) ← {x}
for each A ∈ NT, FIRST(A) ← ∅
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
Computing FIRST sets
13
Outer loop is monotone
increasing for FIRST sets
⇒ | T ∪ NT ∪ EOF ∪ ε | is
bounded, so it terminates
An Example
14
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
1
2
3
4
1st means first “while” iteration
……
while (FIRST sets are still changing) do
for each p ∈ P, of the form X → Y1Y2…Yk do
temp ← FIRST(Y1) – { ε }
i ← 1
while ( i ≤ k-1 and ε ∈ FIRST(Yi) )
temp ← temp ∪ (FIRST(Yi+1) – { ε })
i ← i + 1
end // while loop
if i == k and ε ∈ FIRST(Yk)
then temp ← temp ∪ { ε }
FIRST(X) ← FIRST(X) ∪ temp
end // if – then
end // for loop
end // while loop
An Example
15
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
Pair ::= LP List RP
An Example
16
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
List ::= Pair List
| ε
An Example
17
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
Goal ::= List
An Example
18
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
Pair ::= LP List RP
An Example
19
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
List ::= Pair List
| ε
An Example
20
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Where LP is ( and RP is )
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
If we visit the rules
in order 4, 3, 2, 1
⇒
1
2
3
4
1st means first “while” iteration
Applying
Goal ::= List
An Example
21
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Symbol Initial 1st 2nd
Goal ∅ LP, ε LP, ε
List ∅ LP, ε LP, ε
Pair ∅ LP LP
LP LP LP LP
RP RP RP RP
EOF EOF EOF EOF
• Iteration 1 adds LP to
FIRST(Pair) and {LP,
ε} to FIRST(List) and
FIRST(Goal)
⇒ If we take them in
rule order 4, 3, 2, 1
• Algorithm reaches
fixed point
FIRST Sets
1
2
3
4
1st means first “while” iteration
FOLLOW Sets
22
FOLLOW(A):
For A ∈ NT , define FOLLOW(A) as the set of tokens that can
occur immediately after A in a valid sentential form.
FOLLOW set is defined over the set of non-terminal symbols, NT.
Back to Our Example
23
Start ::= S eof
S ::= a S b |
ε
FOLLOW(S) = { }
Start ⇒ S eof ⇒ a S b eof ⇒ a b eof
One possible derivation process from the start symbol:
Back to Our Example
24
Start ::= S eof
S ::= a S b |
ε
FOLLOW(S) = { }
Start ⇒ S eof ⇒ a S b eof ⇒ a b eof
One possible derivation process from the start symbol:
Back to Our Example
25
Start ::= S eof
S ::= a S b |
ε
FOLLOW(S) = { }
Start ⇒ S eof ⇒ a S b eof ⇒ a b eof
One possible derivation process from the start symbol:
Back to Our Example
26
Start ::= S eof
S ::= a S b |
ε
FOLLOW(S) = { }
Start ⇒ S eof ⇒ a S b eof ⇒ a b eof
One possible derivation process from the start symbol:
Back to Our Example
27
Start ::= S eof
S ::= a S b |
ε
FOLLOW(S) = { } eof , b
Start ⇒ S eof ⇒ a S b eof ⇒ a b eof
One possible derivation process from the start symbol:
Computing FOLLOW Sets
28
• FOLLOW(Bk) includes FOLLOW(A)
• FOLLOW(Bk-1) includes
FIRST(Bk) – ε,
and FOLLOW(A) if Bk can derive ε
• FOLLOW(Bk-2) includes
FIRST(Bk-1Bk) – ε,
and FOLLOW(A) if Bk-1Bk can derive ε
• …
For a production A → B1B2 … Bk-1Bk :
Follow Set Construction
29
Given a rule p in the grammar:
A → B1B2…BiBi+1…Bk
If Bi is a non-terminal, FOLLOW(Bi) includes
• FIRST(Bi+1…Bk) – {ε} U FOLLOW(A), if ε ∈ FIRST(Bi+1…Bk)
• FIRST(Bi+1…Bk) otherwise
Follow Set Construction
30
• Place EOF in FOLLOW(
• For each X as a non-terminal, initialize FOLLOW(X) to ∅
Iterate until no more terminals can be added to any FOLLOW(X):
For each rule p in the grammar
If p is of the form A ::= αBβ, then
if ε ∈ FIRST(β)
Place {FIRST(β) – ε, FOLLOW(A)} in FOLLOW(B)
else
Place {FIRST(β)} in FOLLOW(B)
If p is of the form A ::= αB, then
Place FOLLOW(A) in FOLLOW(B)
End iterate
To Build FOLLOW(X) for non-terminal X:
Computing FOLLOW Sets
31
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
Initially, set FOLLOW for
each non-terminal symbol
Computing FOLLOW Sets
32
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
Set FOLLOW for start
symbol S as {EOF}
Computing FOLLOW Sets
33
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
As long as any
FOLLOW set
changes
Computing FOLLOW Sets
34
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
As long as any
FOLLOW set
changes, check all
the rules
Computing FOLLOW Sets
35
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
set trailing
context to
FOLLOW(A)
Computing FOLLOW Sets
36
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
it goes
backwards
Computing FOLLOW Sets
37
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
if the symbol is
non-terminal,
need to check if it
derives ε
Computing FOLLOW Sets
38
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
Consecutive non-
terminals that derive
ε in trailing context
Computing FOLLOW Sets
39
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
Trailing context
needs to be reset
Computing FOLLOW Sets
40
for each A ∈ NT
FOLLOW(A) ← ∅
FOLLOW(S) ← { EOF }
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
To build FOLLOW sets, we need FIRST sets
when Bi does not
derive ε
An Example
41
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
• Goal, List and Pair are set to ∅
• Goal is then set to { EOF }
Initial Values:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
An Example
42
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1 (of while loop):
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
while (FOLLOW sets are still changing) do
for each p ∈ P, of the form A → B1B2…Bk do
TRAILER ← FOLLOW(A)
for i ← k down to 1
if Bi ∈ NT then
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER
if ε ∈ FIRST(Bi)
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })
else TRAILER ← FIRST(Bi)
else TRAILER ← { Bi }
An Example
43
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
An Example
44
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
Goal ::= List
Add FOLLOW(Goal) to
FOLLOW(List)
An Example
45
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
List ::= Pair List
An Example
46
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
List ::= Pair List
• Add FIRST(List) to
FOLLOW(Pair)
• Add FOLLOW(List) to
FOLLOW(Pair)
An Example
47
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
Pair ::= LP List RP
An Example
48
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
Pair ::= LP List RP
• Add FIRST(RP) to
FOLLOW(List)
An Example
49
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 1:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
1
2
3
4
If we visit the rules
in order 1, 2, 3, 4
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
An Example
50
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 2:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, LP, LP
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
If we visit the rules
in order 1, 2, 3, 4
1
2
3
4
An Example
51
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 2:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, LP, LP
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
If we visit the rules
in order 1, 2, 3, 4
1
2
3
4
Goal ::= List
Add FOLLOW(Goal) to
FOLLOW(List)
An Example
52
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 2:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, LP, RP
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
If we visit the rules
in order 1, 2, 3, 4
1
2
3
4
List ::= Pair List
• Add FIRST(List) to
FOLLOW(Pair)
• Add FOLLOW(List) to
FOLLOW(Pair)
An Example
53
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
Iteration 2:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
If we visit the rules
in order 1, 2, 3, 4
1
2
3
4
• Add FIRST(RP) to
FOLLOW(List)
Pair ::= LP List RP
An Example
54
Consider the simplest parentheses grammar
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
• Production 1 adds nothing new
• Production 2 adds RP to
FOLLOW(Pair)
from FOLLOW(List), ε ∈ FIRST(List)
• Production 3 does nothing
• Production 4 adds nothing new
Iteration 2:
Symbol Initial 1st 2nd
Goal EOF EOF EOF
List ∅ EOF, RP EOF, RP
Pair ∅ EOF, LP EOF, RP, LP
Iteration 3 produces the same result ⇒ reached a fixed point
Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP
EOF EOF
1
2
3
4
Review: LL(1) Predictive Parsing
55
• FIRST (α) ∩ FIRST (β) = ∅, and
• if α ⇒* ε, then FIRST (β) ∩ FOLLOW (A) = ∅
Whenever two productions A ::= α and A ::= β both appear in the
grammar, we would like
Key Property:
This would allow the parser to make a correct
choice with a lookahead of only one symbol!
Analogue case for β ⇒* ε.
Note: due to first condition, at most one of α and β can derive ε.
Review: LL(1) Grammar
56
• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise
Define PREDICT(A ::= δ) for rule A ::= δ
A Grammar is LL(1) iff
(A ::= α and A ::= β) implies
PREDICT( A ::= α) ∩ PREDICT( A ::= β) = ∅
Building Top-down Parsers
57
• Need a PREDICT set for every rule
Building the PREDICT set Symbol FIRST FOLLOW
SetGoal LP, ε EOF
List LP, ε EOF, RP
Pair LP EOF, RP, LP
LP LP –
RP RP –
EOF EOF –
Goal ::= List
List ::= Pair List
List ::= ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, LP
2 LP
3 EOF, RP
4 LP
Define PREDICT(A ::= δ) for rule A ::= δ
• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise
Building Top-down Parsers
58
• Need a PREDICT set for every rule
Building the PREDICT set Symbol FIRST FOLLOW
SetGoal LP, ε EOF
List LP, ε EOF, RP
Pair LP EOF, RP, LP
LP LP –
RP RP –
EOF EOF –
Goal ::= List
List ::= Pair List
List ::= ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, LP
2 LP
3 EOF, RP
4 LP
Define PREDICT(A ::= δ) for rule A ::= δ
• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise
FIRST(Pair List)
FOLLOW(List)
Building Top-down Parsers
59
• Need a row for every NT and a column for every T
• Need an interpreter for the table (skeleton parser)
Building the complete parse table
Goal ::= List
List ::= Pair List
List ::= ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, LP
2 LP
3 EOF, RP
4 LP
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Building Top-down Parsers
60
• Need a row for every NT and a column for every T
• Need an interpreter for the table (skeleton parser)
Building the complete parse table
Goal ::= List
List ::= Pair List
List ::= ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, RP
2 LP
3 EOF, RP
4 LP
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Building Top-down Parsers
61
• Need a row for every NT and a column for every T
• Need an interpreter for the table (skeleton parser)
Building the complete parse table
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, RP
2 LP
3 EOF, RP
4 LP
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Building Top-down Parsers
62
Building the complete parse table
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
Rule PREDICT
1 EOF, RP
2 LP
3 EOF, RP
4 LP
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
• Need a row for every NT and a column for every T
• Need an interpreter for the table (skeleton parser)
Next Lecture
63
• Start programming in C.
• Read Scott, Chapter 3.1 – 3.3; ALSU 7.1
• Read Scott, Chapter 8.1 – 8.2; ALSU 7.1 – 7.3
Things to do: