Is this language LL(1) parseable?

Problem Detail: 

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 

Asked By : FUZxxl

Answered By : Raphael

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)

Best Answer from StackOverflow

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