Incremental parsing and left folds

[Adam Langley]

On Feb 1, 2008 9:35 AM, Bryan O'Sullivan <bos at serpentine.com> wrote:
> It wouldn't be hard to take bytestringparser and perform the same
> transformation on it as Adam Langley did with his IncrementalGet parser
> for strict-binary.  I've been skipping it due to lack of time, but it's
> an obviously right thing to do.

I think the hurdle here would be that you can't easily rollback the
state. Normally, in a parser one can just take the current state and
revert to that if a parsing path fails. However, in an incremental
parser, of the style of IncrementalGet, rolling back the state would
mean that the additional data which has been supplied to the parser,
via continuations, will be lost and needs to be resupplied. That's a
non-solution because the caller shouldn't need to know anything about
the internals of the parser.

I think one could get around this by having a couple of states, the
latter being a list of all the additional ByteStrings that the parser
has received. Then, after having prospectively failed a certain parse
path, the failure must include the list of additional data, which can
be merged into the new state for the next prospective path. This
failure value must be internal and, at the top level, translated into
a more user-friendly failure.

Unless something special is done, this also means that the incremental
parser couldn't walk over huge streams of data, because it would still
be holding all the input in case it gets reverted. Of course, the top
level cannot be reverted, so maybe it's worth special casing this.


AGL

-- 
Adam Langley                                      agl at imperialviolet.org
http://www.imperialviolet.org                       650-283-9641