14
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4 '11 at 0:17
  • $\begingroup$ @Sadeq thanks for the pointer! Would you consider adding an answer with some details? It'd be greatly appreciated! $\endgroup$
    – Agos
    Jan 4 '11 at 12:15
9
$\begingroup$

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:

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).
$\endgroup$
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.