<p>Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7015&amp;rep=rep1&amp;type=pdf" rel="nofollow">"Efficient and Flexible Incremental Parsing"</a>, which extends LR parsing to support incremental  update of the document. </p>

CC BY-SA 3.0
2011-06-05T13:23:56.830Z
2011-06-05T13:23:56.830Z
Neel Krishnaswami
<p>T. Wagners dissertation is about <a href="http://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-thesis.pdf" rel="nofollow">"Incremental Software Development Environments"</a>. You can find a bunch of resources at the <a href="http://harmonia.cs.berkeley.edu/harmonia/publications/harmonia-pubs.html" rel="nofollow">Harmonia and Ensemble Homepage</a></p>

CC BY-SA 3.0
2012-12-26T19:00:14.867Z
2012-12-26T19:00:14.867Z
Stefan K.
<p>I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.</p>

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

<pre><code>((1)())(2)
    ((1)())
        (1)
            1
        ()
    (2)
        2
</code></pre>

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

CC BY-SA 3.0
2011-06-04T13:40:06.423Z
Knowing your motivation for doing this might help answer you question.
Rob
CC BY-SA 3.0
2011-06-04T14:15:17.383Z
@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.
Eliah
CC BY-SA 3.0
2011-06-05T05:10:38.847Z
shouldn't this be off-topic ?
Suresh Venkat
CC BY-SA 3.0
2011-06-05T10:42:52.693Z
@Suresh: incremental parsing is still an active research area. It's also kind of a swamp, so I would want guidance into the literature!
Neel Krishnaswami
CC BY-SA 3.0
2011-06-05T20:40:56.043Z
ok. that's helpful.
Suresh Venkat
<fl.formal-languages><online-algorithms><parsing><compilers>
Brackets expression incremental parsing algorithm
Eliah
# Brackets expression incremental parsing algorithm

(Asked by: username_0 on 2011-06-04)

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?

**Tags:** fl.formal-languages, online-algorithms, parsing, compilers

> **Comments:**
> **username_1**: Knowing your motivation for doing this might help answer you question.  
> **username_0**: @username_1 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.  
> **username_2**: shouldn't this be off-topic ?  
> **username_3**: @Suresh: incremental parsing is still an active research area. It's also kind of a swamp, so I would want guidance into the literature!  
> **username_2**: ok. that's helpful.  

---

## 2 answers

### Answer by username_3 on 2011-06-05. Score: 4

Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, ["Efficient and Flexible Incremental Parsing"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7015&rep=rep1&type=pdf), which extends LR parsing to support incremental update of the document.


---

### Answer by username_4 on 2012-12-26. Score: 1

T. Wagners dissertation is about ["Incremental Software Development Environments"](http://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-thesis.pdf). You can find a bunch of resources at the [Harmonia and Ensemble Homepage](http://harmonia.cs.berkeley.edu/harmonia/publications/harmonia-pubs.html)


---

