Regular expressions: the core syntax

In 1966 Joseph Weizenbaum at MIT published a program that imitated a Rogerian psychotherapist, the kind of therapist who reflects the patient's own words back as questions. He called it ELIZA. Read the exchange below as a patient would have, one line at a time.

It reads like attention. It is not. The whole program is a list of keywords, and for each keyword a small set of decomposition rules that split the input around the keyword, paired with reassembly rules that build a reply out of the pieces. Weizenbaum wrote the rules in his own notation. A decomposition rule such as (0 YOU 0 ME) means "an indefinite number of words, then YOU, then an indefinite number of words, then ME", and its reassembly rule (WHAT MAKES YOU THINK I 3 YOU) inserts the third component, whatever words stood between YOU and ME, into a fixed frame (Weizenbaum, 1966, p. 38). The dictionary he had built "so far" contained about 50 keywords. Nothing is parsed, nothing is understood, and the program has no memory of what "mother" means beyond the fact that it is filed under FAMILY.

Jurafsky and Martin rewrite the same idea in modern regular expression syntax, and this is the version to remember. After the input is uppercased and pronouns are swapped (I'M becomes YOU ARE, MY becomes YOUR), rules like these run in order until one fires (SLP3, section 2.6.7):

• re.sub(r".* YOU ARE (DEPRESSED|SAD) .*", r"I AM SORRY TO HEAR YOU ARE \1", input)
• re.sub(r".* ALWAYS .*", r"CAN YOU THINK OF A SPECIFIC EXAMPLE", input)

The parentheses and the \1 are a capture group and a Backreference, which the next part treats properly. For now the point is the shape of the machine: a keyword selects a rule, a pattern with wildcards splits the sentence, a frame reassembles the pieces. Weizenbaum's paper opens with the exchange "Men are all alike." answered by "IN WHAT WAY", and the reply is not about men at all: a rule keyed on the wording of the input prints a fixed question with no slot to fill.

Why people believed it

Crude as the rules were, SLP3 notes that many people who talked to ELIZA came to believe that it really understood them, and that this led researchers to think for the first time about the impact of chatbots on their users (Weizenbaum, 1976). The effect now carries the program's name. The Eliza effect is the tendency to unconsciously assume that computer behaviors are analogous to human behaviors. Douglas Hofstadter defines its specific form as our susceptibility to read far more understanding than is warranted into strings of symbols strung together by computers (Hofstadter, 1995). The standard illustration is not a chatbot at all but a cash machine that prints THANK YOU at the end of a transaction, which a naive observer might take for real gratitude. ELIZA exploited the same reflex at conversational scale: because it echoed your own words, every reply seemed relevant, and relevance felt like understanding.

What regex is for in an NLP pipeline

A regular expression is fast, flexible pattern matching for text. It needs no training data, and it is precise in a way a learned model cannot be: a pattern either matches or it does not, and you can read off why. The slide lists four jobs, and it is worth having a concrete example ready for each.

The slide's last line matters more than it looks: regex is language- and task-dependent. A class like [a-z] says nothing about Arabic letters. A word boundary \b assumes words are made of letters, digits and underscores separated by something else, which fails outright for Chinese, where there are no spaces, and quietly misbehaves for Arabic under an ASCII-only definition of "letter". Recall the typology in part 04: an isolating language and a templatic one need different patterns for the same task, and a pattern tuned for tweets will not fit legal text. Regex gives you precision; it does not give you generality for free.

Start with the simplest pattern there is. The regex Buttercup matches the substring Buttercup in "I'm called little Buttercup" and nowhere else (SLP3, section 2.6.1). Each letter is a literal that matches itself, and writing letters one after another means "this, then this, then this". That is concatenation, and abc matches exactly the three characters abc in that order.

Two more operators complete the algebra on slide 58. The vertical bar is disjunction: a|b matches either a or b. Parentheses group and define scope, so gupp(y|ies) matches guppy or guppies, while guppy|ies would match guppy or the bare string ies, because the bar has the lowest precedence of all and splits the whole pattern into two halves (SLP3, section 2.6.4). Regex is case sensitive throughout: s does not match S. Concatenation, disjunction and the Kleene star, which the next concept introduces, are the three operations that define regular languages in theory of computation. Parentheses only set scope, and classes, ranges, +, ? and counted repetition are all shorthand built from those three.

The square-bracket class

Disjunction between single characters is so common that it has its own notation. A Character class in square brackets matches exactly one character from the set it lists. This is the fix for case sensitivity: [mM]ary matches Mary or mary. Read every row of the next three tables as the slides present them, pattern, meaning, and the first match marked in the example string.

Look closely at the second row. "In uomini" contains no a, b or c, so the first match is the a in soldati, eighteen characters in. A class matches one character, so a bracket never matches "abc" as a word; SLP3 asks why [catdog] does not mean cat or dog, and the answer is the same: it is one character drawn from c, a, t, d, o, g. Listing every digit is tedious, so a dash inside brackets gives a range in code point order: [0-9], [a-z], [A-Z], but also [2-5] or [b-g].

The caret is the last bracket operator, and it is the one that trips people. When the caret is the first character inside brackets, the class is negated and matches any single character not in the set. Anywhere else inside brackets it is an ordinary caret. Python's documentation states both halves: the caret "has no special meaning if it's not the first character in the set", and [^^] matches any character except a caret.

Notice also that the third row needed no backslash. Inside brackets, special characters other than the backslash lose their special meaning; the Python documentation gives [(+*)] as a class that matches any of the literal characters (, +, * and ). So [^.] means "not a period" with a plain period, while outside brackets a bare period is the wildcard from the next concept and a literal period must be written \.. The two contexts have different grammars, and reading a pattern means always knowing which one you are in.

British and American spelling give the cleanest first example. You want one regex for color and colour. The u is optional, and colou?r says exactly that: the question mark makes the character before it appear zero or one times (SLP3, section 2.6.2). The same trick covers a plural: koalas?.

Now try sheep. Their language is baa!, baaa!, baaaa!, any number of a's of at least two. The Kleene star gives zero or more of the previous element, so baaa*! works: two literal a's, then any number more. The Kleene plus gives one or more, so baa+! says the same thing more readably. Both reject b!. Note what ba*! would do: with zero a's allowed, it accepts b!, which no sheep says. This is the recurring hazard of the star: it also matches nothing.

A Quantifier applies to whatever is immediately before it: one character, one class, or one parenthesized group. So [0-9]+ is an integer of one or more digits, and on "Chapter 12 of 3" it finds 12 at 8 and 3 at 14. SLP3 asks why not [0-9]*, and the sheep already answered: the star matches the empty string, so [0-9]* would "match" at every position of a text with no digits at all. Reach for + whenever at least one is required.

The wildcard

The period matches any single character. In Python's default mode that is any character except a newline, and the DOTALL flag lifts the exception; in JavaScript the dot excludes the line terminators and the s flag lifts it (Python re documentation; MDN). Under a star it becomes the most powerful and most dangerous idiom in the language: .* is any string of zero or more characters. a.*b is an a, then anything, then a b, and rose.*rose finds two roses with anything between.

Greedy versus lazy

Here is the question that decides whether .* does what you meant. Run <.*> on the string <a><b>. You probably wanted the first tag. You get the whole string, because regular expressions always match the largest string they can; SLP3 says the patterns are greedy. The star grabs everything up to the end and then backs off only as far as needed for the final > to match, which is the last one. Adding a question mark after a quantifier makes it lazy: *? and +? match as little as possible, expanding only when the rest of the pattern cannot otherwise succeed (MDN, Python re documentation).

Everything so far matched characters. The last two regex tools match positions. ^The matches The only at the start of a line, $ finds a trailing space at the end of one, and ^The dog\.$ matches a line that is exactly "The dog." and nothing else (SLP3, section 2.6.3).

These are anchors, and the crucial property is that they consume nothing. An anchor matches the empty string at a position that satisfies a condition, so the\b the can match "the the": the boundary sits between the e and the space without using up either. In Python, ^ matches the start of the string, and in MULTILINE mode also immediately after each newline; $ matches the end of the string or just before the final newline, and in MULTILINE mode before every newline (Python re documentation). JavaScript's m flag does the same job, which is why the tester below has one.

That is what "line-based formats" on the slide means in practice: real files are one record per line, and the multiline flag turns ^ and $ into per-line assertions. A comments filter on a corpus file, and a date extractor on a log, are the same pattern shape.

Without the flag, ^ sees only the start of the whole string, so the comments filter finds nothing and the date pattern catches only a first line that happens to begin with a timestamp. With the flag, each newline resets ^ and $, which is exactly how you scan a log or strip comment lines from a file. Flip the m flag on the ^The preset in the tester below to feel the difference.

The word boundary

The slide says \b is useful for matching whole words, and the canonical example is the word "the". Plain the also matches inside other and theme. \bthe\b requires a boundary on each side, so on "the other theme" it lights only the first word. A word character is a letter, a digit or an underscore, and the boundary is the seam between such a character and anything else, or a string edge (Python re documentation). Python's own examples make the rule vivid: r'\bat\b' matches at, at., (at) and the at in "as at ay", but not attempt or atlas.

Digits count as word characters too, which produces the example SLP3 uses to check that you have understood the definition rather than memorized "letters". \b99\b matches in "There are 99 bottles" and in "$99", because a dollar sign is not a word character, but not in "299", because the 2 is. On "There are 299 bottles, $99 each" it finds exactly one match, the 99 at index 24.

SLP3 tells the story of the word "the" as a precision and recall exercise. the misses The at the start of a sentence, a false negative, so you write [tT]he. Now it hits other and there, false positives, so you write \b[tT]he\b. Every regex you write for a real corpus goes through the same two-sided tuning, and the boundary is usually the second fix.

The six aliases

Some classes are needed so often that they get a backslash shorthand. Slide 65 lists six, in three complementary pairs. Each lower case alias is a class, and its upper case partner is the negation of that class.

The expansions in the table are the SLP3 definitions, and they are ASCII. Real engines differ at the edges, and the differences matter for Arabic. In Python 3, a pattern on a str treats \d as any Unicode decimal digit, including Arabic-Indic digits, \w as any Unicode alphanumeric plus the underscore, so Arabic letters count, and \s as anything str.isspace() accepts, which includes the non-breaking space; the ASCII flag switches all three back to the table above, with \s as [ \t\n\r\f\v] (Python re documentation). JavaScript keeps \w at letters, digits and underscore and \d at [0-9], while its \s covers all Unicode whitespace and line terminators (MDN). So a boundary such as \b, which is defined in terms of \w, falls in different places for the same Arabic sentence in the two languages. This is the "language-dependent" warning from slide 57 in its most practical form.

A backslash works both ways

Inside a pattern, a backslash before a special character makes it literal: \. is a period, \^ is a caret. The same backslash before an ordinary letter creates an alias such as \d or \b. The full table of escaped specials, from K\*A\*P\*L\*A\*N to the raw-string question, comes in the next part.

Check every row yourself

The tester below loads every example from slides 59 to 65, the greedy and lazy pairs, and the ELIZA rule with its captured group. Load a preset, read the first match, then edit the pattern and watch the highlight move. Try a^b to see the erratum with your own eyes, and switch the m flag off on the ^The preset to see anchors change meaning.

HE SAYS YOU ARE DEPRESSED MUCH OF THE TIME.