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
2
• Homework 4 will be posted after lecture 10.
• Project 1 will be posted after homework 4 is due.
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 α.
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) 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
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
An Example
7
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
8
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
9
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
10
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
11
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
12
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
13
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
14
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
15
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
16
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
17
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
18
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
19
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
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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
29
• 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
30
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
31
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
32
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
33
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
34
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
35
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
36
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
37
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
38
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
39
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
40
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
41
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
42
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
43
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
44
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
45
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
46
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
47
• 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
48
• 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
49
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
Parentheses grammar PREDICT Sets
Is this grammar LL(1)?
Building Top-down Parsers
50
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
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
51
• 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
52
• 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
53
• 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
54
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)
55
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
56
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
1
2
3
4
Goal
LL(1) Parsing Example
57
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
1
2
3
4
Goal
LL(1) Parsing Example
58
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
1
2
3
4
List
Remaining Input:
LP RP LP LP RP RP
LL(1) Parsing Example
59
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
1
2
3
4
List
Remaining Input:
LP RP LP LP RP RP
LL(1) Parsing Example
60
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
1
2
3
4
List
Remaining Input:
LP RP LP LP RP RP
LL(1) Parsing Example
61
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
1
2
3
4
List
ListPair
Remaining Input:
LP RP LP LP RP RP
LL(1) Parsing Example
62
Goal
Sentential Form:
LP List RP List
Applied Production:
4. Pair ::= LP List RP
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
1
2
3
4
List
ListPair
LP List RP
Remaining Input:
LP RP LP LP RP RP
LL(1) Parsing Example
63
Goal
Sentential Form:
LP List RP List
Applied Production:
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
1
2
3
4
List
ListPair
LP List RP
Remaining Input:
LP RP LP LP RP RP
Match!
LL(1) Parsing Example
64
Goal
Sentential Form:
LP List RP List
Applied Production:
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List RP
Remaining Input:
RP LP LP RP RP
LL(1) Parsing Example
65
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
1
2
3
4
List
ListPair
LP List RP
Remaining Input:
RP LP LP RP RP
ε
LL(1) Parsing Example
66
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
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP LP LP RP RP
ε
Match!
RP
LL(1) Parsing Example
67
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
1
2
3
4
List
ListPair
LP List
Remaining Input:
LP LP RP RP
ε
RP
LL(1) Parsing Example
68
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
1
2
3
4
List
ListPair
LP List
Remaining Input:
LP LP RP RP
ε
RP ListPair
Applied Production:
2. List ::= Pair List
LL(1) Parsing Example
69
Goal
Sentential Form:
LP RP LP List RP ListLP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
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
70
Goal
Sentential Form:
LP RP LP List RP ListLP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
LP LP RP RP
ε
RP ListPair
Applied Production:
List RPLP
Match!
LL(1) Parsing Example
71
Goal
Sentential Form:
LP RP LP List RP List
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
LP RP RP
ε
RP ListPair
Applied Production:
List RPLP
LL(1) Parsing Example
72
Goal
Sentential Form:
LP RP LP Pair List RP ListPair
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
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
73
Goal
Sentential Form:
LP RP LP
LP List RP List RP List
LP
List
RP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
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
74
Goal
Sentential Form:
LP RP LP
LP List RP List RP List
LP
List
RP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
LP RP RP
ε
RP ListPair
Applied Production:
List RPLP
ListPair
List RPLP
Match!
LL(1) Parsing Example
75
Goal
Sentential Form:
LP RP LP
LP List RP List RP List
List
RP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP RP
ε
RP ListPair
Applied Production:
List RPLP
ListPair
List RPLP
LL(1) Parsing Example
76
Goal
Sentential Form:
LP RP LP
LP RP List RP ListRP
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP RP
ε
RP ListPair
Applied Production:
List RPLP
ListPair
ListLP
ε
RP
Match!
LL(1) Parsing Example
77
Goal
Sentential Form:
LP RP LP
LP RP List RP List
List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP
ε
RP ListPair
Applied Production:
List RPLP
ListPair
ListLP
ε
RP
LL(1) Parsing Example
78
Goal
Sentential Form:
LP RP LP
LP RP RP List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP
ε
RP ListPair
Applied Production:
3. List ::= ε
List RPLP
ListPair
ListLP
ε
RP ε
LL(1) Parsing Example
79
Goal
Sentential Form:
LP RP LP
LP RP RP List
RP
List
LP RP EOF
Goal 1 1
List 2 3 3
Pair 4
Goal ::= List
List ::= Pair List
| ε
Pair ::= LP List RP
1
2
3
4
List
ListPair
LP List
Remaining Input:
RP
ε
RP ListPair
Applied Production:
ListLP
ListPair
ListLP
ε
RP ε
RP
Match!
LL(1) Parsing Example
80
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
1
2
3
4
List
ListPair
LP List
Remaining Input:
ε
RP ListPair
Applied Production:
ListLP
ListPair
ListLP
ε
RP ε
RP
LL(1) Parsing Example
81
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
1
2
3
4
List
ListPair
LP List
Remaining Input:
ε
RP ListPair
ListLP
ListPair
ListLP
ε
RP ε
RP ε
Applied Production:
3. List ::= ε
Recursive Descent Parsing
82
• 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)
83
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
1
2
3
4
84
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
1
2
3
4
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;
}
}
85
– Interpreter
– Code generator
– Type checker
– Performance estimator
Syntax Directed Translation
Examples:
Use hand-written recursive descent LL(1) parser
Example: the Original Parser
86
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
87
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
88
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
89
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
90
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
2
Example: the Original Parser
91
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
2
call
Example: the Original Parser
92
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
2
call
call
+
Example: the Original Parser
93
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
2
call
call
+
call
Example: the Original Parser
94
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
2
call
call
+
call
1
Example: the Original Parser
95
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
2
call
call
+
call
1
call
Example: the Original Parser
96
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
2
call
call
+
call
1
call
call
Example: the Original Parser
97
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
2
call
call
+
call
1
call
call
2
Example: the Original Parser
98
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
2
call
call
+
call
1
call
call
2
Example: the Original Parser
99
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
2
call
call
+
call
1
call
call
call
call
2
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: