Re: Regex introduction?

Thanks for the info.  So far, I found this:

APIs

   * XSB and YAP interface return matched positions, ECLiPSe
     returns matched strings.
   * XSB does automatic management of a pool of compiled
     expressions (about 10).
   * ECLiPSe provides both explicit compilation (with options)
     and implicit.  Are these `pooled' too?

RE2 vs PCRE

   * RE2
     + linear and has better stack-size behaviour.
     - C++ (would be only C++ component near the core)
     - Only processes Latin-1 and UTF-8 text
     - There is a remark that it is not portable to Windows.
       Not clear to whether that is an MSVC compiler issue
       (and MinGW works) or a Windows issue, such as Win64
       longs that are 32 bits.  Anyone?
   * PCRE
     - Exponential behaviour is possible
     + Mature portable code base in pure C
     + Can deal with many different encodings, although you
       need to compile different libraries.  These can
       co-exist.  One lib has about half the binary size as
       RE2 (260Kb vs 470Kb, AMD64 code, gcc 4.7).

All in all, especially the ability of PCRE to work on all
our datatypes and its guaranteed portability to Windows
causes me to prefer this.  The ECLiPSe API seems the best
starting point, although I think there should at least be
an additional API that returns match positions rather then
matched strings.

	Cheers --- Jan




On 11/26/2013 01:35 AM, Michael Hendricks wrote:
> On Mon, Nov 25, 2013 at 4:28 PM, Abramo Bagnara
> <[email protected] <mailto:[email protected]>> wrote:
>
>     Il 25/11/2013 23:02, Michael Hendricks ha scritto:
>      > On Mon, Nov 25, 2013 at 12:56 PM, Jan Wielemaker
>     <[email protected] <mailto:[email protected]>> wrote:
>      >
>      >> I'm seriously considering to add regular expression support
>     based on the
>      >> pcre (Perl Compatible Regular Expressions) library. This seems
>     to be the
>      >> library of choice for most modern languages and provides support
>     for the
>      >> two internal representations used in SWI-Prolog for Unicode text.
>      >>
>      >
>      > You might consider RE2, if you haven't already.  It supports nearly
>      > everything that PCRE does but has much better performance
>     characteristics.
>
>     Why you say that? AFAIK this is not true nowadays.
>
>
> PCRE has many clever optimizations to avoid it, but exponential behavior
> is still present.  Compare
>
>     perl -Mre::engine::PCRE -e '("a" x 25)  =~ /(.*){1,100}[bc]/'
>
> against an equivalent pattern match in Go:
> http://play.golang.org/p/9uMv6dzPgd
>
> PCRE takes about 10 seconds (with N=26 it takes twice as long).  RE2
> takes about 0.01 seconds regardless of N.
>
> Russ Cox did some useful performance comparisons in 2010, separate from
> exponential behavior.  They may not be valid with more recent PCRE:
> http://swtch.com/~rsc/regexp/regexp3.html
>
> --
> Michael