# Brackets expression incremental parsing algorithm

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?

• Knowing your motivation for doing this might help answer you question.
– Rob
Jun 4 '11 at 13:40
• @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. Jun 4 '11 at 14:15
• shouldn't this be off-topic ? Jun 5 '11 at 5:10
• @Suresh: incremental parsing is still an active research area. It's also kind of a swamp, so I would want guidance into the literature! Jun 5 '11 at 10:42
• ok. that's helpful. Jun 5 '11 at 20:40

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.

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