Regular Expressions, from Literal to Pattern

Part I · Module 14 · Chapter 14.2 · Regular Expressions, from Literal to Pattern

Chapter 14.1 used literal text and noted that a dot already means something. This chapter is the language it was quietly part of.

1. Four Kinds of Piece

A pattern is built from four kinds of thing, and almost every pattern you will ever write is some arrangement of them.

The fixture for every measurement below:

$ cat re.txt
cat
cot
coat
ccat
scatter
CAT

2. Literals and the Dot

Most of a pattern is ordinary text that matches itself. The first exception:

$ grep -c 'c.t' re.txt
4

. matches any single character — exactly one, never zero. Four lines contain a c, then something, then a t: cat, cot, ccat and scatter.

Note what it did not match: coat has two characters between c and t, and . is exactly one.

To match a literal dot, escape it:

grep 'a\.c' file        # a, a real dot, c
grep -F 'a.c' file      # or turn the language off entirely — 14.1

3. Anchors — Where

$ grep -c '^cat' re.txt
1

$ grep -c 'cat$' re.txt
2

^ matches the start of the line and $ the end. They match a position, not a character — which is why ^cat found only cat itself and not ccat or scatter, and why cat$ found both cat and ccat.

Combining both pins the whole line:

$ grep -c '^...$' re.txt
3

Exactly three characters: cat, cot, CAT.

grep '^$' file           # blank lines
grep -v '^#' file        # lines not starting with a hash
grep '^module ' rtl.v    # a declaration, not a mention
grep '\.sv$' filelist.f  # entries ending in .sv

4. Character Classes — Which

$ grep -c 'c[ao]t' re.txt
4

$ grep -c 'c[^o]t' re.txt
3

[…] matches exactly one character from the set; [^…] matches one character not in it.

Ranges work, and several can be combined:

[0-9]          one digit
[a-z]          one lowercase letter
[A-Za-z0-9_]   one identifier character
[^0-9]         one character that is not a digit

Named classes are clearer and locale-aware, and they are the same ones tr uses (Chapter 13.5):

$ grep -c '[[:digit:]]' run.log
6

The double brackets are not a typo: [[:digit:]] is a bracket expression containing the class [:digit:]. To combine one with other characters, put them inside the outer brackets — [[:digit:]_-].

5. Quantifiers — How Many

$ grep -c 'co*t' re.txt
1

* means "zero or more of the thing before it" — and the thing before it is the single character o, not co. So co*t matches ct, cot, coot, and here matches only cot.

That * applies to one preceding element is the most common early misunderstanding, because the shell's glob * from Chapter 3.5 means something entirely different.

The full set, in the dialect this chapter uses:

$ printf 'a\nab\nabb\nabbb\n' > q.txt
$ grep -c 'ab\{2\}' q.txt
2

Two lines contain two consecutive bs: abb and abbb. Note that \{2\} means "at least this many here" rather than "exactly this many on the line" — abbb contains abb, so it matches. Anchor it if you mean the whole line.

The backslashes on \{ and \} are the dialect showing through, and Chapter 14.3 is where they disappear.

6. Groups — These Belong Together

grep '\(ab\)*' file          # zero or more repetitions of "ab"
grep '\(FAIL\|ERROR\)' file  # either word

\( \) collects pieces so a quantifier or an alternation applies to all of them. Without the group, ab* means a followed by zero or more b.

$ grep -c '\(FAIL\|ERROR\)' run.log
2

\| is alternation — "this or that". It is the piece that makes one search do the work of two:

grep '\(ERROR\|FATAL\|FAIL\)' run.log

The backslashes are heavy, which is exactly the complaint Chapter 14.3 resolves.

Referring back to a group

$ echo 'alu_seed7' | sed 's/.*_seed\([0-9]*\)/\1/'
7

\1 is whatever the first group captured. Chapter 13.6 used this to extract and reorder; here it is as a piece of the pattern language rather than a sed feature.

Within a pattern it means "the same text again":

grep '\(.\)\1' file          # any character immediately repeated

7. Greedy Matching

$ echo 'aXbXc' | sed 's/X.*X/-/'
a-c

$ echo 'aXbXc' | grep -o 'X.*X'
XbX

* takes as much as it can while still allowing the rest of the pattern to match. X.*X found the first X and the last one, swallowing everything between.

That is why Chapter 13.6's sed 's/.*ERROR: //' keeps only the text after the last ERROR: on a line.

Usually it is what you want. When it is not, the fix is to say what must not appear:

grep -o 'X[^X]*X'            # X, then non-X characters, then X
sed 's/"[^"]*"/QUOTED/'      # one quoted string, not everything between the first and last quote

[^X]* is the standard non-greedy idiom in these tools. The *? form exists in Perl-compatible expressions and is not available in grep or sed without -P, which is GNU-only.

8. Building One Up

The method is Chapter 13.9's, applied to a pattern: start with something that matches too much, and tighten.

Goal: find timeout messages and their cycle counts.

$ grep -c timeout run.log
1

Matches. Now make it precise:

$ grep -n 'timeout after [0-9]* cycles' run.log
3:[00:03] ERROR: timeout after 1203 cycles

Extract just the number:

$ grep -o 'timeout after [0-9]*' run.log
timeout after 1203

Tighten further — a timeout must be at least three digits to be interesting:

$ grep -o 'timeout after [0-9]\{3,\}' run.log
timeout after 1203

Four steps, each verified, each one tightening. Writing the final pattern first and debugging it is the slow way.

9. What These Are Not

Three limits worth stating, because people assume otherwise.

These are not Perl-compatible expressions. \d, \w, \s, *?, lookahead and lookbehind are not part of POSIX regular expressions. GNU grep -P enables them where it is compiled with support; BSD grep has no -P at all. Use [[:digit:]] rather than \d and the pattern works everywhere.

They are not glob patterns. Chapter 3.5's *.log is a different language with different rules, and find -name uses that one rather than this one — which Chapter 14.6 will return to.

They cannot match across lines. grep works a line at a time, so a pattern spanning two lines cannot match. That is a property of the tools rather than of the language, and it is the usual reason a pattern that works in an editor fails in a pipeline.

10. In Practice

grep '^module '                      # a declaration, not a mention
grep '^\s*//'                        # a comment line, possibly indented
grep '[0-9]\{4\}-[0-9]\{2\}-[0-9]\{2\}'   # an ISO date
grep '\.sv$'                         # entries ending in .sv
grep -o 'seed[0-9]*'                 # extract every seed
grep '\(ERROR\|FATAL\)'              # either severity
grep '^[^#]'                         # lines not starting with a hash
grep 'clk[^_a-z]'                    # clk not followed by more identifier
sed 's/"[^"]*"/STR/g'                # replace quoted strings, non-greedily

The last two are the ones worth studying. clk[^_a-z] is a hand-rolled word boundary — less readable than grep -w clk, and the right tool when you need the boundary on only one side.

Practice

mkdir -p /tmp/rx && cd /tmp/rx
printf 'cat\ncot\ncoat\nccat\nscatter\nCAT\n' > re.txt
printf 'a\nab\nabb\nabbb\n' > q.txt
cat > run.log <<'EOF'
[00:03] ERROR: timeout after 1203 cycles
[00:05] Error: assertion failed
[00:06] TEST FAILED
EOF

1 — The dot.

grep 'c.t' re.txt
grep -c 'c.t' re.txt

Four, not five. Work out which line it missed and why.

2 — Anchors.

grep '^cat' re.txt
grep 'cat$' re.txt
grep '^...$' re.txt

3 — Classes.

grep 'c[ao]t' re.txt
grep 'c[^o]t' re.txt
grep '[[:upper:]]' re.txt
grep '[[:digit:]]' run.log

4 — Meet the bracket rules.

printf 'a.b\na-b\na]b\n' > br.txt
grep 'a[.]b'  br.txt
grep 'a[-]b'  br.txt
grep 'a[]]b'  br.txt

5 — Quantifiers, and the zero-match trap.

grep -c 'co*t' re.txt
grep -c 'a*' re.txt

The second matches every line. Say why before reading §5 again.

6 — Intervals.

grep 'ab\{2\}'   q.txt
grep 'ab\{2,3\}' q.txt
grep '^ab\{2\}$' q.txt

7 — Groups and alternation.

grep '\(FAIL\|ERROR\)' run.log
grep -c '\(FAIL\|ERROR\|Error\)' run.log

8 — Watch greed, then control it.

echo 'aXbXc' | grep -o 'X.*X'
echo 'aXbXc' | grep -o 'X[^X]*X'
echo 'say "one" and "two"' | sed 's/"[^"]*"/STR/g'
echo 'say "one" and "two"' | sed 's/".*"/STR/'

9 — Build one up.

grep -c timeout run.log
grep -n 'timeout after [0-9]* cycles' run.log
grep -o 'timeout after [0-9]*' run.log
grep -o '[0-9]\{3,\}' run.log

10 — Clean up. cd /tmp && rm -rf /tmp/rx

Check Your Understanding

1. What are the four kinds of piece a pattern is built from?

2. grep 'c.t' matches cat but not coat. Why?

3. What is the difference between the shell's *.log and the regex *?

4. grep 'a*' file returns every line, including lines with no a. Why?

5. sed 's/".*"/X/' on say "one" and "two" replaces everything from the first quote to the last. What is happening, and what is the fix?

6. Why use [[:digit:]] rather than \d?

11. Remember

• A pattern is four kinds of piece composed: anchors, character classes, quantifiers, groups.
• . matches exactly one character, never zero and never two.
• ^ and $ match positions, not characters, and are the cheapest precision available.
• Most patterns that return too much are missing an anchor.
• […] is one character from a set; [^…] is one character not in it.
• Named classes like [[:digit:]] are clearer, locale-aware and portable.
• Inside brackets the rules change: most metacharacters are literal, and ], ^ and - are escaped by position.
• * applies to the one element before it, and the shell's glob * is a different language.
• * permits zero, which is why a* matches every line.
• \{n,m\} is the interval form, with backslashes in this dialect.
• \( \) groups and \| alternates; \1 refers back to a capture.
• Matching is greedy — .* takes as much as it can. [^X]* is the non-greedy idiom.
• These are not Perl expressions. No \d, no \w, no lookaround without -P.
• They cannot match across lines, because grep works a line at a time.
• Build a pattern up and test it on a fixture you control.

Every pattern here needed backslashes on its braces, groups and alternations. The next chapter is why — and the flag that removes them.