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

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.

• Do you mean you are unsatisfied with what's available on Wikipedia on this, including in the references cited there? If that's the case, you should probably tell us more precisely what else do you want to know.
– Fizz
Feb 26, 2015 at 9:04

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.

• That pair of books is (still) one of the best theoretical resources about parsing theory. Highly recommended.
– rici
Feb 26, 2015 at 19:18
• From what I can tell after looking at multiple other LL(k) parser generators, they are very limited and often require you to go to extra lengths. As for this paper, I'll need to look into it, your comment on Wikipedia's article (which I completely missed) give me something to stare at a while. I deleted the other post due to the TLDR frequency. If no one's going to read it, there's no point in posting it. Feb 27, 2015 at 7:12