Predictive Parser

Predictive parser is top-down recursive decent parser. It has the capability to predict which prodction can be used to replace the input string. As it can predict, we don’t have to backtrack for better replacement of input string. So it is non-backtracking recursive deccent parser.

To perfrom parsing, it uses look ahead pointer. Look-ahead pointer points to the next input symbol from input buffer. Along with the look ahead pointer, it also uses a stack and parsing table to parse the input and generate parse tree.

Initially $ symbol is put at the top of stack and also applied at the end of input string. The parser refers the parsing table to take action and element from top of stack together.

fig.1 Block Diagram of Predictive Parser

Constructing Parsing Table

There are two functions to create parsing table: first() and follow()

first(): if there is a variable and from that if we try to derive all the string then that symbol is called as first

follow() are the symbol which follow a variable in the process of derivation

After computing first and follow set, we can construct parsing table. The table row will contain Non teminals and column will contain treminal symmbols.

Let us consider the example

E->AB

A->( E )/aC

B->+E/€

C->*A/€

Parsing table will be as follows

 a+*()$
EAB  AB  
AaC    
B +E    
C  *A   
Table.1 Parsing Table

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *