Sketch-Driven Regular Expression Generation from Natural Language and Examples

Xi Ye, Qiaochu Chen, Xinyu Wang, Isil Dillig, Greg Durrett

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
Anthology ID:
2020.tacl-1.44
Volume:
Transactions of the Association for Computational Linguistics, Volume 8
Month:
Year:
2020
Address:
Cambridge, MA
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
679–694
Language:
URL:
https://aclanthology.org/2020.tacl-1.44
DOI:
10.1162/tacl_a_00339
Bibkey:
Cite (ACL):
Xi Ye, Qiaochu Chen, Xinyu Wang, Isil Dillig, and Greg Durrett. 2020. Sketch-Driven Regular Expression Generation from Natural Language and Examples. Transactions of the Association for Computational Linguistics, 8:679–694.
Cite (Informal):
Sketch-Driven Regular Expression Generation from Natural Language and Examples (Ye et al., TACL 2020)
Copy Citation:
PDF:
https://preview.aclanthology.org/starsem-semeval-split/2020.tacl-1.44.pdf
PDF Search