- cl-ppcre-devel@lists.common-lisp.net - mailman3.common-lisp.net

[cl-ppcre-devel] [Edi Weitz] Re: Lexer that keeps track of line and column #s
by Edi Weitz 23 Apr '07

23 Apr '07

For the list archive. (Sent to the wrong address originally.)

1 0

[cl-ppcre-devel] register-groups-bind tests all groups for nil
by dsb＠prairienet.org 06 Apr '07

06 Apr '07

Using register-groups-bind, sbcl generates a compiler warning if the user doesn't make sure each bound variable is non-nil before using it. Since the body is evaluated only if there's a match, testing bound variables seems kind of redundant for the first N variables, where N is the number of groups in the regex. It looks like an IF form in register-groups-bind is the source of the warning. It checks all groups for nil-ness, even the first ones. I thought variables that match groups would be guaranteed to be non-nil. I would be nice to be able to use matching variables immediately as long as the user is careful not to bind extra ones. I guess eliminating individual tests for bound groups would require that scan returns another value containing the number of matches, or truncates the register-groups array so that the number of matches is just the length of the array. Then matching variables could be bound directly, and extras could be set to nil without the IF. --Dan prairienet.org/~dsb/

2 2

[cl-ppcre-devel] Re: cl-ppcre new feature proposal
by Ondrej Svitek 25 Mar '07

25 Mar '07

Hello Edi, I've followed your list of suggestions and am sending you the patch [note: ASDF recognizes the new system as :cl-ppcre-testing], parser extension is now user-controllable through *ALLOW-NAMED-REGISTERS* switch, changes are documented in the source and html doc. I've also discovered a subtle problem - according to *ALLOW-QUOTING* documentation: * (let ((cl-ppcre:*allow-quoting* t)) (cl-ppcre:scan "^\\Qa+\\E$" "a+")) 0 2 #() #() but my SBCL simply returns NIL. It will be immediately obvious what's happening from the following code: (let ((cl-ppcre:*allow-named-registers* t)) (cl-ppcre:scan "(?<reg>.*)" "abc")) => error ... ; (LOAD-TIME-VALUE (CL-PPCRE:CREATE-SCANNER "(?<reg>.*)")) ; ; caught ERROR: ; (during EVAL of LOAD-TIME-VALUE) ; Character 'r' may not follow '(?<' at position 3 in string "(?<reg>.*)" ; ==> ; (CL-PPCRE:SCAN (LOAD-TIME-VALUE (CL-PPCRE:CREATE-SCANNER (?<reg>.*)")) "abc") ... SCAN function has a compiler-macro, which precompiles constant Perl regexes at load time. But LOAD-TIME-VALUE doesn't know about any runtime bindings (of course) affecting the scanner closure creation. Since compiler-macros may or may not get expanded, it is implementation dependent what happens. This code is likely to work in an interpreted REPL (but SBCL compiles all forms by default, hence it doesn't work here), but less likely to work when compiled. The situation probably affects more special variables than the mentioned two. Again, this is a rather subtle problem and unsuspecting user can get quite puzzled by it. I can think of the following remedies: 1. Clearly mention the pitfall in the doc and warn users to always explicitly use CREATE-SCANNER when binding special variables affecting closure generation. They can even use LOAD-TIME-VALUE, provided that it contains the desired binding inside. 2. Don't use LOAD-TIME-VALUE in the SCAN compiler-macro (I think there are more similar places that have to be fixed too, but haven't investigated them), but rather some kind of "FIRST-TIME-VALUE" - I mean, some simple sort of memoization, which would compute a scanner closure when it is needed for the first time, remembering it afterwards. This would fix the problem with binding of specials (safe only for constant values, though, as only the first-time encountered binding would be remembered and effective). It would also have the effect of spreading closure creation through program execution time. This could be seen as a benefit sometimes, e.g. when a program uses lots of constant regexes, which cause a noticeable start-up pause while compiling them during load time (hypothetically, I haven't run across such a case). Maybe there are some other possibilities, that's why I have just mentioned this issue and haven't done anything to fix it. I hope this helped. Regards, Ondrej On 19/03/07, Edi Weitz < edi(a)agharta.de> wrote: > > [Cc to mailing list.] > > Hi Ondrej, > > On Sat, 17 Mar 2007 00:31:46 +0100, "Ondrej Svitek" <ondrej.svitek(a)gmail.com> > wrote: > > > I've written a little extension to your wonderful CL-PPCRE library - > > support for named registers and back-references. I don't know if > > Perl has them (never used it), but ACL does and they proved useful > > for me in certain situations. > > > > [...] > > > > Feel free to incorporate this change, if you like it. Or not, if not > > :) > > Thanks for the code. I'd be interested to incorporate this, but for > that I'd like you to do the following: > > 1. Send a "unified diff" (diff -u) of your changes instead of a full > tarball. > > 2. Make sure to (if necessary) update all docstrings of functions that > changed their behaviour and to add docstrings for functions, > classes, or slots you added. > > 3. Add a user-visible switch to turn this new behaviour on or off, so > users can opt to have the old, Perl-compatible syntax instead. The > default should be off. > > 4. Update the HTML documentation accordingly. > > Thanks in advance, > Edi. >

2 1

[cl-ppcre-devel] New release 1.3.0
by Edi Weitz 24 Mar '07

24 Mar '07

ChangeLog: Version 1.3.0 2007-03-24 Optional support for named registers (patch by Ondrej Svitek) Download: http://weitz.de/files/cl-ppcre.tar.gz Cheers, Edi.

1 0

[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