Parsing

Techniques
Parsing Techniques
Top-down parsers
 Start at the root of the parse
tree and grow towards
leaves.
 Pick a production and try to
match the input
2
Parsing Techniques
Top-down parsers
 Start at the root of the parse
tree and grow towards
leaves.ck a production and
try to match the input

3
Parsing Techniques
Top-down parsers
 Start at the root of the parse
tree and grow towards
leaves.
 Pick a production and try to
match the input
4
Parsing Techniques
Top-down parsers
 Bad “pick”  may need to
backtrack
 Some grammars are
backtrack-free.

5
Parsing Techniques
Top-down parsers
 Bad “pick”  may need to
backtrack
 Some grammars are
backtrack-free.

6
Parsing Techniques
Bottom-up parsers
 Start at the leaves and grow
toward root
 As input is consumed,
encode possibilities in an
internal state.
7
Parsing Techniques
Bottom-up parsers
 Start at the leaves and grow
toward root
 As input is consumed,
encode possibilities in an
internal state.
8
Parsing Techniques
Bottom-up parsers
 Start at the leaves and grow
toward root
 As input is consumed,
encode possibilities in an
internal state.
9
 Compiler
Construction
Sohail Aslam
Lecture 13
Parsing Techniques
Bottom-up parsers
 Start in a state valid for
legal first tokens
 Bottom-up parsers handle a
large class of grammars

11
Parsing Techniques
Bottom-up parsers
 Start in a state valid for
legal first tokens
 Bottom-up parsers handle a
large class of grammars

12
Top-Down Parser
 A top-down parser starts
with the root of the parse
tree.
 The root node is labeled
with the goal symbol of the
grammar
13
Top-Down Parser
 A top-down parser starts
with the root of the parse
tree.
 The root node is labeled
with the goal symbol of the
grammar
14
Top-Down Parsing Algorithm
 Construct the root node of
the parse tree
 Repeat until the fringe of the
parse tree matches input
string

15
Top-Down Parsing Algorithm
 Construct the root node of
the parse tree
 Repeat until the fringe of the
parse tree matches input
string

16
Top-Down Parsing
 At a node labeled A, select
a production with A on its
lhs
 for each symbol on its rhs,
construct the appropriate
child
17
Top-Down Parsing
 At a node labeled A, select
a production with A on its
lhs
 for each symbol on its rhs,
construct the appropriate
child
18
Top-Down Parsing
 When a terminal symbol is
added to the fringe and it
does not match the fringe,
backtrack
 Find the next node to be
expanded
19
Top-Down Parsing
 When a terminal symbol is
added to the fringe and it
does not match the fringe,
backtrack
 Find the next node to be
expanded
20
Top-Down Parsing
 The key is picking right
production in step 1.
 That choice should be
guided by the input string

21
Top-Down Parsing
 The key is picking right
production in step 1.
 That choice should be
guided by the input string

22
Expression Grammar
1 Goal → expr
2 expr → expr + term
3 | expr - term
4 | term
5 term → term * factor
6 | term ∕ factor
7 | factor
8 factor → number
9 | id
1 | ( expr ) 23
0
Top-Down Parsing
 Let’s try parsing

x–2*y

24
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr + term x – 2 * y
4 term + term x – 2 * y
7 factor + term x – 2 * y
9 <id,x> + term x – 2 * y
9 <id,x> + term x – 2 * y
25
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr + term x – 2 * y
4 term + term x – 2 * y
7 factor + term x – 2 * y
9 <id,x> + term x – 2 * y
9 <id,x> + term x – 2 * y

This worked well except that “–” does not

match “+”
26
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr + term x – 2 * y
4 term + term x – 2 * y
7 factor + term x – 2 * y
9 <id,x> + term x – 2 * y
9 <id,x> + term x – 2 * y

The parser must backtrack to here

27
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr – term x – 2 * y
4 term – term x – 2 * y
7 factor – term x – 2 * y
9 <id,x> – term x – 2 * y
9 <id,x> – term x – 2 * y

This time the “–” and “–” matched

28
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr – term x – 2 * y
4 term – term x – 2 * y
7 factor – term x – 2 * y
9 <id,x> – term x – 2 * y
9 <id,x> – term x – 2 * y
- <id,x> – term x – 2 * y
We can advance past “–” to look at “2”
29
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr – term x – 2 * y
4 term – term x – 2 * y
7 factor – term x – 2 * y
9 <id,x> – term x – 2 * y
9 <id,x> – term x – 2 * y
- <id,x> – term x – 2 * y

Now, we need to expand “term”

30
 P Sentential Form input
- <id,x> – term x – 2 * y
7 <id,x> – factor x – 2 * y
9 <id,x> – x – 2 * y
<num,2>
- <id,x> – x – 2 * y
<num,2>“2” matches “2”
We have more input but no non-terminals
left to expand

31
P Sentential Form input
- <id,x> – term x – 2 * y
7 <id,x> – factor x – 2 * y
9 <id,x> – x – 2 * y
<num,2>
- <id,x> – x – 2 * y
<num,2>
 The expansion terminated
too soon
  Need to backtrack
32
 P Sentential Form input
- <id,x> – term x – 2 * y
5 <id,x> – term * factor x – 2 * y
7 <id,x> – factor * factor x – 2 * y
8 <id,x> – <num,2> * x – 2 * y
factor
- <id,x> – <num,2> * x–2*y
factor
- <id,x> – <num,2> * x – 2 * y
factor
9 <id,x>
Success! – <num,2>
We matched and consumed
* xall–the
2 input
* y
<id,y> 33
Another Possible Parse
P Sentential Form input
- Goal x – 2 * y
1 expr x – 2 * y
2 expr +term x – 2 * y
2 expr +term +term x – 2 * y
2 expr +term +term +term x – 2 * y
2 expr +term +term +term x – 2 * y
+....
Wrong choice of expansion
consuming no input!!
Parser must make the leads
right to non-termination
choice
34
Left Recursion

Top-down parsers cannot

handle left-recursive
grammars

35
Left Recursion
Formally,
A grammar is left recursive
if  A  NT such that  a
derivation A * A , for
some string   (NT  T)*

36
Left Recursion
 Our expression grammar is
left recursive.
 This can lead to non-
termination in a top-down
parser

37
Left Recursion
 Our expression grammar is
left recursive.
 This can lead to non-
termination in a top-down
parser

38
Left Recursion
 Non-termination is bad in
any part of a compiler!

39
Left Recursion
 For a top-down parser, any
recursion must be a right
recursion
 We would like to convert
left recursion to right
recursion
40
Left Recursion
 For a top-down parser, any
recursion must be a right
recursion
 We would like to convert
left recursion to right
recursion
41
Eliminating Left Recursion

To remove left recursion, we

transform the grammar

42
Eliminating Left Recursion
Consider a grammar fragment:

A → A
| 

where neither  nor  starts

with A.

43
Eliminating Left Recursion
We can rewrite this as:

A →  A'

A' →  A'
| 

where A' is a new non-terminal

44
Eliminating Left Recursion
We can rewrite this as:

A →  A'

A' →  A'
| 

where A' is a new non-terminal

45
Eliminating Left Recursion
A →A'
A' →  A'
| 

 This accepts the same

language but uses only right
recursion
46
Eliminating Left Recursion
The expression grammar we
have been using contains two
cases of left- recursion

47
Eliminating Left Recursion

expr → expr + term

| expr – term
| term
term → term * factor
| term ∕ factor
| factor 48
Eliminating Left Recursion
Applying the transformation yields

expr → term expr'

expr' → + term expr'
| – term expr'
| 
49
Eliminating Left Recursion
Applying the transformation yields

term → factor term'

term' → * factor term'
| ∕ factor term'
| 
50
Eliminating Left Recursion
 These fragments use only
right recursion
 They retain the original left
associativity
 A top-down parser will
terminate using them.
51
Eliminating Left Recursion
 These fragments use only
right recursion
 They retain the original left
associativity
 A top-down parser will
terminate using them.
52
Eliminating Left Recursion
 These fragments use only
right recursion
 They retain the original left
associativity
 A top-down parser will
terminate using them.
53
1 Goal → expr
2 expr → term expr'
3 expr' → + term expr'
4 | – term expr'
5 | 
6 term → factor term'
7 term' → * factor term'
8 | ∕ factor term'
9 | 
10 factor → number
11 | id
12 | ( expr ) 54
Predictive Parsing
 If a top down parser picks
the wrong production, it
may need to backtrack
 Alternative is to look ahead
in input and use context to
pick correctly
55
Predictive Parsing
 If a top down parser picks
the wrong production, it
may need to backtrack
 Alternative is to look ahead
in input and use context to
pick correctly
56
Predictive Parsing
 How much lookahead is
needed?
 In general, an arbitrarily
large amount

57
Predictive Parsing
 How much lookahead is
needed?
 In general, an arbitrarily
large amount

58
Predictive Parsing
 Fortunately, large classes
of CFGs can be parsed
with limited lookahead
 Most programming
languages constructs fall in
those subclasses
59
Predictive Parsing
 Fortunately, large classes
of CFGs can be parsed
with limited lookahead
 Most programming
languages constructs fall in
those subclasses
60
Predictive Parsing
Basic Idea:
Given A →  | ,
the parser should be
able to choose
between  and .
61
Predictive Parsing
FIRST Sets:
For some rhs   G, define
FIRST() as the set of
tokens that appear as the
first symbol in some string
that derives from .

62
Predictive Parsing
That is,
x  FIRST()
iff  xfor some.


63