6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I believe you are right, there seems to be no way to distinguish between "this $a$ starts an $S$" and "$S \Rightarrow \epsilon$, the $a$ comes after". None of the standard tricks to LL(1)-ify works. $\endgroup$ – vonbrand Mar 7 '14 at 14:57
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Very good! Would it then be possible to say that this grammar is not $LL(k)$ for any $k$? $\endgroup$ – Adam Venis Mar 15 '16 at 19:51
  • $\begingroup$ cs.stackexchange.com/questions/4888/…. Basically, you can check if your grammar is ll(k) for some specific k using an ll(k) parsing table (or better yet, in polynomial time). However, if you want to know if there exists some value of k for which your grammar ll(k), this problem is undecidable. $\endgroup$ – user979616 Mar 16 '16 at 3:59
  • $\begingroup$ Although yes, testing with some strings that would be generated from the grammar, you can make a pretty strong case that this grammar just isn't ll at all. $\endgroup$ – user979616 Mar 16 '16 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.