<p>As per @Agos request, I turned the comment into an answer.</p>

<p>First, I must admit that I'm not really knowledgeable in this field. Yet I suggest you read the papers <a href="http://portal.acm.org/citation.cfm?id=582175">Building friendly parsers</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7015&amp;rep=rep1&amp;type=pdf">Efficient and Flexible Incremental Parsing</a> to have a view of what algorithms were used for <strong>incremental parsing</strong> before 2000.</p>

<p>For updated treatments, you may take a look at these papers:</p>

<ul>
<li><a href="http://portal.acm.org/citation.cfm?id=1596645">Lazy functional incremental parsing</a> (2009)</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.7916&amp;rep=rep1&amp;type=pdf">Practical, incremental, noncanonical parsing: Celentano's method and the Generalized Piecewise LR parsing algorithm</a> (2006)</li>
<li><a href="http://portal.acm.org/citation.cfm?id=1042050">Incremental validation of XML documents</a> (2004)</li>
<li><a href="http://onlinelibrary.wiley.com/doi/10.1002/spe.422/abstract">Incremental parsing in language-based editors: user needs and how to meet them</a> (2001)</li>
<li><a href="http://74.125.155.132/scholar?q=cache%3aiDsS-Z6xogEJ%3ascholar.google.com/&amp;hl=en&amp;as_sdt=2005&amp;sciodt=2000">Incremental Parsing and the C Preprocessor</a> (Couldn't find the PDF anywhere. It is from Google cache.)</li>
</ul>

<p><strong>More info:</strong> There are (at least) two approaches to parsing/compilation: </p>

<ul>
<li>The <strong>batch</strong> approach, in which the whole block of code is parsed/compiled.</li>
<li>The <strong>incremental</strong> 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 <a href="http://scholar.google.com/scholar?hl=en&amp;safe=off&amp;q=%22background%20compilation%22&amp;um=1&amp;ie=UTF-8&amp;sa=N&amp;tab=ws">background compilation</a>, which is related to <a href="http://scholar.google.com/scholar?hl=en&amp;q=%22lazy+compilation%22&amp;btnG=Search&amp;as_sdt=2000&amp;as_ylo=&amp;as_vis=0">lazy compilation</a>. (You can also search about commercial features such as the  <a href="http://en.wikipedia.org/wiki/IntelliSense">IntelliSense</a>).</li>
</ul>

CC BY-SA 2.5
2011-01-04T12:57:39.007Z
2011-01-04T12:57:39.007Z
Sadeq Dousti
<p>Let's say I have a big block of code which I already have lexed and parsed.<br>
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.</p>

<p>Thanks in advance!</p>

CC BY-SA 2.5
2011-01-04T00:17:04.770Z
Hi, and welcome! I'm not an expert on the subject, but I think the keyword you're looking for is **incremental parsing** or [incremental compilation](http://en.wikipedia.org/wiki/Incremental_compiler).
Sadeq Dousti
CC BY-SA 2.5
2011-01-04T12:15:19.770Z
@Sadeq thanks for the pointer! Would you consider adding an answer with some details? It'd be greatly appreciated!
Agos
<fl.formal-languages><parsing>
Efficient algorithm for updating a parse tree
Agos
# Efficient algorithm for updating a parse tree

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

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!

**Tags:** fl.formal-languages, parsing
> **Comments:**
> **username_1**: Hi, and welcome! I'm not an expert on the subject, but I think the keyword you're looking for is **incremental parsing** or [incremental compilation](http://en.wikipedia.org/wiki/Incremental_compiler).  
> **username_0**: @Sadeq thanks for the pointer! Would you consider adding an answer with some details? It'd be greatly appreciated!  

---

## 1 answers

### Answer by username_1 on 2011-01-04. Score: 9 | Accepted answer

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](http://portal.acm.org/citation.cfm?id=582175) and [Efficient and Flexible Incremental Parsing](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7015&rep=rep1&type=pdf) 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](http://portal.acm.org/citation.cfm?id=1596645) (2009)
* [Practical, incremental, noncanonical parsing: Celentano's method and the Generalized Piecewise LR parsing algorithm](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.7916&rep=rep1&type=pdf) (2006)
* [Incremental validation of XML documents](http://portal.acm.org/citation.cfm?id=1042050) (2004)
* [Incremental parsing in language-based editors: user needs and how to meet them](http://onlinelibrary.wiley.com/doi/10.1002/spe.422/abstract) (2001)
* [Incremental Parsing and the C Preprocessor](http://74.125.155.132/scholar?q=cache%3aiDsS-Z6xogEJ%3ascholar.google.com/&hl=en&as_sdt=2005&sciodt=2000) (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](http://scholar.google.com/scholar?hl=en&safe=off&q=%22background%20compilation%22&um=1&ie=UTF-8&sa=N&tab=ws), which is related to [lazy compilation](http://scholar.google.com/scholar?hl=en&q=%22lazy+compilation%22&btnG=Search&as_sdt=2000&as_ylo=&as_vis=0). (You can also search about commercial features such as the [IntelliSense](http://en.wikipedia.org/wiki/IntelliSense)).


---

