An optimizer for the regular expression AST. Acts upon the AST of a parsed regular expression pattern, transforming it in-place without moving to a compilation step. Where possible, it aims to reduce branching as much as possible in the expression by reducing usage of `|`. Here is a summary of the optimizations that it will do: Class Simplification : `[aab]` => `[ab]` `[aa]` => `[a]` Class Reduction : `[a]` => `a` Range Construction : `[abc]` => `[a-c]` Rune Merging into Range : `[aa-c]` => `[a-c]` Range Merging : `[a-cc-e]` => `[a-e]` `[a-cd-e]` => `[a-e]` `[a-cb-e]` => `[a-e]` Alternation to Optional : `a|` => `a?` Alternation to Optional Non-Greedy : `|a` => `a??` Alternation Reduction : `a|a` => `a` Alternation to Class : `a|b` => `[ab]` Class Union : `[a0]|[b1]` => `[a0b1]` `[a-b]|c` => `[a-bc]` `a|[b-c]` => `[b-ca]` Wildcard Reduction : `a|.` => `.` `.|a` => `.` `[ab]|.` => `.` `.|[ab]` => `.` Common Suffix Elimination : `blueberry|strawberry` => `(?:blue|straw)berry` Common Prefix Elimination : `abi|abe` => `ab(?:i|e)` Composition: Consume All to Anchored End `.*$` => <special opcode> `.+$` => `.` <special opcode> Possible future improvements: - Change the AST of alternations to be a list instead of a tree, so that constructions such as `(ab|bb|cb)` can be considered in whole by the affix elimination optimizations. - Introduce specialized opcodes for certain classes of repetition. - Add Common Infix Elimination. - Measure the precise finite minimum and maximum of a pattern, if available, and check against that on any strings before running the virtual machine.