I think the Thompson NFA matcher could be pushed further if someone would bother to do it. One example is that since it finds all solutions to a given regular

I think the Thompson NFA matcher could be pushed further if someone would bother to do it. One example is that since it finds all solutions to a given regular expression, it could be used within a larger backtracking matcher to support back-references. Consider: (a+)(a+)=\1 With an input like: aaaaa=aa The matcher will find these strings by the time it gets to the '=': (a)(aaaa)= (aa)(aaa)= (aaa)(aa)= (aaaa)(a)= Each match will end up as a separate still-existing thread in the Thompson matcher. Instead of pruning them as soon as possible, keep them and recursively match the rest of the string with the back-reference set in turn to each until a match is found.