Character Classes and Quantifiers

Part II · Module 4 · Chapter 4.2 · Character Classes and Quantifiers

1. From Strings to Shapes

DEBUG matches the text DEBUG. That is useful and limited — it cannot express "a signal name", "a number", or "a blank line", because those are not strings, they are descriptions.

Two pieces of syntax turn a pattern into a description:

   [a-z]          a SET      — one character, from this set
   [a-z]*         + HOW MANY — any number of characters from that set

   [a-z_][a-z0-9_]*
   └──┬──┘└────┬──┘
   must start   then any number of
   with a       letters, digits or
   letter or    underscores
   underscore

That second line is the rule for a legal identifier in almost every hardware language, written in nine characters. The rest of this chapter is the parts it is made of.

2. Bracket Expressions: a Set of Characters

Square brackets mean one character, chosen from this set. List the characters, or give a range with -:

   [abc]      one of a, b or c
   [a-z]      one lowercase letter
   [0-9]      one digit
   [a-z0-9_]  one letter, digit or underscore

Note what brackets are not: they match exactly one character, not a word. [abc] will never match ab. Matching more than one takes a quantifier, which is section 5.

A worked example. Here is a list of filenames, some of them legal identifiers and some not:

cat -n filelists/names.f

     1	alu.sv
     2	fifo_pkg.sv
     3	2bad_name.sv
     4	top.v
     5	Alu.sv
     6	my-block.sv

Now the identifier rule from section 1, applied to the whole name, asking for a .sv extension:

sed -E -n '/^[a-z_][a-z0-9_]*\.sv$/p' filelists/names.f

alu.sv
fifo_pkg.sv

Two of six. Work through the rejections, because each one is a different part of the pattern doing its job:

• 2bad_name.sv — starts with a digit, and the first bracket allows only a letter or underscore.
• top.v — the extension is .v, and the pattern ends with a literal \.sv$.
• Alu.sv — starts with a capital, and [a-z] is lowercase only.
• my-block.sv — contains a hyphen, which is not in [a-z0-9_].

That is a filename policy expressed as a pattern, and it would work identically on a list of four thousand names.

3. POSIX Classes: Named Sets

Ranges like [a-z] are the obvious way to write a set, and there is a better one. POSIX defines named classes that go inside the brackets:

The doubled brackets look odd and are not a typo: the outer [ ] is the bracket expression, and [:space:] is one item inside it. That means you can combine them with other characters — [[:digit:]_] is "a digit or an underscore", and [[:alpha:][:digit:]] is the long way to write [[:alnum:]].

On the data here, a class and a range often agree:

printf 'Alu.sv\nalu.sv\n' | sed -n '/^[a-z]/p'

alu.sv

printf 'Alu.sv\nalu.sv\n' | sed -n '/^[[:lower:]]/p'

alu.sv

Same answer. So why prefer the class? Two reasons, and it is worth being clear that the transcript above does not demonstrate either of them:

• Tabs. [[:space:]] covers a tab; a hand-written [ ] containing only a space does not. For indentation matching — which is most of what you do in RTL and reports — this is the difference between a pattern that works on both tab- and space-indented files and one that silently skips half of them.
• Locale. A range like [a-z] is defined by character ordering, which can differ between locales; a named class is defined by meaning. On a build machine with an unexpected locale setting, the class is the one that keeps meaning what you wrote.

Neither was exercised on the ASCII fixtures here, so treat them as reasons to prefer the class rather than as something these runs proved. The practical upshot is simple: use [[:space:]] always, and the named classes when you mean "a letter" or "a digit" rather than a specific span of characters.

The whitespace class in action, in basic mode and needing nothing extra — every line of a module body that is indented and then has content:

sed -n '/^[[:space:]]\{2\}[^[:space:]]/p' rtl/top.sv

  input  logic clk,
  input  logic rst_n,
  output logic [31:0] data_o,
  inout  wire  sda
  logic [7:0] count;
  wire        ready;

Six lines — every indented line, and none of module top (, ); or endmodule. The \{2\} is an interval, covered in section 6, and [^[:space:]] is a negation, which is next.

4. Negation: Everything Except

A ^ as the first character inside brackets inverts the set:

   [^0-9]              one character that is NOT a digit
   [^[:space:]]        one character that is NOT whitespace
   [^/]                one character that is not a slash

A practical use on the filelist — the lines that are neither a + option, a # comment, nor a ./ relative path:

sed -n '/^[^.+#]/p' filelists/top.f

/proj/old/tb/env.sv

One line out of ten: the only absolute path in the file. A quick audit of "which entries are not written the way the rest are" in one command.

A negated class is also the standard way to express "up to the next delimiter", which is worth having now because it is the fix for a problem section 7 will show:

printf '/proj/old/rtl/alu.sv\n' | sed 's|^/\([^/]*\)/.*|\1|'

proj

[^/]* means "any number of characters, none of which is a slash" — so it stops at the first slash rather than running to the last one.

5. The Star: How Many, Including None

A quantifier follows the thing it repeats. The one available in both dialects with no escaping is *:

   [0-9]*     any number of digits — including ZERO digits
   x*         any number of x characters, including none

The "including zero" is the part that catches people. * is not "one or more"; it is "however many, and nothing is a valid amount".

printf 'clk\nclkkk\nclx\n' | sed -n '/^clk*$/p'

clk
clkkk

The pattern is c, l, then any number of k. clk matched with one k; clkkk matched with three. clx did not match, because after cl it needs only k characters until the end of the line, and x is not one.

Note what the pattern would also match: cl, with zero ks. There is no line like that here, which is exactly the sort of thing to keep in mind — a * makes its item optional, so /^clk*$/ is a looser rule than it looks.

Combined with a class, * is what makes section 1's identifier rule work:

   [a-z_][a-z0-9_]*
   └──┬──┘└────┬──┘
   exactly one   zero or more

The first bracket has no quantifier, so it is mandatory — a name must have a first character. The second is quantified with *, so a.sv is legal with a one-character name. Using * on both would allow the empty name; using it on neither would require exactly two characters.

6. Intervals, + and ?

For exact counts, use an interval. In basic mode the braces need backslashes; under -E they do not. This is the same split as Chapter 4.1's five characters.

   \{3\}     basic mode: exactly 3        -E:  {3}
   \{2,\}    basic mode: 2 or more        -E:  {2,}
   \{1,4\}   basic mode: between 1 and 4  -E:  {1,4}

The registered example for this chapter finds the deeply indented lines of a timing report — four spaces or more:

sed -n '/^[[:space:]]\{4,\}/p' sta/timing.rpt | wc -l

       2

Two lines. Forget the backslashes in basic mode and the braces are literal text, so the pattern looks for [[:space:]]{4,} as characters and finds nothing:

sed -n '/^[[:space:]]{4,}/p' sta/timing.rpt | wc -l

       0

Zero lines, exit status 0, no diagnostic — a silent no-op of exactly the kind Module 3 kept meeting. Under -E the unbackslashed form is correct:

sed -E -n '/^[[:space:]]{4,}/p' sta/timing.rpt | wc -l

       2

Two again, agreeing with the basic-mode version.

+ and ? are extended-mode only, as Chapter 4.1 established. + is "one or more":

printf 'clk\nclkkk\nclx\n' | sed -E -n '/^clk+$/p'

clk
clkkk

Same two lines as the * version here — but unlike *, this one would reject cl. In basic mode + is a literal character:

printf 'clk+\nclkk\n' | sed -n '/^clk+$/p'

clk+

Only the line with a real plus sign. The portable way to say "one or more" without -E is an interval:

printf 'clk\nclkkk\nclx\n' | sed -n '/^clk\{1,\}$/p'

clk
clkkk

And a fixed-width interval is the clean way to match a formatted field — here, a temperature with exactly three digits:

printf 'ss_0p72v_125c\nss_0p72v_25c\n' | sed -n '/_[0-9]\{3\}c$/p'

ss_0p72v_125c

125c matched; 25c did not. Writing that with * would have matched both, and writing it with . would have matched anything.

7. Leftmost, Then Longest

When several parts of a line could match, sed picks the match that starts earliest. Among matches starting at the same place, it takes the longest. Those are two separate rules and one experiment cannot show both, so here are two.

Leftmost first. The alternatives are ab and abcd, on a line containing both:

printf 'ab abcd\n' | sed -E 's/ab|abcd/[&]/'

[ab] abcd

The standalone ab at position 1 won, even though abcd further along is a longer match. Earliest beats longer.

Longest second. Same pattern, on a line where both alternatives start at the same position:

printf 'abcd\n' | sed -E 's/ab|abcd/[&]/'

[abcd]

Now abcd won. With the start position tied, the longer match is taken — and note that it won despite ab being listed first in the pattern. The order of your alternatives does not decide the outcome.

The practical consequence of "longest" is that .* is greedy — it runs as far as it can:

printf 'a1b2c3\n' | sed -E 's/[0-9].*[0-9]/[&]/'

a[1b2c3]

The match started at the leftmost digit, 1, and then .*[0-9] stretched to the last digit rather than stopping at the next one. The classic version of this is stripping a directory:

printf '/proj/old/rtl/alu.sv\n' | sed 's|.*/||'

alu.sv

.*/ took everything up to the last slash, which here is what you want — this is the standard "basename" idiom. But when you want the first field rather than the last, greed is the enemy, and sed has no non-greedy quantifier. The fix is section 4's negated class, which cannot cross the delimiter:

printf '/proj/old/rtl/alu.sv\n' | sed 's|^/\([^/]*\)/.*|\1|'

proj

Remember this pair. .* when you want to reach the last occurrence; [^x]* when you want to stop at the first. Nearly every "my pattern matched too much" bug is a .* that should have been a negated class, and Chapter 7.3 is a whole chapter on diagnosing it.

8. A Blank Line Is Not Always Empty

A worked example that brings the chapter together, and a reminder about test data.

There are two different questions you might be asking about a blank line: is it empty, or does it have nothing but whitespace on it. Here is a file that distinguishes them — cat -et marks line ends with $ so the difference is visible:

cat -net filelists/blanks.f

     1	alu.sv$
     2	$
     3	   $
     4	fifo.sv$

Line 2 is empty. Line 3 has three spaces. Now the two patterns. ^$ means "start of line immediately followed by end of line":

sed -n '/^$/=' filelists/blanks.f

2

One line. And ^[[:space:]]*$ means "start, then any amount of whitespace, then end":

sed -n '/^[[:space:]]*$/=' filelists/blanks.f

2
3

Two lines — the * allows zero whitespace characters, so this pattern covers the empty line as well as the whitespace-only one. That is almost always the one you want, because a line of three spaces looks blank in every editor and is not empty to ^$.

(= prints the line number instead of the line, which is far easier to read than two blank lines of output. It takes only one address, so it cannot be used with the ranges in Chapter 4.4.)

9. Think It Through

1. Write a pattern for a legal SystemVerilog identifier that may contain a dollar sign, and explain why your bracket order matters.

[a-z_][a-z0-9_$]* for the lowercase-only case, or [[:alpha:]_][[:alnum:]_$]* to allow capitals. The $ is an ordinary character inside brackets — the anchoring meaning only applies outside them — so no escaping is needed. What does matter is the hyphen rule from section 2: if you also wanted hyphens, it goes first or last, never between two other characters.

2. Why does /^[[:space:]]*$/ match more lines than /^$/, and which should you normally use?

* allows zero occurrences, so ^[[:space:]]*$ matches the empty line too, plus any line of nothing but spaces or tabs. ^$ matches only the truly empty one. Use the whitespace version for anything that means "blank line", because a whitespace-only line is indistinguishable from an empty one on screen.

3. sed -n '/^[[:space:]]{4,}/p' report.rpt returns nothing and you are sure the report has deep indentation. What is wrong?

Basic mode needs the braces escaped — \{4,\} — otherwise they are literal characters and the pattern looks for a run of whitespace followed by the text {4,}. Either escape them or add -E. Note this failure is silent, exit 0, which is why section 6 shows the zero-line output next to the correct two-line one.

4. You want the first directory of a path, and sed 's|/.*/||' is giving you the wrong answer. Why, and what is the fix?

.* is greedy, so it stretches to the last slash on the line and you lose everything in between. There is no non-greedy quantifier in sed. Use a negated class that cannot cross a slash: sed 's|^/\([^/]*\)/.*|\1|', which captures the characters up to the first slash. This is the single most useful idiom in the chapter.

5. Does the order of alternatives in (ab|abcd) change which one matches?

No. Section 7 measured it: at the same starting position, the longest alternative wins regardless of the order they are written in — ab|abcd matched abcd on the line abcd. What does change the outcome is the starting position: on ab abcd, the earlier short match won. Leftmost first, then longest.

6. Write a command that finds every line of a filelist that is not a comment, not a + option, and not blank.

sed -n '/^[^.+#[:space:]]/p' gets close — it requires the first character to be none of a dot, plus, hash, or whitespace, which also excludes blank lines since an empty line has no first character to match. On filelists/top.f that is one line, the absolute path. The alternative, and usually the clearer one, is to delete what you do not want with negated addresses rather than describing the survivors — which is Chapter 4.4.

10. Summary

• A bracket expression matches one character from a set — [a-z], [0-9], [a-z0-9_]. It never matches more than one character on its own.
• A hyphen is a range in the middle and a literal at the ends. [a-z-] allows hyphens; [a-z-x] is a mistake.
• POSIX classes name sets by meaning — [[:space:]], [[:digit:]], [[:alpha:]]. Prefer [[:space:]] over a literal space because it also covers tabs.
• ^ first inside brackets negates; elsewhere it anchors. [^/] is "not a slash", ^/ is "starts with a slash".
• * means any number, including zero. /^clk*$/ also matches cl.
• Intervals need backslashed braces in basic mode — \{4,\} — and plain braces under -E. Getting that wrong returns nothing with exit 0.
• + and ? are extended-mode only. The portable "one or more" is \{1,\}.
• Matching is leftmost, then longest. Measured separately: the earlier short match beat the later long one, and at a tie the longer alternative won regardless of written order.
• .* is greedy and sed has no non-greedy form. Use [^x]* to stop at the first delimiter — the most useful idiom in this chapter.
• Ask what input would tell two patterns apart, and put a line of it in your fixture. Three chapters in a row have needed it.

You can now describe what text looks like. What you cannot yet control is where on the line it has to appear — and section 7 showed why that matters, since a pattern with no position is free to match inside a longer word. Chapter 4.3 — Anchors and Precise Matching pins patterns down, and it is the chapter that stops a rename of clk from also renaming clk_div and gclk.