2
$\begingroup$

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.

$$L=\{a^nb^m|n,m\in\mathbb N\land n\ge m\}$$

Is my hypothesis true or is this language parseable with an LL(1) parser?

One can use this simple grammar to describe $L$ (of course it is isn't LL(1) parseable):

S -> ε
S -> A
A -> aA
A -> aAb
A -> a
A -> ab
$\endgroup$
  • $\begingroup$ Related question on SO. $\endgroup$ – Raphael Aug 28 '12 at 23:33
  • $\begingroup$ There is a simple grammar that is almost LL(1); the parser can act greedily (i.e. always resolve the single conflict to prefer the non-epsilon rule). In other words, there is a simple deterministic parser which finds left-derivations using one symbol lookahead -- it's just not strictly LL(1). "Only" unambiguity is violated. Another funny/ironic thing here is that $L^R$ is LL(1), so you can trivially parse $L$ with an LL(1) parser (by simply reversing the input). $\endgroup$ – Raphael Aug 29 '12 at 9:35
4
$\begingroup$

Kurki-Suonio has shown some helpful properties [1]:

Theorem 1
Each LL(k) grammar is unambiguous.

That means any inherently ambiguous language is not LL(1).

Theorem 9
For any $k>1$ the grammar $G$:

$\qquad \begin{align} S &\to aSA \mid \varepsilon \\ A &\to a^{k - 1} b S \mid c \end{align}$

generates an LL(k) language which is no LL(k-1) language.

There you have another concrete example by setting $k=2$.


As for your language $L$, assume $L$ is LL(1) and consider the language

$\qquad \displaystyle L' = \{ a^nb^m \mid n < m \land m > 0 \}$.

We make the following observations:

  • $L'$ is LL(1) by the grammar

    $\qquad \begin{align} S &\to AbB \\ A &\to aAb \mid \varepsilon \\ B &\to bB \mid \varepsilon \end{align}$

  • Neither $L$ nor $L'$ is regular (by Pumping Lemma).
  • $L \cap L' = \emptyset$.
  • $L \cup L' = \{a^nb^m \mid n,m \in \mathbb{N}\} \in \mathsf{REG}$.

In unison, these facts contradict this theorem [2]:

Theorem 9
If the finite union of disjoint LL(k) languages is regular, then all the languages are regular.

Thus, $L$ can not be LL(1) (and in fact not LL(k) for any k).


  1. Notes on top-down languages by R. Kurki-Suonio (1969)
  2. Properties of deterministic top-down grammars by D.J. Rosenkrantz and R.E. Stearns (1970)
$\endgroup$
  • 1
    $\begingroup$ @FUZxxl: Got a proof for you now. That's an awesome theorem and the first one I have come across that can be used to show non-LL(k)-ness for languages relatively easily. $\endgroup$ – Raphael Aug 29 '12 at 9:27
  • $\begingroup$ The article [2] is pawalled. Is there a way to get its contents? I'd really like to understand the proof of the lemma you use. $\endgroup$ – FUZxxl Aug 29 '12 at 18:38
  • $\begingroup$ @FUZxxl: Ah, darn; I thought the ACM version might be generally accessible (other than that, it's Elsevier). I surf from a university network, so it can be hard to see which papers are paywalled. But sadly, I don't see a free version. I'd suggest you try to contact the authors (or their students) directly; they'll usually be happy to accomdate you. Failing that, try contacting ACM. They claim to be open-minded towards available research, but I have no experience with them in this regard. $\endgroup$ – Raphael Aug 29 '12 at 20:43
3
$\begingroup$

Your language correspond to the famous dangling else problem and it is well known that no $LL(k)$ grammar is able to parse it. The reason is that a $LL(k)$ grammar should be able to decide if a $a$ is paired with a $b$ when the $a$ is seen and the next $k$ symbols may be $a$.

Note that to make it $LR(1)$ you can't use a grammar like

$\qquad\begin{align} S &\to aSb \\ &\to aS \\ &\to \varepsilon \end{align}$

which is ambiguous. You have to use to

$\qquad\begin{align} S &\to aS \\ &\to R \\ R &\to aRb \\ &\to \varepsilon \end{align}$

But some parser generators like yacc are able to cope with that ambiguity, but the input has to be correctly ordered for them to work. Similarly, if you left factorize the first grammar, you get Raphael's grammar

$\qquad \begin{align} S &\to aST \mid \varepsilon \\ T &\to b \mid \varepsilon \end{align}$

which has an ambiguity which doesn't prevent to generate tables for LL(1) parsers.

$\endgroup$
  • $\begingroup$ I have not been able to find a reference for this "well-known" (Alex ten Brink said so, too) example; do you have one? See my answer for a proof. $\endgroup$ – Raphael Aug 29 '12 at 9:26
  • $\begingroup$ Well known as "stated in about any book on parsing I've read", but I'm pretty sure that most of them don't present a proof. I'll take a look if I find one with a proof or at least a pointer to a proof. I'd be surprised if The Theory of Parsing, Translation, and Compiling by Aho and Ulmann doesn't have one. $\endgroup$ – AProgrammer Aug 29 '12 at 9:31
  • 1
    $\begingroup$ @Raphael, I had the opportunity to have a look at some of my books. It is stated without proof in the Dragon book and in Crafting a compiler, and I didn't found a proof in The Theory of Parsing, Translation, and Compiling. $\endgroup$ – AProgrammer Sep 3 '12 at 9:05
  • $\begingroup$ Thanks for looking! Wow, so it is a folklore theorem, huh? $\endgroup$ – Raphael Sep 3 '12 at 9:29
2
$\begingroup$

Your proposed solution does not correspond to the defined language. Take the example "ab" which is a member of $L$, but not your grammar.

To be a LL(1) grammar, the production rules must not contain left recursions and has to be unambiguous. The following grammar satisfies does not satisfy those criteria:

S → A
A → aAb
A → B
B → aB
B → ԑ

I have one redundant production rule. Let's remove it:

S → aSb
S → A
A → aA
A → ԑ

Update: Based on your hint, I am changing my mind. I think your hypothesis is true. I don't know how to prove correctness for this (probably 1 or 2 might help), but my rationale goes like this: If you parse an token "a" at position $p$ you can (in no way) determine which string it belongs to (either $i_1: 0 \leq p < m$ or $i_2: m \leq p < n$). But this is a required property for context-free languages, because you have to represent $i_1$ using a recursion with one literal on both sides and $i_2$ with a right recursion. This requires two different production rules and therefore a distinction. But because $i_1$ and $i_2$ refers to the same character, this also introduces an ambiguity which excludes the set of LL(1)-parseable grammars. Ergo, it's possible in context-free languages. It's impossible in LL(1).

$\endgroup$
  • $\begingroup$ First of all, your grammar is not an LL(1) grammar, since deductions from both rule 2 and rule 3 can begin with an $a$: $A\to aAb$ and $A\to B\to aB$. Second, $ab$ definitly is deductable from my grammar. The last rule states $A\to ab$. The deduction is $S\to A\to ab$. $\endgroup$ – FUZxxl Aug 28 '12 at 15:58
  • $\begingroup$ You are absolutely correct about your 2 points. Sorry for my mistakes. And now I can see the point of your hypothesis. Let's see if I can come up with another approach. $\endgroup$ – meisterluk Aug 28 '12 at 17:36
  • $\begingroup$ I made a major update to my post. $\endgroup$ – meisterluk Aug 28 '12 at 19:01
  • $\begingroup$ Thank you for the update! I think you mix up context-free languages ($L$ definitly is context-free, look at the grammar) and LL(1)-parseable languages though. $\endgroup$ – FUZxxl Aug 28 '12 at 19:12
  • $\begingroup$ Yeah, it might be ambiguous in some way. I extended the Update section to clarify it. $\endgroup$ – meisterluk Aug 28 '12 at 19:24

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.