LL(2) language that is not LL(1)

Question

In order to further my understanding of parsers and grammars, I'm searching for a (hopefully simple) example of a language that is LL(2) but not LL(1). That is, a language that can be generated by an LL(2) grammar but not by any LL(1) grammar.

Are there useful languages in that class ? I.e could we imagine a computer language that is LL(2) but not LL(1) ?

Herbage

dl.acm.org/citation.cfm?id=805431 (see the abstract) – Zilpah

Thanks, but this is not what I asked. I know that such languages exist. I just want to see one of them as an example. – Herbage

Answer 1

Parsing Techniques by Grune and Jacobs presents an example. An older version of this book is available online at

http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf

and the example is on page 181.

Pieeyed

Answer 2

The example mentioned in the book linked in Gunther's answer:

S -> a S A | epsilon
A -> a^k b S | c

is a grammar describing an LL(k+1) language that is not LL(k). In particular,

S -> a S A | epsilon
A -> a b S | c

is a grammar describing an LL(2) language that is not LL(1).

Herbage

Answer 3

In the book that Gunther mentioned, there's a more trivial example:

S -> a^k b | a^k a

is a grammar describing an LL(k+1) language that is not LL(k). In particular,

S -> ab | aa

is a grammar describing an LL(2) language that is not LL(1).

Vicinage