[Caml-list] Re: Regular expression library: a poll on features

[Xavier Leroy <xavier.leroy@inria.fr>]

As promised, here is a summary of the replies I got concerning the
"feature poll" for OCaml's regexp library.

Feature 1: back-references in regexps (e.g. "([a-z]+)\1", meaning any sequence
of lowercase letters followed by another occurrence of the same
sequence)

     use often                  4
     use occasionally           3
     no use                     5

Feature 2: partial string matching as per Str.string_partial_match, i.e.
the ability to recognize that a string is a prefix of a string that
match a regexp.

     has already used           0
     could use in some cases    6
     no use                     8

A few more remarks on these two features, and why I asked about them
in particular.  

Feature 1 is standard in many regexp packages because it's trivial to
implement in a backtracking regexp matcher.  However, it's essentially
impossible to implement if the regexp is compiled down to a
deterministic automata.  Thus, supporting feature 1 precludes
DFA-based implementations such as Jérôme Vouillon's RE library.

Feature 2 is unusual and I haven't heard from anyone that uses it :-)
I got two replies suggesting one plausible scenario where partial
matching could come handy: find delimiters in a piece of text that
is being read block by block.  However, I'm not sure
Str.string_partial_match is adequate here, it looks like a
"search forward for a partial match" operation is needed, which Str
doesn't provide...

It was also suggested to me that the effect of partial matching
against a regexp R can be achieved by exact matching against a regexp
R' derived from R.  This is true for "textbook regexps", e.g. if R is
"ab*c", then R' would be "epsilon|a(epsilon|b*(epsilon|c))",
but doesn't work for more complex regexps languages, especially if
back-references are supported.  (Consider R = "(a+)\1".)

Thanks for your input,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners