On Mon, May 06, 2013 at 02:30:51PM +0100, Francisco Mota wrote: > Hi everyone. Long time follower but first time poster, here. > Is there an off-the-shelf available incremental parser for PEGs? > Incremental parsing is where a small change in the input string > necessitates only a small amount of additional processing. The idea is > that you parse the string once, and then adding or removing characters > from the string in the middle causes only a small amount of reprocessing. > Yes I implemented it but not entirely integrated in amethyst. See my thesis chapter 3. http://kam.mff.cuni.cz/~ondra/thesis.pdf (I discovered this independently.) > That is, you have some signature like: > > parse : String -> Syntax > insert : Int * String * Syntax -> Syntax > remove : Int * Int * Syntax -> Syntax > > where parse(s) is used for the initial parse, insert(i,s,t) will insert > the string s at position i of t, and reparse, and remove(i,k,t) will > remove k characters from position i of t. > The trivial algorithm is to just reparse the whole string. The downside is > that insert and remove operation has complexity linear in the size of the > whole string, not just the inserted part. > > The more efficient way is to only modify the parts of the parse tree that > are affected. Packrat parsing can be used to this effect. You keep the > cache around after parsing the string the first time. When the string is > updated, you invalidate only some sections of the cache, and you update > the indices of the rest of the cache, and then you reparse using the same > cache. The vast majority of the string will reparse using the cache, so > the cost of this operation is more dependant on the depth of the syntax > tree, rather than its length. (Top-level nodes will have been > invalidated.) > When you can write repetition in way it is associative you could cut this to logarithmic factor. You essentialy keep at k-th level parts consisting from at most 2^k iterations
Ondra. > So my question is: has anyone implemented this algorithm? > _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
