Regular expressions: literals plus operators

A pattern is a set, not a string

A regular expression is a compact way of writing down a set of strings. You write literal characters, which stand for themselves, and operators, which say how the pieces before them may repeat, alternate or float. The tool then asks one question of every line it reads: does this line contain a string that belongs to that set? That is the whole model, and holding on to it is what stops regular expressions feeling like folklore — every operator you learn just changes which strings are in the set.

Three operators do most of the work.

• . stands for any one character. It is greedy about nothing; it consumes exactly one position.
• * means zero or more of the single item immediately before it. That phrase is worth reading twice — the item, not the whole pattern.
• [...] stands for one character drawn from the set inside the brackets, and [^...] for one character not in it.

Everything else is a refinement. ^ and $ do not match a character at all: they match a position, the start and the end of the line, which is why they are called anchors. Alternation | offers a choice between two whole branches. Grouping (...) decides what an operator applies to.

Worked example — three patterns, one candidate list

Take these six candidate lines and evaluate three patterns against them, one candidate at a time. A tool like grep reports a line as matching if any substring of it is in the set, so an unanchored pattern is a containment test.

a
b
bccc
abc
cc
Love

Pattern one: a|bc*. The first thing to settle is what the operators bind to. Alternation has the lowest precedence of the three, and * the highest, so this reads as a or (b followed by zero-or-more c). It does not read as (a or b) followed by zero-or-more c — that would be (a|b)c*. Now the candidates. a matches, on the left branch. b matches on the right branch with zero c characters, and this is the case people miss: c* is perfectly happy matching nothing. bccc matches on the right branch with three. abc matches because it contains an a; the left branch decided it and the bc was never needed. cc fails — neither branch can start there. Love fails.

Pattern two: (a|b)*. Zero or more of (a or b). Because the repetition may be zero, the empty string is a member of this set, and every line contains the empty string — so this pattern matches all six candidates, including Love. A pattern that can match nothing matches everywhere, and that is not a bug in the tool; it is what you asked for. Remember this the next time a filter mysteriously passes every line.

Pattern three: L..e. A literal L, then two of any character, then a literal e — a four-character run. Love matches: L, o, v, e. Lane and Lose would match too. Loose would not, because that is five characters and the pattern reserves exactly two positions between the anchors of L and e. Everything else in the list has no L at all.

Basic and extended are two dialects, not two levels of skill

The operators split into two groups, and the split is the single most common source of the it-works-in-one-tool-but-not-the-other complaint. The basic dialect (BRE) — what plain grep and sed read by default — gives you ., *, [...], ^ and $ unadorned. The extended dialect (ERE) — what grep -E, egrep and awk read — adds |, +, ?, (...) and {n} as plain characters.

In basic, those five are ordinary text unless you backslash them: \|, \+, \?, \(...\), \{n\}. Note that the backslash is doing the opposite of its usual job here. Normally a backslash strips a character of its special meaning; in a BRE it grants one. So grep 'pr\(a\|e\)y' and grep -E 'pr(a|e)y' are the same search written twice, and grep 'pr(a|e)y' is a search for lines containing a literal parenthesis.

One honest caveat: \| in basic grep is a GNU extension rather than POSIX. On a system whose grep is not GNU it may not work at all, which is the real argument for reaching for grep -E whenever you want alternation.