Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 16
TOP DOWN & BOTTOM UP PARSING
Prepared By: Mr.Roshan S. Bhanuse Asst. Prof. IT YCCE Nagpur .
PARSING ■ It is the process of analyzing a continuous stream of input in order to
determine its grammatical structure with respect to a given formal
grammar .
Parse tree:
Graphical representation of a derivation or deduction is called a parse
tree. Each interior node of the parse tree is a non-terminal; the children of
the node can be terminals or non-terminals.
Types of Parsing.
1. Top down parsing
2. Bottom up parsing Parsing…. Ø Top-down parsing : A parser can start with the start symbol and try to
transform it to the input string. Example : LL Parsers.
Ø Bottom-up parsing : A parser can start with input and attempt to rewrite
it into the start symbol. Example : LR Parsers.
TOP-DOWN PARSING It can be viewed as an attempt to find a left-most derivation for an input string or an attempt to
construct a parse tree for the input starting from the root to the leaves. ■ Example for :
Backtracking:
Consider the grammar G : S → cAd
A→ab|a
and the input string w=cad.
The parse tree can be constructed using the following top-down approach : Step1: Initially create a tree with single node labeled S. An input pointer points to ‘c’, the first symbol of w. Expand the tree with the production of S. Step2:
The leftmost leaf ‘c’ matches the first symbol of w, so advance the input
pointer to the second symbol of w ‘a’ and consider the next leaf ‘A’.
Expand A using the first alternative.
BACKTRACKING….. Step 3: The second symbol ‘a’ of w also matches with second leaf
of tree. So advance the input pointer to third symbol of w
‘d’.But the third leaf of tree is b which does not match with the input symbol d. Hence discard the chosen production and reset the pointer to
second backtracking. Step4: BACKTRACKING…..
Now try the second alternative for A. Now we
can halt and announce the successful completion of parsing. BOTTOM-UP PARSING Constructing a parse tree for an input string beginning at the leaves and
going towards the root is called bottom-up parsing. A general type of
bottom-up parser is a shift-reduce parser. SHIFT-REDUCE PARSING
Shift-reduce parsing is a type of bottom-up parsing that attempts to
construct a parse tree for an input string beginning at the leaves (the bottom) and working up towards the root (the top). BOTTOM-UP PARSING….
Example: Consider the grammar: E→E+E
E→E*E E→(E)
E→id
And the input string id1+id2*id3
BOTTOM-UP PARSING….
Actions in shift-reduce parser:
•shift - The next input symbol is shifted onto the top of the stack. •reduce - The parser replaces the handle within a stack with a non-terminal. •accept - The parser announces successful completion of parsing. •error - The parser discovers that a syntax error has occurred and calls an error recovery routine. BOTTOM-UP PARSING…. THANK YOU!!!!!!
