Is this language LL(1) parseable?

ignougroup
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,minmathbb Nland nge 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

Leave a Reply