Efficiently extracting full parse trees using regular expressions with capture groups
Niko Schwarz, Aaron Karper, Oscar Nierstrasz · 2015
Regular expressions with capture groups offer a concise and natural way to define parse trees over the text that they are parsing, however classical algorithms only return a single match for each capture group, not the full parse tree. We describe an algorithm based on finite-state automata that extracts full parse trees from text in Θ ( n,m ) time and Θ( dn + m ) space (where n is the size of the text, m the size of the pattern, and d the number of groups in the pattern). It is the first to do so in a single pass with complete control over greediness. This allows the algorithm to process streaming data using all constructs familiar to users of regular expressions.