I have written a regular expression package in Common Lisp.
It is modeled in code and design after Perl's regex flavor and the libraries
written by Henry Spencer in 1986 and 1999.
It is in early Beta and needs much testing, so please do not set your hopes
too high yet. It has been developed and tested with CLISP version 2.27.
Limited testing has been performed with CMU CL version 18c, SBCL version 0.6.12
and LispWorks version 4.1.20.
The package can be found in source, zip and Gzip format at
http://www2.worldpbx.com/regexp/
I have release the package now to get as much, hopefully positive, feed back
as possible.
There are several global variables that allow parts the packages behavior
to be configured. This is to be as compatible as possible with other regex
libraries and to provide the behavior each individual user prefers.
Please be awar that the character #\~ (tilde) character is used for the
quote character in place of the #\\ (backslash) character. I did this
after finding that the backslash character is special in some Lisp's, and
the idea of typing two backslashes in one Lisp and only one backslash
in another bothered me. I plan to make the quote character user configurable
in the future but have not gotten to it yet.
·······@worldpbx.com (Lorance Stinson) writes:
> I have written a regular expression package in Common Lisp.
> It is modeled in code and design after Perl's regex flavor and the libraries
> written by Henry Spencer in 1986 and 1999.
This is absolutely amazing. I've spent time here and there over the
past week doing the same thing. [1] I was 80% done with the
documentation and 70% done with the implementation. I was going to
release it after I'd finished debugging it and had polished it all,
but I guess I'll finish it and just hang on to it for my own use now.
I can use it in my own code and sneer with disdain at those who use
anything else! ;)
Gabe Garza
[1] Kind of the same thing. My operators expand the regular expression
into Lisp (a big gnarly tagbody) at eval-time if possible, or expand
it into a form that gets COMPILE'd if it must be created at run time.
I wanted it to make extremeley fast matches (it does) at the accepted
cost of taking a long time to compile the RE.
Gabe Garza <·······@ix.netcom.com> wrote in message news:<············@kynopolis.org>...
> ·······@worldpbx.com (Lorance Stinson) writes:
>
> > I have written a regular expression package in Common Lisp.
> > It is modeled in code and design after Perl's regex flavor and the libraries
> > written by Henry Spencer in 1986 and 1999.
>
> This is absolutely amazing. I've spent time here and there over the
> past week doing the same thing. [1] I was 80% done with the
> documentation and 70% done with the implementation. I was going to
> release it after I'd finished debugging it and had polished it all,
> but I guess I'll finish it and just hang on to it for my own use now.
> I can use it in my own code and sneer with disdain at those who use
> anything else! ;)
>
> Gabe Garza
>
> [1] Kind of the same thing. My operators expand the regular expression
> into Lisp (a big gnarly tagbody) at eval-time if possible, or expand
> it into a form that gets COMPILE'd if it must be created at run time.
> I wanted it to make extremeley fast matches (it does) at the accepted
> cost of taking a long time to compile the RE.
There is a package called nregex at (long URL)
http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/match/nregex/0.html
It also compiles the regular expression. It is very interesting but
not
completed. One of my first ideas was to compile the regex into code.
But I
quickly realized that it would take up a large amount of memory and
the code
would have to be very twisted. So I did what Henry Spencer did. It
turns out
that parsing a regex is rather easy (after days of frustration) but
executing
is is not. There are so many special considerations.
I would recommend finishing your package and releasing it anyways. You
have a different approach than mine, wich is good. I'm sure there will
be a
multitude of cases that your package will out-do mine since yours
compiles.
Interestingly I have yet to find a use for regular expressions in
Lisp.
I started with Perl so Lisp was a bit of a shock to me. I only wrote
the
my package to teach myself Lisp. I released it with only the hopes
that it
would be usefull.
·······@worldpbx.com (Lorance Stinson) writes:
> would have to be very twisted. So I did what Henry Spencer did. It
> turns out
> that parsing a regex is rather easy (after days of frustration) but
Looking over your code, I think you might be interested in META, which
is described at:
http://linux.rice.edu/~rahul/hbaker/Prag-Parse.html
It's basically a set of reader macros for writing recursive decent
parsers. Code is given in the paper, but you'll probably want to
alter it quite a bit--which is easy, because it's a simple idea (that's
*very* useful).
> Interestingly I have yet to find a use for regular expressions in
> Lisp.
I've frequently wanted them for manipulating simple input sets into
something easier to get into Lisp--it's just not an S-expression
friendly world out there. Stuff that I could use AWK or sed for, but
obviously portability would be lost. Plus they feel dirty.
> I started with Perl so Lisp was a bit of a shock to me.
Aaaah. Perl to Lisp shouldn't be as much a shock as a blessed relief. ;)
Gabe Garza
Gabe Garza <·······@ix.netcom.com> wrote in message news:<············@kynopolis.org>...
> Looking over your code, I think you might be interested in META, which
> is described at:
>
> http://linux.rice.edu/~rahul/hbaker/Prag-Parse.html
>
Thanks. I'll take a look at it.
> > I started with Perl so Lisp was a bit of a shock to me.
>
> Aaaah. Perl to Lisp shouldn't be as much a shock as a blessed relief. ;)
It was a shock at first. Now I prefere Lisp over Perl. There is much more
power, useability and readability to Lisp that there is to Perl.
* ·······@worldpbx.com (Lorance Stinson)
> Please be awar that the character #\~ (tilde) character is used for the
> quote character in place of the #\\ (backslash) character. I did this
> after finding that the backslash character is special in some Lisp's,
Yes, in Common Lisp \ is the escape character in string literals. However,
~ also has a special meaning when used in format strings. If you're going
to use string based regular expressions in the first place, I imagine you
may frequently want to use format to generate them, so you would have to
type two tildes in stead of two backslashes.
If you really want to break the tradition of using backslash (which i think
is a good idea after having struggled with regexps in emacs), I suggest you
choose something else. For instance, the ` (backquote) can be viewed as a
small backslash.
Erik
Erik Haugan <····@haugan.no> wrote in message news:<··············@kometknut.neitileu.no>...
> * ·······@worldpbx.com (Lorance Stinson)
> > Please be awar that the character #\~ (tilde) character is used for the
> > quote character in place of the #\\ (backslash) character. I did this
> > after finding that the backslash character is special in some Lisp's,
>
> Yes, in Common Lisp \ is the escape character in string literals. However,
> ~ also has a special meaning when used in format strings. If you're going
> to use string based regular expressions in the first place, I imagine you
> may frequently want to use format to generate them, so you would have to
> type two tildes in stead of two backslashes.
>
> If you really want to break the tradition of using backslash (which i think
> is a good idea after having struggled with regexps in emacs), I suggest you
> choose something else. For instance, the ` (backquote) can be viewed as a
> small backslash.
>
> Erik
The reason I chose the ~ is because it's used in format. I wanted to make it
easy and familiar at the same time. Like I said in the original post I will
be adding support for the user to change the quote character to what they
prefer. I will also add an operator to take an argument supplied to
compile-regexp and embed it into the regular expression. This would allow a
regular expression to be built from variables and/or functions. I will also
add an operator to call a function at execution to allow cutomization to
the regex engine. With those two additions using format will become,
hopefully, less of a concern.
One of my objectives to to allow each user to change the behavior of most
all parts of the package to match their favorite tool.
All in all you have an excelent point. And to my knowledge the ` (backquote)
character is not special anywhere. I will make a note in the documentation
to recommend it as a good alternative.
Thank you for your input.
Erik Haugan <····@haugan.no> writes:
> If you really want to break the tradition of using backslash (which i think
> is a good idea after having struggled with regexps in emacs), I suggest you
> choose something else. For instance, the ` (backquote) can be viewed as a
> small backslash.
FWIW, the MOO programming language uses % and it has a pretty good feel to it.
I have posted a new version with a few minor bug fixes. I have also added a
function to test the package (test-regexp) and sample test data
(found at the end of the file). The test function is how I found the bugs.
I any one find the package useful and/or cares to I would appreciate it if
you could send me test data of your own. Especially if it breaks something.
But please send me original data of your own creation. The last thing I want
it to get into a copyright issue.
The package can be found in source, zip and Gzip format at
http://www2.worldpbx.com/regexp/
If you wish to be notified by email when I post a new version please email
······@worldpbx.com and I will send you a short email.
Thank you all in advance for your input.
Lorance Stinson a �crit :
> I have written a regular expression package in Common Lisp.
> It is modeled in code and design after Perl's regex flavor and the libraries
> written by Henry Spencer in 1986 and 1999.
> It is in early Beta and needs much testing, so please do not set your hopes
> too high yet. It has been developed and tested with CLISP version 2.27.
> Limited testing has been performed with CMU CL version 18c, SBCL version 0.6.12
> and LispWorks version 4.1.20.
>
> The package can be found in source, zip and Gzip format at
> http://www2.worldpbx.com/regexp/
> I have release the package now to get as much, hopefully positive, feed back
> as possible.
As a first feed back, may I suggest to "compare" it with the OCaml regexp module,
because I think it the OCaml module has a good design, works prettywell and is
really efficient.
Iban.
I think it's great that there are *two* people who have the patience
to implement a regex package in CL (to understand how nasty regex's
are, you really do have to try implementing them ... yuck!), *and*
release them.
If having whatever regex syntax you come up with is important to you,
well, who am I to question -- after all, did I ever finish *my* regex
package? (answer: no, I got disgusted and started using bindings to
libc) But perhaps you should ask yourself: does the world really need
Yet Another Nonstandard Regular Expression Syntax?; or does the world
need a good, portable standards-conforming regular expression
implementation in CL? (AFAIK, POSIX is the only standard that
specifies regex's).
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) wrote in message news:<···············@apocalypse.OCF.Berkeley.EDU>...
> I think it's great that there are *two* people who have the patience
> to implement a regex package in CL (to understand how nasty regex's
> are, you really do have to try implementing them ... yuck!), *and*
> release them.
I only wrote it to teach myself Lisp. I love a challenge. Once I actually
started parsing them I gained a better understanding of them.
> If having whatever regex syntax you come up with is important to you,
> well, who am I to question -- after all, did I ever finish *my* regex
> package? (answer: no, I got disgusted and started using bindings to
> libc) But perhaps you should ask yourself: does the world really need
> Yet Another Nonstandard Regular Expression Syntax?; or does the world
> need a good, portable standards-conforming regular expression
> implementation in CL? (AFAIK, POSIX is the only standard that
> specifies regex's).
POSIX 1003.2 is the only standard I know of. Though I am far from POSIX
compliant. I am writing much of the package to allow the user to change
bahavior, like the quote character, to conform to what they expect. I aim
to comply with as much of the POSIX standard as I can. And allow the user
to change any of it to suite their wants and/or needs.
And I have no problem with some one taking my code and writting a more
standards compliant version. The license is liberal on purpose.
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> libc) But perhaps you should ask yourself: does the world really need
> Yet Another Nonstandard Regular Expression Syntax?; or does the world
> need a good, portable standards-conforming regular expression
> implementation in CL?
I dunno... I have to admit that, given my choice, I'd rather have
one of the s-expression based regexps, like the one Olin Shivers
was working on. Whenever I read POSIX regexps, my eyeballs screw
up in knots, I think something readable would be a relief.
Just my 0.02.
--
It would be difficult to construe Larry Wall, in article
this as a feature. <·····················@netlabs.com>
Alain Picard <·······@optushome.com.au> writes:
> ···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > libc) But perhaps you should ask yourself: does the world really need
> > Yet Another Nonstandard Regular Expression Syntax?; or does the world
> > need a good, portable standards-conforming regular expression
> > implementation in CL?
>
> I dunno... I have to admit that, given my choice, I'd rather have
> one of the s-expression based regexps, like the one Olin Shivers
> was working on. Whenever I read POSIX regexps, my eyeballs screw
> up in knots, I think something readable would be a relief.
I don't see any a priori reason why there can't be two layers. Either
you can make an s-expression version that compiles down to strings, or
a string version that compiles down to s-expressions. Which is the
lower-level layer should depend only on implementational pragmatics.
Alain Picard <·······@optushome.com.au> writes:
> ···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > libc) But perhaps you should ask yourself: does the world really need
> > Yet Another Nonstandard Regular Expression Syntax?; or does the world
> > need a good, portable standards-conforming regular expression
> > implementation in CL?
>
> I dunno... I have to admit that, given my choice, I'd rather have
> one of the s-expression based regexps, like the one Olin Shivers
> was working on. Whenever I read POSIX regexps, my eyeballs screw
> up in knots, I think something readable would be a relief.
I don't find POSIX regex's any less readable than any other (and Emacs
regex's are by far the ugliest I've seen), but it's probably what
you're used to. FWIW, though, I agree with you that I'd rather write
s-expression regex's, but I'd still want POSIX semantics. Y'know one
of the great things about lisp? It's great at adding s-expression
syntactic sugar. Before I swore off regular expressions to accomplish
substantial things, I had a package that translated an sexp regex
syntax into POSIX strings. It wasn't complete, but if anyone's
interested, I can dig it up. It makes things *soooo* much more
readable (if more verbose).
Now, I just use regex's where it's necessary in order to be a good
UNIX citizen.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
·······@worldpbx.com (Lorance Stinson) writes:
> ···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) wrote in message
> > > I dunno... I have to admit that, given my choice, I'd rather have
> > > one of the s-expression based regexps, like the one Olin Shivers
> > > was working on. Whenever I read POSIX regexps, my eyeballs screw
> > > up in knots, I think something readable would be a relief.
> >
> > I don't find POSIX regex's any less readable than any other (and Emacs
> > regex's are by far the ugliest I've seen), but it's probably what
> > you're used to. FWIW, though, I agree with you that I'd rather write
> > s-expression regex's, but I'd still want POSIX semantics. Y'know one
> > of the great things about lisp? It's great at adding s-expression
> > syntactic sugar. Before I swore off regular expressions to accomplish
> > substantial things, I had a package that translated an sexp regex
> > syntax into POSIX strings. It wasn't complete, but if anyone's
> > interested, I can dig it up. It makes things *soooo* much more
> > readable (if more verbose).
>
> I have modified compile-regexp to aknowledge a list as the source of
> a regexp. I have also started writting a special parser for
> s-expression's. I will complete it over the weekend. I partially
> completed it last night. The results are:
> "^.*$" => '(:BOL (:STAR :ANY) :EOL)
> "^(.*)$" => '(:BOL (:STAR (:CAPTURE :ANY)) :EOL)
> I am also useing different names for the same keyword. For example
> ~w (word bound) is :WORDBOUND and :WORD-BOUND. This allows for either
> brevity or clarity, wich ever is more important.
Cool. I was going to reccomend that you made the names longer, since
that would fit in with-common-lisp's-tendancy to make
long-but-clear-identifiers, but if you're supporting long and short
forms, that's probably even better.
The only thing is, I'd reccomend that you name your symbols after the
meaning of the line-noise, not what the line noise looks like: I
picked :zero-or-more in my system for where you used :star. Maybe
:>=0 would be a good (if ugly) short form?
> Love your sig!
Thanks. Unfortunately, even here, even in Oakland and San Francisco,
even the active, political labor unions are laying low on this one.
But maybe after an initial knee-jerk jingoistic reaction (which is
understandable enough when fire fighters are leading it, for
godsakes), maybe we can turn this into a political issue for the
working class, as a class.
(Plus, I'm a big fan of cute Sabo-Cats :)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
TB> I picked :zero-or-more in my system for where you used :star.
In regular language theory, the operator is called Kleisli's star.
TB> to understand how nasty regex's are, you really do have to try
TB> implementing them
That's nothing. Ever spent a trimester trying to get 200 undergrads
to implement regexps in C++?
(And then a week correcting their projects.)
Juliusz
Juliusz Chroboczek <···@pps.jussieu.fr> writes:
> TB> I picked :zero-or-more in my system for where you used :star.
>
> In regular language theory, the operator is called Kleisli's star.
I actually did know this, (well, Kleene's star, but it's the "star"
that's important), but I don't think it's particularly relevant.
Normal regex's do a fine job of symbolically representing a regex.
The goal of an sexp wrapper is to make it more readable/understandable
to the lisp programmer. Note that I'd call a summing function SUM,
not SIGMA :)
> That's nothing. Ever spent a trimester trying to get 200 undergrads
> to implement regexps in C++?
>
> (And then a week correcting their projects.)
(Shudder)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
* Juliusz Chroboczek <···@pps.jussieu.fr>
> In regular language theory, the operator is called Kleisli's star.
I only know it as the Kleene star. A web search tells me that Kleisli is
some sort of query language.
Erik
From: Michael Hudson
Subject: Re: New CL Regular Expression Package
Date:
Message-ID: <uvggv6d3u.fsf@python.net>
Erik Haugan <····@haugan.no> writes:
> * Juliusz Chroboczek <···@pps.jussieu.fr>
> > In regular language theory, the operator is called Kleisli's star.
>
> I only know it as the Kleene star. A web search tells me that Kleisli is
> some sort of query language.
The name Kleisli comes up in category theory (monads; some Haskell
programmers probably know it). I believe there is something called
the Kleisli star, but don't know what it is (it's not in Mac Lane...).
So Juliusz almost certainly meant Kleene, but it's not a totally
ridiculous slip.
Cheers,
M.
--
Hey, if I thought I was wrong, I'd change my mind. :)
-- Grant Edwards, comp.lang.python
>> In regular language theory, the operator is called Kleisli's star.
EH> I only know it as the Kleene star.
You're right of course. Kleisli is the name of a Category theorist
(and the name of a construction on Categories that I've been spending
too much time staring at).
Sorry for the thinko.
Juliusz
Lorance Stinson <·······@worldpbx.com> wrote:
+---------------
| I have modified compile-regexp to aknowledge a list as the source of
| a regexp. I have also started writting a special parser for
| s-expression's. I will complete it over the weekend. I partially
| completed it last night. The results are:
| "^.*$" => '(:BOL (:STAR :ANY) :EOL)
| "^(.*)$" => '(:BOL (:STAR (:CAPTURE :ANY)) :EOL)
+---------------
Also see <URL:http://www.cc.gatech.edu/fac/Olin.Shivers/sre.txt>
(and the interesting discussion of "100% and 80% solutions").
-Rob
-----
Rob Warnock, 30-3-510 <····@sgi.com>
SGI Network Engineering <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: ·········@sgi.com and ········@sgi.com aren't for humans ]
For your comparisons, also keep in view
http://www.cs.rice.edu/~dorai/pregexp/pregexp.html .
Captures all of Perl regexps (including lookahead and
-behind), and has an underlying s-exp notation.
--d
I have posted a new version. There a a few small bug fixes. I have also
added the package variable *quote-character*. This allows you to change
the quote character from ~ to what you prefer, % and ` have been good
recommendations.
I have also added the metacharacters ~v, ~V and ~F. These consume an
argument supplied to compile-regexp. ~v places the argument into the
regular expression in place of ~v. ~V does the same thing as ~v but
quotes any metacharacters found in the string. ~F stores a function
that is funcall'd at execution time with the string being matched and
the position in the string. The function is expected to return a new
position in the string for success or nil for failure. ~F is intended
to allow expansion of the package without changing it. All three of the
additions work but still need more testing.
The package can be found in source, zip and Gzip format at
http://www2.worldpbx.com/regexp/
I have posted a new release of regexp.lisp.
There are several small bug fixes and the addition of an
s-expression like syntax. This is used by supplying a list to
compile-regexp in place of a string. It is not completed yet
nor documented, but you can look through s-parse-regexp and
the test data at the end to get an idea. The keywords used
are based on those used in matcher available at
ftp.cs.cmu.edu/user/ai/lang/lisp/code/match/
I have used short and long names for the keywords. The long
names to be more Lisp-like and the short names for trying
small regexp's out quick. Once I complete the s-expression
like syntax I will add keywords that describe the action as
per the suggestion from Thomas Burdick. Everyone can then
choose which stays and which I eliminate.
The package can be found in source, zip and Gzip format at
http://www2.worldpbx.com/regexp/
--
Lorance Stinson <·······@worldpbx.com> http://www.worldpbx.com/