Predictive Parsing

By: Prof. Dr. Fazal Rehman | Last updated: March 3, 2022

A predictive parser has the potential to predict which production is to be used by the compiler to replace the input string.
The predictive parser has the advantage that it does not suffer from backtracking.
A look-ahead pointer is used in In predictive parsing, which points to the next input symbols.
The predictive parser accepts only a class of grammar commonly called LL(k) grammar. So, a Predictive Parser can be considered as a LL(1) Parser.

How predictive parser work?
Following are the steps for constructing a predictive parser.

1. Removing the unreachable productions.
2. Removing the ambiguity from the Grammar.
3. Removing the left recursion.
4. Left Factoring of a grammar.
5. First and Follow
6. Constructing a parse table

Removing Unreachable Productions

Algorithm of Removing Unreachable Productions

Data Structures required

• A stack
• A List for Reachable Variables

Method:

Primarily both the stack and list are Empty.

Step 1:

Start symbol to the list of reachable Variables also push onto the stack.

Step 2:

While (The stack is not Empty)

{

P= POP one Item of the stack

for (Each Variables X on right hand side are P)

{

If (X is not in the list of reachable Variables)

{

Push X;

Add X to the list of Reachable Variables;

}

}

}

Step 3:

Remove all the productions  from the  grammar where L-H-S is not in the list of  reachable Variables.

 

Note: Y and Y->c will be ignored because Y can’t be reached with S or X.

CFG Production Rules with unreachable productions

S-> aY | bX

X->a | bXX | aS

Y-> b | aYY | bS

C-> aD | bS |  €

D-> bD |  €

CFG Production Rules with reachable productions

After Removing Unreachable Productions we have the following CFG.

S-> aY | bX

X-> a | bXX | aS

Y-> b | aYY | bS

More examples of Removing unreachable productions

Eliminating Ambiguity from Grammar

A CFG is an ambiguous CFG if it has more than one derivation tree for the given input string i.e., more than one RightMost Derivation Tree or more than one LeftMost Derivation Tree.

Example 1:

For example, we have a CFG.

S →XY | mmY

X →m | Xm

Y →n

Determine whether the grammar G is ambiguous or not?

Let us derive the string “mmn”

The given CFG is ambiguous. The unambiguous CFG is given below;

Unambiguous grammar will be:

S →XY

X →Xm | m

Y →n

Example of Elimination of Left Recursion from a CFG

Left recursion is eliminated by converting the CFG into a right recursive CFG.

Example of Left Recursive Grammar

CFG = X → Xα / β

where β does not begin with an A.

After Elimination of Left Recursion from CFG.

Then, we can eliminate left recursion by replacing the pair of productions with-

X → βX’

X’ → αX’ / ∈

Now the CFG is Right Recursive CFG

Note This right recursive grammar functions the same as left recursive grammar.

Example of removal of Left Recursion from a Grammar

X → XYd / Xa / a

Y → Ye / b

After Elimination of Left Recursion from CFG.

The CFGafter eliminating left recursion is given below;

X→ aX’

X’ → YdX’ / aX’ / ∈

Y → bY’

Y’ → eY’ / ∈