cstjnodLaboratory notebook

Technical memorandum

File
TM-26-1016
From
Charlie O'Donoghue
Date
Reading
8 min
Subject
Programming languages · Raku · Perl

How regex learned to read

Every strange symbol in a regular expression has a date and an author. Read in order, from a 1951 maths memo to a Raku grammar, the line noise turns into layers of history.

I love regular expressions, and I have never been able to read one. I can write \d+(?:\.\d+)? and it works, but if you ask me why a question mark sits next to a colon inside a bracket, I have nothing. It looks like line noise.

It isn’t. Every symbol in that pattern was added by a particular person, in a particular year, for a particular reason, and most of the strangeness is old decisions that could not be undone. Read in the order they were laid down, the symbols stop being noise and start being layers.

So here is one small job, done in each era’s syntax. My charger keeps a log like this:

2026-10-12 07:40 plugged in
2026-10-12 08:55 charged 9 kWh
2026-10-13 18:05 charged 14.2 kWh

The job is to pull out the energy readings. Every example below was run for real on this file, with the output pasted as it came back.

Where the symbols came from. Each era kept what it inherited and added a few of its own.

1951: a star on paper

The story starts with neurons, not text. In 1943 Warren McCulloch and Walter Pitts had described the brain as a net of on-off cells. In 1951, at RAND, the logician Stephen Kleene asked which patterns of input such a net could recognise. His answer was a class he called regular events, built from three operations: E or F, E and F in sequence, and E repeated.

He wrote the repetition as a star, which is why it is still called the Kleene star. In his memo, though, the star joins two things: E*F means any number of Es followed by one F. He explains that he did not use a lone E*, because zero repetitions would be an event lasting no time at all. To say “one or more Es” he wrote E*E. That is the plus sign, decades before it got a symbol of its own.

There is nothing to run here, because it is maths. A digit is D=0∨1∨⋯∨9D = 0 \lor 1 \lor \cdots \lor 9, and a reading of one or more digits is D∗DD * D. The memo was published in 1956 in Automata Studies, edited by Claude Shannon and John McCarthy.

1968: the star gets a keyboard

Ken Thompson put Kleene’s notation into QED, a text editor on MIT’s CTSS time-sharing system. His paper in Communications of the ACM uses a(b|c)*d as its example: | for or, parentheses for grouping, and the star now on its own, after the thing it repeats. Each pattern was compiled on the spot into IBM 7094 machine code, which then ran over the text.

That notation still runs today, because grep -E reads it unchanged. There are no character classes yet, so a digit is ten alternatives:

$ grep -Eo '(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* kWh' charge.log
9 kWh
2 kWh

Nearly. Nothing in the pattern mentions a dot, so it found the 2 at the end of 14.2 and stopped there.

1971: ed, and the symbols that look like noise

When Thompson wrote ed for Unix he went the other way. Dennis Ritchie later described it as a radical simplification of QED’s regular expressions: the star stayed, but alternation and parentheses went. The ed manual of November 1971 lists the whole language in eight short rules, and here is most of the line noise, arriving in one go:

  • ^ matches the start of a line, $ the end.
  • . matches any character.
  • [...] matches any one character in the brackets, and [^...] any character not in them.
  • \ before a special character takes its meaning away.

Why so terse? ed was made for paper teletypes like the Model 33, which printed about ten characters a second, and ed said as little as it could. Its one error message was ?. In that world a one-character operator was a kindness. ed’s own addresses already used . for the current line and $ for the last one.

The command to print every line matching a regular expression was g/re/p, global, regular expression, print. In 1973 Thompson, at Bell Labs, pulled it out into its own program, and that is where the name grep comes from. Here is ed, with only what it had in 1971:

$ ed -s charge.log
g/[0123456789][.0123456789]* kWh/p
2026-10-12 08:55 charged 9 kWh
2026-10-13 18:05 charged 14.2 kWh
q

Two things to notice. There were no ranges yet, so all ten digits are typed out. And inside square brackets . is just a dot. With no way to say “optional”, the best you can do is “a digit, then any digits or dots”, which would also accept 1.2.3.

By 1979 ed had ranges like [0-9], and grouping, but grouping had to be written \( and \). A bare parenthesis had always matched a parenthesis, and old patterns had to keep working, so the new meaning got a backslash. That is why sed and plain grep still write groups that way:

$ sed -n 's/.* \([0-9][0-9.]*\) kWh/\1/p' charge.log
9
14.2

1979: egrep brings the rest back

Seventh Edition Unix shipped a new tool, Alfred Aho’s egrep, for full regular expressions. It added + for one or more and ? for zero or one, and brought back | and plain parentheses. Being a new program, it had no old patterns to protect, so its parentheses needed no backslash.

That split is still with us. In 1992 the POSIX standard wrote the two dialects down as basic and extended regular expressions, and egrep lives on as grep -E:

$ grep -Eo '[0-9]+(\.[0-9]+)? kWh' charge.log
9 kWh
14.2 kWh

This is the first version that says what I mean: digits, then optionally a dot and more digits. The \. is ed’s backslash, still taking the meaning away from a dot.

1987 to 1997: Perl moves in

Larry Wall released Perl on 18 December 1987, and made matching an operator in the language rather than a separate program you pipe through. Perl 1’s manual says its patterns are like egrep’s, plus \w for a word character and \b for a word boundary. Perl 2, in June 1988, swapped in Henry Spencer’s regex library (a free rewrite of the Unix routines he posted to Usenet in January 1986) and added \d for a digit and \s for a space. A backslash before a letter now adds a meaning, and the letter is its initial.

Perl 5, in October 1994, added the rest of what we use. A ? after a quantifier makes it lazy, so *? takes as little as it can. (?:...) groups without capturing, and (?=...) looks ahead without consuming anything. And /x lets you space a pattern out.

Why the ugly (?? Because, as the Perl 5 manual points out, it had been a syntax error in Perl 4. A sequence that meant nothing could be given new meanings without breaking a single old pattern, the same trick as ed’s \(, applied again. The manual adds, half joking, that a question mark should also make you stop and question what is going on.

$ perl -nle 'print $& if /\d+(?:\.\d+)?(?=\s*kWh)/' charge.log
9
14.2
One pattern, six decades. Teal says which character, orange says how many, amber is structure.

With /x the same pattern can breathe, and it still runs:

$ perl -nle 'print $& if / \d+ (?: \. \d+ )? (?= \s* kWh ) /x' charge.log
9
14.2

In 1997 Philip Hazel wrote PCRE, Perl Compatible Regular Expressions, for his Exim mail server. It became the library PHP, Apache and many others use, and it carried Perl’s dialect nearly everywhere. When people say “regex” today, they usually mean Perl 5’s.

An aside: why the old way was fast

Thompson’s 1968 method tracked every place the match could be at once, so it read each character of the text exactly once. Spencer’s library, and Perl after it, instead try one path and back up when it fails. Backing up is what makes extras like lookahead easy, but some patterns force it to try a huge number of paths. In 2007 Russ Cox showed a pattern on a 29-character string that took Perl over sixty seconds, against microseconds for Thompson’s approach.

2002 to 2015: Raku makes it read

Then Wall turned on his own work. In Apocalypse 5, in June 2002, he wrote that “regular expression culture is a mess, and I share some of the blame”. He redesigned it from scratch for Perl 6, the language now called Raku:

  • Whitespace in a pattern is for layout, as if /x were always on.
  • Letters, digits and underscores match themselves. Anything else that should match itself is quoted or escaped, so '.' is a dot.
  • [...] groups without capturing. The (?: goes.
  • <name> calls another named rule, and <?before ...> is lookahead.
  • {...} runs code, and ** 4 means exactly four times.

Here is the same job:

for 'charge.log'.IO.lines {
    say ~$/ if / \d+ [ '.' \d+ ]? <?before \s* kWh> /;
}
$ raku rx.raku
9
14.2

The bigger change is what named rules add up to. Put them together and you get a grammar, a parser written the way a language standard is written in BNF. This one reads the whole line, not just the reading:

grammar ChargeLog {
    rule  TOP    { <date> <time> charged <energy> }
    token date   { <year> '-' <month> '-' <day> }
    token year   { \d ** 4 }
    token month  { \d ** 2 }
    token day    { \d ** 2 }
    token time   { \d\d ':' \d\d }
    token energy { <kwh> \s* kWh }
    token kwh    { \d+ [ '.' \d+ ]? }
}

for 'charge.log'.IO.lines -> $line {
    my $m = ChargeLog.parse($line) or next;
    say "$m<date><day>/$m<date><month> at $m<time>: $m<energy><kwh> kWh";
}

say ChargeLog.parse('2026-10-13 18:05 charged 14.2 kWh');
$ raku grammar.raku
12/10 at 08:55: 9 kWh
13/10 at 18:05: 14.2 kWh
｢2026-10-13 18:05 charged 14.2 kWh｣
 date => ｢2026-10-13｣
  year => ｢2026｣
  month => ｢10｣
  day => ｢13｣
 time => ｢18:05｣
 energy => ｢14.2 kWh｣
  kwh => ｢14.2｣

A token matches exactly what it says. In a rule, the spaces in the pattern match spaces in the text, so TOP reads like the sentence it describes. The “plugged in” line doesn’t fit the grammar, so it fails to parse and is skipped. And the result is not a row of $1, $2, $3 but a tree with names on it.

Perl 6 had its first stable release on Christmas Day 2015, and took the name Raku in October 2019.

Reading it again

Go back to \d+(?:\.\d+)? and it reads as layers. The + and ? are egrep’s, from 1979. The \. is ed’s backslash, from 1971. The \d is Perl 2’s. The (?: is Perl 5 finding a gap in the old syntax it could fill without breaking anything. And under all of it, the idea of repetition is Kleene’s, from a memo about neurons.

The Raku version is what you get when someone is finally allowed to start again. It took 64 years to get from a star on paper to a pattern I can read aloud.

Sources