February 2007 - cl-ppcre-devel@common-lisp.net

[cl-ppcre-devel] Darcs repositories
by Edi Weitz 22 Feb '07

22 Feb '07

[My apologies if you get this more than once.] Several people have asked for Darcs repositories of my software. These do exists now: http://common-lisp.net/~loliveira/ediware/ Special thanks to Luís Oliveira who made this possible and who maintains the repositories. Cheers, Edi.

1 0

[cl-ppcre-devel] searching backward?
by Shawn Betts 16 Feb '07

16 Feb '07

Hi folks, Is there a way to search backward through a string? * (ppcre:scan "abc" "111abc1111abc11") 3 6 #() #() * (ppcre:scan "abc" "111abc1111abc11" :start 15 :end 0) NIL I tried just making end < start which doesn't seem to work :). I suppose what i'm looking for is the equivalent of :from-end that most cl sequence functions have. -Shawn

2 4

[cl-ppcre-devel] Re: Question: PCRE -> Thompson NFA Implementation
by Edi Weitz 14 Feb '07

14 Feb '07

On Tue, 13 Feb 2007 21:08:33 -0800, Brent Fulgham <bfulg(a)pacbell.net> wrote: > The implementations are all written by volunteers who submit them. > If you see any low hanging fruit, let me know and I'll be glad to > update the tests. For example here's a more compact (and most likely faster) way to read a whole file at once (untested): (defun get-input-chars (stream) (let ((result (make-string (file-length stream)))) (read-sequence result stream) result)) See also <http://www.emmett.ca/~sabetts/slurp.html>. It probably won't change the outcome of the benchmark, but the original function looks pretty weird. Also, if you're really obsessed with speed, CL-PPCRE:ALL-MATCHES certainly isn't the best way to count all matches because it conses up a list you don't need. You should use DO-SCANS and count yourself. Finally, I think that ">[^\\n]*\\n|\\n" should be replaced by "(?m)\\n|^>.*" - maybe not for speed, but for clarity and correctness. > But of course, the tests are all for entertainment purposes only ;-) Yes... :)

1 0

[cl-ppcre-devel] Re: Question: PCRE -> Thompson NFA Implementation
by Edi Weitz 13 Feb '07

13 Feb '07

On Tue, 13 Feb 2007 12:23:36 -0800 (PST), Brent Fulgham <bfulg(a)pacbell.net> wrote: > http://shootout.alioth.debian.org/debian/benchmark.php?test=regexdna I took a quick look. That SBCL program doesn't look as if it was written by an experienced Lisper. I hope nobody takes these "Shootouts" seriously, or they should at least attempt not to compare apples with oranges...

1 0

[cl-ppcre-devel] Re: Question: PCRE -> Thompson NFA Implementation
by Edi Weitz 13 Feb '07

13 Feb '07

Hi, first of all: 1. Please use the mailing list. http://weitz.de/cl-ppcre/#mail 2. It's called CL-PPCRE and not PCRE. PCRE is something else... :) On Tue, 13 Feb 2007 12:23:36 -0800 (PST), Brent Fulgham <bfulg(a)pacbell.net> wrote: > Although your Lisp implementation of a Perl-compatible regular > expression engine already handily beats the original Perl version, > it could be modified to be even faster for expressions that do not > contain back-references. See the following article that discusses > the 1960's-era algorithm used in Awk/Grep that discusses this > (http://swtch.com/~rsc/regexp/regexp1.html) > > In my testing, CL-PCRE isn't quite faster than Perl, though it makes > a very creditable showing > (http://shootout.alioth.debian.org/debian/benchmark.php?test=regexdna〈=all) > Tcl, which uses the "Thompson DFA" algorithm discussed in the paper > I referenced is nearly an order of magnitude faster on this > benchmark than Perl. > > Please let me know if you have any interest exploring this. I might > try to play with this and see if I can make any headway... I'm aware of the advantages of DFAs over NFAs for "simple" regular expressions, but I shied away from them until now because having two engines in CL-PPCRE would make the code base even bigger and more complicated than it already is. (And having /only/ a DFA engine wouldn't be enough, right? I haven't read the article yet, but I'm pretty sure you'd have to let go some of Perl's more advanced regex features.) Also, although I boast about CL-PPCRE's performance on its web site, I'm not too concerned about its speed anymore. It's fast enough for what I'm doing with it. Having said that, the idea of automatically switching to a fast DFA engine if possible (I guess this is what you want to do) is kind of tempting. If you come up with something that's really a big improvement and adheres to CL-PPCREs current coding and documentation standards, I'd be willing to review and possibly integrate it. Right now, I'm to busy to help with that, though. Cheers, Edi.

1 0

[cl-ppcre-devel] Quickly finding which alternative matched
by Harold Lee 13 Feb '07

13 Feb '07

For an :ALTERNATION, is there an O(1) way to tell which alternate matched? e.g. for a regexp (a)|(b)|(c)|(d)|... I don't want the O(n) performance of scanning the list returned by SCAN or SCAN-TO-STRINGS. Instead, I'd just like a number saying which one matched. I understand that there can normally be nested groups, alternatives that are not groups, and other complications - so maybe a list/vector of groups that were matched would work as a general interface. More background: For a quick and dirty scanner (similar to lex) I thought I could use CL-PPCRE. The "rules" (in lex terminology) are just regular expressions, and so I combine them into a set of alternatives, e.g. \s+ -> whitespace [0-9]+ -> number [a-zA-Z][a-zA-Z0-9]* -> identifier => "(\\s+)|([0-9]+)|([a-zA-Z][a-zA-Z0-9]*)" Actually, I use CL-PPCRE::PARSE-STRING to get a parse tree for each expression, change any :REGISTER tags to :GROUP tags, and combine them under an :ALTERNATION tag: (defun combine-regexps (&rest regexps) "Combine several regexp strings into a CL-PPCRE parse tree of alternatives." ;; All registers are changed into groups, i.e. (x) -> (?:x) in regexp syntax. ;; That keeps the registers from messing up the scanner's expectation that ;; each register is one of the rules, and allows the list of rules to use ;; () instead of (?:) throughout for readability. (let ((registers (mapcar (lambda (r) `(:register ,(subst :group :register (cl-ppcre::parse-string r)))) regexps))) `(:sequence :start-anchor (:group (:alternation ,@registers)))))

2 2