程序代写代做代考 algorithm interpreter Review: FIRST and FOLLOW Sets

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: