Regular Expressions

The script has so far split paths with cut and counted status codes with fixed strings. Both approaches assume the data’s format is flawless. Real logs contain broken lines, missing fields, and unexpected formats; and patterns such as “codes starting with four hundred” cannot be expressed with a fixed string.

A regular expression is a pattern language that describes a set of strings. In the text algorithms topic of the Algorithms course, pattern matching was defined for a single fixed string; a regular expression sets up the same problem for a set that can be infinite, instead of a single string.

This lesson builds the pattern language. The following lessons connect it to tools.

Two Syntaxes

POSIX defines two regular expression syntaxes, and tools state which one they use through an option.

Basic regular expression (BRE) is the default syntax for the grep and sed commands. Grouping, alternation, and some quantifiers are written with a backslash.

Extended regular expression (ERE) is used by grep -E and awk. The same operators are written without the backslash.

grep -c  '\(404\|500\)' access.log
grep -Ec '(404|500)'   access.log

7
7

The two patterns describe the same set; only their spelling differs. This course prefers ERE: it is easier to read and avoids backslash pileup.

Patterns are written inside single quotes. The $, *, \, [ characters in the pattern language also carry meaning for the shell; single quotes prevent the shell from interpreting them. This is a direct application of the rule from the Variables and Quoting Rules lesson.

Literal Matching and the Dot

Every character with no special meaning matches itself. ., on the other hand, matches any single character — this is the most frequently overlooked special character.

printf '%s\n' 'style.css' 'styleXcss' 'style-css' > names.txt
grep 'style.css' names.txt

style.css
styleXcss
style-css

Once the dot is escaped, only a literal dot matches:

grep 'style\.css' names.txt

style.css

In data containing dots — file names, domain names, IP addresses — this distinction is a matter of correctness.

Quantifiers

A quantifier states how many times the element before it repeats.

ERE	BRE	Meaning
*	*	zero or more
+	\+	one or more
?	\?	zero or one
	\{n\}	exactly n
{n,m}	\{n,m\}	at least n, at most m

printf '%s\n' 'color' 'colorr' 'colorrr' > rep.txt

grep -Ec 'color+'    rep.txt
grep -Ec 'color{2}'  rep.txt
grep -Ec 'color{1,2}' rep.txt

3
2
3

color{2} matched two lines: colorr and colorrr — in the second, the first two r characters are enough, because the pattern does not have to cover the entire line.

This last sentence is critical. A regular expression looks for a match anywhere in the line. If a full-line match is wanted, an anchor is used.

Anchors

^ marks the start of the line, $ the end. Neither matches a character; both match a position and have no width.

grep -c '^10\.0\.0' access.log

14

When the two are used together, the pattern covers the entire line. This is how every line of a log is confirmed to be in the expected format:

PATTERN='^[0-9.]+ - - \[[^]]+\] "[A-Z]+ [^ ]+ HTTP/[0-9.]+" [0-9]{3} [0-9]+$'
grep -Ec "$PATTERN" access.log

30

All thirty lines fit the pattern. When broken lines mix into the log, the -v option filters them out:

{ cat access.log
  echo 'broken line'
  echo '10.0.0.1 - - [x] "GET /a HTTP/1.1" 200 5'
} > all.log
grep -Ev "$PATTERN" all.log

broken line

Two broken lines were added, but the pattern caught only one. The second one’s timestamp is not realistic, yet the \[[^]]+\] part says “at least one character between the square brackets,” so it still fits the pattern. A pattern validates only as much as it describes; a complementary check based on field count will be added in the Field-Based Processing lesson.

Because this pattern is held in a variable, it is expanded with double quotes; had single quotes been used, the variable name would have been passed through literally. The pattern itself was inside single quotes at the point of assignment.

Bracket Expressions

A bracket expression defines a set of characters and matches one of the characters inside it.

• [abc] — one of three letters
• [0-9] — a range
• [^0-9] — not in the set (negation)
• [.-] — most special characters lose their meaning inside a bracket expression

cut -d' ' -f9 access.log | grep -c '^[^2]'
cut -d' ' -f9 access.log | grep -Ec '^[45]'

12
9

Of thirty requests, twelve are outside the success class, nine are in the error class.

Negation carries its special meaning only in the first position of the bracket expression; [a^b] matches one of three characters. The hyphen follows the same rule: in the last position it is literal.

Portable Character Classes

POSIX defines named character classes. They are written inside a bracket expression and are themselves bracketed:

Class	Matches
[[:digit:]]	digits
[[:alpha:]]	letters
[[:alnum:]]	letters and digits
[[:space:]]	whitespace kinds
[[:upper:]], [[:lower:]]	uppercase and lowercase letters

grep -Eo '^[[:digit:]]+\.[[:digit:]]+\.[[:digit:]]+\.[[:digit:]]+' access.log | sort -u

10.0.0.12
10.0.0.31
10.0.2.7
172.16.0.9
192.168.1.5

The -o option writes not the whole line but only the matched portion.

Some implementations offer shortcuts such as \d, \w, \s. These are not defined in POSIX; tools that support them and tools that do not exist side by side. This is the most common reason for getting a different result when running the same pattern on two different systems. A portable script writes [[:digit:]].

The named classes’ second advantage is that ranges such as [a-z] depend on the locale: when the sort order changes, the characters a range covers change too. [[:lower:]] carries no such ambiguity.

Greediness

Quantifiers are greedy: they take the longest text they can match.

echo 'a"one" and "two"z' | grep -Eo '".*"'
echo 'a"one" and "two"z' | grep -Eo '"[^"]*"'

"one" and "two"
"one"
"two"

The .* in the first pattern swallowed everything between the two quote pairs. The second pattern, by saying “characters that are not a quote” with [^"]*, matched each quoted piece separately.

POSIX regular expressions have no non-greedy quantifier (such as *?). The solution is always the same: a character class that negates the delimiter. This pattern — opening delimiter, repetition of non-delimiter characters, closing delimiter — is the basic form of field extraction, and it is also used to capture the square-bracketed timestamp in the log.

Grouping and Backreferences

Parentheses group a subpattern; they are used both to apply a quantifier and to store the matched text. \1, \2 … refer back to the stored text (a backreference).

printf '%s\n' 'aa' 'ab' 'abab' > repeat.txt
grep -E '(.)\1'  repeat.txt
grep -E '(..)\1' repeat.txt

aa
abab

The first pattern describes “the same character repeated twice,” the second “the same two characters repeated twice.” The backreference is the point where regular expressions go beyond their definition in formal language theory: patterns with backreferences exceed the regular language class, and matching cost can become exponential.

The real use of groups is substituting the matched portions; this is taken up in the Transforming with the Stream Editor lesson.

A Method for Writing Patterns

Complex patterns are not written in one pass. The sequence to follow is this:

1. Take one of the lines you want matched and search for it literally.
2. Replace the variable parts, one at a time, with a class and a quantifier; watch the match count with grep -c at every step.
3. If the count is larger than expected, the pattern is too wide; if smaller, it is missing a case.
4. Run the pattern with -o and visually confirm the matched portion.
5. In the last step, add anchors and move to a full-line match.

The line-validation pattern above was built exactly this way. Producing a measurable number at every step is the cheapest way to test a pattern.

Summary

• A regular expression describes a set of strings; POSIX defines two syntaxes, and tools state which one they use through an option.
• Patterns are written inside single quotes; . matches any character and must be escaped to match a literal dot.
• A pattern matches anywhere in the line; a full-line match is built with the ^ and $ anchors.
• Named character classes are portable and unaffected by locale; shortcuts such as \d are not defined in POSIX.
• Quantifiers are greedy and POSIX has no non-greedy form; the solution is a character class that negates the delimiter.

Next Step

The pattern language is built; now it needs to be connected to a tool. The next lesson takes up line filtering: beyond selecting matching lines, counting them, inverting the selection, writing only the matched portion, listing file names, and using grep’s exit code as a condition.