# 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. – Eliah Jun 4 '11 at 14:15
• shouldn't this be off-topic ? – Suresh Venkat 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! – Neel Krishnaswami Jun 5 '11 at 10:42
• ok. that's helpful. – Suresh Venkat Jun 5 '11 at 20:40