A big win about the explicit DFA-based API (though,
again, probably impractical for Snow, just now) is that
if you have that, then you can efficiently use regexps to
scan text that is not contiguous in memory (I didn't sketch
the API quite right to make that clear, sorry).    E.g., you
can stream in stuff very fast, scanning buffers using the DFA,
and driving your protocol engine that way.   Very fun
stuff.


For fun: people should gleefully note the woes of Cisco
regarding regexps as reported on Slashdot today.   I don't
mean we should celebrate a nasty bug just that we should be
encouraged that investing in the engineering effort to make
really solid regexp engines has high social value.

-t



Shiro Kawai wrote:
From: Thomas Lord <lord@emf.net>
Subject: Re: [Snow-users-list] high-priority snow packages and package naming
Date: Sat, 15 Sep 2007 15:45:45 -0700

  
Please, no such thing as match structures.   They are a botched design
in Posix and Perl -- pure legacy.   Simulate them, better, in portable
scheme atop a "true regular expression" back-end.
    

+1 for Tom Lord.

Submatches not only twist engine implementation, but also there are
incompatibilities in edge cases between implementations that can
bite you some day, for exmaple:

- If a capturing group matches more than once, which part of the
  string should be a "submatch"?  The first one matching the group,
  the last one?  Or every one of them should be saved and retrieved
  as a list?  I think I've seen all three types.

- If a capturing group may match an empty string, and it is inside
  repetition, how should it match?  A naive implementation can yield
  infinite loop, since it can match an arbitrary number of repetitions
  of "empty string".   Perl engine and Ruby engine differ in the
  interpretation of this case, though I don't remember the details.

The advantage of having high-level stuff in Scheme is that we can
set the semantics (or we can provide options) portably, instead
of relying slighly differing underlying implementations and
crossing our fingers to work.

I'm not sure the performance impact (and not so optimistic as Tom,
I guess), but if such portable high-level module is coming along,
I'm willing to optimize Gauche's low-level regexp engine toward it.

I heven't fully thought out Tom's suggested spec, but one concern
is the representation of match position in string---Gauche doesn't
like character index.  Internally Gauche's engine compiles given
regexp in an FA that works for octet-stream, and it only calculates
character index when requested (so, actually, in Gauche it may be
faster to get matched substring rather than indices of a submatch,
when the submatch is in the middle of a long mutibyte string.)
It would be nice if the portable high-level layer assumes that
the low-level engine returns implementation-dependent representation
of matched positions, instead of "character index".

--shiro