[antlr-interest] Honey Badger Theory

[Terence Parr]

On Jan 22, 2012, at 12:24 PM, Gokulakannan Somasundaram wrote:

> Hi Terrence,
>               Thanks for the explanation. I could understand part of what
> you said. So i will wait for the paper.
>               My question is how does the parsing strategy in V3 and V4
> compare against each other, if it has no backtracking in V3. More
> specifically, do you expect a LL(k) parser do more work in V4 for the sake
> of being adaptive?

 Basically, both parsing strategies use a DFA to predict which alternative to pick based upon the current input and the current decision. How this DFA is created is what's different. Statically, some of the DFA cannot be created so I failover to backtracking at runtime for v3. In v4, I do all the analysis runtime and so I can take each input on an individual basis. I can always create a proper DFA to predict the alternatives of a decision if I do it at runtime. hence no backtracking with the parser.

Yes, LL(k) for k>1 does more work in v4 while it does the analysis step. Once it warms up, however, it will perform the same amount of work as v3. For example, if you are doing syntax highlighting with the parser inside an IDE, the first time you parse will be slower whereas the future passes will be just as efficient as v3 (in principal, though they are still a bit slower after warm-up at the moment).

ter