Courses

# Top- Down Parsers Top- Down Parsers Top-down Parsing Notes | EduRev

Created by: Meghdha Sharma

## : Top- Down Parsers Top- Down Parsers Top-down Parsing Notes | EduRev

``` Page 1

Top- Down
Parsers
Page 2

Top- Down
Parsers
Top-down Parsing
? Finds the left-most derivation  for an input
string
? Starts at the Start Symbol (distinguished or
root) and creates the nodes
? Creates the tree Top-Down ?
? At node n and non-terminal NT select one of the
productions and construct children at n (using
symbols on RHS of rule)
? Find the next node at which a sub-tree is to be
constructed
Page 3

Top- Down
Parsers
Top-down Parsing
? Finds the left-most derivation  for an input
string
? Starts at the Start Symbol (distinguished or
root) and creates the nodes
? Creates the tree Top-Down ?
? At node n and non-terminal NT select one of the
productions and construct children at n (using
symbols on RHS of rule)
? Find the next node at which a sub-tree is to be
constructed
Forms of Top-Down parsing
? Recursive Descent

? Predictive Parsing
Consider this grammar
A := ab | a
S    S    S

c A d  c  A d   c  A d

a          b    a
(a)   (b)   (c)

Page 4

Top- Down
Parsers
Top-down Parsing
? Finds the left-most derivation  for an input
string
? Starts at the Start Symbol (distinguished or
root) and creates the nodes
? Creates the tree Top-Down ?
? At node n and non-terminal NT select one of the
productions and construct children at n (using
symbols on RHS of rule)
? Find the next node at which a sub-tree is to be
constructed
Forms of Top-Down parsing
? Recursive Descent

? Predictive Parsing
Consider this grammar
A := ab | a
S    S    S

c A d  c  A d   c  A d

a          b    a
(a)   (b)   (c)

Page 5

Top- Down
Parsers
Top-down Parsing
? Finds the left-most derivation  for an input
string
? Starts at the Start Symbol (distinguished or
root) and creates the nodes
? Creates the tree Top-Down ?
? At node n and non-terminal NT select one of the
productions and construct children at n (using
symbols on RHS of rule)
? Find the next node at which a sub-tree is to be
constructed
Forms of Top-Down parsing
? Recursive Descent

? Predictive Parsing
Consider this grammar
A := ab | a
S    S    S

c A d  c  A d   c  A d

a          b    a
(a)   (b)   (c)

Several Difficulties with Top-Down Parsing
1. Left Recursion: A grammar is  left recursive  if it has a non-terminal
A such that there is  a derivation.
+
A ? Aa for some string a . A left recursive grammar can
cause a top-down parser to go into an infinite loop.

2. Backtracking: If we make a sequence of erroneous expansions and
subsequently discover a mismatch, we may have to undo the
semantic effects of making these erroneous expansions.

3. The order in which the alternates are tried can affect the language
accepted.

```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!