Non- Recursive Predictive Parsing.pptx

Compiler Design

1. Non- Recursive Predictive Parsing  

2. Non- Recursive Predictive Parsing   Non-Recursive predictive parsing uses a parsing table that shows which production rule to select from several alternatives available for expanding a given non-terminal and the first terminal symbol that should be produced by that non-terminal . The parsing table consists of rows and columns where there are row for each non-terminal and a column for each terminal symbol including S, the end marker for the input string.  

3. non-recursive parser  Components This non-recursive parser looks up which product to be applied in a parsing table. A LL(1) parser has the following components: (1) buffer: an input buffer which contains the string to be passed (2) stack: a pushdown stack which contains a sequence of grammar symbols (3) A parsing table: a 2d array M[A, a] where A->non-terminal, a->terminal or $ (4) output stream: end of the stack and an end of the input symbols are both denoted with $

4. Algorithm for non recursive Predictive Parsing:   The main Concept ->With the help of  FIRST() and FOLLOW() sets , this parsing can be done using just a stack that avoids the recursive calls . For each rule, A->x in grammar G:  For each terminal ‘a’ contained in  FIRST(A)  add A->x to M[A, a] in the parsing table if x derives ‘a’ as the first symbol.    If FIRST(A) contains null production for each terminal ‘b’ in  FOLLOW(A) , add this production (A->null) to M[A, b] in the parsing table. 

5. LR Parser

6. LR Parser LR parsing is one type of bottom up parsing. It is used to parse the large class of grammars. In the LR parsing, "L" stands for left-to-right scanning of the input. "R" stands for constructing a right most derivation in reverse. "K" is the number of input symbols of the look ahead used to make number of parsing decision.

7. Types of LR Parser LR parsing is divided into four parts: LR (0) parsing, SLR parsing, CLR parsing and LALR parsing.

8. LR algorithm The LR algorithm requires stack, input, output and parsing table. In all type of LR parsing, input, output and stack are same but parsing table is different .

9. Input buffer is used to indicate end of input and it contains the string to be parsed followed by a $ Symbol. A stack is used to contain a sequence of grammar symbols with a $ at the bottom of the stack. Parsing table is a two dimensional array. It contains two parts: Action part and Go To part.