Partial parsing

["Markus Mottl" <markus.mottl@gmail.com>]

Hi,

one feature that I'd love to see with our lexing/parsing tools for
OCaml would be the possibility to perform partial lexing / parsing.

For example, imagine that you read a message from a socket into a
string buffer, but it is not yet complete.  You may not be able to
know that in advance, because that would require parsing it.

What I'd like to be able to do is to e.g. call a lexer or parser
function on this buffer, and it will recognize as much as possible
with the option to continue parsing in another buffer.  For this we
could e.g. define a type "parse_result":

  type parse_result =
    | Done of result * int
    | Cont of parse_fun
  and parse_fun = pos : int -> len : int -> string -> parse_result

If a full parse was detected, it would return e.g. "Done (result,
next_pos)", where "result" is the result of the successful parse, and
"next_pos" is the position in the buffer that contains the character
following the successfully parsed text.

If the buffer did not contain enough data to finish the parse, the
function would return e.g. "Cont f", where "f" can be called to
continue parsing in a new buffer starting at position "pos" and
reading at most "len" characters, e.g. in the case when the rest of
the message arrives in the input buffer.

So far this kind of parsing can only be implemented by hand, which is
very tedious to do and inevitable if one wants to read self-delimiting
messages of variable size from sources that return partial data.  I
don't see any inherent problem extending the code generators for
ocamllex and ocamlyacc to support this feature.

Has anybody already implemented a generic solution to this kind of
parsing problem?  Maybe Menhir, which seems like an ambitious parser
project, could add this feature to support partial parsing (of course,
this would require cooperation from the lexer, too)?

Regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com