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

[cl-ppcre-devel] Re: freeze-type ing cl-ppcre?
by Edi Weitz 23 Aug '04

23 Aug '04

Hi Jim! On Sun, 22 Aug 2004 10:18:39 -0600 (MDT), Jim Prewett <download(a)hpc.unm.edu> wrote: > I was poking around the CMUCL optimizations page and came across the > freeze-type declaration. > > I tried adding it to LoGS and it made a notable improvement. I also > tried adding it to CL-PPCRE and found that that seemed to help as > well. > > Is this going to bite me? Do the cl-ppcre types change ever? I'm not familiar with FREEZE-TYPE. How did you use it and how did it improve CL-PPCRE? Is this new in 19a? Would you mind taking the rest of this exchange to the mailing list (see Cc)? Thanks. Cheers, Edi.

2 3

[cl-ppcre-devel] empty line matches with cl-ppcre
by Jan Rychter 14 Jul '04

14 Jul '04

I'm confused. I must be doing something wrong. I have a string: CL-USER> *str* "1 2 3 4 " Just to make sure it's really what it seems: CL-USER> (loop for c across *str* do (format t "~S " c)) #\1 #\Newline #\2 #\Newline #\3 #\Newline #\Newline #\4 #\Newline NIL I wanted to match empty lines, so I did: CL-USER> (cl-ppcre:regex-replace-all (cl-ppcre:create-scanner "^$" :multi-line-mode t) *str* "!") "1 2 3 !! 4 !!" Now, I would normally expect this: "1 2 3 ! 4 " Playing with regex-coach indeed produces the result I'd normally expect. What am I doing wrong? (using CMUCL 19a, the testing version, and CL-PPCRE-0.7.7) many thanks, --J.

2 5

[cl-ppcre-devel] New version 0.7.9
by Edi Weitz 13 Jul '04

13 Jul '04

Hi! A new release is available from <http://weitz.de/files/cl-ppcre.tgz>. Here's the relevant part from the changelog: Version 0.7.9 2004-07-13 Fixed bug in DO-SCANS (caught by Jan Rychter) Have fun, Edi

1 0

[cl-ppcre-devel] New version 0.7.8
by Edi Weitz 13 Jul '04

13 Jul '04

Hi! A new release is available from <http://weitz.de/files/cl-ppcre.tgz>. Here's the relevant part from the changelog: Version 0.7.8 2004-07-13 New SIMPLE-CALLS keyword argument for REGEX-REPLACE(-ALL) Added environment parameter to compiler macros (thanks to c.l.l article <aczhx5hj.fsf(a)ccs.neu.edu> by Joe Marshall) Added compiler macros for SCAN-TO-STRINGS and REGEX-REPLACE(-ALL) (they somehow got lost) Have fun, Edi

1 0

[cl-ppcre-devel] Re: cl-ppcre
by Edi Weitz 07 Jul '04

07 Jul '04

Sorry for the delay, I had moved this email into the wrong IMAP folder... :( On Sun, 20 Jun 2004 12:07:08 +0200, Daniel Skarda <0rfelyus(a)ucw.cz> wrote: > After more regexp experiments I found that the main difference > between Perl and GNU Regexp is not the syntax of regexps (as I > naively thought), but the definition of "the best match" (especially > for `|' alt node). > > One can agree with Perl man pages, that Perl definition could be > better (and more comprehensible) for handwritten regexps. Is "first > match" strategy also better for writing lexers? I doubt. > > Consider languages where some word (token) can be prefix of > another word. This is not unusual: remember that in Lisp `12345' is > number and `12345a' is symbol :) > > While writing "first match" lexer (and your deflexer macro is > "first match" lexer) one has to be careful with rules ordering and > think about possible prefix ambiguity: Yes. But if you prefer not to be careful you'll definitely sacrifice performance... > My conclusion is, that 'success node is meaningful only for > "longest match" regexps engines, because one can expect, that such > engine could do better than match all 'alt nodes in sequence and > return the longest match. > > My new question is: how hard it would be to add :longest-match > option to create-scanner? Pretty hard. This is not going to be done by me. However, if you manage to add this yourself without breaking the rest of CL-PPCRE (and without making it slower) I'll gladly accept your patches. > ps: I am not subscribed to cl-ppcre-devel mailing list. Please "Cc:" > me your replies. Subscribing to the list is easy and the list is low-volume. If you'd like to continue this discussion please either subscribe to the list or use it via nntp: <http://common-lisp.net/nntp.shtml> Cheers, Edi.

1 0

[cl-ppcre-devel] Re: cl-ppcre
by Edi Weitz 12 Jun '04

12 Jun '04

Hi Daniel! On Sat, 12 Jun 2004 15:54:11 +0200, Daniel Skarda <0rfelyus(a)ucw.cz> wrote: > today I explored the possibilities of regular expressions > implementations in various Debian Common Lisp packages. I really > liked your library - thank you for writing cl-ppcre library. You're welcome. > I also looked into elegant cl-lexer package built on top of > cl-regex library. What I missed in cl-ppcre is a parse-tree node > similar to cl-regex's 'success node, which defines return value of > match/scan functions. With 'success node one can build `deflexer' > macro on top of cl-ppcre as easy as on top of cl-regex package. > > Is it possible to extend cl-ppcre with similar feature? I might look into this for a future version but see below. > Footnote: In cl-lexer, deflexer macro > > (deflexer foo > ("regexp" some action) ; 0 > ("another regexp" another action) ; 1 > ...)) > > numbers each pair of regexp and action, then combine regexp parse > trees into one big parse tree > > `(alt > (seq (regexp tree) (success 0)) > (seq (another regexp tree) (success 1)) > ...) > > and use return value from match (ie regexp serial number) to select > an action associated to matching regexp) I've recently written demo code like this for another CL-PPCRE user who also wanted to build a lexer: (in-package :cl-user) (eval-when (:compile-toplevel :load-toplevel :execute) (defmacro with-unique-names ((&rest bindings) &body body) ;; see <http://www.cliki.net/Common%20Lisp%20Utilities> `(let ,(mapcar #'(lambda (binding) (check-type binding (or cons symbol)) (if (consp binding) (destructuring-bind (var x) binding (check-type var symbol) `(,var (gensym ,(etypecase x (symbol (symbol-name x)) (character (string x)) (string x))))) `(,binding (gensym ,(symbol-name binding))))) bindings) ,@body))) (defmacro deflexer (name &body body) (with-unique-names (regex-table regex token sexpr-regex anchored-regex string start scanner next-pos) `(let ((,regex-table (loop for (,regex . ,token) in (list ,@(loop for (regex token) in body collect `(cons ,regex ,token))) for ,sexpr-regex = (etypecase ,regex (function (error "Compiled scanners are not allowed here")) (string (cl-ppcre::parse-string ,regex)) (list ,regex)) for ,anchored-regex = (cl-ppcre:create-scanner `(:sequence :modeless-start-anchor ,,sexpr-regex)) collect (cons ,anchored-regex ,token)))) (defun ,name (,string &key ((:start ,start) 0)) (loop for (,scanner . ,token) in ,regex-table for ,next-pos = (nth-value 1 (cl-ppcre:scan ,scanner ,string :start ,start)) when ,next-pos do (return (values ,token ,next-pos))))))) You should be able to use it like this: * (deflexer mylexer ("'.*'" 'string) ("#.*$" 'comment) ("[ \t\r\f]+" 'ws) (":=" 'assign) ("[\[]" 'lbrack) ("[\]]" 'rbrack) ("[\,]" 'comma) ("[\:]" 'colon) ("[\;]" 'semicolon) ("[+-]?[0-9]*[\.][0-9]+([eE][+-]?[0-9]+)?" 'float) ("[+-]?[0-9]+" 'integer) ("[a-zA-Z0-9_]+" 'id) ("." 'unknown)) ; Converted MYLEXER. MYLEXER * (mylexer "a:=123.4?") ID 1 * (mylexer "a:=123.4?" :start 1) ASSIGN 3 * (mylexer "a:=123.4?" :start 3) FLOAT 8 * (mylexer "a:=123.4?" :start 8) UNKNOWN 9 This one only returns tokens but it should be trivial to change the macro such that the newly-defined lexer invokes functions instead. Wouldn't that already do what you want? I'm not sure what the approach you sketched above would buy you compared to this one. Cheers, Edi. PS: Please, if possible, continue this conversation on the mailing list. Thanks.

1 0

[cl-ppcre-devel] defpatt updated
by Klaus Harbo 11 Jun '04

11 Jun '04

I have just posted version v0.2.1 of 'defpatt' - a mechanism for defining and using regular expression abstractions with CL-PPCRE. The update fixes a bothersome error affilicting certain types of defpatt expressions. I strongly recommend anyone looking at or using defpatt. 'defpatt' can be downloaded from http://www.harbo.net/downloads. best regards, -Klaus.

1 0

[cl-ppcre-devel] defpatt
by Klaus Harbo 02 Jun '04

02 Jun '04

Working with cl-ppcre, I have found that I increasingly use the s-expr representation rather than the traditional string representation with its infix operators. To make it easier to work with the s-expressions, I've developed 'defpatt' - a package which implements a notation for defininig and referring to regular expressions in terms of cl-ppcre s-expressions. I thought it might interest the readers of this list. The package can be downloaded from http://www.harbo.net/downloads/defpatt-0.2.tar.gz . Suggestions, comments, improvements are welcome. best regards, -Klaus. ------ defpatt examples (from defpatt.lisp): ------ #| EXAMPLES ; If you want to try the examples, be sure to evaluate the ; expression below first - otherwise the other ones won't work. > (defpatt:defpatt-set-default-macro-char) ; Defines #\¤ as macro character => T > (cl-ppcre:all-matches-as-strings ¤(alt "a" "c" "f") "abcdefghi") ; Note: Equivalent to "a|c|f" => ("a" "c" "f") ; That's all very well, but doesn't buy us very much. ; However `defpatt' (as per cl-ppcre's sexpr-based ; representation of REs) enables us to both document ; the patterns much better by letting us insert comments ; into REs... > (cl-ppcre:scan-to-strings ¤(seq digit+ ; used space ws+ digit+ ; available space ws+ digit+ ; remaining space ) "123 4567 7887") ; Note: `ws+' and `digit+' are defined above, in `defpatt-initialize'. => "123 4567 7887", #() ; ...as well as lets us capture data in a structured fashion... > (cl-ppcre:register-groups-bind (used avail remain) (¤(seq (reg digit+) ; used space ws+ (reg digit+) ; available space ws+ (reg digit+) ; remaining space ) "123 4567 7887") (mapcar #'parse-integer (list used avail remain))) ; Note: `(reg ...)' creates a register binding => (123 4567 7887) ; ...but also lets us _FIRST_ define and document the abstraction... > (defpatt match-nums () ¤(seq (reg digit+) ; used space ws+ (reg digit+) ; available space ws+ (reg digit+) ; remaining space )) => MATCH-NUMS ; ...and _THEN_ use it... > (cl-ppcre:register-groups-bind (used avail remain) (¤match-nums "123 4567 7887") (mapcar #'parse-integer (list used avail remain))) => (123 4567 7887) ; which is a lot more easily understood, as I am sure you will ; agree. > (cl-ppcre:scan-to-strings ¤(upto "efg") "abcdefghi") => "abcd", #() > (cl-ppcre:scan-to-strings ¤(upto+ "efg") "abcdefghi") => "abcdefg", #() ; To see the raw cl-ppcre expansion of a `defpatt' expression, ; simply enter it: > ¤(seq (reg digit+) ; used space ws+ (reg digit+) ; available space ws+ (reg digit+) ; remaining space ) => (:SEQUENCE (:REGISTER (:GREEDY-REPETITION 1 NIL (:CHAR-CLASS (:RANGE #\0 #\9)))) (:GREEDY-REPETITION 1 NIL :WHITESPACE-CHAR-CLASS) (:REGISTER (:GREEDY-REPETITION 1 NIL (:CHAR-CLASS (:RANGE #\0 #\9)))) (:GREEDY-REPETITION 1 NIL :WHITESPACE-CHAR-CLASS) (:REGISTER (:GREEDY-REPETITION 1 NIL (:CHAR-CLASS (:RANGE #\0 #\9))))) ; To see _HOW_ `defpatt' expands an expression use `macroexpand': > (macroexpand-1 '¤(seq (reg digit+) ; used space ws+ (reg digit+) ; available space ws+ (reg digit+) ; remaining space )) => (LABELS ((++ (PATT) (REP PATT 1 NIL)) (UPTO (PATT) `(:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING (:NEGATIVE-LOOKAHEAD ,PATT))) :EVERYTHING)) (?? (PATT) (REP PATT 0 1)) (UPTO+ (PATT) `(:SEQUENCE ,(UPTO PATT) ,PATT)) (ALT (&REST ARGS) `(:ALTERNATION ,@ARGS)) (** (PATT) (REP PATT 0 NIL)) (SEQ (&REST ARGS) `(:SEQUENCE ,@ARGS)) (REG (&REST ARGS) `(:REGISTER ,@ARGS)) (REP (PATT &OPTIONAL (MIN 0) (MAX NIL)) `(:GREEDY-REPETITION ,MIN ,MAX ,PATT))) (SYMBOL-MACROLET ((WS+ '(:GREEDY-REPETITION 1 NIL :WHITESPACE-CHAR-CLASS)) (WS* '(:GREEDY-REPETITION 0 NIL :WHITESPACE-CHAR-CLASS)) (DIGIT '(:CHAR-CLASS (:RANGE #\0 #\9))) (DIGIT+ (++ DIGIT)) (MATCH-NUMS (DEFPATT-PATTERN (SEQ (REG DIGIT+) WS+ (REG DIGIT+) WS+ (REG DIGIT+)))) (DIGIT* (** DIGIT))) (SEQ (REG DIGIT+) WS+ (REG DIGIT+) WS+ (REG DIGIT+)))) ; `upto' and `upto+' are good examples of how having an abstraction ; mechanism helps keep maintainable and understandable REs. See ; their definitions above. |#

1 0

[cl-ppcre-devel] Re: Programming Problem - Need your CL-PPCRE Experience
by Edi Weitz 19 May '04

19 May '04

Hi Thomas! Sorry for the delay. On Sat, 15 May 2004 21:52:25 +0200, Thomas Schilling <tjs_ng(a)yahoo.de> wrote: > I'm currently writing a pattern matcher for trees. This is > (hopefully) going to become a tool for easily extracting information > from tree-structured documents, specifically XML/HTML files. (Yes, I > know of SAX and XSLT and XPath but I think this can become more > powerful--I plan to allow embeddable code. Nevertheless it could be > added to e.g. CL-XML.) > > In fact it's a regular expression matcher that two-dimensionally > matches on lists. (car is considered to be the node's name, > i.e. tag-name, and the cdr it's children). So that's the reason why > I'm asking you. > > So here's my problem: > I, well, stole some ideas from you. Because we need heavy > backtracking and looking ahead I implemented it (just like you, I > think) largely via closures, i.e. each rule is matched via a > function, and the rules are linked via a next-rule (function-) > variable that is put inside each closure. So e.g. the repetion > function can check by itself if the rest of the pattern matches when > the number of repetitions is tried. This works great except in the > folloing case: > > When I have (in perl-notation) "abaa" =~ /^(a|ab)*a/ the match > failes. That's because the alternative which has only the > information of the two choices "a" and "ab" but no successor > information (because it can have two--the alternative itself or the > "a" after the repetition) succeeds when matching the first > alternative and never tries to match the second, although then the > repetition could match. > > I currently have no real solution to this problem. How did you solve > this? I looked it up in your code but I couldn't find it (maybe it's > masked by the many optimizations?). > > I would be very thankful if you could help me. > > Ok, so here's the code: http://www.inf.tu-dresden.de/~s3815210/lisp > tree-match.lisp. You can simply C-c C-k it. and then C-x C-e the > (test-all) at the end of the file. It should print the one failing > test. The interesting functions are probably OR-M and > GREEDY-REPEAT-M. The problem is mentioned in line 286 in the > PARSE-PATTERN function. I only looked briefly at your code 'cause I'm busy with other things but I /think/ the problem is in OR-M: (defun or-m (options next-rule) (declare (type function next-rule)) (matcher-fn (do ((r options (cdr r))) ((null r) nil) (multiple-value-bind (pos inp) (funcall (the function (car r)) input position) (when pos (multiple-value-bind (pos2 inp2) (funcall next-rule inp pos) (when pos2 (return (values position inp2))))))))) Here you try each function in OPTIONS in turn and if one of them succeeds you immediately call NEXT-RULE so there's no chance for backtracking. What you have to do is to construct a new function for each element in OPTIONS which itself knows how to proceed (namely via NEXT-RULE) and try these new functions instead of the ones in OPTIONS. FWIW, here's the relevant code from CL-PPCRE: (defmethod create-matcher-aux ((alternation alternation) next-fn) ;; first create closures for all alternations of ALTERNATION (let ((all-matchers (mapcar #'(lambda (choice) (create-matcher-aux choice next-fn)) (choices alternation)))) ;; now create a closure which checks if one of the closures ;; created above can succeed (lambda (start-pos) (declare (type fixnum start-pos)) (loop for matcher in all-matchers thereis (funcall (the function matcher) start-pos))))) I don't think this is masked by too many optimizations... :) The important part is the creation of ALL-MATCHERS from (CHOICES ALTERNATION) (which would be your OPTIONS). Does that help? This is just a wild guess from looking at your code for a couple of minutes. If that doesn't help feel free to ask me again. > Please ask me if you have any questions. > > If you think of a place to which should post this please tell me. I've sent a copy to the cl-ppcre-devel mailing list. We should take further discussion there so they'll be archived (if you don't mind). HTH, Edi.

1 0

[cl-ppcre-devel] New release 0.7.7
by Edi Weitz 19 May '04

19 May '04

Hi! A new release is available from <http://weitz.de/files/cl-ppcre.tgz>. Here's the relevant part from the changelog: Version 0.7.7 2004-05-19 Fixed bug in NEWLINE-SKIPPER (caught by RegexCoach user Thomas-Paz Hartman) Added doc strings for PPCRE-SYNTAX-ERROR and friends (after playing with slime-apropos-package) Added hyperdoc support Have fun, Edi.

1 0