grep is one of the smallest programs that routinely exposes a large idea. At the command line it finds a symbol in a codebase, locates a failed request in a log, filters a pipeline, or tests whether a configuration setting exists. Underneath, it connects a practical question about bytes with formal languages, finite automata, compiler construction, and careful algorithm design.

The central problem is simple enough to state without any terminology. We are given some text and a description of what we want to find. Which parts of the text satisfy that description? grep answers this question line by line. Given a pattern \(r\) and input lines \(L_1, \ldots, L_n\), it emits the lines for which \(r\) matches. The newline is its default record separator, so the program can work incrementally: read a record, decide, emit or discard it, and continue. This small design choice is why it fits the Unix pipeline so well.

Begin with one literal string

Suppose the description 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. It is entirely adequate for short strings and makes the desired predicate concrete: at a position \(i\), every character of the pattern must equal the corresponding character of the text.

This is exactly the job of grep -F, whose F means fixed. In this mode punctuation has no hidden meaning:

grep -F 'a.b' file

searches for the three literal characters a, ., and b. That is already useful, but it soon becomes too rigid. A log search might need either warning or error; an identifier might start with a letter and continue with any number of digits; a configuration line might allow an optional minus sign. Listing every acceptable string is impossible when the set is infinite. Before building a language for those descriptions, it helps to see the small command interface through which grep exposes them.

The command interface

The usual form is

grep [options] PATTERN [FILE ...]

If no file is supplied, grep reads standard input. It writes selected lines to standard output and uses its exit status as a compact answer for scripts: 0 means that at least one line was selected, 1 means that none was selected, and 2 denotes an error in GNU grep [1]. This is why a command such as the following works naturally in a shell conditional:

if grep -q '^enabled=true$' settings.conf; then
    start_service
fi

The option -q suppresses normal output and makes the command a boolean test. The anchors ^ and $ say that the whole line, rather than merely a substring, must have the required form.

Some options are so common that they are worth treating as part of the command's vocabulary:

  • grep -n PATTERN FILE prints selected lines with line numbers.
  • grep -i PATTERN FILE ignores case distinctions.
  • grep -v PATTERN FILE selects lines which do not match.
  • grep -c PATTERN FILE counts selected lines.
  • grep -l PATTERN FILES... prints names of files containing a match.
  • grep -r PATTERN DIR searches recursively below a directory.
  • grep -w PATTERN FILE requires a match to be a whole word.
  • grep -x PATTERN FILE requires the pattern to match the entire line.
  • grep -o PATTERN FILE prints each non-empty matched substring rather than its line.
  • grep -A 2 -B 2 PATTERN FILE includes two lines of trailing and leading context.

Patterns should normally be enclosed in single quotes. The shell has its own language: it expands $name, treats * as a filename wildcard, and uses backslashes for quoting. Single quotes hand the pattern to grep intact. Thus grep 'error|warning' app.log means what it appears to mean, whereas an unquoted * could have been expanded by the shell before grep ever sees it.

There are four relevant matching modes in GNU grep [1]. They are not merely convenience switches; they describe different languages and permit different implementations.

Option Pattern language Typical use
-G Basic regular expressions (BRE) The default and the traditional POSIX notation.
-E Extended regular expressions (ERE) Readable alternation, grouping, and repetition.
-F Fixed strings Literal identifiers, messages, and lists of known strings.
-P Perl-compatible regular expressions (PCRE), when supported Features beyond POSIX regular expressions.

For ordinary work, -E is often the most legible choice and -F is often the most appropriate when no pattern structure is needed. grep -F 'a.b' file searches for the three literal characters a, ., and b; without -F, the dot has a special meaning. The historical names egrep and fgrep correspond to grep -E and grep -F, but are obsolete interfaces rather than new ideas [1]. With the interface in place, we can construct the pattern language itself.

Build the language from small operations

A regular expression denotes a set of strings, called a language. Start with a literal: cat denotes the singleton language containing only cat. We now need only three ways to make larger languages from smaller ones.

First, concatenation describes succession. If a describes the string a and b describes b, then ab describes the string obtained by putting them together. Second, alternation describes a choice: cat|dog is the two-string language \(\{\texttt{cat}, \texttt{dog}\}\). Finally, 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.

The core of an extended regular expression can therefore be described recursively. If \(r\) and \(s\) are regular expressions, then so are:

  • A literal character a, which matches the one-character string a.
  • Concatenation rs, which matches a string from \(r\) followed by a string from \(s\).
  • Alternation r|s, which matches a string from either language.
  • Repetition r*, which matches zero or more consecutive strings from \(r\).

The empty expression \(\epsilon\) matches the empty string. 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*). Nothing in this definition mentions a particular programming language or implementation. It is a tiny algebra for sets of strings.

At this point c[ae]t is just convenient notation for cat|cet, and . is shorthand for an alternation over all characters in the current character set. Bracket expressions make another common finite choice compact: [abc] means a|b|c. grep searches for a substring that belongs to the pattern's language unless the pattern is anchored or -x is used.

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:

Form Meaning Example
. Any one character a.c matches abc and a-c.
[abc] One character from a set [aeiou] matches a vowel.
[^abc] One character outside a set [^0-9] matches a non-digit.
[[:digit:]] A POSIX character class Prefer this where locale-aware digit semantics matter.
^, $ Beginning and end of the record ^TODO: begins a line with TODO:.
r*, r+, r? Zero-or-more, one-or-more, optional -?[0-9]+ matches a signed decimal integer.
r{m,n} Bounded repetition [0-9]{4} matches four digits.
r|s Alternation warn|error matches either word.
(r) Grouping (ab)+ matches ab, abab, and so on.

Bracket expressions deserve a little caution. [a-z] is often intended to mean ASCII lowercase letters, but in a non-C locale its interpretation can depend on collation rules. [[:alpha:]], [[:space:]], and related POSIX classes communicate intent more clearly when text is locale-sensitive. Conversely, LC_ALL=C is often chosen for byte-oriented, reproducible processing. Text is never just abstract characters once encodings and locales enter the picture.

Basic regular expressions are largely the same language written with different punctuation. In GNU grep, +, ?, |, (, ), and interval braces are ordinary characters in BRE syntax; their special versions are \+, \?, \|, \(, \), and \{m,n\}. Thus these two commands express the same intention:

grep -E 'colou?r|gray' colours.txt
grep 'colou\?r\|gray' colours.txt

This is an historical accident worth understanding, not a style to emulate. Prefer -E when writing a new human-facing command; use portable BRE syntax when a POSIX environment requires it.

From logic to Unix

The theory predates the command by decades. In 1951 Stephen Cole Kleene introduced regular events and their algebraic notation while studying representations of neural nets and finite automata [3]. The central result now called Kleene's theorem says that the languages described by regular expressions are exactly those recognized by finite automata. Two descriptions that look quite different, symbolic expressions and small state machines, have precisely the same expressive power.

Finite automata became a standard model of computation through the work of Michael Rabin and Dana Scott in the late 1950s. In the 1960s, Ken Thompson brought regular expressions from theory into interactive computing through the QED editor on CTSS, and later carried them into the Unix lineage with Dennis Ritchie [2]. Thompson's 1968 paper, Regular Expression Search Algorithm, gave a practical construction and execution technique [4].

The command name is itself a fossil of the editor interface. In ed, a global command could print every line matching a regular expression:

g/regular expression/p

Written compactly, this was g/re/p, which became grep [1]. The name is not an acronym invented after the fact; it preserves a command sequence from line editing.

By the late 1970s, regular expressions had become common infrastructure in Unix: ed, sed, grep, awk, and lex all used them [2]. That adoption was unusually fruitful because the interface was small enough to fit on a command line, while its semantics rested on a mature theory. A shell pipeline can use a single pattern to describe a potentially infinite family of strings, and an automaton can apply that description one record at a time without first collecting the whole input.

What a matcher must remember

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.

The direct construction becomes awkward as soon as the expression contains a choice. For a(b|c)d, should the state after a be described as "waiting for b" or "waiting for c"? Both are true. 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. An NFA 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.

The equivalence is constructive. Given an NFA, create a DFA state for each set of NFA states that could be active after a prefix. The start state is the \(\epsilon\)-closure of the NFA start state: all states reachable without consuming input. On a character \(c\), move every active NFA state along its \(c\)-labelled transitions, then take the \(\epsilon\)-closure again. A DFA state is accepting when its represented set includes an accepting NFA state.

There can be up to \(2^{|Q|}\) such subsets, which is a genuine worst-case exponential expansion. This is not a contradiction of the equivalence; it shows that a compact nondeterministic description can correspond to a large deterministic machine. Practical engines often construct only the subsets they actually encounter, cache them, or choose an NFA simulation when that trade-off is better.

Regular expressions are not all "regex"

The finite-state account identifies an important boundary. The word regex has acquired a much broader meaning: 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 the clearest boundary case. 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\), made by repeating 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.

The distinction is practical. Pure regular expressions admit matching algorithms with reliable time bounds. Backreferences make useful comparisons possible, but require retaining the matched text and can force a matcher into search. GNU grep documents this directly: its fast automata handle ordinary cases, while unusual features such as backreferences invoke a slower matcher; backreferences can create exponentially many possibilities [1]. The notation may look almost identical, while the computational problem has changed category.

Thompson's construction and simulation

Thompson's construction converts a regular expression into an \(\epsilon\)-NFA by composing small fragments. A literal a becomes one transition labelled a. Concatenation connects the accepting edge of one fragment to the start of the next. Alternation creates a split state with an \(\epsilon\)-edge to each alternative. A star creates a split that either enters the repeated fragment or bypasses it, and connects the fragment's end back to the split. The graph for a(b|c)*d is therefore not guessed by a clever global procedure: it is assembled from four local rules, one for each kind of expression node.

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].

The remaining question is how to execute an NFA without trying one path, failing, and then trying another. Thompson's answer is to 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. 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 hides implementation details, but not the central insight: represent all viable paths by their current states, not by a growing collection of path histories. An NFA with \(m\) states can have exponentially many paths, yet there are only \(m\) states to retain at any instant. A straightforward simulation takes \(O(mn)\) time for a pattern of length \(m\) and input of length \(n\), with space proportional to the automaton [2]. For a fixed pattern, this is linear in the input size.

This approach also explains why a familiar bad pattern is not intrinsically dangerous. Consider a pattern with \(k\) optional a expressions followed by \(k\) required a expressions, applied to exactly \(k\) a characters. A backtracking engine that tries the optional matches first has \(2^k\) possible decisions about which optional expressions consume an a; only the last choice, where all are skipped, leaves enough input for the required suffix. A Thompson simulation keeps the possible states together and takes \(O(k^2)\) time for this growing pattern and input, rather than exponential time [2].

Backtracking and its consequences

Backtracking is another way to execute the same NFA. At a choice, an engine chooses one branch, records enough information to return, and tries the branch. On failure it restores the saved position and attempts the next one. It is compact, supports captures naturally, and gives a straightforward interpretation to ordered alternatives and greedy or lazy repetition. It is also a search procedure.

For a pattern containing nested ambiguous repetition, the search tree can become enormous. The important variable is not only the input length but the number of nearly plausible ways to divide the input among repeated pieces. A matcher may need to visit every such possibility before it can prove that no path matches. This failure mode is commonly called catastrophic backtracking, and when an attacker can provide both or influence the input it can become a regular-expression denial of service vulnerability.

Backtracking is not inherently wrong. It is the natural cost of offering features that depend on a particular path through the match, especially backreferences. The engineering mistake is to assume that every pattern language and every engine has the same complexity guarantees. A matcher intended for untrusted, large, or latency-sensitive input should make its language and algorithmic limits explicit.

The semantics differ too. POSIX regular expressions specify a leftmost-longest rule: select the earliest match, and among matches beginning there, the longest one. Many Perl-style engines are leftmost-first: alternatives are attempted in source order, and the first successful path determines the match. For line selection this distinction is often invisible. For capture groups, replacement, and -o, it can be material. A regular expression is therefore not a portable program independent of its engine; syntax, matching policy, locale, and record model belong to its meaning.

Returning to fixed strings

The literal-search problem with which we began has more structure than the naive comparison algorithm uses. For one fixed pattern, an implementation may use Boyer-Moore search. Rather than comparing the pattern from left to right at every text position, Boyer-Moore compares from the end and uses a mismatch to establish that several intervening starting positions cannot work, then skips ahead by that distance [5]. Its worst case remains linear with suitable refinements, but its practical attraction is that ordinary text often permits large jumps.

For multiple literal patterns, the Aho-Corasick algorithm 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 [6].

GNU grep documents both optimizations: when feasible it uses Boyer-Moore for a single fixed pattern and Aho-Corasick for multiple fixed patterns, while its general regular-expression path uses automata and delegates features such as backreferences to a slower matcher [1]. The command-line switch is therefore more than a request for different punctuation. -F tells the program a stronger fact about the problem, and strong facts allow better algorithms.

A disciplined way to write patterns

Patterns are programs in miniature. They benefit from the same habits as other programs.

  1. State the desired record boundary. Use ^...$ or -x when a whole line must conform; otherwise a substring match can accept accidental context.
  2. Use -F for literal text. It improves clarity, avoids escaping, and may unlock faster matching.
  3. Use -E for conventional regular structure. Group alternatives deliberately: ^(debug|info|warn|error)$ is less ambiguous than an unanchored list of words.
  4. Quote patterns at the shell boundary. Single quotes prevent a second language from rewriting the first.
  5. Keep locale in mind. Prefer POSIX character classes when their semantics are wanted, and choose LC_ALL=C deliberately when byte semantics are wanted.
  6. Avoid backreferences and elaborate PCRE features unless they are genuinely necessary. Their compact notation can conceal a qualitatively harder problem.
  7. Test a negative case. The question is rarely just whether the intended string matches; it is whether a near miss is rejected.

For example, suppose a log format is exactly an ISO date, a severity, and a message:

2026-07-21 ERROR database connection timed out

A useful first pattern is

grep -E '^[0-9]{4}-[0-9]{2}-[0-9]{2} (DEBUG|INFO|WARN|ERROR) .+$' app.log

It does not establish that the date exists on a calendar or that the message is semantically meaningful. Regular expressions are excellent at local lexical structure, not at every form of validation. The right response to that boundary is not to force all parsing into a single pattern. It is to use the smallest formalism that expresses the property at hand, then pass structured fields to a parser when the structure becomes recursive, arithmetic, or context-dependent.

Closing perspective

grep remains useful because it occupies a carefully chosen level of abstraction. It does not need to understand a programming language in order to find an identifier, nor to build a database in order to filter a log stream. It exposes a language for local structure, an interface for composing processes, and an implementation path backed by finite automata.

There is a satisfying continuity here. A few algebraic operators define a family of strings; the same operators compile into a graph; the graph becomes a small evolving set of states; and that state set selects lines from a live stream of bytes. The command is terse because the mathematics is doing real work beneath it. Knowing where that mathematics applies, and where extensions escape it, is what turns a convenient shell habit into a dependable engineering tool.

References

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