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