Yeah I think you are right -- the nongreedy match can be simply written as a more awkward pattern. I think regular language negation and intersection also help

Yeah I think you are right -- the nongreedy match can be simply written as a more awkward pattern. I think regular language negation and intersection also help (which the rarer derivatives-based implementations seem to have). They are still regular and equivalent in power, but there's a richer set of operators for writing patterns. I would also divide it into the "recognition problem" and the "parsing/capturing problem". Recognition is just yes/no -- does it match? And notably that excludes common regex APIs that either return the end position (Python's re.match) or search (re.search). It is more like math -- is it in the set or not? For the recognition problem, there's no difference between greedy and non-greedy, in terms of the result. (It does matter in terms of performance, which shows up in practice in backtracking engines!) But parsing / capturing is more relevant to programmers. I don't remember all the details but there is some discussion on the interaction between greediness and capturing here: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html It looks like it can all be done in linear time and RE2 supports it fine. So in that case maybe the 2 questions are closer than I thought. I have a very similar set of regexes that I use for parsing (my own) HTML, but I use one regex for each kind of token, and I do it with the help of an explicit stack. I'm using Python's engine so I think it is better to separate each case, for performance reasons. But maybe with RE2 it would be fine to combine them all into one big expression as is done here, for "parallel" matching. The expression is a little weird because it's solving a specific problem and not something more general (which is useful and natural).