[antlr-interest] Complexity of ANTLR
Terence Parr
parrt at cs.usfca.edu
Sun Jan 20 14:47:38 PST 2008
On Jan 19, 2008, at 10:31 AM, Alessandro wrote:
> 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 ?
Sounds like the worst case would be highly nonlinear, yes. it would
be O(n^2) I think for n input symbol. Each symbol would have to look
at rest of input: n+n-1+n-2+n-3 etc...
> Is it possible to have accurate complexities (average and worse) ?
Average? Well, you can run -profile, but in theory I'm not sure.
mostly it's LL(1). backtracking adds a high constant (if
memoizing). In summary, i've not done the aveage case ;)
Ter
More information about the antlr-interest
mailing list