1

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?

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
aliza
  • 45
  • 7

1 Answers1

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

Community
  • 1
  • 1
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • Thank you, but I have a doubt which is: – aliza Dec 19 '15 at 20:01
  • @alisa: please [`[edit]`](http://stackoverflow.com/posts/34374300/edit) your question. – Willem Van Onsem Dec 19 '15 at 20:11
  • Thank you for the reply. I have a doubt. As you mentioned "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." Could you please also elaborate this? Also S->(epsilon) is not a production in the original given grammar, how could it be possible to add it? Please advise. – aliza Dec 19 '15 at 20:26
  • @alisa: most grammars have this rule implicitly: otherwise your `S` would generate an infinite amount of `S'`es. – Willem Van Onsem Dec 19 '15 at 20:28