Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm reading a Basics of Compiler Design and on page 84 it is making the following statement:
A language may well be LL(1) even though the grammar used to describe it is not.
Can someone give such an example? I'm not really sure how this is possible. I thought grammars generate languages, therefore if a grammar is non LL(1) then a language generated by it is also non LL(1). Apparently that is not the case.
Any help is appreciated.
If some grammar for $L$ is LL(1), then $L$ is LL(1) (by definition). But the converse is not true: the fact that a particular grammar for $L$ is not LL(1) says nothing at all about $L$. In order to demonstrate that $L$ is not LL(1), you would need to show that no grammar for the language is LL(1).
For example:
$$L \to a | La $$
is clearly not LL(1), since it is left-recursive. (This grammar is LR(1).)
$$L \to a | aL$$ (which generates the same language) is also not LL(1), since it requires left-factoring. (This grammar is LL(2).)
But there is a simple LL(1) grammar for this language:
$$L \to a L'$$ $$L' \to \epsilon | aL'$$
So we can see that $L$ (the set of non-empty words all of whose symbols are $a$) is LR(1), LL(2) and LL(1).
Well a language is XX iff there exists an XX grammar for it. There might be other grammars for an XX language. For instance you might have a context-free grammar for what is actually a regular language.
Read the book. It contains techniques (with examples!) that show how some non-LL(1) grammars can be transformed into LL(1) grammars. The techniques are called elimination of left recursion and factorization.
