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).
