LL(*)Edit
LL(*) is the new top-down recognition algorithm developed by Terence Parr for ANTLR 3.
Differences from LL(k)
Previously, ANTLR used an LL(k) algorithm that was capable of differentiating between alternatives by using a fixed amount of lookahead:
foo
: A B C D '!'
| A B C D '?'
;
In order to predict which alternative to match, an LL(k) algorithm must use 5 symbols of lookahead to see past the initial A B C D to the ! or ? which distinguish the two alternatives. The prediction is made using an acyclic DFA (one which does not contain any loops).
LL(k) is not capable of predicting alternatives which contain arbitrary repetition:
bar
: A B* '!'
| A B* '?'
;
This is because LL(k) uses acyclic DFAs and arbitrary repetition is not possible. No fixed k will allow the prediction of rule bar using an acyclic DFA.
LL(*) instead uses cyclic DFAs and can therefore handle the kind of repetition expressed in rule bar.
Limitations
Although LL(*) is much more powerful than LL(k) it is still limited to recognizing only regular language structures (that is, structures that can be recognized using a DFA or regular expression). It cannot recognize recursive structures. Therefore, to recognize recursive structures using ANTLR it is necessary to provide some "help" to the LL(*) algorithm in one of the following ways: