[phunge]

If you're interested in getting parse trees from regexes (ie all the submatch locations), check out Kleenex, it looks really interesting and is based on some new research. Full parse trees are a harder problem than matching, and one that is not a primary focus in RE2 performance AFAICS.

[nly]

Isn't it true that once you have backtracking in your regex engine that there's no longer a guarantee that there's only a single parse tree?

I've found the hardest part of using e.g. a recursive descent parser is having to correct captured state while backtracking.