vregex

RegEx engine based on ASTs and Automata

Github

Details

My initial plan was to closely follow what we do with Thompson's construction. Get a RegEx, convert it to a ∈-NFA, convert it into a DFA using subset construction, and then finally minimise the DFA.

After starting the implementation, I had to add another step. I had to parse the RegEx into an AST. That also made me realise that implementations of RegEx aren't consistent. Different libraries have slight differences in their syntax. I made a decision here to not follow another implementation or a standard closely here. This gave me the freedom to focus on what I really wanted to understand from this project — graphs and automata.

There was also the fact that DFAs converted from NFAs grow exponentially in the number of nodes. Instead, having a set of possible states at every step traded off a higher time complexity for much better space complexity. And so I decided to use the constructed NFA as is, in the end.

vregex live

 

Click here to fill a demo value.

. matches any character.

| is used for alternate: a|b matches a or b.

[] is used for defining classes: [abc] matches any of the characters within.

Use ^ at the beginning of a class([^abc]) to make it exclusive.

There are also character classes available. Lowercase classes are inclusive, uppercase are exclusive.

\d, and \D for digits.

\l, and \L for lowercase characters.

\u, and \U for uppercase characters.

\s, and \S for whitespace.