How do LL(*) parsers work?

Question

I cannot find any complete description about LL(*) parser, such as ANTLR, on Internet.

I'm wondering what is the difference between an LL(k) parser and an LL(*) one and why they can't support left-recusrive grammars despite their flexibility.

Answer 1

Here is an article (by Terence Parr, the author of antlr) about LL(*) grammar analysis: article with a nice example of what is LL(*) but not LL(k), for any k.

Another good reference (and much more complete) is the "Definitive ANTLR Reference", again by Terence Parr, and the original journal article describing how antlr works [pdf].

Answer 2

When ever you see this it generally the amount of token look ahead in order to parse the language.

This is the same thing for LR parser.

So k is the maximum mount of token that the parer will fetch before taking a decision. Be aware that the more k is hight the harder the parser will be unless you use a generator (ANTLR, yacc, bison, ...).

LL parser use a top down approach which mean that it will look for the deepest tree. Because of that left recursion will make an infinitively deep tree and will break the parser.

AFAIK Most of the language use LR parser.