14

I have a grammar and I can check whether or not is is LL(1). However, is there any way to check if the language generated by the grammar is LL(1)? And what exactly is the difference between LL(1) grammars and LL(1) languages?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Rakesh
  • 141
  • 1
  • 3

1 Answers1

16

Any grammar that is LL(1) defines an LL(1) language. By definition, a language is LL(1) if there is some grammar that generates it that is LL(1), so the fact that you have an LL(1) grammar for the language automatically means that the language is LL(1).

To elaborate, a language is a set of strings and a grammar for that language is a means of describing that language. Some languages have LL(1) grammars while others do not. However, the fact that a grammar is not LL(1) does not mean that the language it describes is not. For example, consider this grammar:

A -> ab | ac

This grammar is not LL(1) because it contains a FIRST/FIRST conflict when trying to predict the production for A when seeing terminal a. However, it describes an LL(1) language, since the language is also described by the grammar

A -> aX
X -> b | c

So the language generated by these grammars (which just contains ab and ac) is indeed LL(1).

Determining whether the language described by an arbitrary grammar is LL(1) is much harder and to the best of my knowledge the only way to do it would be to either explicitly exhibit an LL(1) grammar for the language generated by the initial grammar (which is tricky) or to mathematically prove that no such grammar exists.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 2
    So a LL(1) *language* may be defined by a number of other *grammars* that are not LL(1) (as long as there is such an LL(1) grammar)? -- Just trying to confirm in my head. –  Aug 20 '11 at 19:06
  • 3
    @pst, yes, it is enough that there is one LL(1) grammar. –  Aug 20 '11 at 19:09