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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Knowing your motivation for doing this might help answer you question. $\endgroup$
    – Rob
    Jun 4, 2011 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, 2011 at 14:15
  • 2
    $\begingroup$ shouldn't this be off-topic ? $\endgroup$
    – Suresh Venkat
    Jun 5, 2011 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, 2011 at 10:42
  • 1
    $\begingroup$ ok. that's helpful. $\endgroup$
    – Suresh Venkat
    Jun 5, 2011 at 20:40

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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