  Given a regular expression $R$ and a string $Q$, the regular expression
parsing problem is to determine if $Q$ matches $R$ and if so, determine how it
matches, e.g., by a mapping of the characters of $Q$ to the characters in $R$.
Regular expression parsing makes finding matches of a regular expression even
more useful by allowing us to directly extract subpatterns of the match, e.g.,
for extracting IP-addresses from internet traffic analysis or extracting
subparts of genomes from genetic data bases. We present a new general
techniques for efficiently converting a large class of algorithms that
determine if a string $Q$ matches regular expression $R$ into algorithms that
can construct a corresponding mapping. As a consequence, we obtain the first
efficient linear space solutions for regular expression parsing.
