[antlr-interest] Language Design Patterns and incremental parsing

[Andrew Haritonkin]

Hello Andreas,

1. It depends on which steps you have to repeat and which you can
simply refresh. You can make lexer incremental, this could save half
of the time. You can also make parser incremental which produces AST
and then use it for computations. Otherwise, if you have embedded
actions in parser rules then it would be hard to make it incremental,
if not impossible.

2. If you use AST from the parser, then you just change the way you
get it. Instead of rebuilding it each time you will just refresh it
and re-run your tree walker. Tree walker part is already
non-incremental and will be exactly the same as before.

Let's think about white spaces. What difference would it make if you
type one space more between two words (provided that language is not
sensitive to white spaces)? Instead of re-parsing the whole text you
could just adjust tokens' start and end positions and you are pretty
much done. The same can be done with comments.

Andrew

On Wed, Jul 22, 2009 at 6:59 PM, Andreas Stefik<stefika at gmail.com> wrote:
> Andrew,
>
> So far as I understand it, where incremental parsing comes in really handy
> is when you have something continually reparsing a file. In my case, I use
> ANTLR to parse a custom programming language, which is then integrated into
> the NetBeans platform. The NetBeans parser, by default, continually reparses
> the source as the user types to try and determine whether there are errors
> in what the user is typing. It then generates visual feedback on the fly
> (e.g., little red squiggly lines), depending upon if there are errors.
>
> In practice, even with a non-incremental parser, this generally works fine
> for 1 file (the user can only type in one at a time), but since everything
> is done in real time, you want to the minimum amount of computation done
> while the user is typing so that the visual (and in my case, aural, since my
> language is for blind children), feedback to be as fluid and consistent as
> possible. Since ANTLR is not incremental, I currently have NetBeans wipe the
> build information for the file every time it requests a re-parse (which
> happens often!!), and then ask ANTLR to do it from scratch. It would be nice
> though, if ANTLR could only update the pieces of code the user was typing
> in, as it would, in theory at least, be much faster.
>
> In my case though, there are a few things I'm not sure how I would handle
> yet if ANTLR were incremental.
>
> 1. How would the different phases of my VM interact (e.g., would the tree
> walker also incrementally change?)
>
> 2. Would I be able to figure out how to modify my post-ANTLR compiler phases
> if ANTLR were incremental?
>
> I'm sure there are solutions to questions like these, and I highly support
> incremental parsing for ANTLR, if it's feasible, but so far as I understand
> it, it's a pretty tricky technology.
>
> Andreas
>
>
>
> On Wed, Jul 22, 2009 at 8:56 AM, Andrew Haritonkin <thikone at gmail.com>
> 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
>
>