patternMinor
non LL(1) grammar but LL(1) language
Viewed 0 times
butgrammarlanguagenon
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#55531, answer score: 5
Revisions (0)
No revisions yet.