Matching Patterns in Streams

Suppose you have a long run of text and you want to know whether a particular piece of it appears somewhere inside. For a short note, you can read the whole thing by eye. That approach becomes impractical for a log file, a long document, or a stream of incoming input. A regular expression gives you a way to describe the piece you are looking for and then ask a program to locate it.

The simplest use of a pattern is to search for it in a stream. Everything else in regular expression work builds on this one idea, so it is worth understanding slowly before adding any complexity. Keep the example below in mind as you read: a pattern is a plain word, and the stream contains that word somewhere in the middle.

The two words in this topic play different roles, and mixing them up makes every later result harder to read. The pattern is the thing you are looking for. The stream is the text in which you look for it. The search is the act that brings the two together. A search does not ask what the stream contains in general; it asks a narrower question about one specific pattern.

The word stream suggests text that is read in order rather than inspected all at once. A helpful picture is a line of characters with a reader moving steadily along it, one character after another. The source does not explain how this reading is implemented in any particular engine, so treat this picture as a way to hold the idea in mind rather than as a description of the internal machinery.

Follow the reader through the stream 'the cat sat' while searching for the pattern cat. Each step shows one character that has just been read and what it is being compared with. The first few characters do not match the first character of the pattern, so the reader keeps moving. When the reader reaches the c of cat, the comparison begins to succeed, and the next characters must continue to agree with the pattern in order.

The diagram is a picture of one progression through the stream, not a claim about how every search works. The key idea it carries is that the pattern is compared against the text as the text is read, and the search moves forward along the stream as it goes.

The simplest form of a regular expression search uses a plain pattern, which is a sequence of literal characters. A plain pattern is found only when its exact characters occur in order in the stream. Each character of the pattern must agree with a character of the stream, and the agreeing characters must follow one another without anything else being required by the pattern.

Once a match is found, it occupies particular positions in the stream. Counting from zero, the stream 'the cat sat' has the character t at position 0, h at position 1, e at position 2, a space at position 3, c at position 4, a at position 5, t at position 6, and so on. The pattern cat therefore occupies positions 4 through 6. The diagram lines up each stream character with its position so you can see which positions the match covers.

Notice that the t at position 10 is also a t, but it does not complete the pattern because the characters before it are not c and a in order. A match is about the whole pattern occurring as a block of characters in order, not about any single character agreeing.

Now try a pattern that the stream does not contain. Searching the same stream 'the cat sat' for dog produces no match. The reader moves to the end of the stream without finding d, o, g in order. At that point the search has shown that the pattern is absent. This is a complete and valid answer to the question the search asks, and it is the same kind of outcome as a success, just with the opposite value.

The flowchart is a simplified picture of the two possible endings. Either the pattern is located, or the stream runs out with no match. Both endings produce a result, and the no-match result is the one that tells you the pattern is absent from the stream.