Lookarounds

In the previous section, we used groups and greediness to extract stems from words ending in /ʃən/—like extracting /æbstɹæk/ from /æbstɹækʃən/. We also saw the anchors ^ and $, which assert something about the position in the string (beginning or end) without consuming any characters. Lookarounds are a generalization of the same idea to arbitrary patterns: you can assert that a particular pattern does or does not occur at a given position, without that assertion consuming any of the string.

Load IPA representation of CMU Pronouncing Dictionary

with open("cmudict-ipa", encoding="utf-8") as f:
    entry_rows: list[list[str]] = [
        line.strip().split(",", maxsplit=1) for line in f
    ]
    entries: dict[str, list[str]] = {
        word: ipa.split() for word, ipa in entry_rows
    }

Positive lookahead

A positive lookahead (?=...) asserts that what follows the current position matches a given pattern. Recall our /ʃən/ extraction from the previous section: we captured the stem with (.+?)(?:eɪ)?ʃən$, which required careful management of greediness to avoid swallowing the /eɪ/. With a lookahead, we can instead find the position just before /ʃən/ (or /eɪʃən/) without consuming the suffix at all.

import re

regex_stem = r'(.+?)(?=(?:eɪ)?ʃən$)'

n_matches = 0

for w, ipa in entries.items():
    joined = "".join(ipa)
    m = re.search(regex_stem, joined)
    if m and joined.endswith('ʃən'):
        if n_matches < 15:
            n_matches += 1
            print(f"{joined:20s}  stem: {m.group(1):10s}  ({w})")
        else:
            break

The (?=(?:eɪ)?ʃən$) checks that what follows the current position is (optionally /eɪ/ and then) /ʃən/ at the end of the string—but it doesn’t consume those characters. The capturing group (.+?) thus gets exactly the stem, with none of the suffix leaking in. Compare this to the greediness-based approach from the previous section, where we had to think carefully about whether .+ would swallow /eɪ/.

Negative lookahead

A negative lookahead (?!...) asserts that what follows does not match a given pattern. This is useful for expressing phonotactic constraints—restrictions on what sequences of sounds a language allows.

Let’s find all words in the CMU dictionary where /ʃ/ appears but is not followed by /ən/—i.e. cases where /ʃ/ is not part of the /-ʃən/ suffix we’ve been studying. This gives us a sense of what other contexts /ʃ/ appears in.

regex = r'ʃ(?!ən)'

n_matches = 0

for w, ipa in entries.items():
    joined = "".join(ipa)
    if re.search(regex, joined):
        if n_matches < 15:
            n_matches += 1
            pos = re.search(regex, joined).start()
            print(f"{joined:20s}  /ʃ/ at position {pos}  ({w})")
        else:
            break

These are words where /ʃ/ appears in contexts other than the /-ʃən/ suffix: initial /ʃ/ (as in she), medial /ʃ/ before other vowels (as in machine), etc. The negative lookahead expresses the constraint “not followed by /ən/” directly. Without it, we would need to enumerate all the things /ʃ/ can be followed by, which is tedious and error-prone.

Lookbehind

A lookbehind asserts something about what precedes the current position: (?<=...) for positive and (?<!...) for negative. In Python’s re module, the pattern inside a lookbehind must have a fixed length—you can’t use * or + inside it.¹

Let’s use a lookbehind to separate the two allomorphs of the /-ʃən/ suffix that we identified in the previous section: /eɪʃən/ (as in accreditation) versus plain /ʃən/ (as in abstraction).

regex_ation = r'(?<=eɪ)ʃən$'
regex_tion = r'(?<!eɪ)ʃən$'

ation_words = []
tion_words = []

for w, ipa in entries.items():
    joined = "".join(ipa)
    if re.search(regex_ation, joined):
        ation_words.append((w, joined))
    elif re.search(regex_tion, joined):
        tion_words.append((w, joined))

print("/eɪʃən/ words:")
for w, ipa in ation_words[:10]:
    print(f"  {ipa:20s}  ({w})")

print()
print("/ʃən/ (without /eɪ/) words:")
for w, ipa in tion_words[:10]:
    print(f"  {ipa:20s}  ({w})")

The lookbehind checks the preceding context without consuming it, so we don’t need to worry about greediness at all—the two allomorphs fall out of the two patterns directly.

Combining lookarounds for phonotactic queries

You can stack multiple lookarounds at the same position to express conjunctive constraints. Suppose we want to find all VCCV sequences in the lexicon—a vowel followed by two consonants and then another vowel. These sequences are relevant for syllabification, since the question of where the syllable boundary falls between the two consonants depends on properties like their relative sonority.

vowels = {'ɑ', 'æ', 'ə', 'ʌ', 'ɔ', 'aʊ', 'aɪ', 'ɛ', 'ɝ', 'eɪ',
          'ɪ', 'i', 'oʊ', 'ɔɪ', 'ʊ', 'u'}
consonants = {'b', 'tʃ', 'd', 'ð', 'f', 'g', 'h', 'dʒ', 'k', 'l', 'm',
              'n', 'ŋ', 'p', 'ɹ', 's', 'ʃ', 't', 'θ', 'v', 'w', 'j', 'z', 'ʒ'}

vowel_pattern = '(?:' + '|'.join(map(re.escape, sorted(vowels))) + ')'
consonant_pattern = '(?:' + '|'.join(map(re.escape, sorted(consonants))) + ')'
regex_vccv = (
    f'{vowel_pattern} {consonant_pattern} '
    f'{consonant_pattern} {vowel_pattern}'
)

n_matches = 0

for w, ipa in entries.items():
    joined = " ".join(ipa)
    matches = list(re.finditer(regex_vccv, joined))
    if matches:
        if n_matches < 10:
            n_matches += 1
            for m in matches:
                cluster = m.group()
                print(f"{joined:20s}  VCCV: {cluster}  ({w})")
        else:
            break

We can refine this with a lookahead: suppose we want only VCCV sequences where the second consonant is a stop (/p t k b d g/).

stops = {'p', 't', 'k', 'b', 'd', 'g'}
stop_pattern = '(?:' + '|'.join(map(re.escape, sorted(stops))) + ')'

regex_vcsv = (
    f'{vowel_pattern} {consonant_pattern} '
    f'(?={stop_pattern} {vowel_pattern}){stop_pattern} {vowel_pattern}'
)

n_matches = 0

for w, ipa in entries.items():
    joined = " ".join(ipa)
    matches = list(re.finditer(regex_vcsv, joined))
    if matches:
        if n_matches < 10:
            n_matches += 1
            for m in matches:
                print(f"{joined:20s}  VCstopV: {m.group()}  ({w})")
        else:
            break

Formal perspective

So do lookarounds let us describe languages that ordinary regular expressions cannot? They do not. We can make this claim precise with a split-point construction (SPC).

Fix arbitrary regular expressions $\alpha$, $\rho$, and $\beta$. We consider anchored, full-string matching of $\alpha(?=\rho)\beta$: $\alpha$ consumes a prefix, the assertion is checked at that split, and $\beta$ consumes the entire remainder. Write $A=\operatorname{eval}(\alpha)$, $R=\operatorname{eval}(\rho)$, and $B=\operatorname{eval}(\beta)$. A positive lookahead succeeds exactly when the unconsumed suffix begins with a member of $R$, that is, when the suffix belongs to $R\circ\Sigma^*$. The whole pattern thus describes

\[A\circ\bigl(B\cap(R\circ\Sigma^*)\bigr).\]

This is another use of double inclusion, which we used earlier to prove the correctness of the regular-expression evaluator. The left side and right side of the displayed equation are both languages, so they are sets of strings. We prove that the languages are equal by showing that every string described by either side is also described by the other.

For the first inclusion, suppose $w$ matches the lookahead pattern. Then there is a split $w=xy$ such that $x\in A$, $y\in B$, and the assertion guarantees $y\in R\circ\Sigma^*$. Hence $y$ belongs to the intersection and $w$ belongs to the displayed language. For the reverse inclusion, suppose $w$ belongs to the displayed language. Then $w=xy$ for some $x\in A$ and $y\in B\cap(R\circ\Sigma^*)$. The membership $y\in R\circ\Sigma^*$ says that $\rho$ matches a prefix of the suffix at the split, so the lookahead succeeds without consuming material; $\beta$ then consumes $y$. Thus, the original pattern matches $w$.

Consider $\alpha=a^*$, $\rho=bc$, and $\beta=b\Sigma$, corresponding to the pattern a*(?=bc)b.. The string aabc has the split $\text{aa}\mid\text{bc}$: aa belongs to $A$, bc belongs to $B$, and bc belongs to $R\circ\Sigma^*$. The assertion succeeds and the full string is accepted. In contrast, aabd has the only full-match split $\text{aa}\mid\text{bd}$. The suffix bd belongs to $B$ but not to $bc\circ\Sigma^*$, so the assertion fails and the string is rejected.

A negative lookahead reverses only the assertion. Its language is

\[A\circ\bigl(B\cap\overline{R\circ\Sigma^*}\bigr),\]

where the complement is taken relative to $\Sigma^*$. Positive lookbehind is symmetric: requiring the consumed prefix to end in $R$ replaces $A$ with $A\cap(\Sigma^*\circ R)$, and negative lookbehind uses the complement of that suffix condition.

Regular languages are closed under concatenation, intersection, and complement. Every language in these constructions is thus regular. The SPC proves that lookarounds, like quantifiers and character classes before them, are notational conveniences rather than extensions of expressive power. For unanchored search, the construction must additionally allow arbitrary material before and after the matched span; the displayed equality itself is scoped to full matching.²

Footnotes

The engine would need to try all possible lengths for the lookbehind at each position, which is expensive. The third-party regex module relaxes this restriction.↩︎
This formalization abstracts away from engine-specific features such as backreferences inside assertions, which need not remain regular.↩︎

--- title: Lookarounds jupyter: python3 --- In the previous section, we used groups and greediness to extract stems from words ending in /ʃən/—like extracting /æbstɹæk/ from /æbstɹækʃən/. We also saw the anchors `^` and `$`, which assert something about the *position* in the string (beginning or end) without consuming any characters. Lookarounds are a generalization of the same idea to arbitrary patterns: you can assert that a particular pattern does or does not occur at a given position, without that assertion consuming any of the string. ```{python} #| code-fold: true #| code-summary: Load IPA representation of CMU Pronouncing Dictionary with open("cmudict-ipa", encoding="utf-8") as f: entry_rows: list[list[str]] = [ line.strip().split(",", maxsplit=1) for line in f ] entries: dict[str, list[str]] = { word: ipa.split() for word, ipa in entry_rows } ``` ## Positive lookahead A *positive lookahead* `(?=...)` asserts that what follows the current position matches a given pattern. Recall our /ʃən/ extraction from the previous section: we captured the stem with `(.+?)(?:eɪ)?ʃən$`, which required careful management of greediness to avoid swallowing the /eɪ/. With a lookahead, we can instead find the position just before /ʃən/ (or /eɪʃən/) without consuming the suffix at all. ```{python} import re regex_stem = r'(.+?)(?=(?:eɪ)?ʃən$)' n_matches = 0 for w, ipa in entries.items(): joined = "".join(ipa) m = re.search(regex_stem, joined) if m and joined.endswith('ʃən'): if n_matches < 15: n_matches += 1 print(f"{joined:20s} stem: {m.group(1):10s} ({w})") else: break ``` The `(?=(?:eɪ)?ʃən$)` checks that what follows the current position is (optionally /eɪ/ and then) /ʃən/ at the end of the string—but it doesn't consume those characters. The capturing group `(.+?)` thus gets exactly the stem, with none of the suffix leaking in. Compare this to the greediness-based approach from the previous section, where we had to think carefully about whether `.+` would swallow /eɪ/. ## Negative lookahead A *negative lookahead* `(?!...)` asserts that what follows does *not* match a given pattern. This is useful for expressing phonotactic constraints—restrictions on what sequences of sounds a language allows. Let's find all words in the CMU dictionary where /ʃ/ appears but is *not* followed by /ən/—i.e. cases where /ʃ/ is not part of the /-ʃən/ suffix we've been studying. This gives us a sense of what other contexts /ʃ/ appears in. ```{python} regex = r'ʃ(?!ən)' n_matches = 0 for w, ipa in entries.items(): joined = "".join(ipa) if re.search(regex, joined): if n_matches < 15: n_matches += 1 pos = re.search(regex, joined).start() print(f"{joined:20s} /ʃ/ at position {pos} ({w})") else: break ``` These are words where /ʃ/ appears in contexts other than the /-ʃən/ suffix: initial /ʃ/ (as in *she*), medial /ʃ/ before other vowels (as in *machine*), etc. The negative lookahead expresses the constraint "not followed by /ən/" directly. Without it, we would need to enumerate all the things /ʃ/ *can* be followed by, which is tedious and error-prone. ## Lookbehind A *lookbehind* asserts something about what *precedes* the current position: `(?<=...)` for positive and `(?<!...)` for negative. In Python's `re` module, the pattern inside a lookbehind must have a fixed length—you can't use `*` or `+` inside it.^[The engine would need to try all possible lengths for the lookbehind at each position, which is expensive. The third-party `regex` module relaxes this restriction.] Let's use a lookbehind to separate the two allomorphs of the /-ʃən/ suffix that we identified in the previous section: /eɪʃən/ (as in *accreditation*) versus plain /ʃən/ (as in *abstraction*). ```{python} regex_ation = r'(?<=eɪ)ʃən$' regex_tion = r'(?<!eɪ)ʃən$' ation_words = [] tion_words = [] for w, ipa in entries.items(): joined = "".join(ipa) if re.search(regex_ation, joined): ation_words.append((w, joined)) elif re.search(regex_tion, joined): tion_words.append((w, joined)) print("/eɪʃən/ words:") for w, ipa in ation_words[:10]: print(f" {ipa:20s} ({w})") print() print("/ʃən/ (without /eɪ/) words:") for w, ipa in tion_words[:10]: print(f" {ipa:20s} ({w})") ``` The lookbehind checks the preceding context without consuming it, so we don't need to worry about greediness at all—the two allomorphs fall out of the two patterns directly. ## Combining lookarounds for phonotactic queries You can stack multiple lookarounds at the same position to express conjunctive constraints. Suppose we want to find all VCCV sequences in the lexicon—a vowel followed by two consonants and then another vowel. These sequences are relevant for syllabification, since the question of where the syllable boundary falls between the two consonants depends on properties like their relative sonority. ```{python} vowels = {'ɑ', 'æ', 'ə', 'ʌ', 'ɔ', 'aʊ', 'aɪ', 'ɛ', 'ɝ', 'eɪ', 'ɪ', 'i', 'oʊ', 'ɔɪ', 'ʊ', 'u'} consonants = {'b', 'tʃ', 'd', 'ð', 'f', 'g', 'h', 'dʒ', 'k', 'l', 'm', 'n', 'ŋ', 'p', 'ɹ', 's', 'ʃ', 't', 'θ', 'v', 'w', 'j', 'z', 'ʒ'} vowel_pattern = '(?:' + '|'.join(map(re.escape, sorted(vowels))) + ')' consonant_pattern = '(?:' + '|'.join(map(re.escape, sorted(consonants))) + ')' regex_vccv = ( f'{vowel_pattern} {consonant_pattern} ' f'{consonant_pattern} {vowel_pattern}' ) n_matches = 0 for w, ipa in entries.items(): joined = " ".join(ipa) matches = list(re.finditer(regex_vccv, joined)) if matches: if n_matches < 10: n_matches += 1 for m in matches: cluster = m.group() print(f"{joined:20s} VCCV: {cluster} ({w})") else: break ``` We can refine this with a lookahead: suppose we want only VCCV sequences where the second consonant is a stop (/p t k b d g/). ```{python} stops = {'p', 't', 'k', 'b', 'd', 'g'} stop_pattern = '(?:' + '|'.join(map(re.escape, sorted(stops))) + ')' regex_vcsv = ( f'{vowel_pattern} {consonant_pattern} ' f'(?={stop_pattern} {vowel_pattern}){stop_pattern} {vowel_pattern}' ) n_matches = 0 for w, ipa in entries.items(): joined = " ".join(ipa) matches = list(re.finditer(regex_vcsv, joined)) if matches: if n_matches < 10: n_matches += 1 for m in matches: print(f"{joined:20s} VCstopV: {m.group()} ({w})") else: break ``` ## Formal perspective So do lookarounds let us describe languages that ordinary regular expressions cannot? They do not. We can make this claim precise with a **split-point construction** (SPC). Fix arbitrary regular expressions $\alpha$, $\rho$, and $\beta$. We consider anchored, full-string matching of $\alpha(?=\rho)\beta$: $\alpha$ consumes a prefix, the assertion is checked at that split, and $\beta$ consumes the entire remainder. Write $A=\operatorname{eval}(\alpha)$, $R=\operatorname{eval}(\rho)$, and $B=\operatorname{eval}(\beta)$. A positive lookahead succeeds exactly when the unconsumed suffix begins with a member of $R$, that is, when the suffix belongs to $R\circ\Sigma^*$. The whole pattern thus describes $$A\circ\bigl(B\cap(R\circ\Sigma^*)\bigr).$$ This is another use of [double inclusion](../languages-as-formal-objects/set-relations.qmd#equality-by-double-inclusion), which we used earlier to prove the correctness of the [regular-expression evaluator](evaluating-regular-expressions.qmd). The left side and right side of the displayed equation are both languages, so they are sets of strings. We prove that the languages are equal by showing that every string described by either side is also described by the other. For the first inclusion, suppose $w$ matches the lookahead pattern. Then there is a split $w=xy$ such that $x\in A$, $y\in B$, and the assertion guarantees $y\in R\circ\Sigma^*$. Hence $y$ belongs to the intersection and $w$ belongs to the displayed language. For the reverse inclusion, suppose $w$ belongs to the displayed language. Then $w=xy$ for some $x\in A$ and $y\in B\cap(R\circ\Sigma^*)$. The membership $y\in R\circ\Sigma^*$ says that $\rho$ matches a prefix of the suffix at the split, so the lookahead succeeds without consuming material; $\beta$ then consumes $y$. Thus, the original pattern matches $w$. Consider $\alpha=a^*$, $\rho=bc$, and $\beta=b\Sigma$, corresponding to the pattern `a*(?=bc)b.`. The string `aabc` has the split $\text{aa}\mid\text{bc}$: `aa` belongs to $A$, `bc` belongs to $B$, and `bc` belongs to $R\circ\Sigma^*$. The assertion succeeds and the full string is accepted. In contrast, `aabd` has the only full-match split $\text{aa}\mid\text{bd}$. The suffix `bd` belongs to $B$ but not to $bc\circ\Sigma^*$, so the assertion fails and the string is rejected. A negative lookahead reverses only the assertion. Its language is $$A\circ\bigl(B\cap\overline{R\circ\Sigma^*}\bigr),$$ where the complement is taken relative to $\Sigma^*$. Positive lookbehind is symmetric: requiring the consumed prefix to end in $R$ replaces $A$ with $A\cap(\Sigma^*\circ R)$, and negative lookbehind uses the complement of that suffix condition. Regular languages are closed under concatenation, intersection, and complement. Every language in these constructions is thus regular. The SPC proves that lookarounds, like quantifiers and character classes before them, are notational conveniences rather than extensions of expressive power. For unanchored search, the construction must additionally allow arbitrary material before and after the matched span; the displayed equality itself is scoped to full matching.^[This formalization abstracts away from engine-specific features such as backreferences inside assertions, which need not remain regular.]