Predictive Parsing

Recursive-descent parsing is a top-down method of syntax analysis that executes a set of recursive procedure to process the input. A procedure is associated with each nonterminal of a grammar.

A predictive parsing is a special form of recursive-descent parsing, in which the current input token unambiguously determines the production to be applied at each step.

Let the grammar be:

expr → term rest
rest → + term rest | - term rest | 6
term → 0 | 1 | . . . | 9

In a recursive-descent parsing, we write code for each nonterminal of a grammar. In the case of above grammar, we should have three procedure, correspond to nonterminals expr, rest, and term.

Since there is only one production for nonterminal expr, the procedure expr is:

expr ( )
{
term ( );
rest ( );
return
}

Since there are three (3) productions for rest, procedure rest uses a global variable, 'lookahead', to select the correct production or simply selects "no action" i.e.,

E - production, indicating that lookahead variable is neither + nor -

rest ( )
{
IF (lookahead = = '+') {
match ( ' + ' );
term ( );
rest ( );
return
}
ELSE IF ( lookahead = = '-') {
match (' - ');
term ( );
rest ( );
return
{
ELSE {
return;
}
}

The procedure term checks whether global variable lookahead is a digit.

term ( ) {
IF ( isdigit (lookahead)) {
match (lookahead);
return;
}
else{
ReportError ( );
}

After loading first input token into variable 'lookahead' predictive parser is stared by calling starting symbol, 'expr'.
If the input is error free, the parser conducts a depth-first traversal of the parse tree and return to caller routine through expr.

Problem with Predictive Parsing: left recursion