5
$\begingroup$

I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.

Consider the example with expression like "((1)())(2)". Parse tree for that expression is:

((1)())(2)
    ((1)())
        (1)
            1
        ()
    (2)
        2

Lets assume we inject additional symbols ")(" in the middle of the expression: "((1)()())(2)". My question is how to apply changes in the parse tree without reparsing of the whole input?

$\endgroup$
  • 1
    $\begingroup$ Knowing your motivation for doing this might help answer you question. $\endgroup$ – Rob Jun 4 '11 at 13:40
  • $\begingroup$ @Rob I'm going to implement some kind of incremental parser for my own programming language with C-like syntax. My current idea is to split source code by operator blocks(blocks between curly brace symbols) and parse such blocks separately using usual LL or LR parser. Therefore algorithm of efficient splitting by such blocks might be useful. $\endgroup$ – Eliah Jun 4 '11 at 14:15
  • 2
    $\begingroup$ shouldn't this be off-topic ? $\endgroup$ – Suresh Venkat Jun 5 '11 at 5:10
  • 2
    $\begingroup$ @Suresh: incremental parsing is still an active research area. It's also kind of a swamp, so I would want guidance into the literature! $\endgroup$ – Neel Krishnaswami Jun 5 '11 at 10:42
  • 1
    $\begingroup$ ok. that's helpful. $\endgroup$ – Suresh Venkat Jun 5 '11 at 20:40
4
$\begingroup$

Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, "Efficient and Flexible Incremental Parsing", which extends LR parsing to support incremental update of the document.

$\endgroup$
1
$\begingroup$

T. Wagners dissertation is about "Incremental Software Development Environments". You can find a bunch of resources at the Harmonia and Ensemble Homepage

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.