# Sketch-Driven Regular Expression Generation from Natural Language and Examples

arXiv: https://arxiv.org/abs/1908.05848 · HTML: https://mlsanity.com/paper/1908.05848/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2019.

## Built on by (most cited first, 10 of 10)

- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [Recent Advances in Text-to-SQL: A Survey of What We Have and What We Expect](https://mlsanity.com/paper/2208.10099/) (2022)
- [LLM-JEPA: Large Language Models Meet Joint Embedding Predictive Architectures](https://mlsanity.com/paper/2509.14252/) (2025)
- [Formal Specifications from Natural Language](https://mlsanity.com/paper/2206.01962/) (2022)
- [Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database](https://mlsanity.com/paper/2211.05165/) (2022)
- [InfeRE: Step-by-Step Regex Generation via Chain of Inference](https://mlsanity.com/paper/2308.04041/) (2023)
- [An Evaluation Study of Hybrid Methods for Multilingual PII Detection](https://mlsanity.com/paper/2510.07551/) (2025)
- [Regular Expressions for Fast-response COVID-19 Text Classification](https://mlsanity.com/paper/2102.09507/) (2021)
- [Lost in Translation? Converting RegExes for Log Parsing into Dynatrace Pattern Language](https://mlsanity.com/paper/2506.19539/) (2025)
- [Domain Agnostic Text Redaction from Natural Language Rules using Instruction Tuning](https://mlsanity.com/paper/2608.14693/) (2026)

## Abstract (arXiv)

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. Realworld 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.