Predictive parser

compiler design

1. Predictive parser by jothi lakshmi

2. Predictive parsers Transition diagrams for predictive parsers Non recursive predictive parser Construction of predictive parsing tables CONTENT

3. It is top – down parsing An efficient non-backtracking form of top-down parser called a predictive parser. LL(1) grammars from which predictive parsers can be constructed automatically. PREDICTIVE PARSER

4. To construct a predictive parser we must know Input symbol a Non terminal A to be expanded Alternatives of production A-->a1|a2|….|an That derives a string beginning with a Proper alternative must be detectable by looking at only first symbol it derives. Flow of control constructs most programming language with their keywords that are detected. PREDICTIVE PARSERS

5. Recursive descent parser that needs no backtracking i.e (predictive parser). Eg :- stmt  if expr then stmt else stmt while expr do stmt begin stmt_list end Keywords tells us which alternative is the one that could find the statement. PREDICTIVE PARSERS

6. To construct the transition diagram of a predictive parser from a grammar. Eliminate LR from the grammar Then left factor the grammar Then for each non terminal A do the following Create an initial and final state For each production A  x1 ,x2…. xn . Create a path from initial to final state With edges labeled x1,x2,…. xn TRANSITION DIAGRAMS FOR PREDICTIVE PARSERS

7. NON RECURSIVE PREDICTIVE PARSER

8. it is possible to build a non recursive predictive parser by maintaining stack-explicit recursive calls – implicit key problem – determining production to be applied for a non terminal predictive parser has :- input - contain string to parser followed by $ stack - sequence of grammar symbols with $ parsing table - 2 dimension array M[ A,a ] output stream - gives output NON RECURSIVE PREDICTIVE PARSER

9. $ - right endmarker to indicate end of string A – non terminal , a – terminal program considers X – top of the stack a – current input symbol the behavior of the parser can be described in terms of its configuration which gives the stack contents and the remaining input NON RECURSIVE PREDICTIVE PARSER

10. two symbols determine the action of the parser. there are 3 possibilities if X=a=$ , parser halts and announces successful completion of parsing. If X=a!=$ , parser deletes X off the stack and the input pointer to next input symbol. If X is non terminal , program consults entry M[ X,a ]Of the parsing table M NON RECURSIVE PREDICTIVE PARSER

11. The following rules are used to construct the predictive parsing table: 1. for each terminal a in FIRST(α), add A → α to matrix M[ A,a ] 2. if λ is in FIRST(α), then for each terminal b in FOLLOW(A), add A → α to matrix M[ A,b ] Construction of predictive parsing tables

12. Thank you