[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