Searching with Regular Expressions

Suppose you want a program to find every place a particular shape of text appears inside a larger document. The shape might be a sequence of digits followed by a dot, or a word that starts with a capital letter. A regular expression is the compact notation that describes such a shape. Writing the notation is the easy part. The harder question is how a program can check text against that description quickly, no matter how long the text is.

The source gives a direct answer to that harder question. The syntax and meaning of regular expressions were designed so that each expression can be converted into a state machine, and that state machine can then be run efficiently against input. This article follows that idea through three questions: what the conversion produces, when the conversion happens, and which flavor of notation the source's library accepts.

The key phrase is exactly one state. At every moment the machine occupies a single state, and the next state is determined entirely by the current state and the next character. There is no lookahead into the whole input and no backtracking described in the source. The machine simply reads, moves, and at the end checks whether it is sitting in an accepting state.

The source illustrates the general control flow with the pattern ab. The machine starts in an initial state. For each character, it follows the transition that matches that character. If no transition applies, the machine cannot continue along that path. If the input ends while the machine sits in an accepting state, the input matches. The following illustration is a generated teaching example that shows one possible machine for the pattern ab. It is not a claim about the exact internal layout any particular library builds.

The important move is a change of representation. The regular expression is a description written as text. The state machine is a set of states and transitions that a program can follow step by step. The source says the regular expression syntax and semantics were designed so this change is possible, and that the resulting machine supports efficient execution.

In other words, the matching work is done by walking a machine, not by re-reading the description of the pattern each time a character is examined. Once the pattern has become a machine, each input character causes one transition, and the machine's current state carries all the information needed to decide what comes next. The source describes this efficiency qualitatively; it does not give timing figures, so the benefit to learn here is the structure of the work, not a measured speed.

The source is specific about timing. The regular expression type performs the compilation at run time. The conversion from pattern to state machine is carried out while the program is running, not as a separate step performed ahead of time on the pattern text. The compiled form therefore belongs to the running program and is produced from the pattern it is given.

The timeline below orders these steps. The source places the conversion inside the running program, and then places the search, which runs the machine over the input from left to right, after the machine exists. The source does not go further than this, so the timeline makes no claim about caching, reuse across calls, or the details of the conversion algorithm.

A match can also fail. Using the same generated machine for ab, consider the input ax. The machine starts in State 0 and reads a, moving to State 1. In State 1, the only transition in this machine is for b. The character x has no transition that applies, so the machine cannot continue along that path. The input does not match.

Regular expression notation is not one single standard that every tool reads in exactly the same way. The source notes that the regular expression library can recognize several variants of the notation. A pattern therefore depends on which variant the library is set to read, even though the underlying idea of describing a text shape stays the same.

The source names its default. It uses a variant of the ECMA standard, the standard used for ECMAScript, which is more commonly known as JavaScript. When the source writes its patterns, this is the notation it is using. If you carry a pattern from one tool to another, check which variant each one expects before assuming the same text means the same thing.