1 Aug
2020
1 Aug
'20
4:57 a.m.
I've always been intrigued with regexes. When I was first exposed to
them, I was mystified and lost in the greediness of matches. Now, I use
them regularly, but still have trouble using them. I think it is because
I don't really understand how they work.
My question for y'all has to do with early unix. I have a copy of
Thompson, K. (1968). Regular expression search algorithm. Communications
of the ACM, 11(6), 419-422. It is interesting as an example of
Thompson's thinking about regexes. In this paper, he presents a
non-backtracking, efficient, algorithm for converting a regex into an
IBM 7094 (whatever that is) program that can be run against text input
that generates matches. It's cool. It got me to thinking maybe the way
to understand the unix regex lies in a careful investigation into how it
is implemented (original thought, right?). So, here I am again to ask
your indulgence as the latecomer wannabe unix apprentice. My thought is
that ed is where it begins and might be a good starting point, but I'm
not sure - what say y'all?
I also have a copy of the O'Reilly Mastering Regular Expressions book,
but that's not really the kind of thing I'm talking about. My question
is more basic than how to use regexes practically. I would like to
understand them at a parsing level/state change level (not sure that's
the correct way to say it, but I'm really new to this kind of lingo).
When I'm done with my stepping through the source, I want to be able to
reason that this is why that search matched that text and not this text
and why the search was greedy, or not greedy because of this logic here...
If my question above isn't focused or on topic enough, here's an
alternative set to ruminate on and hopefully discuss:
1. What's the provenance of regex in unix (when did it appear, in what
form, etc)?
2. What are the 'best' implementations throughout unix (keep it pre 1980s)?
3. What are some of the milestones along the way (major changes, forks,
disagreements)?
4. Where, in the source, or in a paper, would you point someone to
wanting to better understand the mechanics of regex?
Thanks!
Will
--
GPG Fingerprint: 68F4 B3BD 1730 555A 4462 7D45 3EAA 5B6D A982 BAAF
1 Aug
1 Aug
6:01 a.m.
On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com> wrote:
I've always been intrigued with regexes. When I was first exposed to them, I was
mystified and lost in the greediness of matches. Now, I use them regularly, but still have
trouble using them. I think it is because I don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear, in what form, etc)?
2. What are the 'best' implementations throughout unix (keep it pre 1980s)?
3. What are some of the milestones along the way (major changes, forks, disagreements)?
4. Where, in the source, or in a paper, would you point someone to wanting to better
understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.]
6:36 a.m.
I think this link - https://swtch.com/~rsc/regexp/regexp1.html i- s the
best place to start. Superb exposition on the background, theory, and
implementation as well as a bit of history of how the industry lost its way
with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn
<will.senn(a)gmail.com> wrote:
I've always been intrigued with regexes. When I was first exposed to
them, I
was mystified and lost in the greediness of matches. Now, I use
them regularly, but still have trouble using them. I think it is because I
don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear, in what
form,
etc)?
2. What are the 'best' implementations
throughout unix (keep it pre
1980s)?
3. What are some of the milestones along the way
(major changes, forks,
disagreements)?
4. Where, in the source, or in a paper, would you
point someone to
wanting to better understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.] 
6:53 a.m.
Hear hear. And I think it should be possible to analyze regular expressions
to determine if "simple" (hence fast) regexps are adequate. "Fancy"
re's
are rare. At least from those of us where they couldn't be expressed.
On Fri, Jul 31, 2020 at 8:38 PM Rob Pike <robpike(a)gmail.com> wrote:
I think this link -
https://swtch.com/~rsc/regexp/regexp1.html i- s the
best place to start. Superb exposition on the background, theory, and
implementation as well as a bit of history of how the industry lost its way
with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn
<will.senn(a)gmail.com> wrote:
I've always been intrigued with regexes. When I was first exposed to
them, I
was mystified and lost in the greediness of matches. Now, I use
them regularly, but still have trouble using them. I think it is because I
don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear, in what
form,
etc)?
2. What are the 'best' implementations
throughout unix (keep it pre
1980s)?
3. What are some of the milestones along the way
(major changes, forks,
disagreements)?
4. Where, in the source, or in a paper, would you
point someone to
wanting to better understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.]
7:31 a.m.
I was trying to get Will to try simple stuff out himself from first principles (to get
started) but this is of course far better!
On Jul 31, 2020, at 5:36 PM, Rob Pike
<robpike(a)gmail.com> wrote:
I think this link - https://swtch.com/~rsc/regexp/regexp1.html
<https://swtch.com/~rsc/regexp/regexp1.html> i- s the best place to start. Superb
exposition on the background, theory, and implementation as well as a bit of history of
how the industry lost its way with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org
<mailto:bakul@iitbombay.org>> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com
<mailto:will.senn@gmail.com>> wrote:
I've always been intrigued with regexes. When I was first exposed to them, I was
mystified and lost in the greediness of matches. Now, I use them regularly, but still have
trouble using them. I think it is because I don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear, in what form, etc)?
2. What are the 'best' implementations throughout unix (keep it pre 1980s)?
3. What are some of the milestones along the way (major changes, forks, disagreements)?
4. Where, in the source, or in a paper, would you point someone to wanting to better
understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
<https://en.wikipedia.org/wiki/Thompson%27s_construction>
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.] 
7:39 a.m.
That link is a great read.
On Sat, Aug 01, 2020 at 10:36:48AM +1000, Rob Pike wrote:
I think this link -
https://swtch.com/~rsc/regexp/regexp1.html i- s the
best place to start. Superb exposition on the background, theory, and
implementation as well as a bit of history of how the industry lost its way
with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org> wrote:
> On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com> wrote:
> >
> > I've always been intrigued with regexes. When I was first exposed to
> them, I was mystified and lost in the greediness of matches. Now, I use
> them regularly, but still have trouble using them. I think it is because I
> don't really understand how they work.
> > ...
> > 1. What's the provenance of regex in unix (when did it appear, in what
> form, etc)?
> > 2. What are the 'best' implementations throughout unix (keep it pre
> 1980s)?
> > 3. What are some of the milestones along the way (major changes, forks,
> disagreements)?
> > 4. Where, in the source, or in a paper, would you point someone to
> wanting to better understand the mechanics of regex?
>
> Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
>
> [I learned about regular expressions in an automata theory class,
> before I knew anything about Unix. What helped me was learning
> about finite state machines. You won't need more than paper and
> pencil to construct one. Reading source code would make more
> sense once you grasp how to construct a FSM corresponding to a RE.]
--
---
Larry McVoy lm at mcvoy.com http://www.mcvoy.com/lm
8:33 a.m.
Yes, I googled it per Clem's suggestion and wound up on that exact link
after wandering around admiring the scenery. I envy the more
mathematically inclined among us their view of matters technical. This
piece, being in C and having step by step articulation of the diagrams,
is better for me than the more formal wikipedia article, although, when
I get enough background, that looks like it'll be good, too.
Thanks Rob, Clem and Bakul.
Will
On 7/31/20 7:36 PM, Rob Pike wrote:
I think this link -
https://swtch.com/~rsc/regexp/regexp1.html i- s
the best place to start. Superb exposition on the background, theory,
and implementation as well as a bit of history of how the industry
lost its way with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org
<mailto:bakul@iitbombay.org>> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com
<mailto:will.senn@gmail.com>> wrote:
--
GPG Fingerprint: 68F4 B3BD 1730 555A 4462 7D45 3EAA 5B6D A982 BAAF
I've always been intrigued with regexes. When I was first
exposed to
them, I was mystified and lost in the greediness of
matches. Now, I use them regularly, but still have trouble using
them. I think it is because I don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear,
in what
form, etc)?
2. What are the 'best' implementations
throughout unix (keep it
pre 1980s)?
3. What are some of the milestones along the way
(major changes,
forks, disagreements)?
4. Where, in the source, or in a paper, would you
point someone
to wanting to better understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.]
8:50 a.m.
You might want to pick up a used copy of this book, if only as an occasional resource:
https://www.amazon.com/Mastering-Regular-Expressions-Jeffrey-Friedl/dp/0596…
-r
9:01 a.m.
I was a fan of this:
http://www.cse.yorku.ca/~oz/regex.bun
my employees moved me to PCRE at some point but OZ has a talent for writing
really small implementations of useful stuff. Very early Unix like.
On Fri, Jul 31, 2020 at 07:50:57PM -0700, Rich Morin wrote:
You might want to pick up a used copy of this book, if
only as an occasional resource:
https://www.amazon.com/Mastering-Regular-Expressions-Jeffrey-Friedl/dp/0596…
-r
--
---
Larry McVoy lm at mcvoy.com http://www.mcvoy.com/lm
9:07 a.m.
Oh, and one good google over another, I also found this:
https://www.drdobbs.com/architecture-and-design/regular-expressions/1844109…
Which is also great and simple to follow :).
Will
On 7/31/20 7:36 PM, Rob Pike wrote:
I think this link -
https://swtch.com/~rsc/regexp/regexp1.html i- s
the best place to start. Superb exposition on the background, theory,
and implementation as well as a bit of history of how the industry
lost its way with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org
<mailto:bakul@iitbombay.org>> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com
<mailto:will.senn@gmail.com>> wrote:
--
GPG Fingerprint: 68F4 B3BD 1730 555A 4462 7D45 3EAA 5B6D A982 BAAF
I've always been intrigued with regexes. When I was first
exposed to
them, I was mystified and lost in the greediness of
matches. Now, I use them regularly, but still have trouble using
them. I think it is because I don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear,
in what
form, etc)?
2. What are the 'best' implementations
throughout unix (keep it
pre 1980s)?
3. What are some of the milestones along the way
(major changes,
forks, disagreements)?
4. Where, in the source, or in a paper, would you
point someone
to wanting to better understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.]
10:31 a.m.
I have a 30k+ character regex that I used to parse US street addresses from a single line
of input into component pieces. That’s the largest ( and yes it was crazy... but it just
grew and grew...and made sense to me as I decomposed the problem ). That’s the largest
one I ever saw.... and it was the fastest way I could solve the problem.. both mentally
and processing wise.
( there was some post processing to deal with soundex matching and data base matching of
the pieces to confirm the right answer. But it solved the problem with 95%+ accuracy...
that I got into the high 99%’s with the post processing. )
So that’s at least an example of an arbitrary problem that was solved with regex.
Earl
Sent from my iPhone
On Jul 31, 2020, at 11:08 PM, Will Senn
<will.senn(a)gmail.com> wrote:
Oh, and one good google over another, I also found this:
https://www.drdobbs.com/architecture-and-design/regular-expressions/1844109…
Which is also great and simple to follow :).
Will
On 7/31/20 7:36 PM, Rob Pike wrote:
I think this link - https://swtch.com/~rsc/regexp/regexp1.html i- s the best place to
start. Superb exposition on the background, theory, and implementation as well as a bit of
history of how the industry lost its way with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org> wrote:
> On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com> wrote:
> >
> > I've always been intrigued with regexes. When I was first exposed to them,
I was mystified and lost in the greediness of matches. Now, I use them regularly, but
still have trouble using them. I think it is because I don't really understand how
they work.
> > ...
> > 1. What's the provenance of regex in unix (when did it appear, in what
form, etc)?
> > 2. What are the 'best' implementations throughout unix (keep it pre
1980s)?
> > 3. What are some of the milestones along the way (major changes, forks,
disagreements)?
> > 4. Where, in the source, or in a paper, would you point someone to wanting to
better understand the mechanics of regex?
>
> Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
>
> [I learned about regular expressions in an automata theory class,
> before I knew anything about Unix. What helped me was learning
> about finite state machines. You won't need more than paper and
> pencil to construct one. Reading source code would make more
> sense once you grasp how to construct a FSM corresponding to a RE.]
--
GPG Fingerprint: 68F4 B3BD 1730 555A 4462 7D45 3EAA 5B6D A982 BAAF 
10:53 a.m.
kernighan did this one at a talk at udel in 1976: find all the words
in the dictionary that you can see on a calculator looking at it
upside down.
On Fri, Jul 31, 2020 at 9:32 PM Earl Baugh <earl.baugh(a)gmail.com> wrote:
I have a 30k+ character regex that I used to parse US street addresses from a single line
of input into component pieces. That’s the largest ( and yes it was crazy... but it just
grew and grew...and made sense to me as I decomposed the problem ). That’s the largest
one I ever saw.... and it was the fastest way I could solve the problem.. both mentally
and processing wise.
( there was some post processing to deal with soundex matching and data base matching of
the pieces to confirm the right answer. But it solved the problem with 95%+ accuracy...
that I got into the high 99%’s with the post processing. )
So that’s at least an example of an arbitrary problem that was solved with regex.
Earl
Sent from my iPhone
On Jul 31, 2020, at 11:08 PM, Will Senn <will.senn(a)gmail.com> wrote:
Oh, and one good google over another, I also found this:
https://www.drdobbs.com/architecture-and-design/regular-expressions/1844109…
Which is also great and simple to follow :).
Will
On 7/31/20 7:36 PM, Rob Pike wrote:
I think this link - https://swtch.com/~rsc/regexp/regexp1.html i- s the best place to
start. Superb exposition on the background, theory, and implementation as well as a bit of
history of how the industry lost its way with regular expressions.
Regular expressions are beautiful, simple, and widely misunderstood.
-rob
On Sat, Aug 1, 2020 at 10:03 AM Bakul Shah <bakul(a)iitbombay.org> wrote:
On Jul 31, 2020, at 3:57 PM, Will Senn <will.senn(a)gmail.com> wrote:
--
GPG Fingerprint: 68F4 B3BD 1730 555A 4462 7D45 3EAA 5B6D A982 BAAF
I've always been intrigued with regexes. When I was first exposed to them, I was
mystified and lost in the greediness of matches. Now, I use them regularly, but still have
trouble using them. I think it is because I don't really understand how they work.
...
1. What's the provenance of regex in unix (when did it appear, in what form, etc)?
2. What are the 'best' implementations throughout unix (keep it pre 1980s)?
3. What are some of the milestones along the way (major changes, forks, disagreements)?
4. Where, in the source, or in a paper, would you point someone to wanting to better
understand the mechanics of regex?
Start here: https://en.wikipedia.org/wiki/Thompson%27s_construction
[I learned about regular expressions in an automata theory class,
before I knew anything about Unix. What helped me was learning
about finite state machines. You won't need more than paper and
pencil to construct one. Reading source code would make more
sense once you grasp how to construct a FSM corresponding to a RE.] 
11:48 a.m.
during the mid 80s, i was preparing one of the first invited talks for USENIX on the
subject of regular expressions.
i had concocted a massive RE that matched all the known spellings of saddam hussein. (it
was complicated,
and there were many different romanizations active at the time.)
dennis ritchie wandered into the unix room and asked what it was and then immediately
applied it to our
somewhat newish AP news wire feed. it matched two new spellings!!
7:31 p.m.
during the mid 80s, i was preparing one of the first
invited talks for
USENIX on the subject of regular expressions.
i had concocted a massive RE that matched all the known spellings of
saddam hussein. (it was complicated,
I wonder if that was the inspiration for the Qaddafi torture test; see
http://sources.vsta.org/comp.sources.unix/volume9/fastgrep/part01 (June 87)
The first time I saw "p[-1]" was looking at some regexp source. It
blew/expanded my mind.
7:43 p.m.
i apologise.
i was in fact referring to the qaddafi torture test (another victim of my stroke).
thanks to rich for catching that slip.
On Aug 1, 2020, at 6:31 AM, Richard Salz
<rich.salz(a)gmail.com> wrote:
during the mid 80s, i was preparing one of the first invited talks for USENIX on the
subject of regular expressions.
i had concocted a massive RE that matched all the known spellings of saddam hussein. (it
was complicated,
I wonder if that was the inspiration for the Qaddafi torture test; see
http://sources.vsta.org/comp.sources.unix/volume9/fastgrep/part01
<http://sources.vsta.org/comp.sources.unix/volume9/fastgrep/part01> (June 87)
The first time I saw "p[-1]" was looking at some regexp source. It
blew/expanded my mind.
2 Aug
2 Aug
6:45 a.m.
On Sat, 1 Aug 2020 at 02:38, Andrew Hume <andrew(a)humeweb.com> wrote:
during the mid 80s, i was preparing one of the first invited talks for
USENIX on the subject of regular expressions.
i had concocted a massive RE that matched all the known spellings of
saddam hussein. (it was complicated,
and there were many different romanizations active at the time.)
dennis ritchie wandered into the unix room and asked what it was and then
immediately applied it to our
somewhat newish AP news wire feed. it matched two new spellings!!
I recalled that one being about Khadaffi, of Libya, and there being a
punchline involving one of the names being
"squid-breath."
--
When confronted by a difficult problem, solve it by reducing it to the
question, "How would the Lone Ranger handle this?"
9 Aug
9 Aug
7 a.m.
On Fri, 31 Jul 2020, Andrew Hume wrote:
i had concocted a massive RE that matched all the
known spellings of
saddam hussein. (it was complicated, and there were many different
romanizations active at the time.)
Another neat test was to run it against all the variations of "Muammar
Gaddafi" and its various Anglicised spellings.
-- Dave
7:15 a.m.
Dave Horsfall writes about complex regular expressions:
> ... a test was to run it against all the
variations of "Muammar
> Gaddafi" and its various Anglicised spellings.
The name "Chebyshev" is well known in numerical computation in
mathematics, science, and engineering. This Web site lists 207
variants in its transliteration from the Cyrillic alphabet to the
Roman one:
https://mathreader.livejournal.com/9239.html
The MathSciNet and zbMATH databases each record more than 4300
publications with "Chebyshev" in their titles. Alas, no online
publication database that I know of permits regular expressions in
searches, so finding publications that use the 200+ variants would be
rather difficult.
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- University of Utah FAX: +1 801 581 4148 -
- Department of Mathematics, 110 LCB Internet e-mail: beebe(a)math.utah.edu -
- 155 S 1400 E RM 233 beebe(a)acm.org beebe(a)computer.org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------
10 Aug
10 Aug
5:53 a.m.
On Sat, 8 Aug 2020, Nelson H. F. Beebe wrote:
The name "Chebyshev" is well known in
numerical computation in
mathematics, science, and engineering. This Web site lists 207 variants
in its transliteration from the Cyrillic alphabet to the Roman one:
https://mathreader.livejournal.com/9239.html
Interesting; I was taught it was "Chebychev", which as second ranking
doesn't even come close to "Chebyshev"...
Possibly a cultural thing; I went to an Australian university (UNSW).
-- Dave
7:38 a.m.
On Sun, Aug 9, 2020 at 7:53 PM Dave Horsfall <dave(a)horsfall.org> wrote:
Interesting; I was taught it was "Chebychev", which as second ranking
doesn't even come close to
"Chebyshev"...
"Chebychev" is downright bizarre. The first "Ch" is as in English
"Chebyshev", the second is as in French "Tchebychev". The other
variants
are mostly explicable: for example, in German it's "Tschebyschew".
The final vowel is written "e" but pronounced "o" in Russian, and can
come
out either way in transliteration. Likewise, the final "v" is pronounced
"f", and can be written "v" or "ff" in transliteration.
Tolstoy was
affected by this too: his first name is usually given as either "Leo"
(which is what it means) or "Lev" nowadays, but in the 19C it was usually
spelled "Lyoff" (one syllable), which is how it's pronounced.
John Cowan http://vrici.lojban.org/~cowan cowan(a)ccil.org
You are a child of the universe no less than the trees and all other acyclic
graphs; you have a right to be here. --DeXiderata by Sean McGrath
1594
days inactive
1604
days old
19 comments
14 participants
participants (14)
-
Andrew Hume -
Bakul Shah -
Christopher Browne -
Dave Horsfall -
Earl Baugh -
John Cowan -
John P. Linderman -
Larry McVoy -
Nelson H. F. Beebe -
Rich Morin -
Richard Salz -
Rob Pike -
ron minnich -
Will Senn