程序代写代做代考 algorithm Review: Top-Down Parsing – LL(1)

y

α
β

Review: Predictive Parsing

4

Basic idea:

For any two productions A ::= α and A ::= β, we would like
a distinct way of choosing the correct production to expand.

5

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

Applied Production:

id_list_tail

id_list

id(A)

Revisiting the id_list Example

6

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

Applied Production:
id_list_tail ::= ;

id_list_tail

id_list

id(A)

;

Revisiting the id_list Example

Mismatch!

7

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

Applied Production:

id_list_tail

id_list

id(A)

Revisiting the id_list Example

8

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

Applied Production:
id_list_tail ::= , id id_list_tail

id_list_tail

id_list

id(A)

, id(B) id_list_tail

Revisiting the id_list Example

9

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

id_list_tail

id_list

id(A)

, id(B) id_list_tail
Match!

Revisiting the id_list Example

Applied Production:
id_list_tail ::= , id id_list_tail

Review: First Set

10

For some string α, define FIRST(α) as the set of tokens that
appear as the first symbol in some string derived from α.

That is

x ∈ FIRST(α) iff α ⇒∗ xγ for some string γ

Review: Predictive Parsing

11

• FIRST (α) ∩ FIRST (β) = ∅, and
• if α ⇒* ε, then FIRST (β) ∩ FOLLOW (A) = ∅
• Analogue case for β ⇒* ε. Note: due to first condition, at most

one of α and β can derive ε.

Whenever two productions A ::= α and A ::= β both appear in the
grammar, we would like

Key Property:

12

id_list ::= id id_list_tail
id_list_tail ::= , id id_list_tail
id_list_tail ::= ;

Remaining Input:
, B , C ;

id_list_tail

id_list

id(A)

Revisiting the id_list Example

FIRST( , id id_list_tail ) = { , }

FIRST( ; ) = { ; }

If the first token of remaining input is , we choose the rue

If the first token of remaining input is ; we choose the rule

Given id_list_tail as the first non-terminal to expand in the tree:

id_list_tail ::= , id id_list_tail

id_list_tail ::= ;

FIRST ( , id id_list_tail ∩ FIRST ( ; ) = ∅

Revisiting the LL(1) Parsing Example

13

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Revisiting the LL(1) Parsing Example

14

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Sa b
S ::= a S b

Mismatch!
It only means S ::= aSb is not the right production rule to use!

Revisiting the LL(1) Parsing Example

15

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Revisiting the LL(1) Parsing Example

16

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

ε
S ::= ε

S ::= ε turns out to be the right rule later.

However, at this point, ε does not match “b” either !

Review: Follow Set

17

For a non-terminal A, define FOLLOW(A) as the set of terminals that
can appear immediately to the right of A in some sentential form.

Thus, a non-terminal’s FOLLOW set specifies the tokens that can
legally appear after it. A terminal symbol has no FOLLOW set.

FIRST and FOLLOW sets can be constructed automatically

Review: Predictive Parsing

18

• 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

19

• 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 ::= β) = ∅

Table Driven LL(1) Parsing

20

a b eof other

S S ::= aSb S ::= ε S ::= ε error

S ::= a S b | ε

LL(1) parse table

Example:
PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) ={b, eof}

Predict Sets

Table Driven LL(1) Parsing

21

a b eof other

S S ::= aSb S ::= ε S ::= ε error

S ::= a S b | ε

LL(1) parse table

Example:
PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) ={b, eof}

Predict Sets

22

Review: Table Driven LL(1) Parsing

Input: a string w and a parsing table M for G
push eof
push Start Symbol
token ← next_token()
X ← top-of-stack
repeat
if X is a terminal then
if X == token then
pop X
token ← next_token()
else error()
else /* X is a non-terminal */
if M[X, token] == X → Y1Y2 . . . Yk then
pop X
push Yk, Yk−1, . . . , Y1
else error()
X ← top-of-stack
until X = EOF
if token != EOF then error()

M is the parse table

a b eof other
S S ::= aSb S ::= ε S ::= ε error

Predictive Parsing

23

scanner parser

stack

parsing
tables

source
code

intermediate
representation

Rather than writing code, we build tables.
Building tables can be automated!

Now, a predictive parser looks like:

Predictive Parsing

24

scanner parser

stack

parsing
tables

source
code

intermediate
representation

Rather than writing code, we build tables.
Building tables can be automated!

Now, a predictive parser looks like:

grammar parser
generator

25

• Introduced FIRST, FOLLOW, and PREDICT sets
• Introduced LL(1) condition:
‣ A grammar G can be parsed predictively with one symbol of lookahead

if for all pairs of productions A ::= α and A ::= β that satisfy:
PREDICT(A ::= α) ∩ PREDICT(A ::= β) = ∅

• Introduced a recursive descent parser for an LL(1) grammar

Predictive Parsing

So far:

How to automatically construct FIRST and FOLLOW sets?

FIRST and FOLLOW Sets

26

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

Computing FIRST Sets

27

• 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

28

• For each X as a terminal, then FIRST(X) is {X}
• If X ::= ε, then ε ∈ FIRST(X)
• 1. For each X as a non-terminal, initialize FIRST(X) to ∅ 


2. Iterate until no more terminals or ε can be added to any FIRST(X):

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

End iterate

For each rule in the grammar of the form X ::= Y1Y2…Yk

add ε to FIRST(X) if ε ∈ FIRST(Yi) for all 1 ≤ i ≤ k

Filling in the Details: Computing FIRST sets

29

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 ε

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

30

ε 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

31

ε complicates matters

If the entire rhs 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

32

Outer loop is monotone
increasing for FIRST sets
⇒ | T ∪ NT ∪ EOF ∪ ε | is
bounded, so it terminates

Example

33

Consider the SheepNoise grammar and its FIRST sets

Goal ::= SheepNoise
SheepNoise ::= SheepNoise baa |

baa

Clearly, FIRST(x) = {baa}, Ɐ x ∈ (T ∪ NT)

Symbol FIRST Set

Goal baa

SheepNoise baa

baa baa

baa is a terminal symbol

Computing FIRST sets

34

Initialization assigns each
FIRST set a value

Symbol FIRST Set
Goal ∅

SheepNoise ∅

baa {baa}

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

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

35

Symbol FIRST Set
Goal ∅

SheepNoise {baa}
baa {baa}

Goal ::= SheepNoise

SheepNoise ::= SheepNoise baa

SheepNoise ::= baa

1
2
3

If we visit the rule
in the order 3, 2, 1

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

36

Symbol FIRST Set
Goal {baa}

SheepNoise {baa}
baa {baa}

Goal ::= SheepNoise

SheepNoise ::= SheepNoise baa

SheepNoise ::= baa

1
2
3

If we visit the rule
in the order 3, 2, 1

An Example

37

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

An Example

38

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

An Example

39

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

An Example

40

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

An Example

41

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

An Example

42

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

An Example

43

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

An Example

44

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

An Example

45

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

An Example

46

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 at Iteration 2

1
2
3
4

FOLLOW Sets

47

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.

Follow Set Construction

48

• Place EOF in FOLLOW()
• 1. For each X as a non-terminal, initialize FOLLOW(X) to ∅ 


2. 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

49

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 // domain checking
FOLLOW(Bi) ← FOLLOW(Bi) ∪ TRAILER

if ε ∈ FIRST(Bi) // add right context
TRAILER ← TRAILER ∪ (FIRST(Bi) – { ε })

else TRAILER ← FIRST(Bi) // no ε => truncate the right context
else TRAILER ← { Bi } // Bi ∈ T => only 1 symbol

Don’t add ε

To build FOLLOW sets, we need FIRST sets

Computing FOLLOW Sets

50

• It works its way backward through the production: 

Bk, Bk-1, … B1

• It builds the FOLLOW sets for the rhs symbols, 

B1, B2, … Bk, not A

• In the absence of ε, FOLLOW(Bi) is just FIRST(Bi+1)
– As always, ε makes the algorithm more complex

For a production A → B1B2 … Bk :

To handle ε, the algorithm keeps track of the first word in the trailing
right context as it works its way back through rhs: Bk, Bk-1, … B1

Computing FOLLOW Sets

51

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

52

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

Assume FIRST Sets are
obtained using the algorithm we
discussed in previous slides.

An Example

53

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

54

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

55

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

56

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

57

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

An Example

58

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

An Example

59

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

An Example

60

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

An Example

61

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 (omitted in the table)

Symbol FIRST Set
Goal LP, ε
List LP, ε
Pair LP
LP LP
RP RP

EOF EOF

1
2
3
4

Next Lecture

62

• Read Scott, Chapter 2.1 – 2.3.3; ALSU 2.4

Things to do: