Regex (V2 WIP)

A pure Swift implementation of a Regular Expression Engine

Trying again with V2 using DFAs instead of NFAs to get grep-like performance

Usage

To avoid compiling overhead it is possible to create a Regex instance

// Compile the expression
let regex = try! Regex(pattern: "[a-zA-Z]+")

let string = "RegEx is tough, but useful."

// Search for matches
let words = regex.match(string)

/*
words = [
	RegexMatch(match: "RegEx", groups: []),
	RegexMatch(match: "is", groups: []),
	RegexMatch(match: "tough", groups: []),
	RegexMatch(match: "but", groups: []),
	RegexMatch(match: "useful", groups: []),
]
*/

If compiling overhead is not an issue it is possible to use the =~ operator to match a string

let fourLetterWords = "drink beer, it's very nice!" =~ "\\b\\w{4}\\b" ?? []

/*
fourLetterWords = [
	RegexMatch(match: "beer", groups: []),
	RegexMatch(match: "very", groups: []),
	RegexMatch(match: "nice", groups: []),
]
*/

By default the Global flag is active. To change which flag are active, add a / at the start of the pattern, and add /<flags> at the end. The available flags are:

• g Global - Allows multiple matches
• i Case Insensitive - Case insensitive matching
• m Multiline - ^ and $ also match the begining and end of a line

// Global and Case Insensitive search
let regex = try! Regex(pattern: "/\\w+/ig")

Supported Operations

Character Classes

Pattern	Description	Supported
.	[^\n\r]
[^]	[\s\S]
\w	[A-Za-z0-9_]
\W	[^A-Za-z0-9_]
\d	[0-9]
\D	[^0-9]
\s	[\ \r\n\t\v\f]
\S	[^\ \r\n\t\v\f]
[ABC]	Any in the set
[^ABC]	Any not in the set
[A-Z]	Any in the range inclusively

Anchors (Match positions not characters)

Pattern	Description	Supported
^	Beginning of string
$	End of string
\b	Word boundary
\B	Not word boundary

Escaped Characters

Pattern	Description	Supported
\0	Octal escaped character
\00	Octal escaped character
\000	Octal escaped character
\xFF	Hex escaped character
\uFFFF	Unicode escaped character
\cA	Control character
\t	Tab
\n	Newline
\v	Vertical tab
\f	Form feed
\r	Carriage return
\0	Null
\.	.
\\	\
\+	+
\*	*
\?	?
\^	^
\$	$
\{	{
\}	}
\[	[
\]	]
\(	(
\)	)
\/	/
|	`	`

Groups and Lookaround

Pattern	Description	Supported
(ABC)	Capture group
(<name>ABC)	Named capture group
\1	Back reference
\'name'	Named back reference
(?:ABC)	Non-capturing group
(?=ABC)	Positive lookahead
(?!ABC)	Negative lookahead
(?<=ABC)	Positive lookbehind
(?<!ABC)	Negative lookbehing

Greedy Quantifiers

Pattern	Description	Supported
+	One or more
*	Zero or more
?	Optional
{n}	n
{,}	Same as *
{,n}	n or less
{n,}	n or more
{n,m}	n to m

Lazy Quantifiers

Pattern	Description	Supported
+?	One or more
*?	Zero or more
??	Optional
{n}?	n
{,n}?	n or less
{n,}?	n or more
{n,m}?	n to m

Alternation

Pattern	Description	Supported
|	Everything before or everything after

Flags

Pattern	Description	Supported
i	Case insensitive
g	Global
m	Multiline

Inner Workings

(Similar to before)

• Lexer (String input to Tokens)
• Parser (Tokens to NFA)
• Compiler (NFA to DFA)
• Optimizer (Simplify DFA (eg. char(a), char(b) -> string(ab)) for better performance)
• Engine (Matches an input String using the DFA)

---

Note

Swift treats \r\n as a single Character. Use \n\r to have both.

Resources

• regexr.com - Regex testing
• swtch.com - Implementing Regular Expressions
• Powerset construction - NFA to DFA
• Minimization