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. 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.) So my question is: has anyone implemented this algorithm? Take care, Francisco Mota
_______________________________________________ PEG mailing list [email protected] https://lists.csail.mit.edu/mailman/listinfo/peg
