0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Fizz
    Feb 26, 2015 at 9:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That pair of books is (still) one of the best theoretical resources about parsing theory. Highly recommended. $\endgroup$
    – rici
    Feb 26, 2015 at 19:18
  • $\begingroup$ 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. $\endgroup$
    – Allen Clark Copeland Jr
    Feb 27, 2015 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.