3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

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.