Compiler Construction - CS606 Power Point Slides Lecture 13.ppt

Compiler construction lecture ( Parser) which is used to make the tokens different parsing technique's

1. Parsing Parsing
TechniquesTechniques

2. 2
Parsing TechniquesParsing 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

3. 3
Parsing TechniquesParsing 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

4. 4
Parsing TechniquesParsing 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

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

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

7. 7
Parsing TechniquesParsing Techniques
Bottom-up parsers
Start at the leaves and grow
toward root
As input is consumed,
encode possibilities in an
internal state.

8. 8
Parsing TechniquesParsing Techniques
Bottom-up parsers
Start at the leaves and grow
toward root
As input is consumed,
encode possibilities in an
internal state.

9. 9
Parsing TechniquesParsing Techniques
Bottom-up parsers
Start at the leaves and grow
toward root
As input is consumed,
encode possibilities in an
internal state.

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

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

12. 12
Top-Down ParserTop-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. 13
Top-Down ParserTop-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. 14
Top-Down Parsing AlgorithmTop-Down Parsing Algorithm
Construct the root node of
the parse tree
Repeat until the fringe of the
parse tree matches input
string

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

16. 16
Top-Down ParsingTop-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. 17
Top-Down ParsingTop-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. 18
Top-Down ParsingTop-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. 19
Top-Down ParsingTop-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. 20
Top-Down ParsingTop-Down Parsing
The key is picking right
production in step 1.
That choice should be
guided by the input string

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

22. 22
Expression GrammarExpression Grammar
1Goal→expr
2expr→expr + term
3 |expr - term
4 |term
5term→term * factor
6 |term ∕ factor
7 |factor
8factor→ number
9 |id
10 |( expr )

23. 23
Top-Down ParsingTop-Down Parsing
Let’s try parsing
x – 2 * y

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

25. 25
This worked well except that “–” does not
match “+”
PSentential Forminput
-Goal x – 2 * y
1expr x – 2 * y
2expr + term x – 2 * y
4term + term x – 2 * y
7factor + term x – 2 * y
9<id,x> + term x – 2 * y
9<id,x> + term x – 2 * y

26. 26
The parser must backtrack to here
PSentential Form input
-Goal x – 2 * y
1expr x – 2 * y
2expr + term x – 2 * y
4term + term x – 2 * y
7factor + term x – 2 * y
9<id,x> + term x – 2 * y
9<id,x> + term x – 2 * y

27. 27
This time the “–” and “–” matched
PSentential Forminput
-Goal x – 2 * y
1expr x – 2 * y
2expr – term x – 2 * y
4term – term x – 2 * y
7factor – term x – 2 * y
9<id,x> – term x – 2 * y
9<id,x> – term x – 2 * y

28. 28
We can advance past “–” to look at “2”
PSentential Forminput
-Goal x – 2 * y
1expr x – 2 * y
2expr – term x – 2 * y
4term – term x – 2 * y
7factor – term x – 2 * y
9<id,x> – term x – 2 * y
9<id,x> – term x – 2 * y
-<id,x> – term x – 2 * y

29. 29
Now, we need to expand “term”
PSentential Forminput
-Goal x – 2 * y
1expr x – 2 * y
2expr – term x – 2 * y
4term – term x – 2 * y
7factor – term x – 2 * y
9<id,x> – term x – 2 * y
9<id,x> – term x – 2 * y
-<id,x> – term x – 2 * y

30. 30
PSentential Forminput
-<id,x> – term x – 2 * y
7<id,x> – factorx – 2 * y
9<id,x> – <num,2> x – 2 * y
-<id,x> – <num,2> x – 2 * y
“2” matches “2”
We have more input but no non-terminals
left to expand

31. 31
The expansion terminated
too soon
 Need to backtrack
PSentential Forminput
-<id,x> – term x – 2 * y
7<id,x> – factorx – 2 * y
9<id,x> – <num,2> x – 2 * y
-<id,x> – <num,2> x – 2 * y

32. 32
PSentential Form input
-<id,x> – term x – 2 * y
5<id,x> – term * factorx – 2 * y
7<id,x> – factor * factorx – 2 * y
8<id,x> – <num,2> * factorx – 2 * y
-<id,x> – <num,2> * factorx – 2  * y
-<id,x> – <num,2> * factorx – 2 *  y
9<id,x> – <num,2> * <id,y>x – 2 *  y
-<id,x> – <num,2> * <id,y>x – 2 * y 
Success! We matched and consumed all the input

33. 33
Another Possible ParseAnother Possible Parse
PSentential Form input
-Goal x – 2 * y
1expr x – 2 * y
2expr +term x – 2 * y
2expr +term +term x – 2 * y
2expr +term +term +term x – 2 * y
2expr +term +term +term +....x – 2 * y
consuming no input!!
Wrong choice of expansion leads to non-termination
Parser must make the right choice

34. 34
Left RecursionLeft Recursion
Top-down parsers cannot
handle left-recursive
grammars

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

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

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

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

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

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

41. 41
Eliminating Left RecursionEliminating Left Recursion
To remove left recursion, we
transform the grammar

42. 42
Eliminating Left RecursionEliminating Left Recursion
Consider a grammar fragment:
A → A 
| 
where neither  nor  starts
with A.

43. 43
Eliminating Left RecursionEliminating Left Recursion
We can rewrite this as:
A →  A'
A' →  A'
| 
where A' is a new non-terminal

44. 44
Eliminating Left RecursionEliminating Left Recursion
We can rewrite this as:
A →  A'
A' →  A'
| 
where A' is a new non-terminal

45. 45
Eliminating Left RecursionEliminating Left Recursion
A →  A '
A' →  A'
| 
This accepts the same
language but uses only right
recursion

46. 46
Eliminating Left RecursionEliminating Left Recursion
The expression grammar we
have been using contains two
cases of left- recursion

47. 47
Eliminating Left RecursionEliminating Left Recursion
expr→expr + term
|expr – term
|term
term→
term * factor
|term ∕ factor
|factor

48. 48
Eliminating Left RecursionEliminating Left Recursion
Applying the transformation yields
expr→term expr'
expr'→+ term expr'
|– term expr'
|

49. 49
Eliminating Left RecursionEliminating Left Recursion
Applying the transformation yields
term→factor term'
term'→
* factor term'
|∕ factor term'
|

50. 50
Eliminating Left RecursionEliminating Left Recursion
These fragments use only
right recursion
They retain the original left
associativity
A top-down parser will
terminate using them.

51. 51
Eliminating Left RecursionEliminating Left Recursion
These fragments use only
right recursion
They retain the original left
associativity
A top-down parser will
terminate using them.

52. 52
Eliminating Left RecursionEliminating Left Recursion
These fragments use only
right recursion
They retain the original left
associativity
A top-down parser will
terminate using them.

53. 53
1Goal →expr
2expr →term expr'
3expr'→ + term expr'
4 |– term expr'
5 |
6term →factor term'
7term'→ * factor term'
8 |∕ factor term'
9 |
10factor→ number
11 |id
12 |( expr )

54. 54
Predictive ParsingPredictive 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. 55
Predictive ParsingPredictive 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. 56
Predictive ParsingPredictive Parsing
How much lookahead is
needed?
In general, an arbitrarily
large amount

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

58. 58
Predictive ParsingPredictive Parsing
Fortunately, large classes
of CFGs can be parsed
with limited lookahead
Most programming
languages constructs fall in
those subclasses

59. 59
Predictive ParsingPredictive Parsing
Fortunately, large classes
of CFGs can be parsed
with limited lookahead
Most programming
languages constructs fall in
those subclasses

60. 60
Predictive ParsingPredictive Parsing
Basic Idea:
Given A →  | ,
the parser should be
able to choose
between  and .

61. 61
Predictive ParsingPredictive 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. 62
Predictive ParsingPredictive Parsing
That is,
x  FIRST()
iff 

xfor some.