path: root/src/blog/2023-06-16-regex/regex.md

# UNIX text filters, part 0 of 3: regular expressions

*This post is part of a [series](../../series)*

One of the most important features of UNIX and its descendants, if
not *the* most important feature, is input / output redirection:
the output of a command can be displayed to the user, written to a
file or used as the input for another command seamlessly, without
the the program knowing which of these things is happening. This
is possible because most UNIX programs use *plain text* as their
input/output language, which is understood equally well by the three
types of users - humans, files and other running programs.

Since this is such a fundamental feature of UNIX, I thought it would
be nice to go through some of the standard tools that help the user
take advantage of it. At first I thought of doing this as part of
my *man page reading club* series, but in the end I decided to give
them their own space. My other series has also been going on for
more than a year now, so it is a good time to end it and start a
new one.

Let me then introduce you to: **UNIX text filters**.

## Text filters

For the purpose of this blog series, a *text filter* is a program
that reads plain text from standard input and writes a modified,
or *filtered* version of the same text to standard output. According
to the introductory paragraph, this definition includes most UNIX
programs; but we are going to focus on the following three, in
increasing order of complexity:

* grep
* sed
* awk

In order to unleash the true power of these tools, we first need
to grasp the basics of
[regular expressions](https://en.wikipedia.org/wiki/Regular_expression).
And what better way to do it than following the dedicated
[OpenBSD manual page](https://man.openbsd.org/OpenBSD-7.3/re_format)?

## (Extended) regular expressions

Regular expressions, or regexes for short, are a convenient way to
describe text patterns. They are commonly used to solve genering
string matching problems, such as determining if a given piece
of text is a valid URL. Many standard UNIX tools, including the three
we are going to cover in this series, support regexes.

Let's deal with the nasty part first: even within POSIX, there is
not one single standard for regular expressions; there are at least
two of them: Basic Regular Expressions (BREs) and Extended Regular
Expressions (ERE). As it always happens when there is more than one
standard for the same thing, other people decided to come up with
another version to replace all previous "standards", so we have also
[PCREs](https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions),
and probably more. [Things got out of hand quickly](https://xkcd.com/927).

In this post I am going to follow the structure of
[re_format(7)](https://man.openbsd.org/OpenBSD-7.3/re_format) and
present *extended* regular expresssions first. After that I'll point
out the differences with *basic* regular expressions.

The goal is not to provide a complete guide to regexes, but rather
an introduction to the most important features, glossing over the
nasty edge-cases. Keep also in mind that I am in no way an expert
on the subject: we are learning together, here!

### The basics

You can think of a regular expression as a *pattern*, or a *rule*,
that describes which strings are "valid" (they are *matched* by the
regular expression) and which are not. As a trivial example, the
regular expression `hello` matches only the string "hello". A less
trivial example is the regex `.*` that matches *any* string.  I'll
explain why in a second.

Beware not to confuse regular expressions with *shell globs*, i.e.
the rules for shell command expansion. Although they use similar
symbols to achieve a similar goal, they are not the same thing. See
[my post on sh(1)](../2022-09-13-sh-1) or
[glob(7)](https://man.openbsd.org/OpenBSD-7.3/glob.7) for an
explanation on shell globs.

### General structure and terminology

A general regex looks something like this:

```
piece piece piece ... | piece piece piece ... | ...
```

A sequence of *pieces* is called a *branch*, and a regex is a
sequence of branches separated by pipes `|`. Pieces are not separated
by spaces, they are simply concatenated.

The pipes `|` are read "or": a regex matches a given string if any
of its branches does. A branch matches a given string if the latter
can be written as a sequence of strings, each matching one of the
pieces, in the given order.

Before going into what pieces are exactly, consider the following
example:

```
hello|world
```

This regex matches both the string "hello" and the string "world",
and nothing else. The pieces are the single letters composing the
two words, and as you can see they are juxtaposed without spaces.

But what else is a valid piece? In general, a piece is made up of
an *atom*, optionally followed by a *multiplier*.

### Atoms

As we have already seen, the most simple kind of atom is a single
character. The most *general* kind of atom, on the other hand, is
a whole regular expression enclosed in parentheses `()`. Yes, regexes
are recursive.

There are some special characters: for example, a single dot `.`
matches *any* single character. The characters `^` and `$` match
an empty string at the beginning and at the end of a line, respectively.
If you want to match a special character as if it was regular, say
because you want to match strings that represent values in the
dollar currency, you can *escape* them with a backslash. For example
`\$` matches the string "$".

The last kind of atoms are *bracket expressions*, which consist of
lists of characters enclosed in brackets `[]`. A simple list of
characters in brackets, like `[xyz]`, matches any character in the
list, unless the first character is a `^`, in which case it matches
every character *not* in the list. Two characters separated by a
dash `-` denote a range: for example `[a-z]` matches every lowercase
letter and `[1-7]` matches all digits from 1 to 7.

You can also use cetain special sets of characters, like `[:lower:]`
to match every lowercase letter (same as `[a-z]`), `[:alnum:]` to
match every alphanumeric character or `[:digit:]` to match every
decimal digit. Check the
[man page](https://man.openbsd.org/OpenBSD-7.3/re_format)
for the full list.

### Multipliers

The term "multiplier" does not appear anywhere in the manual page, I
made it up. But I think it fits, so I'll keep using it.

Multipliers allow you to match an atom repeating a specified or
unspecified amount of times. The most general one is the *bound*
multiplier, which consists of one or two comma-separated numbers
enclosed in braces `{}`.

In its most simple form, the multiplier `{n}` repeats the multiplied
atom `n` times. For example, the regex `a{7}` is equivalent to the
regex `aaaaaaa` (and it matches the string "aaaaaaa").

The form `{n,m}` matches *any number* between `n` and `m` of copies
of the preceeding atom. For example `a{2,4}` is equivalent to
`aa|aaa|aaaa`. If the integer `m` is not specified, the multiplied
atom matches any string that consists of *at least* `n` copies of
the atom.

Now we can explain very quickly the more common multipliers `+`,
`*` and `?`: they are equivalent to `{1,}`, `{0,}` and `{0,1}`
respectively.  That is to say, `+` matches at least one copy of the
atom, `*` matches any number of copies (including none) and `?`
matches either one copy or none.

## Basic regular expressions

Basic regular expressions are less powerful than their extended
counterpart (with one exception, see below) and require more
backslashes, but it is worth knowing them, because they are used
by default in some programs (for example [ed(1)](../2022-12-24-ed)).
The main differences between EREs and BREs are:

* BREs consist of one single branch, i.e. there is no `|`.
* Multipliers `+` and `?` do not exist.
* You need to escape parentheses `\(\)` and braces `\{\}` to
  use them with their special meaning.

There is one feature of BREs, called *back-reference*, that is
absent in EREs. Apparently it makes the implementation much more
complex, and it makes BREs more powerful. I noticed the author of
the manual page despises back-references, so I am not going to learn
them out of respect for them.

## Conclusion

Regexes are a powerful tool, and they are more than worth knowing.
But, quoting from the manual page:

```
     Having two kinds of REs is a botch.
```

I hope you enjoyed this post, despite the lack of practical examples.
If you want to see more applications of regular expressions, stay
tuned for the next entries on grep, sed and awk!

*Next in the series: [grep](../2023-08-20-grep)*