Parse input string using LL(1) parser

 

LL(1) is top down parser without backtracking. So left recursion and left factor is removed before top down parsing without backtracking can be applied.  

Steps to follow while parsing string using LL(1) parser

• Elimination of left recursion and left factor.
• Computation of FIRST and FOLLOW.
• Construct predictive parsing table using FIRST and FOLLOW.
• Perform parsing of input string with the help of predictive parsing table.

Example

S->(L)|a

L->SL'

L'->, SL'|∈

Construct predictive parser for above grammar.

Is this grammar LL(1).

Check  whether string(a,a) is Accepted or not?

Solution

In this grammar no left recursion and no left factor.

Next Step is compute FIRST and FOLLOW

FIRST  of S={(,a}

FIRST of L=FIRST of S={(,a}

FIRST of L'={, , ∈}

FOLLOW of L={)}

FOLLOW of L'=FOLLOW of L={)}

FOLLOW of S=FIRST of L'={,}U FOLLOW of L

                                              ={,}U )

FOLLOW of S={,),$}

Next Step construct predictive table

That grammar is LL(1) because there are no multiple entries of production in any box of the predictive table.

Now check string (a,a) is accepted  or not using stack and predictive table

So the grammar is LL(1) and that accept string (a,a).because stack is empty and input string is also empty so string is accepted by LL(1) parser.