[SOLVED] interpreter lec9 (edited).key

$25

File Name: interpreter_lec9_(edited).key.zip
File Size: 273.18 KB

5/5 - (1 vote)

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 formX ::= Y1Y2Yk

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 formX ::= Y1Y2Yk

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 formX ::= Y1Y2Yk

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+1Bk

If Bi is a non-terminal, FOLLOW(Bi) includes

FIRST(Bi+1Bk) {} U FOLLOW(A), if FIRST(Bi+1Bk)
FIRST(Bi+1Bk)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 setSymbol 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 setSymbol 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 grammarPREDICT 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 grammarPREDICT 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, Yk1, . . . , 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;

}
}

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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

+ 09 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:

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[SOLVED] interpreter lec9 (edited).key
$25