The regular expression module which is included in the distribution is a simple rather naīve one written in Erlang which uses a back-tracking algorithm directly on the AST. It has all the problems Russ Cox mentioned in his paper. I wrote it long ago when no one was interested in parsing regexps in Erlang. :-)

I am rewriting it at the moment, still in Erlang but using the same algorithm, or similar to the one, which Russ describes. It is about the same speed as the existing one for simpler regexps but it can handle all the pathological cases as it should. It will handle POSIX syntax and semantics (but no back-references*). There will also be a version which will implement a subset of PERL regexps with PERL semantics. Both will work on either lists or binaries.

<br><br>I hadn't seen the lambda-the-ultimate discussion you mentioned and will check it out.<br><br>There are a number of regexp packages for Erlang which use PCRE or other libraries which I don't have references to. Look in the 

"Not an Erlang fan" thread here which gives some references to them.<br><br>An interesting alternative would be to write the regexp parser/compiler in Erlang and have the basic regexp matcher in the emulator. This actually wouldn't be so big, I think. Get the best of both worlds. An I used to complain (still do in fact) that the emulator is to big. :-)

<br><br>Robert<br><br>* Actually there are two types of POSIX  regexps in the standard, one which has back-references and one which doesn't.<br><br><br><div><span class="gmail_quote">On 25/09/2007, <b class="gmail_sendername">

G Bulmer</b> <<a href="mailto:gbulmer@gmail.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">gbulmer@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

After reading the original thread, I wondered what implementation of

<br>regular expression matching is used by Erlang?<br><br>I ask because this paper points out that many implementations have<br>bad pathological behaviour:<br><a href="http://swtch.com/%7Ersc/regexp/regexp1.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

http://swtch.com/~rsc/regexp/regexp1.html

</a><br>An observation they make is:<br>"Regular expression matching can be simple and fast, using finite<br>automata-based techniques that have been known for decades. In<br>contrast, Perl, PCRE, Python, Ruby, Java, and many other languages

<br>have regular expression implementations based on recursive<br>backtracking that are simple but can be excruciatingly slow."<br><br>This is followed by a discussion at <a href="http://lambda-the-ultimate.org/" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

http://lambda-the-ultimate.org/

</a><br>node/2064<br>Which seems to come to a working implementation.<br>Usefully, they note that Thompson's original patent has expired, so<br>there is no obstacle to using the original, and apparently superior,<br>

algorithm

<br><br>I looked at 'man regex' on my Mac, and it describes the POSIX<br>implementation of regex. It does contain the note "Originally written<br>by Henry Spencer", which is suggested as the basis/culprit of the

<br>pathological regular expression implementations (I should add, as<br>Henry Spencer is one of my heroes, that he is also credited with TCL<br>8 regex, which works very well according to the graphs in the paper).<br><br>

I have tried grep'ing through *.c in otp_src for regex and regcomp,<br>and came up with nothing!<br><br>Does anyone know what is used in Erlang? It may be a relatively small<br>amount of work to incorporate a new regex to provide more stable

<br>behaviour.<br><br>GB<br><br>On 25 Sep 2007, at 10:00, <a href="mailto:erlang-questions-request@erlang.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">erlang-questions-request@erlang.org</a>

 wrote:<br><br>> Date: Mon, 24 Sep 2007 09:20:08 -0700 (PDT)<br>> From: Thomas Lindgren <

<a href="mailto:thomasl_erlang@yahoo.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">thomasl_erlang@yahoo.com</a>><br>> Subject: Re: [erlang-questions] Not an Erlang fan<br>> To: "Erlang-Questions \(E-mail\)" <

<a href="mailto:erlang-questions@erlang.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

erlang-questions@erlang.org</a>><br>> Message-ID: <<a href="mailto:761781.89097.qm@web38802.mail.mud.yahoo.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">761781.89097.qm@web38802.mail.mud.yahoo.com

</a>><br>> Content-Type: text/plain; charset=iso-8859-1

> > > - > Note that this does not include the actual regexp > search of each line ... The code to do that could be > an FSM + dictionary insert instead of the simple > check-and-accumulate for newline. Extra cost? Unclear.

<br>><br>> One could merge that code into the scanning the binary<br>> but this should ideally be done by a regexp compiler,<br>> shouldn't it? Not done at this time AFAIK.<br>><br>> Best,<br>> Thomas

<br><br>> Date: Mon, 24 Sep 2007 19:55:12 +0200<br>> From: Claes Wikstrom <<a href="mailto:klacke@hyber.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">klacke@hyber.org</a>><br>> Subject: Re: [erlang-questions] Not an Erlang fan

<br>> To: Bob Ippolito <

<a href="mailto:bob@redivi.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">bob@redivi.com</a>><br>> Cc: "Erlang-Questions \(E-mail\)" <<a href="mailto:erlang-questions@erlang.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

erlang-questions@erlang.org</a>><br>> Message-ID: <<a href="mailto:46F7FA00.8070507@hyber.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

46F7FA00.8070507@hyber.org</a>><br>> Content-Type: text/plain; charset=ISO-8859-1; format=flowed<br>><br>> Bob Ippolito wrote:<br>><br>>> On 9/24/07, Patrick Logan <<a href="mailto:patrickdlogan@gmail.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

patrickdlogan@gmail.com</a>> wrote:<br>>><br>>>>>>>  <a href="http://www.tbray.org/ongoing/When/200x/2007/09/22/Erlang" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.tbray.org/ongoing/When/200x/2007/09/22/Erlang

</a><br>>>>>>>

<br>>>>>>> Tim Bray might raise some valid points here, even if he's<br>>>>>>> slightly<br>>>>>>> biased by his background.<br>>>>>>><br>><br>

> No, the only fast way today to process a large file line/by/line is to<br>><br>> 1. file:open(Filename, [read, raw])<br>> 2. In a loop {ok, Bin} = file:read(Fd, BufSize),<br>> 3. Use a binary regex matcher such as

<br>>     <a href="http://yaws.hyber.org/download/posregex-1.0.tgz" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://yaws.hyber.org/download/posregex-1.0.tgz</a><br>><br>> (I don't know the state of the regex lib in OTP today, last time

<br>>   I looked it sucked bigtime though)

<br>><br>> /klacke<br>><br>_______________________________________________<br>erlang-questions mailing list<br><a href="mailto:erlang-questions@erlang.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

erlang-questions@erlang.org</a><br><a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

http://www.erlang.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><br>