
\documentclass[12pt]{article}
\usepackage[T2A,OT1]{fontenc}
\usepackage[default]{cantarell}
\usepackage[a4paper, top=20mm, bottom=20mm, left=20mm, right=20mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}
\usepackage{tabu}
\usepackage{hyperref}
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}
\usepackage{setspace}
\onehalfspacing
\author{Artyom Bologov \href{mailto:the-regex@aartaka.me}{(email)}}
\date{\today}
\title{There Is No Such Thing As The Regex}
\makeatletter
\def\endenv{\expandafter\end\expandafter{\@currenvir}}
\makeatother
\begin{document}
\maketitle

\includegraphics[width=\textwidth,height=\textheight,keepaspectratio]{./assets/the-regex.png}

I have a new challenge for myself: solving RosettaCode only using \verb|ed| scripts.
Not even \verb|sed|, plain old \verb|ed|.
This makes me try to run as many versions of this venerable editor.
Or at least read the manuals—it’s hard to get BSD/Mac ed while on Guix.
Several things I noticed:

\begin{itemize}\item CLI flags differ dramatically between versions, both in meaning and quantity, with 10 for GNU ed and 1 for Plan 9 ed.
\item Command lists are slightly incompatible too—GNU ed \verb|z| command is \verb|b| in Plan 9 ed, for example.
\item And the regex syntax is not really portable, with many essential features missing from some versions.
\end{itemize}

I’m saying "essential", but who’s to decide?
Apparently, GNU, BSD, MacOS, and Plan 9 \verb|ed| maintainers chose their regex version consciously.
And, apparently, they thought their version is The Regex.

But there’s no such thing as The Regex.
There are only heaps of slightly incompatible syntaxes and extensions to the basic idea.
And there’s no basic idea either, as I’ll try to show.

I’ll use the chrestomathic example: parsing email addresses.
Don’t expect the RFC-compliant pattern, rather let’s simplify this to essentials.
Email address comes in three parts:

\begin{itemize}\item A user name with almost anything in it.
\item And an alphanumeric and dashed domain name with periods.
\item Separated by an at sign.
\end{itemize}

This should be enough to showcase the features of most dialects.
But (here’s a spoiler) it might be too simple for some regex to shine.

\section*{Regular Languages and Kleene Star} \label{regular-languages}

So they wanted to describe languages in the middle of previous century.
\href{https://wikipedia.org/wiki/Regular_language}{The definition from Wikipedia} is:
"[Regular language] is a formal language that can be defined by a regular expression."
Not making things clearer.
Luckily, Wikipedia defines it more rigorously below.
Here’s my summary:

\begin{description}\item[Ø]
Empty language, nothingness.
\item[a]
Some symbol.
\item[{a...}]
A set of symbols.
\item[X*]
Something with Kleene star, repeated zero or more times.
\item[∪ and •]
Union and concatenation, set operations on sub-languages.
\end{description}

Quite different from the popular idea of regex as we know it, right?
The only comforting resemblance is Kleene star.
Let’s try to define a regular expression describing emails in it.

\begin{figure}[h!]\begin{verbatim}
{a..z, A..Z, 0..9, ...}*•{@}•{a..z, A..Z, 0..9, -}*•({.}•{a..z, A..Z, 0..9, -})*
\end{verbatim}\caption{Email addresses as regular language}\end{figure}

Notice that these ellipses are just me being lazy and not wanting to list out every possible character.
Because that’s what happens when you mess with math people.
No mercy.

"Regular expressions" as they initially were... look quite alien.
But they’ll fix it in the course of history, right?

\section*{Thompson \& Basic POSIX/UNIX Regex} \label{posix}

Ken Thompson fixed regex and turned them into something we’re familliar with.
The transitionary state can be seen in the
\href{https://dl.acm.org/doi/abs/10.1145/363347.363387}{Regular Expression Search Algorithm paper}.
There’s still • operator, even if used internally.
∪ turns into a vertical bar \verb|||.
And Kleene star remains as is.
That’s it really.

What followed is so-called Basic Regular Expressions.
Notable additions:

\begin{itemize}\item Period \verb|.| as the placeholder for any single char.
\item Character classes delimited by square brackets.
\item \verb|^| for start of line and \verb|$| for end of line.
\item Curly braces for "match N to M times" scenario.
\item Parentheses for regex grouping.
\item Kleene star is stil there, of course.
\end{itemize}

One problematic thing is that one has to mark braces and parentheses by backslash.
To highlight their special status.
What about square brackets?
No backslash.
Inconsistent and error-prone.

Here’s how POSIX Basic Regular Expressions version of email address might look like:

\begin{figure}[h!]\begin{verbatim}
.\{1,\}@[-[:alnum:]]*\(\.[-[:alnum:]]*\)*
\end{verbatim}\caption{Email address as POSIX Basic Regex}\end{figure}

A lot of backslashes, ugh.
It’s only intuitive that one might want less backslashes.
One superpower of BRE, though: backreferences!
\verb|\n| (backslash with a number) means referencing the previous regex group.
The parenthesized one.
Most of the flawors below lost this ability for some reason.
A shame.

\section*{Plan 9 Regex} \label{plan-9}

\href{https://9fans.github.io/plan9port/man/man7/regexp.html}{These Plan 9 regex}
are closer to initial Thompson ones, but add some quality of life features:

\begin{itemize}\item \verb|+| for "one or more match".
\item \verb|?| for "one or zero matches".
\item No backslashes!
\end{itemize}

\begin{figure}[h!]\begin{verbatim}
.+@[-a-zA-Z0-9]+(\.[-a-zA-Z0-9]+)+
\end{verbatim}\caption{Email address as Plan 9}\end{figure}

What Plan 9 regex miss is curly braces and spelled-out char classes.
Yes, no quantified matches and convenient Unicode-aware matching.
So overall Plan 9 regex are a syntactic evolution over BRE, but they miss a lot of semantic necessities.
For whatever reason.

\section*{Extended POSIX Regex} \label{extended-posix}

The synthesis (not necessarily historical, but rather ideological) of BREs and Plan 9: ERE.
\href{https://manpage.me/index.cgi?q=re_format&sektion=7&apropos=0&manpath=FreeBSD+12-CURRENT+and+Ports}{Extended Regular Expressions}.
No backslashes, curly braces are back, as are char classes.
That’s where we get closer to conventional regex as we know them:

\begin{figure}[h!]\begin{verbatim}
.+@[-[:alnum:]]+(\.[-[:alnum:]]+)+
\end{verbatim}\caption{Email address as POSIX Basic Regex}\end{figure}

\section*{GNU \& Emacs Regex} \label{gnu-emacs}

GNU regex (as present in GNU ed, which I’m currently using, and in GNU Emacs as the main dissemination source) are extending over POSIX ones.
Mainly via backslash sequences.
\href{https://gnu.org/software/emacs/manual/html_node/emacs/Regexp-Backslash.html}{Lots of them}.
Notable highlights:

\begin{description}\item[\w]
For any word (alphanumeric and underscore) char.
\item[\W]
For any NON-word char.
\item[\b]
For word boundary.
\item[\B]
For inside-word char boundary.
\item[\s]
For spaces.
\item[\S]
For NON-spaces.
\end{description}

You probably got the idea—some letter for char class, and its capital version for inversion or special case.
No, wait, there are lots of special cases.
I’m not even sure what’s the heuristic.
But still, lots of special sequences for fun and profit:

\begin{figure}[h!]\begin{verbatim}
.+@\w+(\.\w+)+
\end{verbatim}\caption{Email address as GNU regex}\end{figure}

Our email pattern gets shorter and shorter, which is a win.
(Ignore the fact that I’m excluding dashes from domain names now.)
But it’s also confined to GNU software, which sucks.
Because there is other software.
Like...

\section*{SQL \& Postgres} \label{sql-postgres}

SQL has these weird \verb|LIKE| patterns:

\begin{figure}[h!]\begin{verbatim}
an_thing -- _ stands for any single char
%prefixed -- % is any set of chars
suffixed% -- Same %, but ending a string now
%wrapped% -- A string containing ’wrapped’ in any position
\end{verbatim}\caption{LIKE patterns in SQL}\end{figure}

But these are unrelated to regex, right?
They look so alien, after all.
Unfortunately, there are systems where this alien syntax is valid regex.
Like Postgres.

Postgres regex, as they call it, is a frivolous mix of POSIX and SQL LIKE.
Period (\verb|.|), our trusted friend, is missing in Postgres syntax, and is replaced by underscore (\verb|_|).
A soul-calming \verb|.*| sequence is \verb|%| instead.
The rest is plain POSIX EREs.

\begin{figure}[h!]\begin{verbatim}
%@[-a-zA-Z0-9]+(.[-a-zA-Z0-9]+)+
\end{verbatim}\caption{Email address as Postgres regex}\end{figure}

\section*{Scheme Regex (SRFI 115)} \label{scheme-regex}

Scheme (and Lisps in general) are famous for the Domain-Specific Languages.
You can build a subset of a language that maps 1-to-1 to the problem domain.
Which is a blessing, isn’t it?
But this also gives rise to really complex and Turing-complete languages one can conjure.
Like Scheme Regular Expressions (SRE)
\href{https://srfi.schemers.org/srfi-115}{described in SRFI 115}.

These encode regular expressions as parenthesised lists.
The patterns form trees of expressions that are parseable but somewhat verbose.
And, I bet, they don’t look like the idea of The Regex:

\begin{figure}[h!]\begin{verbatim}
(: (* any) #\@ (* (or #\- alnum)) (+ (: #\. (+ (or #\- alnum)))))
\end{verbatim}\caption{(Untested) email pattern as a Scheme regex}\end{figure}

Here’s your portion of parentheses disgust for today.
No need to thank me.

\section*{Perl Regex} \label{perl}

I’ll skip this section, because I’m unfamiliar with Perl.
But what I know is that Perl regex/string processing it Turing-complete.
They basically are Extended Extended Extended POSIX regex.
Pretty with the basics, yet syntactically horrifying with advanced things
(like lookaheads and recursive matching.)

I’m not listing an email example here, because it’s going to look the same as GNU one.
See? No longer a useful litmus test!

\section*{Modern Regex: Python, JS, .NET} \label{modern}

Most modern languages and runtimes have their own regex libraries/syntax.
Some (JS) even go as far as having a dedicated language syntax for regex literals.
Given the ubiquity of regex, they must be similar, transferable, and still powerful, right?
Only the latter is true.

\href{https://stackoverflow.com/questions/546433/regular-expression-to-match-balanced-parentheses}{See this StackOverflow question}
for a staggering showcase of the syntaxes modern RE systems boast.
\href{run:paren-regex}{(And check my BRE approach to the problem!)}
I’m linking to it in part because my example with email is no longer useful.
Most modern RE systems will have something similar(ly short) to Perl/GNU regex.

\section*{Post Modern Regex: Any Pattern-Matching Language?} \label{post-modern}

What about PEG?
Parsing Expression Grammar, I mean.
The thing specifying parsers.
A parser for email might read:

\begin{figure}[h!]\begin{verbatim}
.*@[-a-zA-Z0-9]+(\.[-a-zA-Z0-9]+)+
\end{verbatim}\caption{A potential PEG parser for emails}\end{figure}

Which looks almost like POSIX ERE, right?
Yet it’s called PEG.
So one has two options here:

\begin{itemize}\item Say that regexes are what looks like ones and embrace PEG.
\item Say that regexes are what’s called that (including Scheme Regex) and reject PEG regex-yness.
\end{itemize}

Either way, regex proves to be a complicated concept with no set syntax/definition.
And any other pattern-matching language has a chance to be called regex, really.
Be it \verb|scanf| patterns, BNF/yacc parsers, or templating engines.

\section*{The Regex, Really?} \label{really}

Given the variety of syntaxes listed in this post, there seem to be no basic properties to regex.
The only thing making appearance everywhere is Kleene star.
The only one.
Other "obvious" and "basic" things like \verb|.| and \verb|{}| are often missing or re-imagined.
So, is there The Regex?

No.

\paragraph{A longer answer would be:} \begin{quote}
There’s no definitive spec / version / implementation.
Some implementations, like Perl and GNU, are more successful / useful / influential.
Some syntactic features appear more than the others.
But there’s no consensus and there are lots of weird outliers.
\end{quote}

Use whatever you like and don’t let anyone tell you it is not regex.
(Just remember to mention which syntax/implementation you use when sharing your sed one-liners with people.)


\par\noindent\rule{\textwidth}{0.4pt}
\href{https://creativecommons.org/licenses/by/4.0}{CC-BY 4.0} 2022-2026 by Artyom Bologov (aartaka,)
\href{https://codeberg.org/aartaka/pages/commit/a91befa}{with one commit remixing Claude-generated code}.
Any and all opinions listed here are my own and not representative of my employers; future, past and present.
\end{document}
