Efficient algorithm for updating a parse tree

Question

Let's say I have a big block of code which I already have lexed and parsed.
Suppose that just one character changes; I would want to update my parsing, but since the modification is very small compared to the whole thing, I would like to know if it's possible not to parse the whole thing again, but if there are algorithms to determine the range to re-parse, and to properly deal with moving token boundaries.

Thanks in advance!

Answer 1

As per @Agos request, I turned the comment into an answer.

First, I must admit that I'm not really knowledgeable in this field. Yet I suggest you read the papers Building friendly parsers and Efficient and Flexible Incremental Parsing to have a view of what algorithms were used for incremental parsing before 2000.

For updated treatments, you may take a look at these papers:

• Lazy functional incremental parsing (2009)
• Practical, incremental, noncanonical parsing: Celentano's method and the Generalized Piecewise LR parsing algorithm (2006)
• Incremental validation of XML documents (2004)
• Incremental parsing in language-based editors: user needs and how to meet them (2001)
• Incremental Parsing and the C Preprocessor (Couldn't find the PDF anywhere. It is from Google cache.)

More info: There are (at least) two approaches to parsing/compilation:

• The batch approach, in which the whole block of code is parsed/compiled.
• The incremental approach, in which the document is first parsed/compiled in the batch mode, and then changes are detected and the minimal re-parsing/re-compilation is applied. This approach not only increases the parse/compilation speed, but also helps in IDE nifty features such as background compilation, which is related to lazy compilation. (You can also search about commercial features such as the IntelliSense).

Answer 2

if your incremental parser saves state at each end of line, you re-parse just from the last valid parser state (at best case, e.g. after a full-parse this is just the begin of line where modification starts) and stop parsing at end of line where modification ends (internally parser might look ahead beyond the modification to recognize properly the structure)