A library for regular expressions (RE) and finite automata (FA) in the context of Javascript RegExp.
About
refa is a general library for DFA, NFA, and REs of formal regular languages. It also includes methods to easily convert from JS RegExp to the internal RE AST and vice versa.
Test whether the accepted language is the empty set/a finite set
Accept all prefixes/suffixes of a language
DFA specific operations
Minimization
Complement
Structural equality
NFA and ENFA specific operations
Union and Concatenation with other FA
Quantification
See the API documentation for a complete list of all currently implemented operations.
RE AST format
refa uses its own AST format to represent regular expressions. The RE AST format is language agnostic and relatively simple.
It supports:
Concatenation (e.g. ab)
Alternation (e.g. a|b)
Quantifiers (greedy and lazy) (e.g. a{4,6}, a{2,}?, a?, a*)
Assertions (e.g. (?=a), (?<!a))
Characters/character sets (represented by interval sets)
Unknowns (elements that cannot be represented otherwise. E.g. backreferences)
Some features like atomic groups and capturing groups are not supported (but might be added in the future).
For information on how to parse JS RegExp and convert RE AST to JS RegExp, see the JS namespace.
Universal characters
refa does not use JavaScript strings represent characters or a sequences of characters. Instead it uses integers to represent characters (see the Char type) and arrays of numbers to represent words/strings (see the Word type).
This means that any text encoding can be used.
The Words namespace contains functions to convert JavaScript data into refa-compatible words and characters.
For the sets of characters, the CharSet class is used.
General limitations
This library will never be able to support some modern features of regex engines such as backreferences and recursion because these features, generally, cannot be be represented by a DFA or NFA.
Usage examples
refa is a relatively low-level library. It only provides the basic building blocks. In the following examples, JS RegExps are used a lot so we will define a few useful helper function beforehand.
In the above examples, we have been using the toNFA helper function to parse and convert RegExps. This function assumes that the given RegExp is a pure regular expression without assertions and backreferences and will throw an error if the assumption is not met.
However, the JS parser and NFA.fromRegex provide some options to work around and even solve this problem.
Backreferences
Firstly, the parser will automatically resolve simple backreferences. Even toNFA will do this since it's on by default:
But it will throw an error for non-trivial backreferences that cannot be resolved:
toNFA(/(#+).*\1|foo/);// Error: Backreferences are not supported.
The only way to parse the RegExp despite unresolvable backreferences is to remove the backreferences. This means that the result will be imperfect but it might still be useful.
Prefer using the parser to remove assertions if possible. The parser is quite clever and will optimize based on that assertions can be removed resulting in faster parse times.
However, simply removing assertions is not ideal since they are a lot more common than backreferences. To work around this, refa has AST transformers. AST transformers can make changes to a given AST. While each transformer is rather simple, they can also work together to accomplish more complex tasks. Applying and removing assertions is one such task.
The simplest transformer to remove assertions (among other things) is the simplify transformer. It will inline expressions, remove dead branches, apply/remove assertions, optimize quantifiers, and more.
import { JS, NFA, Transformers, transform } from "refa";const regex = /\b(?!\d)\w+\b|->/;const { expression, maxCharacter } = JS.Parser.fromLiteral(regex).parse();console.log(JS.toLiteral(expression));// => { source: '\\b(?!\\d)\\w+\\b|->', flags: '' }const modifiedExpression = transform(Transformers.simplify(), expression);console.log(JS.toLiteral(modifiedExpression));// => { source: '(?<!\\w)[A-Z_]\\w*(?!\\w)|->', flags: 'i' }// Most assertions have been removed but the patterns are still equivalent.// The only assertions left assert characters beyond the edge of the pattern.// Removing those assertions is easy but slightly changes the pattern.const finalExpression = transform(Transformers.
AST transformers can handle a lot of assertions, but there are limitations. Transformers cannot handle assertions that are too complex or require large-scale changes to the AST. Let's take a look at a few examples:
Transformers.simplify is very aggressive when it comes to assertions. It will try to remove assertions whenever possible even if it means that the overall AST will become more complex (within some limits). This may result in longer/more complex regexes, but it will also allow NFA and ENFA to support many more regexes.