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