Generating the LL(1) parsing table for the given CFG

Question

The CFG is as following :

S -> SD|SB
B -> b|c
D -> a|dB

The method which I tried is as following:

I removed non-determinism from the first production (S->SD|SB) by left-factoring method.

So, the CFG after applying left-factoring is as following:

S -> SS'
S'-> D|B
B -> b|c
D -> a|dB

I need to find the first of S for the production i.e. S -> SS' in order to proceed further. Could some one please help or advise?

Answer 1

You cannot convert this grammar that way into an LL(1) parser: the grammar is left recursive, you thus will have to perform left recursion removal. The point is that you can perform the following trick: since the only rule for S is S -> SS' and S -> (epsilon), it means that you simply reverse the order, and thus introduce the rule S -> S'S. So now the grammar is:

S -> S'S
S'-> D|B
B -> b|c
D -> a|dB

Now we can construct first: first(B)={b,c}, first(D)={a,d}, first(S')={a,b,c,d} and first(S)={a,b,c,d}.