Implements the basic ideas described by Russ Cox which basically uses Thompson's Construction to generate a non-deterministic finite automaton. The generated NFA can be used to match strings against a regex in linear time.
This is mainly for educational purposes. If you are searching for a production ready regex engine which doesn't use backtracking, check out google's re2.
- Quantifiers: "*", "+", "?", "{3,4}"
- Character classes: "[abc]", "[^abc]"
- Ranges: "[a-z]"
- Metacharacters: "\d", "\s", ...
- Grouping: "(abc)*"
- Alternation: "a|b"
- Wildcard: "."
- Group extraction
- ...