程序代写代做代考 interpreter lec9 (edited).key

lec9 (edited).key

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 9: LL(1) Parsing Review

October 3, 2018

Class Information

• Homework 4 will be posted after lecture 10.
• Project 1 will be posted after homework 4 is due.

Review: FIRST and FOLLOW Sets

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

That is, x ∈ FIRST(α) iff α ⇒∗ xγ for some γ

T: terminals NT: non-terminals

First Set Example

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

• 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) excluding ε 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

• 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

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Iter. 1 means iteration 1

• 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 ∅  

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

Initialization

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Iter. 1 means iteration 1

• 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 ∅  

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

Iteration 1 (of the outer loop below):

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

If we visit the rules
in order 4, 3, 2, 1

⇒

The order of the rules do not
affect the final FIRST set results:

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

Goal ∅ LP, ε LP, ε

List ∅ LP, ε LP, ε

Pair ∅ ? LP

LP LP LP LP

RP RP RP RP

EOF EOF EOF EOF

1
2
3
4

Applying Rule 4
Pair ::= LP List RP

FIRST sets in progress

add first(LP list RP) to first(Pair)

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 4
Pair ::= LP List RP

FIRST sets in progress

add first(LP list RP) to first(Pair)

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 4
Pair ::= LP List RP

FIRST sets in progress

add first(LP list RP) to first(Pair)

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

Goal ∅ LP, ε LP, ε

List ∅ ? LP, ε

Pair ∅ LP LP

LP LP LP LP

RP RP RP RP

EOF EOF EOF EOF

1
2
3
4

Applying Rule 2 and Rule 3
List ::= Pair List

| ε

add first(ε) to first(List)

add first(Pair List) to first(List)

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 2 and Rule 3
List ::= Pair List

| ε

add first(ε) to first(List)

add first(Pair List) to first(List)

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 2 and Rule 3
List ::= Pair List

| ε

add first(ε) to first(List)

add first(Pair List) to first(List)

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

Goal ∅ ? LP, ε

List ∅ LP, ε LP, ε

Pair ∅ LP LP

LP LP LP LP

RP RP RP RP

EOF EOF EOF EOF

1
2
3
4

Applying Rule 1
Goal ::= List

add first(List) to first(Goal)

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 1
Goal ::= List

add first(List) to first(Goal)

FIRST sets in progress

Iter. 1 means iteration 1

Iteration 1:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

We just finished the first iteration!
Recall that one iteration reviews all the rules!

FIRST sets in progress

Iter. 1 means iteration 1

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Before the second iteration starts…

FIRST sets in progress

Iter. 1 means iteration 1

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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 FIRST sets in progress

Before the second iteration starts…

Iter. 1 means iteration 1

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 4
Pair ::= LP List RP

add first(LP list RP) to first(Pair)

LP is already in first(Pair)

FIRST sets in progress

Iteration 2:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 2 and Rule 3
List ::= Pair List

| ε

add first(ε) to first(List)

add first(Pair List) to first(List)

LP and ε are already in FIRST(List)

FIRST sets in progress

Iteration 2:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Where LP is ( and RP is )

Symbol Initial Iter. 1 Iter. 2

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

Applying Rule 1
Goal ::= List

add first(List) to first(Goal)

LP and ε are already in FIRST(Goal)

FIRST sets in progress

Iteration 2:

parentheses grammar

An Example

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Symbol Initial Iter. 1 Iter. 2

Goal ∅ LP, ε LP, ε

List ∅ LP, ε LP, ε

Pair ∅ LP LP

LP LP LP LP

RP RP RP RP

EOF EOF EOF EOF

FIRST Sets

1
2
3
4

Comparing the FIRST sets at the end
of iteration 1 and the end of iteration

2, nothing new is added.

Reached fixed point! We have
constructed complete FIRST sets!

parentheses grammar

FOLLOW Sets

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

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:

FIRST and FOLLOW Sets

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

Given a rule p in the grammar:

A → B1B2… Bi Bi+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

Relationship between FOLLOW sets and FIRST sets of different symbols

Follow Set Construction

• 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:

An Example for FOLLOW Set Construction

parentheses grammar

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Initialization

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

• 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

FOLLOW sets in progress

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Iteration 1 (of the outer loop below):

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

• 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

An Example for FOLLOW Set Construction

FOLLOW sets in progressparentheses 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

The order of the rules do not affect
the final FOLLOW set results:

An Example for FOLLOW Set Construction

FOLLOW sets in progressparentheses 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

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 for FOLLOW Set Construction

Rule 1

FOLLOW sets in progressparentheses 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

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 for FOLLOW Set Construction

Rule 1

FOLLOW sets in progressparentheses 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

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

EOF EOF

List ::= Pair List

An Example for FOLLOW Set Construction

Rule 2

FOLLOW sets in progressparentheses 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

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 for FOLLOW Set Construction

Rule 2

FOLLOW sets in progressparentheses 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

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 for FOLLOW Set Construction

Rule 2

FOLLOW sets in progressparentheses 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

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

EOF EOF

Pair ::= LP List RP

An Example for FOLLOW Set Construction

Rule 4

FOLLOW sets in progressparentheses grammar

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

Iteration 1:

Symbol Initial 1st 2nd

Goal EOF EOF EOF

List ∅ EOF, ? 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

Pair ::= LP List RP
• Add FIRST(RP) to

FOLLOW(List)

An Example for FOLLOW Set Construction

Rule 4

FOLLOW sets in progressparentheses 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

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 for FOLLOW Set Construction

Rule 4

FOLLOW sets in progressparentheses grammar

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

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

An Example for FOLLOW Set Construction

End of First Iteration
and Before the Second

Iteration starts

FOLLOW sets in progressparentheses grammar

Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP

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

1
2
3
4

An Example for FOLLOW Set Construction

End of First Iteration
and Before the Second

Iteration starts

FOLLOW sets in progressparentheses 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

1
2
3
4

Goal ::= List

An Example for FOLLOW Set Construction

Rule 1

• Add FOLLOW(Goal) to
FOLLOW(List)

EOF already in FOLLOW(list)

FOLLOW sets in progressparentheses 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

1
2
3
4

List ::= Pair List

An Example for FOLLOW Set Construction

Rule 2
• Add FIRST(List)-ε to

FOLLOW(Pair)
• Add FOLLOW(List) to

FOLLOW(Pair)
Added RP

FOLLOW sets in progressparentheses 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

1
2
3
4

Pair ::= LP List RP

An Example for FOLLOW Set Construction

Rule 4
• Add FIRST(RP) to

FOLLOW(List)

RP already in FOLLOW(list)

FOLLOW sets in progressparentheses 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

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

An Example for FOLLOW Set Construction

We omit the results of Iteration 3.

FOLLOW sets in progressparentheses grammar

Building Top-down Parsers

• 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

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

• 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

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

Goal ::= List

List ::= Pair List

List ::= ε

Pair ::= LP List RP

Rule PREDICT

1 EOF, LP

2 LP

3 EOF, RP

4 LP

Parentheses grammar PREDICT Sets

Is this grammar LL(1)?

Building Top-down Parsers

Goal ::= List

List ::= Pair List

List ::= ε

Pair ::= LP List RP

Rule PREDICT

1 EOF, LP

2 LP

3 EOF, RP

4 LP

Parentheses grammar PREDICT Sets

Is this grammar LL(1)?

Since only Rule 2 and Rule 3 correspond to the same non-terminal, and
PREDICT(Rule 2) and PREDICT(Rule 3) are disjoint, the grammar is LL(1).

Building Top-down Parsers

• 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

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

• 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

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

• 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

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

Building the complete parse table

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

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)

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

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

LL(1) Parsing Example

Remaining Input:
LP RP LP LP RP RP

Sentential Form:
Goal

Applied Production:

Goal

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

Goal

LL(1) Parsing Example

Remaining Input:
LP RP LP LP RP RP

Sentential Form:
Goal

Applied Production:

Goal

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

Goal

LL(1) Parsing Example

Goal

Sentential Form:
List

Applied Production:
1. Goal ::= List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

Remaining Input:
LP RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
List

Applied Production:
1. Goal ::= List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

Remaining Input:
LP RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
List

Applied Production:
1. Goal ::= List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

Remaining Input:
LP RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
Pair List

Applied Production:
2. List ::= Pair ListPair

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair
Remaining Input:

LP RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
LP List RP List

Applied Production:
4. Pair ::= LP List RP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List RP

Remaining Input:
LP RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
LP List RP List

Applied Production:

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List RP

Remaining Input:
LP RP LP LP RP RP

Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP List RP List

Applied Production:
List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List RP

Remaining Input:
RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP List

Applied Production:
3. List ::= εRP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List RP

Remaining Input:
RP LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP List

Applied Production:
RP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP LP LP RP RP

ε
Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP RP List

Applied Production:

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP LP RP RP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP Pair List

Pair

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP LP RP RP

RP ListPair

Applied Production:
2. List ::= Pair List

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP List RP ListLP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP LP RP RP

RP ListPair

Applied Production:
4. Pair ::= LP List RP

LP List RP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP List RP ListLP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP LP RP RP

RP ListPair

Applied Production:

List RPLP
Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP List RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP RP RP

RP ListPair

Applied Production:

List RPLP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP Pair List RP ListPair

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP RP RP

RP ListPair

Applied Production:
2. List ::= Pair List

List RPLP

ListPair

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP List RP List RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP RP RP

RP ListPair

Applied Production:
4. Pair ::= LP List RP

List RPLP

ListPair

LP List RP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP List RP List RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
LP RP RP

RP ListPair

Applied Production:

List RPLP

ListPair

List RPLP
Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP List RP List RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP RP

RP ListPair

Applied Production:

List RPLP

ListPair

List RPLP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP RP List RP ListRP

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP RP

RP ListPair

Applied Production:

List RPLP

ListPair

ListLP

RP
Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP RP List RP List
List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP

RP ListPair

Applied Production:

List RPLP

ListPair

ListLP

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP RP RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP

RP ListPair

Applied Production:
3. List ::= ε

List RPLP

ListPair

ListLP

RP ε

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP RP RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:
RP

RP ListPair

Applied Production:

ListLP

ListPair

ListLP

RP ε

RP
Match!

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP

LP RP RP List

List

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:

RP ListPair

Applied Production:

ListLP

ListPair

ListLP

RP ε

LL(1) Parsing Example

Goal

Sentential Form:
LP RP LP LP RP RP

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

4
List

ListPair

LP List

Remaining Input:

RP ListPair

ListLP

ListPair

ListLP

RP ε

RP ε
Applied Production:

3. List ::= ε

Recursive Descent Parsing

• Each non-terminal has an associated parsing procedure that can
recognize any sequence of tokens generated by that non-terminal

• There is a main routine to initialize all globals (e.g:the token variable
in previous code example) and call the start symbol. On return, check
whether token==EOF, and whether errors occurred.

• Within a parsing procedure, both non-terminals and terminals can
be matched:
➡ Non-terminal A: call procedure for A
➡ Token t: compare t with current input token;  

if matched, consume input, otherwise, ERROR
• Parsing procedure may contain code that performs some useful

“computations” (syntax directed translation)

Recursive descent parser for LL(1)

Recursive Descent Parsing (pseudo code)

main: {
token := next_token( );
if ( List( ) and token == EOF) print “accept” else print “error”;

}

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

bool List( ): {
switch token {

case LP:
call Pair( );
call List( );

break;
case RP:
case EOF: return true;
break;
default: return false;
} 
return true;

}

Recursive Descent Parsing (pseudo code)

LP RP EOF

Goal 1 1

List 2 3 3
Pair 4

Goal ::= List

List ::= Pair List

| ε

Pair ::= LP List RP

bool Pair( ): {
switch token {
case LP: token := next_token( );
call List( );
if ( token == RP ) {
token := next_token( );
return true;

}
else
return false;
break;
default: return false;

}
}

– Interpreter
– Code generator
– Type checker
– Performance estimator

Syntax Directed Translation

Examples:

Use hand-written recursive descent LL(1) parser

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

bool expr( ) {

switch token {
case +: token := next_token( );

expr( );
expr( ); break;

case 0..9: digit( ); break;
…

}
}

bool digit( ) { // return value of constant
switch token {

case 1: token := next_token( ); break;
case 2: token := next_token( ); break;

…
} 
}

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

bool expr( ): // return value of the expression

switch token {
case +: token := next_token( );

expr( );
expr( ); break;

case 0..9: digit( ); break;
…

}

bool digit( ): // return value of constant
switch token {

case 1: token := next_token( ); break;
case 2: token := next_token( ); break;

…
}

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +
bool expr( ): // return value of the expression

switch token {
case +: token := next_token( );

expr( );
expr( ); break;

case 0..9: digit( ); break;
…

}

bool digit( ): // return value of constant
switch token {

case 1: token := next_token( ); break;
case 2: token := next_token( ); break;

…
}

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Example: the Original Parser

1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9

+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error

What happens when you parse expression
“ + 2 + 1 2”

call

call +

call

call
+

call

Next Lecture

100

• 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:

Published by admin

Leave a Reply Cancel reply