[Solved]: Can this CFG be written into an equivalent LL(1) grammar?

Problem Detail: 

I have the following CFG which I suspect cannot be rewritten to one which is LL(1):

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$

I've thought about it for a while, and can't seem to make any progress. I know that the simpler grammar here can be rewritten into LL(1), but it seems like there is something different about the above grammar which prevents a rewriting in a similar style. Is it possible? If not, is there an easy way to prove that this is the case?

Asked By : Adam Venis

Answered By : user979616

The comment above is correct. What is referenced here is generally called a "first-follow set clash" and occurs when a non-terminal is nullable, and has non disjoint first and follow sets. You can try to remove these by substituing for the nullable non terminal (shown for your grammar below). However, this process might result in a loop. If that happens, your grammar can't be transformed to LL(1).

Note that . simply denotes esp.

S → a S b S |   c S2 S |   d S1 S |   . S1 →    a S b S1 |   c S2 S1 |   d S1 S1 |   c . S2 →    a S b S2 |   c S2 S2 |   d S1 S2 |   d .  S2 =    S d. (uh-oh, we've gone in a loop here) S1 =    S c. 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19178