Parser Generator for changing file.

Question

Hi,

are there any Parser Generator which generated parsers are capable of the following: Parse a file and if you change line n then it only reparses the line or the lines which changed because of this. So that the parser don't need to reparse the full file.

Greets,

Mathias

Answer 1

I can not give a definite yes or no but I doubt it. Parser generators are designed to create parsers for arbitrary grammars. Updating a parse tree by only reinspecting a single line puts strong constraints on the grammar or the allowed changes because it must effect only a highly localized part of the parse tree. So I strongly doubt that someone integrated such a feature in a general purpose parser generator.

Answer 2

Tim Wagner worked on this for quite awhile. See his GLR parsing engine paper. It works basically by keeping the parse tree around and trying to reparse the "entire stream" as a sequence of parse trees and changed tokens. Its quite clever.

Scott McPeak claims that Elsa implements an incremental GLR parser. AFAIK, Elsa is mostly used for batch parsing.

Answer 3

I had some success in implementing a general parsing engine on top of Packrat. It fits well this purpose because of the memoisation - an editor invalidates only the memoised chunks that overlaps the modified line, and then the whole file is reparsed, but only the modified line is actually parsed, all the rest stays memoised from the previous run.

There are no ready usable solutions, but you can pick up any Packrat implementation and brew your own thing on top of it.

You can take a look at how Packrat integrates with a text editor here:

http://www.meta-alternative.net/mbase.html