Types of Parser

Parser types
Top Down Parser
Bottom up Parser
LALR(0) Parser
SLR(0) Parser
LL(0) Parser
LR(!) Parser

1. Types of Parsers Group : TY 57

2. Contents Parser Types of Parser Top down parser Bottom up parser Difference between top-down and bottom-up parser Conclusion

3. Parser Parser is a compiler that is used to break the data into smaller elements coming from lexical analysis phase. A parser takes input in the form of sequence of tokens and produces output in the form of parse tree. There are mainly 2 types of parsing in compiler design. Top Down Parser Bottom Up Parser

4. Role of Parser

5. Types of Parser

6. Top-Down Parser 1.

7. G enerates parse for the given input string with the help of grammar productions by expanding the non-terminals. The process of constructing the parse tree which starts from the root and goes down to the leaf. There are 2 types of top down parser. 1) Recursive descent parser. 2) LL(1) parser

8. Recursive Descent Parser T echnique that constructs the parse tree from the top and the input is read from left to right. There are two types of recursive descent parser. 1) Backtracking parser 2) Non-Backtracking parser. Given Grammer: S → aAd A → ab / a Input string: W = cad

9. W = cad i/p

10. Non Recursive Descent parser Also known as LL(1) parser or predictive parser or dynamic parser. S pecial form of recursive descent parsing, where no backtracking is required. So this can predict which products to use to replace the input string.

11. Algorithm to construct LL(1) Parser Step 1: First check for left recursion in the grammar, if there is left recursion in the grammar remove that and go to step 2. Step 2: Calculate First() and Follow() for all non-terminals. Step 3: For each production A –> α. (A tends to alpha) Find First(α) and for each terminal in First(α), make entry A –> α in the table. If First(α) contains ε (epsilon) as terminal than, find the Follow(A) and for each terminal in Follow(A), make entry A –> α in the table. If the First(α) contains ε and Follow(A) contains $ as terminal, then make entry A –> α in the table for the $.

12. 2. Bottom-Up Parser

13. Starts from the leaf nodes of a tree and works in upward direction till it reaches the root node. Generates the parse tree for the given input string with the help of grammar productions by compressing the non-terminals. There are 2 types of bottom up parser. 1) LR parser 2) Operator Precedence parser.

14. LR-Parser In the LR parsing, "L" stands for left-to-right scanning of the input, and “R” stands for constructing a right most derivation in reverse. It is used to parse the large class of grammars. generates the parse tree for the given string by using unambiguous grammar.

15. LR(0) parser An LR(O)parser is a shift-reduce parser that uses zero tokens of lookahead to determine what action to take (hence the 0). We need two functions – Closure(): If I is a set of items for a grammar G, then closure(I) is the set of items constructed from I by the two rules: Goto(): Goto(I, X) => 1. Add I by moving dot after X. 2. Apply closure to first step SLR(1) parser T he SLR parser is similar to LR(0) parser except that the reduced entry. SLR(1) parsers can parse a larger number of grammars than LR(0). There are 2 functions in SLR(1) parser such as goto[list of terminals] and action[list of non-terminals]

16. CLR(1) Parser Canonical LR parser. Large set of items called LR(1) items. It is a more powerful LR parser and makes use of lookahead symbols. STEPS: Add Augment Production rule ,insert ‘.’ symbol at the first position for every production in G . Add the lookahead at each state. If variable comes then open each statement.Otherwise go to the next state.

17. CLR(1) Example

18. LALR(1) Parser L ookahead LR parser. It is the most powerful parser which can handle large classes of grammar. The canonical collection of LR(1) items is used.

19. LALR(1) Parsing Table

20. Operator Precedence Parser B ottom-up parser that interprets an operator-precedence grammar . A simple shift-reduce parser that is capable of parsing a subset of LR(1) grammars. It accepts only operator grammar E→ E+E / E*E / id There are 3 operator precedence relation. a ⋗ b a ⋖ b a ≐ b

21. Bottom up parser First looks at the lowest level of the parse tree. Works up the parse tree by using the rules of grammar. This parsing technique uses Right Most Derivation. First looks at the highest level of the parse tree . Works down the parse tree by using the rules of grammar . This parsing technique uses Left Most Derivation. Top Down Parser Difference between top-down and bottom-up parser

22. Conclusion Parser - Break data into smaller elements. Two types of parsers - Top down and bottom up Algorithms to construct different parsers. Differences Examples

23. References https://www.geeksforgeeks.org/types-of-parsers-in-compiler-design/ https://www.youtube.com/watch?v=hGuXUIefVkc&t=47s https://www.tutorialspoint.com/difference-between-top-down-parsing-and-bottom-up-parsing https://www.javatpoint.com/operator-precedence-parsing https://www.tutorialspoint.com/compiler_design/compiler_design_types_of_parsing.htm

24. Thank you !