arxiv-1908-03316 SRC-0251 · paperMulti-modal Synthesis of Regular Expressions
Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, Isil Dillig
Created: 2019-08-09 · Ingested: 2026-09-19
https://arxiv.org/abs/1908.03316(opens in a new tab)In this paper, we propose a multi-modal synthesis technique for automatically constructing regular expressions (regexes) from a combination of examples and natural language. Using multiple modalities is useful in this context because natural language alone is often highly ambiguous, whereas examples in isolation are often not sufficient for conveying user intent. Our proposed technique first parses the English description into a so-called hierarchical sketch that guides our programming-by-example (PBE) engine. Since the hierarchical sketch captures crucial hints, the PBE engine can leverage this information to both prioritize the search as well as make useful deductions for pruning the search space. We have implemented the proposed technique in a tool called Regel and evaluate it on over three hundred regexes. Our evaluation shows that Regel achieves 80% accuracy whereas the NLP-only and…
In brief
Combining a natural-language parse with input/output examples synthesizes regular expressions far more often than either modality alone. Regel parses an English description into a "hierarchical sketch" with constrained holes, then runs a programming-by-example search that uses the sketch both to prioritize enumeration and to compute tighter over- and under-approximations for pruning, plus symbolic integers solved with Z3 instead of enumerating repeat counts.
Evaluation covers over 300 regexes from 2 sources: 200 benchmarks adapted from the DeepRegex data set, annotated by users with on average 4 positive and 5 negative examples, and 122 harder StackOverflow tasks with ground truth converted by hand into the DSL. Regel finds the intended regex in 80% of cases; the pure PBE variant reaches 26% and the DeepRegex seq2seq baseline 43%. Against an adapted AlphaRegex, the PBE engine is an order of magnitude faster on sketch completion, including when AlphaRegex's search is given the sketch.
The comparison is well isolated: Regel-Pbe is the same engine with an unconstrained sketch, and AlphaRegex is given the sketch too, so the gain is attributable to the hints and to the engine separately. Weaker points: training sketches were constructed by the authors, manually for StackOverflow, and the user study of 20 participants reporting users are twice as likely to succeed is self-run.
Settings differ by data set (10s and top-1 vs 60s and top-5), and up to 4 rounds of extra examples are supplied interactively, so single-shot accuracy is not what is reported. The DSL excludes capture groups and lookaround.
If you treat regex generation as an NLP task, this says the examples are doing most of the disambiguation work.
Written from the abstract by claude-opus-5 on 2026-10-17, with every figure checked against it. Not a substitute for the paper.
Referenced by
Claims in this catalog that draw on this source, and whether as support or counterpoint.