[antlr-interest] Language Design Patterns and incremental parsing

[Andrew Haritonkin]

Hi Ter,

Thanks for the insights.

Interesting... so, the lexer could be hardest part, good to know. It
seems incremental parsing is both, a very complex problem and not so
needed feature. Of course, computers become faster and faster, but why
work for one month to buy a new computer when you can spend years
trying to optimize it for the old one? ;-)

ANTLR is already good enough and besides I'm not so far to think about
optimization yet. Just thought that this topic is lost somewhere. I'm
very interested in it because I'm building an IDE as my home project.
And there it really makes the difference. Well, if you are lucky,
parser would have complexity O(n). And if re-parse is done after each
typed in character, then for file n characters long complexity would
be O(n*(n-1)/2) = O(n^2). But usually for comprehensive computer
language parser has bigger complexity. And therefore, parsing or not
parsing each time is a very big difference.

But even if it's hard to implement, could be there some paper or
chapter in the book. There is one existing implementation - ANTLR
Studio plug-in. Or that can only come together with new ANTLR version
that implements that? What about incremental parser only, without
lexer? If it's easily done, why not write about it?

Andrew

On Wed, Jul 22, 2009 at 9:31 PM, Terence Parr<parrt at cs.usfca.edu> wrote:
> hi Andrew,
>
> Well, Prashant and I have been discussing this for years now. After talking
> to the netbeans and javafx teams as well, I've come to the conclusion it's
> not the best use of my time. It's a really hard problem (and least the lexer
> is; parser is easy incrementally) and computers are fast enough now that is
> just not worth me going crazy over it.  Sorry to say...you should be fine
> though; we're talking about an O(n) process fortunately.
>
>  glad you like the LDP book!
> Ter
> On Jul 22, 2009, at 8:56 AM, Andrew Haritonkin wrote:
>
>> Hello Ter,
>>
>> Language Design Patterns is very nice book, even in beta version. I
>> love it - just what I needed after ANTLR  book... Thank you for that.
>>
>> I remember there was a talk about incremental parsing option for ANTLR
>> 3. It started with Prashant Deva when he implemented it for his ANTLR
>> Studio plug-in for Eclipse. In his blog he said that it was planned
>> for ANTLR 3 release, then for ANTLR 3.1. And you mentioned it once
>> here that you plan to write a paper with Prashant about incremental
>> top-down parsing. But I couldn't find any news about that.
>>
>> There is not much information could be found about incremental parsing
>> and most of them (or all of them), are related to LR parser. It seems
>> like it's not very known topic. Or maybe it's not needed so much? On
>> the other hand, Language Design Patterns is mostly about LL parser.
>> And I think discussing this topic in this book for LL parser would add
>> a great value to it.
>>
>> Of course, there is always something more to ask and you never can
>> have it all... right?
>>
>> Any comments? Can you share your opinion about this topic and how
>> important it is?
>>
>> Thank you,
>> Andrew
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe:
>> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>