Grep and the Theory of Pattern Matching

grep is one of those small programs that expose a large idea. It can find symbols in codebases, locate failed requests in a log, filter pipelines, or test whether a configuration setting exists. The central problem is simple enough: we are given some text, and a description of what we want to find. grep is what solves this line by line. The newline is its default record separator, so the program can work incrementally: read a record, decide whether to emit or discard it based on the description, and continue. This small design choice is why it fits the Unix pipeline so well. Underneath, it hides interesting connections to formal languages, finite automata, compiler construction, and careful algorithm design. Let's explore.

First steps. Suppose the description, also called pattern, we're looking for is just the word error. The direct solution is to align the pattern against every possible position in a line, compare the characters one by one, and stop at the first complete agreement. For text of length \(n\) and a pattern of length \(m\), this elementary algorithm performs at most \(O(mn)\) comparisons. To find a match at position \(i\), every character of the pattern (e,r,r,o,r) must literally equal the corresponding character of the text. This is the job of grep -F, whose F means fixed. In this mode punctuation has no hidden meaning.

That is already useful, but it soon becomes too rigid. Sometimes what we want to find is best described through its structure. And this structure may be shared by many strings, too many to enumerate. So we need to build a language for those descriptions.

Regexes. A regular expression (regex) denotes a set of strings, called a language. The term comes from linguistics and formal systems, where a language is a particular set of strings over an alphabet of symbols. We build descriptions of regular languages from a few small rules that tell us how to construct new strings that belong to the language. For regular expressions, we start with a literal: abc denotes the singleton language containing only abc. We now need rules to make larger languages from smaller ones.

1. Concatenation describes succession - one string following another. If a and b are descriptions of strings, then ab describes the string obtained by putting them together.
2. Alternation describes a choice: cat|dog is the two-string language \(\{\texttt{cat}, \texttt{dog}\}\).
3. Repeated structure requires a way to say "again": ab* describes a followed by zero or more b characters. The single symbol * replaces an infinite list: a, ab, abb, abbb, and so on.

That's all we need: sequential structure, choice, and repetition. The core of an extended regular expression can therefore be described recursively. If \(r\) and \(s\) are regular expressions, then so are concatenation rs, which matches a string from \(r\) followed by a string from \(s\), alternation r|s, repetition r*, as well as any literal character a, which matches the one-character string a.

Why do we need repetition? Can't we describe it through concatenation? Well, for example, if you want to recognize only \(\{\texttt{a}, \texttt{aa}\}\), then your regex would be just a|aa. But if you want to recognize a language with an arbitrary number of \(\texttt{a}\)-s, including zero, you can't write ε|a|aa|aaa|.... That'd be an infinitely long regex. For those cases we have the repetition rule a*. It means the pattern accepts strings with arbitrarily many, but always finitely many, repetitions.

Convenient notation. From this small basis follow the familiar abbreviations r+ for one or more copies, r? for zero or one copy, and r{m,n} for between \(m\) and \(n\) copies. The zero-or-more operation is the Kleene star. Parentheses control grouping. As in arithmetic, precedence matters: ab|cd means (ab)|(cd), while ab* means a(b*). A bracket expression can also denote alternation in a more compact way: [abc] means a|b|c. We let . be a shorthand for an alternation over all characters in the current character set. Using these the regex a(b|c)*d describes the language \(\{\texttt{ad}, \texttt{abd}, \texttt{acd}, \texttt{abcd}, \texttt{acbd}, \texttt{abbd}, ...\}\).

Grep. The command-line utility grep is what realizes the above ideas in practice and brings in additional conveniences related to line matching and output formatting. The usual form is

grep [options] PATTERN [FILE ...]

It can read from stdin and writes selected lines to stdout. Its exit status (0 if any match is found, 1 if no matches are found, 2 for errors in GNU grep [1]) can be used as a conditional in scripts. Various options customize its behaviour. It can print line numbers (-n), ignore case distinctions (-i), select lines which don't match (-v), search recursively below a directory (-r), require a match to be a whole word (-w) or a whole line (-x), include context (-C) and so on.

Patterns should normally be enclosed in single quotes so the shell doesn't expand variables like $name, or treat * as a filename wildcard. There are four relevant matching modes in GNU grep [1]. They describe different languages and permit different implementations.

grep -F 'a.b' will match only the string a.b. The BRE version will match any 3-character string starting with a and ending with b. But in BRE +, ?, |, (, ), {, } are ordinary characters, and their special versions are \+, \?, \|, \(, \), \{, \}. In ERE we don't need to escape them. For new patterns with regular-expression structure, ERE is usually the most readable choice; use -F when the pattern is entirely literal. An ERE such as

^(GET|POST|PUT) /api/v[0-9]+/users/[0-9]+$

matches a complete request line with one of three methods, a version number, and a numeric user identifier. Its pieces illustrate most of the practical syntax.

Locale issues. Text is never just abstract characters once encodings and locales enter the picture. Consider a very simple experiment. We create a file containing ASCII a and é. In UTF-8, é is one character but is encoded as two bytes. Assuming GNU grep is running in an available UTF-8 locale, . treats each input character as one match, so both lines satisfy -x .. Under the C locale, grep uses byte-oriented character semantics: the dot can match only one byte, so the two-byte é line no longer matches the whole-line pattern.

printf 'a\né\n' > characters.txt

grep -n -x '.' characters.txt
# 1:a
# 2:é

LC_ALL=C grep -n -x '.' characters.txt
# 1:a

With a suitable UTF-8 locale, both [[:alpha:]] and [a-z] operate on characters rather than UTF-8 bytes. They nevertheless express different properties. [[:alpha:]] asks whether a character is alphabetic according to the locale, so it can match é. [a-z] asks whether a character lies in the locale-dependent ordered range from a to z; it is not a synonym for “lowercase letter,” and its membership can vary with collation rules. Under LC_ALL=C, [a-z] has its familiar stable ASCII meaning, while [[:alpha:]] recognizes only ASCII letters.

History. The theory predates the command by decades. In the 1950s, Stephen Kleene introduced an algebra of “regular events” (what we now call regular languages), and Kleene's theorem established that regular expressions and finite automata describe exactly the same class of languages. In the 1960s, Ken Thompson brought regular expressions into interactive computing through the QED editor on CTSS, then into the Unix lineage with Dennis Ritchie; his 1968 paper described a practical regular-expression search algorithm [3].

The name grep comes from line editing. In ed, g/re/p meant “globally print lines matching a regular expression,” and its compressed spelling became the command’s name. By the late 1970s, regular expressions had become shared infrastructure across Unix tools including ed, sed, grep, awk, and lex. Their success came from pairing a compact command-line notation with a mature theory and an implementation that could process text incrementally, a record at a time.

Pattern recognition. To recognize ab*c, we do not need to preserve the entire prefix already read. We only need to know which of a few situations we are in: no useful prefix has appeared, an a has appeared and any number of bs may follow, or a final c has completed the pattern. The next character determines how this small piece of information changes. A character other than a cannot begin the match; after a, another b keeps us in the middle; after a c we have a match.

This is a state machine. A deterministic finite automaton (DFA) consists of a finite set of states \(Q\), an alphabet \(\Sigma\), a transition function \(\delta: Q \times \Sigma \rightarrow Q\), an initial state \(q_0\), and a set \(F \subseteq Q\) of accepting states. It reads one input character at a time. After reading a prefix, it has exactly one current state. If the state after the final character belongs to \(F\), the input is accepted. Its entire memory is that current state. That is the meaning of finite: no stack, no unbounded buffer, and no record of an arbitrarily long prefix.

This gives a direct algorithm. Start at \(q_0\); on every character \(c\), replace the current state \(q\) with \(\delta(q,c)\); accept if the final state belongs to \(F\). Once a DFA has been built, it performs one transition per input character. The interesting work has moved into the construction of the states and their transitions.

NFAs. A direct construction can become awkward when choice and repetition leave many partial matches viable at once. For (a|b)*a(a|b){n-1}, which recognizes binary strings whose \(n\)-th character from the end is a, a state after a long prefix would have to remember every possible a among the last \(n\) positions. A nondeterministic finite automaton (NFA) makes this representation explicit: it permits several possible next states for a state and character, and may have \(\epsilon\)-transitions which consume no input character. It accepts if some path from the start to an accepting state consumes the input. This sounds more powerful, but it is not: every NFA has an equivalent DFA. The difference is representation. NFAs are compact and follow the expression's syntax; DFAs make every next step unambiguous.

For this example, the difference is numerical. An NFA needs only \(n+1\) states: one state scans an arbitrary prefix, and each a may start a chain that counts the remaining \(n-1\) characters. A DFA must instead retain the last \(n\) bits of input. It therefore needs \(2^n\) states for the possible length-\(n\) suffixes, plus shorter start-up states; a straightforward construction has \(1+2+4+\cdots+2^n\) states. For \(n=3\), the NFA has four states, while the DFA has \(15\), as shown in Fig. 2. Every NFA can nevertheless be transformed into an equivalent DFA. Practical matchers often construct only the states they encounter, cache them, or simulate the NFA directly when that is the better trade-off.

Beyond classical regex. Modern engines commonly add look-around assertions, lazy quantifiers, conditionals, named captures, Unicode properties, and backreferences. These can be convenient, but they are not all properties of the mathematical object introduced by regular-language theory.

A backreference is a good example. In (cat|dog)\1, \1 means "the exact string that the first parenthesized subexpression matched". It matches catcat and dogdog, but not catdog. The general form describes strings \(ww\), for an arbitrary string \(w\). To see why finite memory is insufficient, imagine a DFA with \(q\) states. There are more than \(q\) distinct binary strings, so two different prefixes \(x\) and \(y\) must leave the machine in the same state. Appending \(x\) should make the machine accept \(xx\), but from the identical state it would also accept \(yx\), even though \(y \ne x\). This contradiction shows that \(\{ww \mid w \in \{a,b\}^*\}\) is not regular.

Backreferences make useful comparisons possible, but require retaining the matched text and can force a matcher into search. GNU grep documents that its fast automata handle ordinary cases, while unusual features such as backreferences invoke a slower matcher [1].

NFA construction. Given a regex, how do we construct the NFA for it? Ken Thompson provided one algorithm for this. It's basically a tiny compiler that turns a regex's syntax tree into a directed graph. An NFA state is a node in the graph. An edge is a directed arrow from one state to another. Edges can be character-labeled (an a edge can be crossed only by consuming the character a) or ε-labeled (can be crossed without consuming a character). A fragment is an unfinished, reusable piece of the graph, representing a subexpression. It has an entry state and one or more unfinished outgoing edges, to connect to whatever comes next. Here's how the basic operations look like.

Literal: a
start ──a──> exit

Concatenation: rs
r-start ── r fragment ──> r-exit ─ε─> s-start ── s fragment ──> s-exit

Alternation: r|s
                  ┌─ε─> r fragment ─ε─┐
start ──ε split ──┤                   ├─ε─> exit
                  └─ε─> s fragment ─ε─┘

Star: r*
                  ┌─ε─> r fragment ─ε─┐
start ──ε split ──┤                   ├── back to split
                  └─ε─────────────────┘
                          skip r

The construction follows the syntax tree so directly that it is nearly a proof by induction. Each rule preserves the language denoted by the corresponding expression. It uses at most one state per character or metacharacter, apart from grouping syntax, so an expression of length \(m\) produces an NFA of size \(O(m)\) [2].

NFA execution. Once we've constructed the NFA, how do we execute it without trying one path, failing, and then trying another? We keep a set of active states. Initially this is the \(\epsilon\)-closure of the start state: all states reachable before consuming a character. For each input character, advance every active state whose transition accepts that character, collect its successor, and close the resulting set under \(\epsilon\)-transitions (i.e, add any other states that are reachable by taking zero or more ε-edges). If an accepting state is active at the relevant point, the expression matches.

active = epsilon_closure({start})
for character in input:
    next = {}
    for state in active:
        if state has a transition accepting character:
            next.add(state.successor)
    active = epsilon_closure(next)
accept if active contains a final state

The pseudocode recognizes a complete input string. A simple modification, which we don't show here, can make it search within the line, acting more like the command-line grep.

Computational complexity. Thus, an NFA with \(m\) states can have exponentially many paths, yet there are only \(m\) states to retain at any instant. Let the search pattern be of length \(m\) and the input text of length \(n\). Then the NFA construction takes \(O(m)\) time and \(O(m)\) space for the graph, while the simulation takes \(O(mn)\) time and \(O(m)\) of additional space for the set of active states. For comparison, an equivalent DFA takes \(O(n)\) time and \(O(1)\) space to scan the text once constructed, but may require up to \(2^m\) states and therefore exponential construction time and space.

Backtracking. Backtracking is another way to execute the same NFA. At each choice, an engine selects a branch, saves enough state to return, and tries it; on failure it restores that state and tries the next branch. This compact approach supports captures, ordered alternatives, and greedy or lazy repetition naturally, but nested ambiguous repetition can create an enormous search tree. A matcher may have to examine every nearly plausible way to divide the input among repeated pieces before proving that no path matches: catastrophic backtracking. When an attacker can influence the input, this can become a regular-expression denial of service vulnerability.

Note that there can be noticeable differences in the output produced from different pattern languages and engines. POSIX standardizes the result of matching, not the algorithm used to produce it. It requires a leftmost-longest result. So if you're matching (a|ab) in the text ab it should find ab. Many Perl-style engines are leftmost-first, so they'd match a. This difference can produce different capture groups which will affect backreferences (\1, \2, ...).

Back to fixed search. Our initial setting, where we search over a literal string, has more structure than the naive comparison algorithm uses. For one fixed pattern, an efficient algorithm is Boyer-Moore search. Suppose we're looking for ERROR in 12345ERROR. We place the pattern at index \(0\) first and start comparing 12345 and ERROR. We compare from right to left. We know that 5 occurs nowhere in the pattern (this requires preprocessing). If we shift the pattern to any index \(1\), \(2\), \(3\), or \(4\) it will still line up to some wrong character of the pattern. So we can directly skip these indices. That's the basic kind of jump the algorithm provides [4]. It has broad similarities to KMP.

Multiple patterns. Sometimes we're looking for multiple patterns, passed as -e PATTERN or -f PATTERN_FILE. With \(N\) of them, do we have to do \(N\) independent search runs? No. That's where the Aho-Corasick algorithm comes in. It constructs a trie of all patterns and augments it with failure links. As each character is read, the automaton follows a trie edge when possible and otherwise falls back through failure links to the longest suffix that remains a viable prefix. The resulting automaton finds all occurrences in time linear in the text plus the number of matches, after preprocessing the pattern set [5].

Suppose we're looking for 4 patterns: he, she, his, hers. We construct a trie that looks like this.

root
├── h ── e* ── r ── s*
│    └── i ── s*
└── s ── h ── e*

The * marks the end of a pattern. Now we scan ushers character by character and move along the trie accordingly. At the e we recognize the pattern she. But the algorithm has also precomputed a failure link failure(she) = he so it also recognizes he. Continuing through rs, it finally reports hers.

GNU grep uses Boyer-Moore for a single fixed pattern and Aho-Corasick for multiple fixed patterns. For general regular-expressions it uses automata, specifically something called a lazy DFA. The idea is to construct the NFA and directly start executing a DFA, building it as you go. For example, suppose after constructing the NFA the initial epsilon closure is \(d_0 = \{q_0, q_1, q_4\}\). A character \(c\) comes in. We don't know the DFA transition \(\delta(d_0, c)\), so we process the character according to the NFA, which provides the next state, say \(\{q_2, q_5\}\). Now we let \(d_1\) represent \(\{q_2, q_5 \}\), set \(\delta(d_0, c) = d_1\), cache (memoize) it, and continue. In this way we're building the DFA on the fly and reusing the past transitions. That's how a lazy DFA works. More advanced features such as backreferences are delegated to a slower matcher [1]. In general, the command-line switch -F is therefore more than a request for different punctuation. It tells the program a stronger fact about the problem, and strong facts allow better algorithms.

Conclusion. grep turns a compact description of local text structure into a stream of useful results, one record at a time. Its power comes from matching the problem to the right abstraction: finite automata for regular patterns, and specialized algorithms for fixed strings. But it searches lexical records, not structured files or programs; nested syntax, scopes, types, and semantics require a parser. Use grep -F for literals, grep -E for ordinary regular structure, and a more structured tool when the data demands one.

References

[1] GNU Project. GNU Grep Manual.
[2] Russ Cox. Regular Expression Matching Can Be Simple And Fast (2007).
[3] Ken Thompson. Regular Expression Search Algorithm. Communications of the ACM, 11(6), 419-422 (1968).
[4] Robert S. Boyer and J Strother Moore. A Fast String Searching Algorithm. Communications of the ACM, 20(10), 762-772 (1977).
[5] Alfred V. Aho and Margaret J. Corasick. Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM, 18(6), 333-340 (1975).