On Mon, May 06, 2013 at 06:36:54PM +0100, Francisco Mota wrote: > > Changing the input stream would throw off memoization in a Packrat > parser. > Only some parts of the memoization table would be invalidated by an insert > or a remove. You would need to update the rest of the memoization table in > order to support the new indices. (The right data structure for the table > would help keep costs down.) This is precisely why I think Packrat parsing > works well for incremental parsing. > > > Mizushima and others on this list have work showing that memory use in > Packrat parsers can be sublinear with the addition of cuts, and that cut > insertion can be automated. > > I don't think this would work if one wants to optimize incremental > parsing, as opposed to one-time parsing. You need to keep the old parsing > data around in order to minimize future duplication of effort. I reckon > that you would always need at least a linear amount of information in the > memoization table, otherwise you'll have to reparse the entire string (at > least linearly many bits of it) whenever a change is made. But this is > speculation on my part. > As far as I remember on problem of maintaining parity if you use O(n^(1-e)) memory then you need do queries of size n^e . You can write parity problem as a grammar so incremental parsing is special case.
For memory complexity my solution is relatively simple. First idea is measure how long call takes and memoize only these that take say 1000 cycles. This has problem that it is platform dependent. You can get similar results if you memoize calls that call at least 16 other rules(recursively.) Or if you do not care about pathological grammars you can memoize only rules that inspect more than 16 characters. _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
