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  
  S := cAd 
   A := ab | a 
Input string is  cad 
  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  
  S := cAd 
   A := ab | a 
Input string is  cad 
  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  
  S := cAd 
   A := ab | a 
Input string is  cad 
  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. 
 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!