程序代写代做代考 compiler lec6.key

lec6.key

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 6: LL(1) Parsing

September 21, 2018

Class Information

2

• Homework 2 posted, due Tuesday 9/25/2018 11:55pm.

Review: Top-Down Parsing – LL(1)

3

• The parse tree is constructed from the root, expanding non-terminal
nodes on the tree’s frontier following a leftmost derivation.

• The input program is read from left to right, and input tokens are read
(consumed) as the program is parsed.

• The next non-terminal symbol is replaced using one of its rules. The
particular choice has to be unique and uses parts of the input (partially
parsed program), for instance the first token of the remaining input.

Basic Idea:

x

y

α
β

Another LL(1) Parsing Example

4

::= id
::= , id
::= ;

Consider this example grammar:

Another LL(1) Parsing Example

5

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

Consider this example grammar:

How to parse the following input string?

A, B, C;

6

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

Remaining Input:
A, B, C;

Sentential Form:
id_list

Applied Production:

id_list

Another LL(1) Parsing Example

7

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

Remaining Input:
A, B, C;

Sentential Form:
id(A) id_list_tail

Applied Production:
id_list ::= id id_list_tail

id_list_tail

id_list

id(A)

Another LL(1) Parsing Example

8

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

Remaining Input:
A , B , C ;

Sentential Form:
id(A) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)
Match!

Another LL(1) Parsing Example

9

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

Remaining Input:
, B , C ;

Sentential Form:
id(A) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

Another LL(1) Parsing Example

10

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

Remaining Input:
, B , C ;

Sentential Form:
id(A) , id(B) id_list_tail

Applied Production:
id_list_tail ::= , id id_list_tail

id_list_tail

id_list

id(A)

, id(B) id_list_tail

Another LL(1) Parsing Example

11

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

Remaining Input:
, B , C ;

Sentential Form:
id(A) , id(B) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail
Match!

Another LL(1) Parsing Example

12

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

Remaining Input:
B , C ;

Sentential Form:
id(A) , id(B) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

Another LL(1) Parsing Example

13

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

Remaining Input:
B , C ;

Sentential Form:
id(A) , id(B) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail
Match!

Another LL(1) Parsing Example

14

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

Remaining Input:
, C ;

Sentential Form:
id(A) , id(B) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

Another LL(1) Parsing Example

15

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

Remaining Input:
, C ;

Sentential Form:
id(A) , id(B) , id(C) id_list_tail

Applied Production:
id_list_tail ::= , id id_list_tail

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

Another LL(1) Parsing Example

16

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

Remaining Input:
, C ;

Sentential Form:
id(A) , id(B) , id(C) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail
Match!

Another LL(1) Parsing Example

17

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

Remaining Input:
C ;

Sentential Form:
id(A) , id(B) , id(C) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

Another LL(1) Parsing Example

18

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

Remaining Input:
C ;

Sentential Form:
id(A) , id(B) , id(C) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail
Match!

Another LL(1) Parsing Example

19

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

Remaining Input:
;

Sentential Form:
id(A) , id(B) , id(C) id_list_tail

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

Another LL(1) Parsing Example

20

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

Remaining Input:
;

Sentential Form:
id(A) , id(B) , id(C) ;

Applied Production:
id_list_tail ::= ;

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

;

Another LL(1) Parsing Example

21

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

Remaining Input:
;

Sentential Form:
id(A) , id(B) , id(C) ;

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

;
Match!

Another LL(1) Parsing Example

22

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

Remaining Input:

Sentential Form:
id(A) , id(B) , id(C) ;

Applied Production:

id_list_tail

id_list

id(A)

, id(B) id_list_tail

, id(C) id_list_tail

;

Another LL(1) Parsing Example

Predictive Parsing

23

Basic idea:

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

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

That is

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

a string of symbols

24

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

Remaining Input:
, B , C ;

Applied Production:

id_list_tail

id_list

id(A)

Revisiting the id_list Example

25

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

Remaining Input:
, B , C ;

Applied Production:
id_list_tail ::= , id id_list_tail

id_list_tail

id_list

id(A)

, id(B) id_list_tail

Revisiting the id_list Example

26

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

Remaining Input:
, B , C ;

id_list_tail

id_list

id(A)

, id(B) id_list_tail
Match!

Revisiting the id_list Example

Applied Production:
id_list_tail ::= , id id_list_tail

27

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

Remaining Input:
, B , C ;

Applied Production:

id_list_tail

id_list

id(A)

Revisiting the id_list Example

28

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

Remaining Input:
, B , C ;

Applied Production:
id_list_tail ::= ;

id_list_tail

id_list

id(A)

;

Revisiting the id_list Example

Mismatch!

29

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

Remaining Input:
, B , C ;

id_list_tail

id_list

id(A)

Revisiting the id_list Example

If the first token of remaining input is “,” we choose the rule

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

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

id_list_tail ::= , id id_list_tail

id_list_tail ::= ;

FIRST( , id id_list_tail ) = { , }

FIRST( ; ) = { ; }

Predictive Parsing

30

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

one of α and β can derive ε.

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

Key Property:

31

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

Remaining Input:
, B , C ;

id_list_tail

id_list

id(A)

Revisiting the id_list Example

FIRST( , id id_list_tail ) = { , }

FIRST( ; ) = { ; }

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

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

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

id_list_tail ::= , id id_list_tail

id_list_tail ::= ;

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

Predictive Parsing

32

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

one of α and β can derive ε.

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

Key Property:

This rule is intuitive. However, it is not enough, because
it doesn’t handle ε rules. How to handle ε rules?

Revisiting the LL(1) Parsing Example

33

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Revisiting the LL(1) Parsing Example

34

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Sa b
S ::= a S b

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

Revisiting the LL(1) Parsing Example

35

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

Revisiting the LL(1) Parsing Example

36

S ::= a S b | ε

S Remaining Input: b b b

Applied Production:

Sa b

Sa b

S ba

ε
S ::= ε

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

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

Predictive Parsing

37

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

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

FIRST and FOLLOW sets can be constructed automatically

Predictive Parsing

38

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

one of α and β can derive ε.

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

Key Property:

This would allow the parser to make a correct choice with a
lookahead of only one symbol!

Predictive Parsing

39

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

one of α and β can derive ε.

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

Key Property:

This would allow the parser to make a correct choice with a
lookahead of only one symbol!

Predictive Parsing

40

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

one of α and β can derive ε.

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

Key Property:

This would allow the parser to make a correct choice with a
lookahead of only one symbol!

LL(1) Grammar

41

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Define PREDICT(A ::= δ) for rule A ::= δ

A Grammar is LL(1) iff
(A ::= α and A ::= β) implies

PREDICT( A ::= α) ∩ PREDICT( A ::= β) = ∅

Back to Our Example

42

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

43

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

44

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

45

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

46

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

47

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Back to Our Example

48

Start ::= S eof
S ::= a S b | ε

FIRST(aSb) = {a}
FIRST(ε) = {ε}
FOLLOW(S) = {eof, b}

PREDICT(S ::= aSb) = {a}
PREDICT(S ::= ε) = ( FIRST(ε) – {ε} ) ∪ FOLLOW(S) ={eof, b}

Define PREDICT(A ::= δ) for rule A ::= δ

• FIRST (δ) – { ε } U Follow (A), if ε ∈ FIRST(δ)
• FIRST (δ) otherwise

Is the grammar LL(1)?

Table Driven LL(1) Parsing

49

S ::= a S b | ε

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

LL(1) parse table

Example:

How to parse input a a a b b b ?

Table Driven LL(1) Parsing

50

a b eof other
S aSb ε ε error

S ::= a S b | ε

LL(1) parse table

Example:

How to parse input a a a b b b ?

51

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()

52

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()

53

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()

54

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()

55

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()

Top – Down Parsing – LL(1) (cont.)

56

Example:

S ::= a S b | ε

How can we parse (automatically construct a leftmost derivation)
the input string a a a b b b using a PDA (push-down automaton)
and only the first symbol of the remaining input?

INPUT: a a a b b b eof

LL(1) Parsing Example

57

S ::= a S b | ε

S Remaining Input: a a a b b b

Sentential Form:
S

Applied Production:

S
a b eof other

S aSb ε ε error

LL(1) Parsing Example

58

S ::= a S b | ε

S Remaining Input: a a a b b b

Sentential Form:
a S b

Applied Production:
S ::= a S b

Sa b

a

S

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

59

S ::= a S b | ε

S Remaining Input: a a a b b b

Sentential Form:
a S b

Applied Production:

Sa b

Match!

a

S

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

60

S ::= a S b | ε

S Remaining Input: a a b b b

Sentential Form:
a S b

Applied Production:

Sa b

S

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

61

S ::= a S b | ε

S Remaining Input: a a b b b

Sentential Form:
a a S b b

Applied Production:
S ::= a S b

Sa b

Sa b

a

S

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

62

S ::= a S b | ε

S Remaining Input: a a b b b

Sentential Form:
a a S b b

Applied Production:

Sa b

Sa b

Match!
a

S

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

63

S ::= a S b | ε

S Remaining Input: a b b b

Sentential Form:
a a S b b

Applied Production:

Sa b

Sa b

S

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

64

S ::= a S b | ε

S Remaining Input: a b b b

Sentential Form:
a a a S b b b

Applied Production:
S ::= a S b

Sa b

Sa b

S ba

a

S

b

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

65

S ::= a S b | ε

S Remaining Input: a b b b

Sentential Form:
a a a S b b b

Applied Production:

Sa b

Sa b

S ba
Match!

a

S

b

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

66

S ::= a S b | ε

S Remaining Input: b b b

Sentential Form:
a a a S b b b

Applied Production:

Sa b

Sa b

S baS

b

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

67

S ::= a S b | ε

S Remaining Input: b b b

Sentential Form:
a a a b b b

Applied Production:
S ::= ε

Sa b

Sa b

S ba

ε
b

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

68

S ::= a S b | ε

S Remaining Input: b b b

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

ε
Match!b

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

69

S ::= a S b | ε

S Remaining Input: b b

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

εb

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

70

S ::= a S b | ε

S Remaining Input: b b

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

ε

Match!

b

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

71

S ::= a S b | ε

S Remaining Input: b

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

ε

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

72

S ::= a S b | ε

S Remaining Input: b

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

ε

Match!

b
a b eof other

S aSb ε ε error

LL(1) Parsing Example

73

S ::= a S b | ε

S Remaining Input:

Sentential Form:
a a a b b b

Applied Production:

Sa b

Sa b

S ba

ε

a b eof other
S aSb ε ε error

Predictive Parsing

74

scanner parser

stack

parsing
tables

source
code

intermediate
representation

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

Now, a predictive parser looks like:

Predictive Parsing

75

scanner parser

stack

parsing
tables

source
code

intermediate
representation

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

Now, a predictive parser looks like:

grammar parser
generator

Recursive Descent Parsing

76

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

Now, we can produce a recursive descent parser for our LL(1) grammar.
Recursive descent is one of the simplest parsing techniques used in
practical compilers:

Recursive Descent Parsing (pseudo code)

77

a b eof other
S aSb ε ε error

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

}

78

bool S: {
switch token {

case a: token := next_token( );
call S( );
if (token == b) {
token := next_token( );
return true;

}
else
return false;
break;
case b:
case eof: return true;
break;
default: return false;

}
}

Recursive Descent Parsing (pseudo code)

a b eof other
S aSb ε ε error

Next Lecture

79

• LL(1) parsing and syntax directed translation
• Read Scott, Chapter 2.3.1 – 2.3.3

Next Time: