[antlr-interest] Complexity of ANTLR
Alessandro
alessnet at gmail.com
Sat Jan 19 10:31:53 PST 2008
Hello,
Sorry if my question has already been answered.
I want to know the complexity of ANTLR (without using backtracking).
ANTLR uses a (cyclic) DFA to choose the correct alternative. If the
language isn't LL(k) for a fixed k, in the worse case, in every rule,
the DFA scan the whole piece of input matching the rule before
entering in it. So it is exponential ?
Is it possible to have accurate complexities (average and worse) ?
Thanks a lot :-)
Alessandro
More information about the antlr-interest
mailing list