Neuro-Symbolic Regex Synthesis Framework via Neural Example Splitting
Due to the practical importance of regular expressions (regexes, for short),
there has been a lot of research to automatically generate regexes from
positive and negative string examples. We tackle the problem of learning
regexes faster from positive and negative strings by relying on a novel
approach called `neural example splitting'. Our approach essentially split up
each example string into multiple parts using a neural network trained to group
similar substrings from positive strings. This helps to learn a regex faster
and, thus, more accurately since we now learn from several short-length
strings. We propose an effective regex synthesis framework called `SplitRegex'
that synthesizes subregexes from `split' positive substrings and produces the
final regex by concatenating the synthesized subregexes. For the negative
sample, we exploit pre-generated subregexes during the subregex synthesis
process and perform the matching against negative strings. Then the final regex
becomes consistent with all negative strings. SplitRegex is a
divided-and-conquer framework for learning target regexes; split (=divide)
positive strings and infer partial regexes for multiple parts, which is much
more accurate than the whole string inferring, and concatenate (=conquer)
inferred regexes while satisfying negative strings. We empirically demonstrate
that the proposed SplitRegex framework substantially improves the previous
regex synthesis approaches over four benchmark datasets.