Top down parsering and bottom up parsering.pptx

Compiler techniques

1. Top down parsing The top-down parsing technique parses the input, and starts constructing a parse tree from the root node gradually moving down to the leaf nodes. When the parser starts constructing the parse tree from the start symbol and then tries to transform the start symbol to the input, it is called top-down parsing. Top down parsing is a left most derivation.  

2. Recursive descent parsing : It is a common form of top-down parsing. It is called recursive as it uses recursive procedures to process the input. Recursive descent parsing suffers from backtracking . Backtracking : It means, if one derivation of a production fails, the syntax analyzer restarts the process using different rules of same production. This technique may process the input string more than once to determine the right production. Top down parsing

3. For example, consider the grammar E ::= E+T | T (E is the start symbol) T ::= T*F | F F ::= id (assume some finite set of possible ids) Here is a top-down parse of the sentence x+y*z. Note that it is LL: we always expand the leftmost nonterminal node. Top down parsring

4. Top down parsing

5. The top-down parse corresponds to the derivation E ->E+T T+T F+T x+T x+T *F x+F *F x+y*F x+y*z Top down parsing

6. As the name suggests, bottom-up parsing starts with the input symbols and tries to construct the parse tree up to the start symbol. Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches the root node. Here, we start from a sentence and then apply production rules in reverse manner in order to reach the start symbol. Bottom up parsing is a right most derivation. Bottom-up Parsing

7. Here is a bottom-up parse of the same sentence: x+y*z. Note that both parses produce the same tree; it is the order in which the nodes are produced that changes. To read this as a derivation we have to go from the bottom to the top, and then it is LR: we always expand the rightmost node. Bottom-up Parsing

8. Bottom-up Parsing

9. Here is the bottom-up parse written as a derivation: E E+T E+T*F E+T*z E+F*z E+y *z T+y *z F+y *z x+y*z Bottom-up Parsing

10. Top down and bottom up parsing