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

Anchors (Match positions not characters)

Escaped Characters

Groups and Lookaround

Greedy Quantifiers

Lazy Quantifiers

Alternation

Flags

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