Overview

In this lesson, you'll be introduced to regular expressions (regexes) and practice using this pattern language to identify spans of text.

Outcomes

After completing this lesson, you'll be able to …

describe patterns using regular expressions
specify repetitions in regular expressions using quantifiers
specify contextual constraints in regular expressions using lookaround assertions

Background

You've been tasked with identifying all mentions of occupations in a collection of documents.

You've been given a few examples to get started:

tokens = ["teacher", "farmer", "doctor", "professor", "lawyer"]

You notice all of these terms have the er/or suffix and recognize these as surface forms of the same agent morpheme. You decide to write some custom code to recognize these:

def agent_er(words):
  return [w for w in words if w.endswith("er") or w.endswith("or")]
 
for valid in agent_er(tokens):
  print(valid)

Problem solved! Time to head to the beach! 🏖️ But before you can so much as reach for the sunscreen, your boss sends you some new test cases:

tokens = ["teacher", "doctor", "professor", "lawyer", "geologist", "mathematician"]

Before adding another conditional to that function, you realize things could quickly get messy.

It's clear that we want to match a few specific suffixes (er, or, ist, cian, etc.).

Regular expressions

Regular expressions are a way of formalizing such patterns. Rooted in formal language theory as a means of describing regular languages, regular expressions have been widely adopted by most text editors and programming languages as means of general text search.

Most popular implementations (ex. the Python re module, Perl, grep, etc.) include extensions such as backreferences and named captures. These memory mechanisms greatly increase the expressive power of regular expressions, enabling them to describe languages more complex than regular languages (beyond type-3). To draw a distinction, we'll adopt the convention of using regexes to refer to this extended form.

Language

You may be surprised to learn that you already know some regexes. The simplest examples are those expressions which match literal strings:

a is a regex that will match exactly one string: a.
cat is a regex that will match exactly one string: cat.

Regexes are far more expressive that that, though. Here are some of the core features of the language:

Language feature	Example	Description
disjunction	`a`\|`b`	matches `a` OR `b`
character class	`[abc]`	matches `a` OR `b` or `c`
negative character class	`[^a]`	matches any character except `a`
character range	`[a-z]`	character range matching any lowercase letter from a to z
	`[a-z0-9]`	character range matching any lowercase letter from a to z or any digit from 0-9
wildcard	`.`	matches a single occurence of any symbol. `a.` will match `aa`, `ab`, `ac`, etc.
left-side anchor	`^My`	My name is Inigo Montoya .
right-side anchor	`ed$`	matches a string that ends with `ed$`
optionality	`colou?r`	`?` makes the preceding character `u` optional; expression will match either `color` or `colour`
pattern scope	`walk(ed)?`	matches either `walk` or `walked`. Use of pathentheses changes the scope of `?` such that `ed` is made optional.

👀 Based on the table above, write a regex to match them and they.

In addition to the features in the previous table, there are also a few convenient shorthand symbols:

Language feature	Example	Description
any "word character"	`\w`	Matches any "word character"; equivalent to the character class `[A-Za-z0-9_]`
any digit	`\d`	Any digit 0-9
any whitespace	`\s`	Matches any whitespace character including tabs
word boundary	`\b`	This is a zero-width assertion (i.e., it doesn't capture any character) denoting word boundaries

All of these shorthand symbols have negated version indicated by capital letters (\W matches anything but a "word character").

👀 Since ., (, ), ?, and other symbols have special meaning in regexes, we need to escape them by prepending a \ when we wish to match the symbol itself. For example, if we want to match a literal question mark, we'd write the following:

\?

Let's apply what we've learned so far to do some field work and document Bovino, an invented cow language…

🐄 💬 moo
🐄 💬 moomoo

Based on what we've seen so far, it seems Bovino consists of only the utterances moo and moomoo.

One possible expression is the following:

moo|moomoo

Can you come up with an alternative?

After many months in the field and countless hours of analysis, we come to realize that in Bovino, moo can be repeated a seemingly infinite number of times.

How can we modify our regex to capture this observation? We need some way of specifying repetitions.

Quantifiers

Regexes support quantification (repetitions). We've already introduced one such quantifier, ?, to mark optional patterns, but there are others:

Symbol	Description
`?`	The preceding pattern is optional.
`*`	Repeat the quantified pattern zero or more times.
`+`	Repeat the quantified pattern one or more times.
`{n}`	Exact repetition. Repeat the quantified pattern n times.
`{n,m}`	Ranged repetition. Repeat the quantified pattern between n and m times, where n < m.
`{,m}`	Open start ranged repetition. Repeat the quantified pattern between 0 and m times, where m > 0.
`{n,}`	Open end ranged repetition. Repeat the quantified pattern at least n times, where n > 0.

By default, these quantifiers are considered greedy. They will match as many times as they can:

$mooooo \rightarrow mo* \rightarrow mooooo$

They can be made lazy by appending a ?. In such cases, the quantifier will stop matching after matching the absolute minimum:

$mooooo \rightarrow mo*? \rightarrow m$

Let's use quantifiers to describe the Bovino language:

🐄 💬 moo
🐄 💬 moomoo
🐄 💬 moomoomoomoomoomoomoomoomoo…

We want to say that moo can repeat an infinite number of times. Which quantifier is appropriate?

You can test your answer in Python using the match¹ function defined in the re module:

samples = ["moo", "moo", "moomoomoomoomoomoomoomoomoo", "meow"]
 
# replace <your-pattern-here> with your solution
pattern = re.compile("<your-pattern-here>")
 
# for every "udderance" ...
for tok in samples:
  is_match = True if re.match(pattern, tok) else False
  print(f"'{tok}' is Bovino?\t{is_match}")

What if Bovino allowed at most 3 repetitions of moo? How would your pattern change?

$B \rightarrow a$
$B \rightarrow aC$
$B \rightarrow \epsilon$

Lookaround expressions 👀

Lookaround expressions can be used to specify contextual constraints that you don't want to end up in your result (ex. "only match B if it's preceded by A"). These are all "zero-width assertions" meaning they don't capture or return the portion of the string they match, but rather only check that the assertion is true. Lookarounds can be both positive (ex. "match X only when it is preceded by Y") or negative (ex. "match X but only when it is not preceded by Y").

Symbol	Description	Example Pattern	Match (in bold)
`(?=...)`	postive lookahead	`Inigo(?= Montoya)`	My name is Inigo Montoya .
`(?!...)`	negative lookahead	`Inigo(?! Arocena)`	My name is Inigo Montoya .
`(?<=...)`	positive lookbehind	`(?<=Inigo )Montoya`	My name is Inigo Montoya .
`(?<!...)`	negative lookbehind	`(?<!Carlos )Montoya`	My name is Inigo Montoya .

Using regexes with Python

Let's look at some examples of recognizing and replacing strings using regexes in Python.

Recognizing strings

Let's imagine we want to analyze words containing the phone /ð/ (voiced interdental fricative):

tokens = ["the", "think", "then", "father", "wither", "other", "mother", "ninth"]

From these examples, it looks like th is pronounced /ð/ when followed by an e. In such cases, it doesn't appear to matter what precedes th or follows e.

In terms of regular expresions, that would mean something like .*the.*

zero or more characters .* … followed by th … followed by e e … followed by zero or more characters

Let's use Python's re.match function to apply that expression to check each term in a list:

import re
 
tokens = ["the", "think", "then", "father", "wither", "other", "mother", "ninth"]
pattern = ".*the.*"
for tok in tokens:
  is_match = True if re.match(pattern, tok) else False
  print(f"'{tok}' contains /ð/?\t{is_match}")

Replacing strings

Earlier, we looked at recognizing words that contain /ð/ using the re.match function. Now let's imagine we wanted to generate a phonetic transcription of those text by replacing such instances of th with ð.

To make things simple, let's introduce the idea of a lookahead expression which allows us to peek ahead to see if what follows matches some specified pattern.

(?=<pattern>)

So if we want to match th only when it is followed by e, we could write that in the following way:

th(?=e)

Using the re.sub function, we can apply this pattern to replace all such occurrences of th with ð. ```python import re tokens = ["the", "think", "then", "father", "wither", "other", "mother", "ninth"]

for tok in tokens: res = re.sub("th(?=e)", 'ð', tok) print(res) ```

When coupled with backreferences, re.sub() is capable of very complex replacements. We'll save that discussion for another time.

Next steps

You now know the basics of writing and using regexes. Let's practice…

Practice

Write a regex to recognize URLs. Refine your regex using the following test cases:

Example	Match?
miscommunication	NO
https://example.com	YES
http://example.com/some/link	YES
example.com	YES
example.org	YES
www.example.com	YES
inorganic	NO

Write a regex to recognize phone numbers. Your regex should handle formats such as 1-(111)-111-1111, (111)-111-1111, 111-1111, 1 (111) 111-1111, and 1.111.111.1111.

Footnotes

As described in the docs, re.match() will only match a regex from the start of a string. To match a pattern any point in a string, use re.search(). ↩
https://xkcd.com/208/ ↩