Benchmarking Multimodal Regex Synthesis with Complex Structures (2020)

Abstract: Existing datasets for regular expression (regex) generation from natural language are limited in complexity; compared to regex tasks that users post on StackOverflow, the regexes in these datasets are simple, and the language used to describe them is not diverse. We introduce StructuredRegex, a new regex synthesis dataset differing from prior ones in three aspects. First, to obtain structurally complex and realistic regexes, we generate the regexes using a probabilistic grammar with pre-defined macros observed from real-world StackOverflow posts. Second, to obtain linguistically diverse natural language descriptions, we show crowdworkers abstract depictions of the underlying regex and ask them to describe the pattern they see, rather than having them paraphrase synthetic language. Third, we augment each regex example with a collection of strings that are and are not matched by the ground truth regex, similar to how real users give examples. Our quantitative and qualitative analysis demonstrates the advantages of StructuredRegex over prior datasets. Further experimental results using various multimodal synthesis techniques highlight the challenge presented by our dataset, including non-local constraints and multi-modal inputs.

## introduction regular expressions (regexes) are known for their usefulness and wide applicability, and yet they are hard to understand and write, even for many programmers @xcite . recent research has therefore studied how to construct regexes from natural language (nl) descriptions, leading to the emergence of nl-to-regex datasets including positive: negative: natural language description i want three hyphen-separated numbers. the first and second numbers have 3 digits while the last one has 4 digits. kb13 @xcite and nl-turk @xcite . however, kb13 is small in size, with only 814 nl-regex pairs with even fewer distinct regexes. @xcite subsequently employed a generate-and-paraphrase procedure @xcite to create the larger nl-turk dataset. however, the regexes in this dataset are very simple, and the descriptions are short, formulaic, and not linguistically diverse because of the paraphrasing annotation procedure @xcite . as a result, even when models achieve credible performance on these datasets, they completely fail when evaluated on the stackoverflow dataset @xcite , a real-world dataset collected from users seeking help on stackoverflow. the limited size of this dataset (only 62 nl-regex pairs) makes it (a) i need to validate the next pattern: starts with "c0" and finish with 4 digits exactly. and(startwith(<@xmath0,endwith(rep(<num>,4))) figure 2 : examples of complex regexes from stackoverflow. each regex can be viewed as a set of components composed with a high-level template. regex (a), for example, can be as viewed the intersection of two constraints specifying the characteristics of the desired regex. (rep means repeat). to enable the development of large-scale neural models in this more realistic regex setting, we present structuredregex, a new dataset of english language descriptions and positive/negative examples associated with complex regexes. using a new data collection procedure (figure 1 ), our dataset addresses two major limitations in nl-turk. first, we generate our regexes using a structured probabilistic grammar which includes macro rules defining high-level templates and constructions that involve multiple basic operators. these grammar structures allow us to sample more realistic regexes, with more terminals and operators, while avoiding vacuous regexes. by contrast, the random sampling procedure in nl-turk leads to simple regexes, and attempting to sample more complex regexes results in atypical regex structures or even contradictory regexes that do not match any string values @xcite . second, to achieve more realistic language descriptions, we prompt turkers to write descriptions based on abstract figures that show the desired regexes. we design a set of visual symbols and glyphs to draw a given regex with minimal textual hints. we thereby avoid priming turkers to a particular way of describing things, hence yielding more linguistically diverse descriptions. using this methodology, we collect a total of 3,520 english descriptions, paired with ground truth regexes and associated positive/negative examples. we conduct a comprehensive analysis and demonstrate several linguistic features present in our dataset which do not occur in past datasets. we evaluate a set of baselines, including grammar-based methods and neural models, on our dataset. in addition, we propose a novel decoding algorithm that integrates constrained decoding using positive/negative examples during inference: this demonstrates the potential of our dataset to enable work at the intersection of nlp and program synthesis. the performance of the best existing approach on structuredregex only reaches 37%, which is far behind 84% on nl-turk. however, this simple model can nevertheless solve 13% of the stackoverflow dataset, indicating that further progress on this dataset can be useful for real-world scenarios. ## structured regex generation process we first describe the structured generative process we adopt to produce the regexes in our dataset. for better readability, we denote regexes using a domain specific language (dsl) similar to regex dsls in prior work @xcite . our dsl has the same expressiveness as a standard regular language and can be easily mapped back to standard regular expressions. 2 to collect the nl-turk dataset, locascio et al. (2016) sampled regexes using a hand-crafted grammar similar to a standard regex dsl. however, regexes sampled from this process can easily have conflicts (e.g. and(<let>,<@xmath1.g. or(<let>,<@xmath2. one solution to this problem is rejection sampling, but this still does not yield regexes with compositional, realworld structure. we show three prominent types of composition observed from stackoverflow in figure 2. each regex above is built by assembling several sub-regexes together according to a highlevel template: regex (a) is the intersection of two base regexes expressing constraints, regex (b) is a sequence of three simple parts, and regex (c) is a cattemp concat( comp , comp , comp ) reprange( expr ,1,2) literal reprange( expr ,1,2) • • • • • • • • • one or two digits then "." and one or two digits septemp concat( seg , delimiter , seg , delimiter , seg ) cattemp inttemp inttemp const const • • • • • • • • • • • • • • • three delimited values, first will be an integer, with other two being either numeric or a string inttemp and( cons , cons ) startwith( expr ) endwith( expr ) • • • • • • starts with "c0" and end with 4 digits cons start[end]with(expr) | not(start[end]with(expr)) # must (not) start/end with contain(expr) | not(contain(expr)) # must (not) contain rep(<any>,k) | repatleast(<any>,k) |reprange(<any>,k,k) # length constraints advstartwithcons | advendwithcons # adversative macro (e.g., start with capitals except a) condcontaincons # conditional macro. (e.g. letter, if contained, must be after a digit) comp literal | or(literal,literal,...) # literals like digits, letters, strings, or set of literals. rep(expr,k) | repatleast(expr,k) | reprange(expr,k,k) figure 3 : examples of our top-level templates and how they cover the three regexes in figure 2 , and overview of sub-regexes (in table) that can possibly be derived from cons and comp. expr as a category here indicates various different constrained sets of sub-regexes. more detail about this structure is available in the full grammar in the appendix. a string of numbers and digits that must start with a number except "0". inttemp and( cons , cons ) consistofcons advstartwithcons repatleast( literalset ,1) and(startwith( literal ),not(startwith( literal ))) or(<num>,<@xmath3,<@xmath4,1),and(startwith(<@xmath5,not(startwith(<0>)))) figure 4 : the generation of a deep and complex regex using our grammar. here, advstartwithcons is a macro rule that yields a complex sub-tree with an adversative constraint. ## dataset analysis we demonstrate the advantages of our dataset over prior datasets @xcite through both quantitative and qualitative analysis. we list the key statistics of our dataset as well as kb13 and nl-turk for comparison in ## methods we evaluate the accuracy of both existing grammar-based approaches and neural models, as well as a novel method that targets the multimodal nature of our dataset. ## experiments 6.1 comparison to prior datasets we evaluate the baseline models on kb13, nl-turk, and our dataset ( ## conclusion we introduce structuredregex, a new dataset for regex synthesis from natural language and examples. our dataset contains compositionally structured regexes paired with linguistically diverse language, and organically includes distinguishing examples. better methods are needed to solve this dataset; we show that such methods might generalize well to real-world settings. a regex dsl b details of structured grammar b.1 grammar rules see figure 7.