Sketch-Driven Regular Expression Generation from Natural Language and Examples (2020)

Abstract: Recent systems for converting natural language descriptions into regular expressions (regexes) have achieved some success, but typically deal with short, formulaic text and can only produce simple regexes. Real-world regexes are complex, hard to describe with brief sentences, and sometimes require examples to fully convey the user’s intent. We present a framework for regex synthesis in this setting where both natural language (NL) and examples are available. First, a semantic parser (either grammar-based or neural) maps the natural language description into an intermediate sketch, which is an incomplete regex containing holes to denote missing components. Then a program synthesizer searches over the regex space defined by the sketch and finds a regex that is consistent with the given string examples. Our semantic parser can be trained purely from weak supervision based on correctness of the synthesized regex, or it can leverage heuristically derived sketches. We evaluate on two prior datasets (Kushman and Barzilay 2013; Locascio et al. 2016) and a real-world dataset from Stack Overflow. Our system achieves state-of-the-art performance on the prior datasets and solves 57% of the real-world dataset, which existing neural systems completely fail on.1

## introduction regular expressions (regexes) are widely used in various domains, but are notoriously difficult to write: regex is one of the most popular tags of posts on stack overflow, with over 200,000 posts. recent research has attempted to build semantic parsers that can translate natural language descriptions into regexes, via rule-based techniques @xcite , semantic parsing @xcite , or seq-to-seq neural network models @xcite @xcite . although this prior work has achieved relatively high accuracy on benchmark datasets, trained models still do not generalize to real-world applications: these benchmarks describe simple regexes with short natural language descriptions and limited vocabulary. real-world regexes are more complex in terms of length and tree-depth, requiring natural language descriptions that are longer and more complicated @xcite . moreover, these descriptions may be under-specified or ambiguous. one way to supplement such descriptions is by including positive/negative examples of strings for the target regex to match. in fact, such examples are typically provided by users posting questions on stack overflow. previous methods cannot leverage the guidance of examples at test time beyond naive postfiltering. in this paper, we present a framework to exploit both natural language and examples for regex synthesis by means of a sketch. rather than directly mapping the natural language into a concrete regex, we first parse the description into an intermediate representation, called a sketch, which is an incomplete regular expression that contains holes to denote missing components. this representation allows our parser to recognize partial structure and fragments from the natural language without fully committing to the regex's syntax. we then use an off-the-shelf program synthesizer, mildly customized for our task, to figure 1: our regex synthesis approach from language and positive/negative examples. natural language is parsed into a sketch using a semantic parser. the finished sketch (the root node of the tree) is passed to a program synthesizer, which searches over programs consistent with the sketch and examples. each leaf node in the search tree is a concrete regex; we return the first one consistent with all the examples. produce a regex consistent with both the sketch and the provided examples. critically, this twostage approach modularizes the language interpretation and program synthesis, allowing us to freely swap out these components. we evaluate our framework on several english datasets. because these datasets vary in scale, we consider two sketch generation approaches: neural network-based with a seq-to-seq model @xcite or grammar-based with a semantic parser @xcite . we use two large-scale datasets from past work, the kb13 dataset of @xcite and the turk dataset of @xcite , augmented with automatically produced positive/negative examples for each regex. our neural sketch model can exploit these large labeled datasets, allowing our sketch-driven approach to outperform existing seq-to-seq methods, even when those methods are modified to take advantage of examples. to test our model in a more realistic setting, we also evaluate on a dataset of real-world regex synthesis problems from stack overflow. these problems organically have english language descriptions and paired examples that the user wrote to communicate their intent. this dataset is small, only 62 examples; to more robustly handle this setting without large-scale training data, we instantiate our sketch framework with a grammar-based semantic parser. our approach can solve 57% of the benchmarks, where existing deep learning approaches solve less than 10%. more data is needed, but this dataset can motivate further work on more challenging regex synthesis problems. ## regex synthesis framework in this section, we illustrate how our regex synthesis framework works using a real-world example from a stack overflow post. 2 in this post, the user describes the desired regex as ''the max number of digits before comma is 15 then accept at max 3 numbers after the comma.'' additionally, the user provides eight positive/ negative examples to further specify their intent. in this instance, the nl description is underspecified: the description doesn't clearly say whether the decimal part is compulsory, and a period (.) is mistakenly described as a comma. these issues in nl pose problems for systems attempting to directly generate the target regex based only on the description. figure 1 shows how our framework handles this example. the natural language description is first parsed into a sketch by a semantic parser, which in this case is grammar-based (section 3.2) but could also be neural in nature (section 3.1). the purpose of the sketch is to capture useful components from the description as well as the high-level structure of the regex. for example, the sketch in figure 1 depicts the target regex as the concatenation of two regexes, where the first regex likely involves composition @xmath1,> in some way. we later feed this sketch, together with positive/negative examples, into the synthesizer, which enumeratively instantiates holes with constructs from our regex dsl until a consistent regex is found. we describe our semantic parsers in section 3 and our synthesizer in section 4. regex/sketch dsl our regex language (figure 2 ) is similar to the one presented in @xcite , but more expressive. our dsl adds some additional constructs, such as repeat(s,k), repeating a regex s exactly k times, in our dsl, which is not supported by @xcite . this dsl is equivalent in power to standard regular expressions, in that it can match any regular language. our sketch language builds on top of our regex dsl by adding a new construct called a ''constrained hole'' (the red rule in figure 2 ). our sketch dsl introduces an additional grammar symbol s and the notion of hole . holes can be produced with the rule {s 1 , . . . , s m }, where each s i on the right-hand side is also a sketch. a concrete regex r belongs to the space of regexes defined by a constrained hole if at least one of its s i defines any concrete regex r, that is, one of the subtrees in r. put another way, the regex rooted at s must contain a subtree that matches at least one of the s i , but it does not have to match all of them. however, the synthesizer we use supports using the s i in its search heuristic to prefer certain programs. in this fashion, the constraint serves as a hint for the leaf nodes of the regex, but it only loosely constraints the structure. for example, consider the sketch shown in figure 1 . here, all programs on the leaf nodes of the search tree are included in the space of regexes defined by this sketch. note that the first two explored regexes only include some of the components mentioned in the sketch (e.g., <@xmath2,1,3)), whereas the final correct regex happens to include every mentioned component. ## semantic parser given a natural language description @xmath3, l 2 , . . . , l m , our semantic parser generates a sketch s that encapsulates the user's intent. when combined with examples in the synthesizer, this sketch should yield a regex matching the ground truth regex. as stated before, our semantic parser is a modular component of our system, so we can use different parsers in different settings. we investigate two paradigms of semantic parser: a seq-to-seq neural network parser and a grammarbased parser, as well as two ways of training the parser: maximum likelihood estimation based on a pseudo-gold sketch and maximum marginal likelihood based on whether the sketch leads to the correct synthesis result. figure 3 : examples of rules and the parse tree for building one possible derivation. the left side of a rule is the source sequence of tokens or syntactic categories (marked with a @xmath0program denotes a concrete regex without holes and $sketch denotes sketches containing holes. lexical rule 4 denotes mapping any token of an integer to its value. ## program synthesizer in this section, we describe the program synthesizer, which takes as input a sketch and a set of examples and returns a regex that is consistent with the given examples. specifically, our synthesizer explores the space of programs defined by the sketch while additionally being guided by the examples. enumerative synthesis from sketches we use an enumeration-based program synthesizer that is a generalized version of the regex synthesizer proposed by @xcite . given a program sketch and a set of positive/negative examples, the synthesizer searches the space of programs that can be instantiated by the given sketch and returns a concrete regex that accepts all positive examples and rejects all negative examples. specifically, the synthesizer instantiates each hole with our dsl constructs or the components for the hole. if a hole is instantiated with a dsl terminal such @xmath4, the hole will just be replaced by the terminal. if a hole is instantiated using a dsl operator, the hole will first be replaced by this operator, we introduce new holes for its arguments, and we require the components for at least one of the holes to be the original holes' components. see figure 1 for an example of regexes that could be instantiated from the given sketch. whenever the synthesizer produces a complete instantiation of the sketch (i.e., a concrete regex with no holes), it returns this regex if it is also consistent with the examples (accepts all positive and rejects all negative examples). otherwise, the synthesizer moves on to the next program in the sketch language. the synthesizer terminates when it either finds a regex consistent with the examples or it has exhausted every possible instantiation of the sketch up to depth d. our synthesizer differs from that of @xcite in two main ways. first, their regex language is extremely restricted, only allowing the characters 0 and 1 (a binary alphabet). second, their technique enumerates dsl programs from scratch, whereas our synthesizer performs enumeration based on an initial sketch. this significantly reduces the search space and therefore allows us to synthesize complex regexes much more quickly. enumeration order our synthesizer maintains a worklist of partial programs to complete, and enumerates complete programs in increasing order of depth. specifically, at each step, we pop the ## datasets we evaluate our framework on two datasets from prior work, kb13 and turk, and a new dataset, stackoverflow. we list the statistics about these datasets and a typical example from each of them in kb13 kb13 (kushman and barzilay, 2013) was created with crowdsourcing in two steps. first, workers from amazon mechanical turk wrote the original english language descriptions to describe a subset of the lines in a file. then, a set of programmers from odesk are required to write the corresponding regex for each of these language descriptions. in total, 834 pairs of description and regex are generated. turk @xcite collected the largerscale turk dataset to investigate the performance figure 4 : examples of natural language description from each of the three datasets. turk tends to be very formulaic, while stackoverflow is longer and much more complex. the generate-and-paraphrase procedure is an efficient way to obtain description-regex pairs, but it also leads to several issues that we find in the dataset. the paraphrase procedure inherently limits the originality in natural language, leading to artificial descriptions. in addition, because the regexes are stochastically generated without being validated, many of them are syntactically correct but semantically meaningless. for instance, the regex \b(<@xmath5. these null regexes account for around 15% of the data. moreover, other regexes have formulaic descriptions since their semantics are randomly made up (more examples can be found in section 6). ## conclusion we have proposed a sketch-driven regular expression synthesis framework that utilizes both natural language and examples, and we have instantiated this framework with both a neural and a grammarbased parser. experimental results reveal the artificialness of existing public datasets and demonstrate the advantages of our approach over existing research, especially in real-world settings.