Regular Expression Complexity
Counts the operators in a regular expression and computes Ehrenfeucht and Zeiger's four complexity measures: the tool behind the FIRE/J paper's operator table.
A small command-line tool, and a Java library, that measures regular expressions. It counts the operators each expression uses and computes the four complexity measures of Ehrenfeucht and Zeiger (Journal of Computer and System Sciences, 1976). The operator count is the one behind the occurrence table in the FIRE/J paper (Software: Practice and Experience, 2008), whose evaluation used two of the four measures, size and length, to line its benchmark expressions up. The tool now reports all four, and it was published in October 2026.
The four measures
Size (N) is the number of alphabet symbols written in the expression. Star height (H) is how deep unbounded repetition is nested. Length (L) is the longest path that does not go around a loop. Width (W) is the dual of length. Each is defined for a symbol, a union, a concatenation and a star, and everything else follows:
| Expression | N | H | L | W |
|---|---|---|---|---|
ab|c | 3 | 0 | 2 | 2 |
(a|b)(c|d|e) | 5 | 0 | 2 | 3 |
(a*)* | 1 | 2 | 1 | 1 |
(a*)(b*) | 2 | 1 | 2 | 1 |
[a-z]+ | 26 | 1 | 1 | 26 |
a{10} | 1 | 0 | 1 | 1 |
[a-z] is a union of 26 symbols, so it is 26 wide and 1 long. (a*)(b*) has star height 1 because its two stars sit side by side, while (a*)* has height 2 because one contains the other.
Using it
Build it with ant on any JDK; there are no other dependencies. Give it one expression with -e, or files of one expression per line, or standard input:
$ java -cp build org.fire.complexity.RegexComplexity -e '(ab|c)*' (ab|c)* Size (N) = 3 Star height (H) = 1 Length (L) = 2 Width (W) = 2 Star (*) = 1 Plus (+) = 0 Dot (.) = 0 Question (?) = 0 Or (|) = 1 Character Classes ([]) = 0 Groups ( () ) = 1
With two or more expressions it prints the averages, and -v prints each expression as well. A syntax error is reported with its line, and the rest are still counted.
Where it stops
- It measures the expression as written. Ehrenfeucht and Zeiger also define the complexity of a language, as the minimum over every expression for it; the tool does not search for a smaller expression.
- A few counting choices are its own. A quantifier does not copy its body (
a{10}is size 1), complements are taken over ASCII ([^a]is 127), the dot is one symbol, and case flags do not multiply letters. - What it cannot size, it rejects.
\p{L},\Rand\Xget an error rather than a made-up number. - It is not a ReDoS detector. Star height 2 is a property of the expression, not a verdict on the engine that runs it.
It is written up in a post on the blog.
Source
Apache License 2.0. Its tests check every character class against the ASCII characters java.util.regex itself accepts.