Difference between predictive parser and ll(1) parser
Answers
Answer:
. G R O U P M E M B E R S : H I R A S H A H Z A D J A V E R I A K H A L I D T A N Z E E L A H U S S A I N P R E S E N T E D T O : M S . S A N I A B A T O O L
2. COMPILER CONSTRUCTION
3. PARSING • The term parsing comes from Latin pars meaning “part”. • Parsing is a process that constructs a syntactic structure (i.e. parse tree) from the stream of tokens. • Parsing is the process of determining if a string of tokens can be generated by a grammar. • For any context-free grammar there is a parser that takes at most Ο(n3) time to parse a string of n tokens. • Parsing a string with a CFG: – Finding a derivation of the string consistent with the grammar – The derivation gives us a PARSE TREE
4. PARSING TECHNIQUES • Syntax analyzers follow production rules defined by means of context-free grammar. The way the production rules are implemented (derivation) divides parsing into two types : Top-down parsing and Bottom-up parsing.
5. TYPES OF PARSING Parsing Bottom-up parsing Top-Down Parsing Predictive parsing Recursive decent parsing Recursive predictive parsing Non-Recursive predictive parsing Shift reduce parsing LALR parsing Canonical parsing SLR parsing Operator Precedence parsing
6. TOP DOWN PARSING • Top-down parsers build parse trees from the top (root) to the bottom (leaves). • A top-down parse corresponds to a preorder traversal of the parse tree • A leftmost derivation is applied at each derivation step • Top-Down Parsing may need to backtracking • Two top-down parsing are further sub-divided into the following categories: Predictive Parsing. Recursive Descent Parsing
7. EXAMPLE: Consider the following Grammar: <program> begin <stmts> end $ <stmts> SimpleStmt ; <stmts> <stmts> begin <stmts> end ; <stmts> <stmts> € Input: begin SimpleStmt; SimpleStmt; end $
8. RECURSIVE DECENT PARSER • This parsing technique recursively parses the input to make a parse tree • A recursive-descent parser consists of several small functions, one for each nonterminal in the grammar • A procedure is associated with each nonterminal of a grammar.. • Recursive descent parsing involves backtracking. • For an input string: read S → rXd X → oa X → ea
9. PREDICTIVE PARSING • Predictive parser, has the capability to predict which production is to be used to replace the input string. • The predictive parser does not suffer from backtracking. • The predictive parser uses a look-ahead pointer, which points to the next input symbols. • To make the parser back-tracking free, the predictive parser puts some constraints on the grammar. • It accepts only a class of grammar known as LL(k) grammar. • Hence, Predictive Parser is also known as LL(1) Parser.
10. LL(1) PARSER • LL(1) Parser accepts LL(1) grammar. • LL(1) grammar is a subset of context-free grammar but with some restrictions to get the simplified version • In LL(1) parser, the first L in LL(1) is parsing the input from left to right, the second L in LL(1) stands for left-most derivation and the 1 means one input symbol of look ahead.
11. CONSTRUCTING PREDICTIVE PARSER Following are the steps for constructing predictive parser. o Removing unreachable productions. o Removing ambiguity from the Grammar. o Eliminating left recursion. o Left Factoring of a grammar. o First and Follow o Constructing a parse table
12. REMOVING UNREACHABLE PRODUCTIONS An unreachable production is one that cannot possibly appear in the parse tree rooted at the start symbol. For example, in the following grammar : S A (1) A a (2) B b (3) Production (3) is unreachable because the non-terminal B does not appear on the right side of any production. A non-terminal can be unreachable either it appears on the right side of any production. if it is on the right side of unreachable non-terminal.
13. Data Structures: • A stack • A List for Reachable Non-Terminals Method: Initially both the stack and list are Empty. Step 1: Start symbol to the list of reachable non- terminal also push onto the stack. Step 2: While (The stack is not Empty) { P= POP one Item of the stack for (Each non-terminal X on right hand side are P) { If (X is not in the list of reachable non - terminals) { Push X; Add X to the list of Reachable non- terminal; } } } Step 3: Remove all the productions from the grammar where L-H-S is not in the list of reachable non –terminals. Algorithmto remove unreachable production