Experiments

4 min read

Regex Engines

Regex Engine Families

Perl Compatible Family

  • Traditional NFA
  • Driven by backtracking machine architecture
  • Supports advanced features: Lookarounds, Backreferences, non-greedy quantifiers, atomic grouping
  • Can exhibit exponential time complexity (susceptible to ReDoS / Catastrophic Backtracking)
  • PCRE2 (Perl Compatible Regular Expression)
  • Oniguruma/Onigmo
    • original implementation has been archived
    • powers Ruby, VSCode syntax tokenization, TextMate, Sublime Text, jq, bat
  • java.util.regex from Java
    • does not support POSIX character classes
    • supports Unicode property escapes like \p{Letter}
  • re from Python
    • does not support Unicode property escapes

ECMAScript family

  • Similar to Perl-Compatible/Traditional NFA Family
  • Standardized by ECMA-262 spec
  • No possessive quantifiers, atomic groups
  • Can exhibit exponential time complexity (susceptible to ReDoS / Catastrophic Backtracking)
  • Does not support POSIX character classes like [[:alnum:]]
  • Irregexp
    • embedded in V8 engine
    • powers chromium based browsers, Node.js, Deno
  • YARR (Yet Another Regex Runtime)
    • embedded in JavascriptCore engine
    • powers Apple Safari, Webkit frameworks, Bun

POSIX Family

  • Hybrid NFA/DFA
  • prioritizes POSIX standard compliance over raw performance
  • Enforces the Leftmost-Longest rule (immune to ReDoS unless tracking backreferences)
  • Doesn’t support Unicode property escapes
  • powers Unix Tools like grep, sed, awk

Thompson NFA Family

  • Linear Time Family
  • Intentionally omits features requiring arbitrary backtracking like lookarounds and backreferences
  • Guarantees O(n) matching time, n = length of string
  • re2 written in C++ from Google
  • regex Rust crate

ReDOS

Major Features of Regex Engines

  • Character classes
    • Negated Character classes
    • Character class range
    • Shorthands
    • Unicode Properties
    • POSIX character classes
  • Dot
  • Anchors
  • Word Boundaries
  • Alternation
  • Quantifier
  • Non-greedy quantifier
  • Look around
    • Look ahead
    • Look behind
  • Named capture and Backreferences
  • Atomic grouping
  • Conditionals
  • Comments

Unicode character classes

  • aka Unicode Property escapes or Unicode Character property
  • https://en.wikipedia.org/wiki/Unicode_character_property
  • https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Regular_expressions/Unicode_character_class_escape
  • https://unicode.org/Public/UCD/latest/ucd/PropertyValueAliases.txt
  • Every Unicode character has a set of properties that describe it
    • This info can be accessed via unicode database (UCD)
    • https://codepoints.net/ can be used and shows all properties under “Complete Record”
    • unicode command line also gives this info, although it is less technical
  • a has:
    • General_Category=Lowercase_letter
    • Script=Latn
  • Categories are hierarchical in nature
    • Main category use 1-Letter (L = Letter, N = Number)
    • Sub category use 2-letter (Ll = Lowercase Letter, Nd = Decimal Number)
    • Matching main category automatically targets all sub-categories
  • Syntax: \p{Property_Key=Value}
    • \p{Value} where Property_Key=General_Category
    • \p{Property_Key} where Property_Key is Binary
  • Examples
    • \p{L} — matches letter (implicit General_Category)
    • \p{Lu} — matches upper case letter (implicit General_Category)
    • \p{Script=Deva} — matches Devanagari characters
    • \p{Emoji} — matches emojis (Binary Property)
    • \P{Emoji} — matches characters which are not emojis (Binary Property)
  • Example Regex
    • Text: Chloé smiled as she typed her name into the form!
    • Regex: ^\p{L}+ (^\w+ may fail in some engines because of presence of é)
    • Match: Chloé

General_Category

  • alias: gc, Category
  • Major Categories and Sub categories are shown below
Parent Value (Short)Child Value (Short)Description & Examples
Letter (L)Matches any letter in any global alphabet
Uppercase_Letter (Lu)Capital letters
Examples: A, Δ
Lowercase_Letter (Ll)Small letters
Examples:a, λ
Titlecase_Letter (Lt)Ligatures printed at the start of words
Examples: Dž
Modifier_Letter (Lm)Spacing modifier letters
Examples: ʰ
Other_Letter (Lo)Ideographs with no case distinction
Examples: 书 (Chinese), و (Arabic)
Number (N)Matches any numerical symbol
Decimal_Number (Nd)Standard digits used for math
Examples: 0-9, 𝟟
Letter_Number (Nl)Numerals composed of letters
Examples: Ⅵ (Roman numeral)
Other_Number (No)Fractions, superscripts, subscripts
Examples: ½, ³
Punctuation (P)Matches all typographic punctuation markers
Dash_Punctuation (Pd)Hyphens and dashes
Examples: -, —
Open_Punctuation (Ps)Opening brackets
Examples: (, [, {
Close_Punctuation (Pe)Closing brackets
Examples: ), ], }
Symbol (S)Matches math, currency, or technical signs
Math_Symbol (Sm)Mathematical syntax operators
Examples: +, =, ∞
Currency_Symbol (Sc)Currency units
Examples: $, €, ₹
Separator (Z)Matches spaces and hidden layout breaks
Space_Separator (Zs)Standard horizontal graphic spaces
Examples: U+0020 (Standard Space), U+00A0 (No break space, same as &nbsp)
Mark (M)Combined character accents and text modifiers
Nonspacing_Mark (Mn)Accents that sit over letters without widening text width
Example: ◌́ (Combining Acute Accent)
Spacing_Mark (Mc)Diacritics that expand letter width layout dynamically
Example: ◌ा (Hindi vowel marker)
Other (C)Matches structural system flags, legacy codes, and code points
Control (Cc)Legacy ASCII commands and device signal codes
Examples: \n, \r, \t
Format (Cf)Hidden script direction layout controls
Examples: U+200E (Left-to-Right Mark), U+200F (Right-to-Left Mark)

Scripts

  • Script
    • alias: sc
  • Script_Extensions
    • alias: scx
Value (Short)Description & Examples
Latin (Latn)Western European alphabets
Han (Hani)Chinese Hanzi and Japanese Kanji characters
Cyrillic (Cyrl)Slavic alphabets (e.g., Б, я)
Greek (Grek)Greek text and math symbols (e.g., π, Ω)
Hiragana (Hira)Japanese phonetic Hiragana
Katakana (Kana)Japanese phonetic Katkana
Devanagari (Deva)Hindi, Marathi, and Sanskrit script

Binary

  • Emoji
  • Whitespace
  • Hex_digit