LL(k) Prediction Techniques (and Insight on method applied)

Question

I'm requesting references for LL(k) in situations where k > 1 for reasons described below.

I'm looking for research/notes/anything involving LL(k) predictions.

Any time I look up LL(k) I end up with the description starting about LL(k) and focusing on LL(k) where k = 1.

Is there a formal description for the process to predictions where k can be greater than one, sometimes even as high as 7 to 15? Granted I can't vouch for or against the performance implications of the k being so high as that, but I just wanted to know if there's been any literature on the subject.

Answer 1

It turns out someone wrote half a book about LL(k) parsing, which wasn't mentioned on Wikipedia until I added it a coupe of minutes ago.

• Parsing Theory: LR(k) and LL(k) Parsing by Seppo Sippu; Eljas Soisalon-Soininen (1990).

I've looked briefly through it and it does have LL(2) examples too.

EDIT: As rici says below, this is the 2nd volume of a two-book series by the same authors; the first volume in the series is titled Parsing Theory: Languages and Parsing (1988).

And you can obviously find some level of info on LL(k) in most compiler books, but Sippu and Soisalon-Soininen have the most extensive treatment I found of LL(k). More recent introductory textbooks generally punt the proofs on anything to do with LL(k) with to Sippu & Soisalon-Soininen's 2nd volume.

LL(∗) however is not covered by Sippu & Soisalon-Soininen (as far as I can tell), but that's probably understandable given the book's age. For LL(∗) the 2011 ANTLR PLDI paper is probably the best reading.