sml-regex

A regular-expression engine for Standard ML built on Thompson NFAs and the Pike virtual machine (Russ Cox). Matching runs in time linear in the product of input length and pattern size — no catastrophic backtracking ReDoS.

Compared to sml-rederiv

	sml-regex (this library)	sml-rederiv
Engine	Thompson NFA → Pike VM	Brzozowski derivatives
Captures	Numbered + named groups	None (grouping only)
Alternation	Perl-style ordered (first wins)	POSIX leftmost-longest
Quantifiers	Greedy + lazy (*?, +?, ??)	Greedy only
Anchors / flags	^ $ \A \z \b \B, (?i) (?m) (?s)	Basic syntax only
Search	find / findAll with capture spans	Leftmost-longest, no groups
Replace	$1, ${name} capture expansion	Function receives matched text only

Both libraries stay linear-time for a fixed pattern, including pathological inputs like a*a*a*...a*b.

Supported syntax (compile / matchStr)

literals            a b c ...
.                   any single character (respects (?s) dotall)
*  +  ?  *?  +?  ?? greedy / lazy quantifiers
{m} {m,} {m,n}      bounded repetition
|                   ordered alternation
( )                 capturing group
(?: )               non-capturing group
(?<name> ) (?P<name> )  named capture
[abc] [a-z] [^...]  character classes
\d \D \w \W \s \S  shorthand classes
^ $ \A \z \b \B    anchors
(?i) (?m) (?s)     inline / leading flags
\\c                 escape a metacharacter

Out of scope

The Pike VM deliberately does not implement features that require backtracking:

• Backreferences (\1, \k<name>)
• Lookbehind / lookahead assertions that need arbitrary backtracking

Use a backtracking engine if you need those features.

Known limitations

• (?i) and character classes: prior to the current version, (?i) only case-folded literal characters (IChar); character classes ([a-z]) baked their predicate at parse time and the VM ignored icase when evaluating them. This is fixed: the VM now applies Char.toLower/Char.toUpper before testing class predicates when icase is set. (?i)[a-z] now correctly matches uppercase letters.

• replaceStr multi-character group expansion: expandRep accumulated substituted group text in the same reverse-then-final-List.rev buffer used for literal characters, but spliced each group's text in as a forward-order block instead of a reversed one — so any $n / ${name} substitution longer than one character (and not a palindrome) came out reversed (e.g. ${year} for "2024" rendered as "4202"). Existing tests didn't catch this because every multi-character capture they exercised happened to be a palindrome ("bbb", "aa"). This is fixed.

API sketch

val re = Regex.compile "(?<word>\\w+)"

Regex.matches re "hello"                    (* whole-string match *)
Regex.find re "say hello there"             (* SOME {start, len, groups} *)
Regex.findAll re "a1 b22"                   (* non-overlapping matches *)
Regex.replaceStr re "$1!" "x y"             (* capture expansion in replacement *)
Regex.split (Regex.compile ",") "a,b,c"     (* ["a","b","c"] *)

matches is anchored to the entire input string. find / findAll scan for the leftmost Perl-style match at each position.

Example

make example builds and runs examples/demo.sml, which compiles a date pattern with named capture groups, matches and searches with it, reformats matches with ${name} template expansion, and splits a string (output is byte-identical under MLton and Poly/ML):

Pike-VM regex engine (sml-regex)

  matchStr "[a-z]+" "hello"      = true
  matches "2024-03-15"           = true
  matches "2024-03-15 "          = false

Pattern: (?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})
  nGroups                        = 3
  groupName "month"              = 2
  find: start=11 len=10 -> "2024-03-15"
  findAll count                  = 2

  replaceStr "${month}/${day}/${year}" -> Meeting on 03/15/2024 and again on 12/01/2024.
  split ",\\s*"                  = [red|green|blue|orange]

Portability

Pure Standard ML (Basis library only). Verified on MLton and Poly/ML, with byte-identical test output across both.

Numeric ${n} group references in replacement templates are parsed within the signed 32-bit range (-2147483648 .. 2147483647); a larger index is treated as a nonexistent group and expands to nothing. Both compilers use a fixed-width default int (32-bit on MLton, 63-bit on Poly/ML), so a plain Int.fromString on an oversized index would raise Overflow on MLton while succeeding on Poly/ML — the range check keeps the two byte-identical.

Building and testing

make test        # MLton
make test-poly   # Poly/ML
make all-tests   # both
make clean

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-regex
smlpkg sync

Reference from your .mlb:

lib/github.com/sjqtentacles/sml-regex/regex.mlb

Project layout

sml.pkg
Makefile
lib/github.com/sjqtentacles/sml-regex/
  regex.sig          REGEX signature
  ast.sml            internal AST
  parse.sml          surface-syntax parser
  nfa.sml            Thompson NFA compiler
  pikevm.sml         Pike virtual machine
  regex.sml          public facade
  regex.mlb
test/
  test.sml           assertion suite (11 sections)
.github/workflows/ci.yml

License

MIT. See LICENSE.