in Compiler Design
896 views
0 votes
0 votes
Is the following grammar LL(1) ?

S→ aABbCD | ϵ

A→ ASd |  ϵ

B→ Sac| hC | ϵ

C→ Sf |Cg

D→ aBD | ϵ

Draw the LL(1) parsing table for the given grammar.
in Compiler Design
896 views

2 Answers

1 vote
1 vote

If our intention is to only check if this grammar is LL(1) or not then we dont need to do any of these first ,follow calculation then creating LL(1) parsing table and check if one cell contain multiple entries or not .

By looking at the grammar we can conclude that it is not LL(1) as it is left recursive .

The left recursive productions are

1)A→ ASd

2)C→ Cg.

now we can eliminate the left recursion and try to check for LL(1) or not but that is a topic for another question  we have to consider the grammar which we have given.

First we need to compute the first and follow set for the grammar.

Non terminal First Follow
$S$ $\left \{ a,\epsilon \right \}$ $\left \{ a,f,d,dollor \right \}$
$A$ $\left \{ a,d,\epsilon \right \}$ $\left \{ a,h,b,d \right \}$
$B$ $\left \{ a,h,\epsilon \right \}$ $\left \{ a,b,f,d,dollor \right \}$
$C$ $\left \{ a,f \right \}$ $\left \{ a,b,f,d,g,dollor \right \}$
$D$ $\left \{ a,\epsilon \right \}$ $\left \{ a,f,d,dollor \right \}$

 

Now we have to draw LL(1) parsing table:-

  $a$ $b$ $c$ $d$ $f$ $g$ $h$ $Dollor$
$S$

$S → aABbCD$

$S→ \epsilon$

    $S->\epsilon$ $S->\epsilon$     $S->\epsilon$
$A$

$A-> ASd$ 

$A-> \epsilon$

$A-> \epsilon$  

$A-> ASd$

$A-> \epsilon$

    $A-> \epsilon$  
$B$

$B-> Sac$

$B-> \epsilon$

$B-> \epsilon$   $B-> \epsilon$ $B-> \epsilon$   $B-> hC$ $B-> \epsilon$
$C$ $C-> Sf$       $C-> Sf$      
$D$

$D-> aBD$

$D-> \epsilon$

    $D-> \epsilon$ $D-> \epsilon$     $D-> \epsilon$

As we can see multiple entries in single cell then we can conclude it is not LL(1).

 

0 votes
0 votes
Left recursion present in grammar definitely not LL(1)