S → aABb
A → c|π
B → d|π
Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions. Ex. A -> α β | α γ
Left Recursion is a property a grammar has whenever you can derive from a given variable (non terminal) a RHS that begins with the same variable, in one or more steps. Ex. A -> A α
In the above grammar, there is no Left Factoring, or Left Recursion. So, we can say that this is LL(1).
FIRST(S)={a}
FIRST(A)={c,π}
FIRST(B)={d,π}
FOLLOW(S)={$}
FOLLOW(A)={d,b}
FOLLOW(B)={b}
LL(1) Parsing Table:
|
|
a |
b |
c |
d |
$ |
|
S → aABb |
S → aABb |
|
|
|
|
|
A → c|π |
|
A → π |
A → c |
A → π |
|
|
B → d|π |
|
B → π |
|
B → d |
|
Checking the acceptance of the string ‘ab’
|
Stack |
Input |
Action |
Output |
|
$S |
ab$ |
Top of stack is Nonterminal, so expand |
S → aABb |
|
$bBAa |
ab$ |
Top of stack is Terminal, so pops off |
|
|
$bBA |
b$ |
Top of stack is Nonterminal, so expand |
A → π |
|
$bB |
b$ |
Top of stack is Nonterminal, so expand |
B → π |
|
$b |
b$ |
Top of stack is Terminal, so pops off |
|
|
$ |
$ |
Accept, successful completion |
|
Checking the acceptance of the string ‘acdb’
|
Stack |
Input |
Action |
Output |
|
$S |
acdb$ |
Top of stack is Nonterminal, so expand |
S → aABb |
|
$bBAa |
acdb$ |
Top of stack is Terminal, so pops off |
|
|
$bBA |
cdb$ |
Top of stack is Nonterminal, so expand |
A → c |
|
$bBc |
cdb$ |
Top of stack is Terminal, so pops off |
|
|
$bB |
db$ |
Top of stack is Nonterminal, so expand |
B → d |
|
$bd |
db$ |
Top of stack is Terminal, so pops off |
|
|
$b |
b$ |
Top of stack is Terminal, so pops off |
|
|
$ |
$ |
Accept, successful completion |
|