Sketch-Driven Regular Expression Generation from Natural Language and Examples

Sketch-Driven Regular Expression Generation from Natural Language and Examples Xi Ye♦ Qiaochu Chen♦ Xinyu Wang♠ Isil Dillig♦ Greg Durrett♦ ♦Department of Computer Science, The University of Texas at Austin ♠Computer Science and Engineering Department, University of Michigan, Ann Arbor {xiye,qchen,isil,gdurrett}@cs.utexas.edu xwangsd@umich.edu Abstract Recent systems for converting natural lan- guage 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 exam- ples 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 nat- ural language description into an intermediate sketch, which is an incomplete regex contain- ing 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 exam- ples. Our semantic parser can be trained purely from weak supervision based on correct- ness 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 com- pletely fail on.1 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 1Code and data available at https://github.com /xiye17/SketchRegex/. posts on Stack Overflow, with over 200,000 posts. Recent research has attempted to build se- mantic parsers that can translate natural language descriptions into regexes, via rule-based tech- niques (Ranta, 1998), semantic parsing (Kushman and Barzilay, 2013), or seq-to-seq neural network models (Locascio et al., 2016; Zhong et al., 2018a; Park et al., 2019). Although this prior work has achieved relatively high accuracy on benchmark datasets, trained models still do not generalize to real-world applications: These benchmarks de- scribe 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 lan- guage descriptions that are longer and more com- plicated (Zhong et al., 2018b). Moreover, these descriptions may be under-specified or ambigu- ous. One way to supplement such descriptions is by including positive/negative examples of strings for the target regex to match. In fact, such exam- ples are typically provided by users posting ques- tions 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 …

Content truncated to 500 words