Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Archived » IMP » Incremental parsing
Incremental parsing [message #29539] Tue, 21 July 2009 09:54 Go to next message
Eclipse User
Originally posted by: lennart.x.akobson.analogix.com

Hi Newsgroup,

I am pretty new to IMP and LPG so please bare with me if this is newbi
questions.

As far as I understand it is possible to do incremental parsing with LPG,
but I guess
that the EBNF (.gi, .g files) must have been written in some special way to
handle this?
I guess also that one need to tell the parser that the passed source is not
a complete compilation unit?

Can someone please explain this to me.

Thanks in advance

Lennart
Re: Incremental parsing [message #29593 is a reply to message #29539] Thu, 23 July 2009 20:44 Go to previous messageGo to next message
Robert M. Fuhrer is currently offline Robert M. Fuhrer
Messages: 294
Registered: July 2009
Senior Member
Lennart J wrote:
> Hi Newsgroup,
>
> I am pretty new to IMP and LPG so please bare with me if this is newbi
> questions.
>
> As far as I understand it is possible to do incremental parsing with LPG,
> but I guess
> that the EBNF (.gi, .g files) must have been written in some special way to
> handle this?
> I guess also that one need to tell the parser that the passed source is not
> a complete compilation unit?
>
> Can someone please explain this to me.

In principle, the idea is to:

- Instruct the parser generator to provide multiple "entry points" to the
parser, one for each construct that might be re-parsed. E.g., for Java,
the entry points would be something like types, methods, blocks.

Recent versions of LPG (say, 2.0.15 or so and later) allow one to specify
multiple start symbols in the "%Start" segment.

- Figure out the innermost such construct that contains the editing
"damage", and call the appropriate parser entry point.

- Knit the AST produced for the fragment just parsed into the existing
AST. The manner of doing this would be specific to the kind of AST
being produced. There's no specific support for this in LPG-generated
ASTs, but there's also nothing in their design that (AFAIK) should
prevent it or make it difficult.

That said, I don't think we have quite enough API in IMP to really take
advantage of this. In particular, I don't think there's any API yet to
pass the damage region into the parser.

On the other hand, it's certainly something we've been wanting to do for
long enough that if people express enough interest, I'd definitely be
willing to work to add whatever's needed in the relatively near term.

--
Cheers,
-- Bob

--------------------------------
Robert M. Fuhrer
Research Staff Member
Programming Technologies Dept.
IBM T.J. Watson Research Center

IDE Meta-tooling Platform Project Lead (http://www.eclipse.org/imp)
X10: Productive High-Performance Parallel Programming (http://x10.sf.net)
Re: Incremental parsing [message #536309 is a reply to message #29593] Thu, 27 May 2010 15:20 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan Ujhelyi
Messages: 216
Registered: July 2009
Senior Member
Hi,

I think, this could be really helpful, as it should reduce the need to reparse - and then recolor the showed syntax.

As tried to research for my lock described in http://www.eclipse.org/forums/index.php?t=msg&th=168947& amp;start=0& I think reducing the need to fully parse the entire document could help, as a lot less annotations could change, etc. (On the other hand it is also possible that simply my parser/handler code is too slow),
Re: Incremental parsing [message #576286 is a reply to message #29539] Thu, 23 July 2009 20:44 Go to previous messageGo to next message
Robert M. Fuhrer is currently offline Robert M. Fuhrer
Messages: 294
Registered: July 2009
Senior Member
Lennart J wrote:
> Hi Newsgroup,
>
> I am pretty new to IMP and LPG so please bare with me if this is newbi
> questions.
>
> As far as I understand it is possible to do incremental parsing with LPG,
> but I guess
> that the EBNF (.gi, .g files) must have been written in some special way to
> handle this?
> I guess also that one need to tell the parser that the passed source is not
> a complete compilation unit?
>
> Can someone please explain this to me.

In principle, the idea is to:

- Instruct the parser generator to provide multiple "entry points" to the
parser, one for each construct that might be re-parsed. E.g., for Java,
the entry points would be something like types, methods, blocks.

Recent versions of LPG (say, 2.0.15 or so and later) allow one to specify
multiple start symbols in the "%Start" segment.

- Figure out the innermost such construct that contains the editing
"damage", and call the appropriate parser entry point.

- Knit the AST produced for the fragment just parsed into the existing
AST. The manner of doing this would be specific to the kind of AST
being produced. There's no specific support for this in LPG-generated
ASTs, but there's also nothing in their design that (AFAIK) should
prevent it or make it difficult.

That said, I don't think we have quite enough API in IMP to really take
advantage of this. In particular, I don't think there's any API yet to
pass the damage region into the parser.

On the other hand, it's certainly something we've been wanting to do for
long enough that if people express enough interest, I'd definitely be
willing to work to add whatever's needed in the relatively near term.

--
Cheers,
-- Bob

--------------------------------
Robert M. Fuhrer
Research Staff Member
Programming Technologies Dept.
IBM T.J. Watson Research Center

IDE Meta-tooling Platform Project Lead (http://www.eclipse.org/imp)
X10: Productive High-Performance Parallel Programming (http://x10.sf.net)
Re: Incremental parsing [message #577806 is a reply to message #29593] Thu, 27 May 2010 15:20 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan Ujhelyi
Messages: 216
Registered: July 2009
Senior Member
Hi,

I think, this could be really helpful, as it should reduce the need to reparse - and then recolor the showed syntax.

As tried to research for my lock described in http://www.eclipse.org/forums/index.php?t=msg&th=168947& amp;start=0& I think reducing the need to fully parse the entire document could help, as a lot less annotations could change, etc. (On the other hand it is also possible that simply my parser/handler code is too slow),
Re: Incremental parsing [message #654634 is a reply to message #536309] Wed, 16 February 2011 14:28 Go to previous message
Robert M. Fuhrer is currently offline Robert M. Fuhrer
Messages: 294
Registered: July 2009
Senior Member
Zoltán Ujhelyi wrote:
> Hi,
>
> I think, this could be really helpful, as it should reduce the need to
> reparse - and then recolor the showed syntax.
>
> As tried to research for my lock described in
> http://www.eclipse.org/forums/index.php?t=msg&th=168947& amp;start=0& I think
> reducing the need to fully parse the entire document could help, as a
> lot less annotations could change, etc. (On the other hand it is also
> possible that simply my parser/handler code is too slow),

A quick update on this front - LPG now provides some API for incremental
lexing, and so at long last we're going to slot support for this into the
IMP API to take advantage of that. The changes shouldn't be too significant.

As for incremental parsing itself, that issue is a bit harder, for a few
reasons: (1) for the parser itself, determining the extent of the token
stream (or character stream for scannerless parsing) that requires re-
parsing is not entirely trivial, (2) the result of parsing the damaged
text could be a different type/structure from that of the previous parse,
(3) to take maximal advantage of incremental parsing, one needs a way of
transmitting an "AST delta" to all the interested parties.

--
Cheers,
-- Bob

--------------------------------
Robert M. Fuhrer
Research Staff Member
Programming Technologies Dept.
IBM T.J. Watson Research Center

IDE Meta-tooling Platform Project Lead (http://www.eclipse.org/imp)
X10: Productive High-Performance Parallel Programming (http://x10-lang.org)
Previous Topic:Two problems using LPG
Next Topic:Proposed changes to indexing and PDB API
Goto Forum:
  


Current Time: Thu Oct 02 16:27:21 GMT 2014

Powered by FUDForum. Page generated in 0.02236 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software