Differences from LL(k)
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* '?' ;
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: