ExReg: Using Automated Example Generation to Guide Candidate Disambiguation and Validation in Regular Expression Construction

Abstract

Regular expressions (regexes) are widely used in software development but remain difficult to author and validate due to their compact syntax and subtle semantics. While large language models (LLMs) can now generate regexes from natural-language descriptions, their outputs often miss developer intent, and existing refinement techniques rely on developers to craft positive and negative examples—especially discriminatory ones that expose fine-grained semantic differences. Producing such examples is cognitively demanding and often leaves regexes under-validated. This paper introduces ExReg, a human-in-the-loop workflow that shifts this burden away from developers. Given an ambiguous natural-language specification, an LLM first proposes multiple plausible regex candidates. Instead of requiring developers to devise discriminative examples, the system automatically generates them using SMT-based constraint solving. Developers need only affirm whether these synthesized test strings match their intent. The system further mutates candidates and reuses discriminative strings to systematically eliminate incorrect patterns. Across six benchmark datasets and six state-of-the-art LLMs, ExReg accurately identifies valid regexes—or determines that none are appropriate—while requiring only minimal developer validation. In particular, ExReg achieves an average accuracy of 87%, while requiring users to inspect only 5 examples on average, each with a mean length of 8 characters and an inter-example waiting time of under 13 seconds. These results highlight how automated example generation guided by formal methods and mutations can improve the reliability, efficiency, and trustworthiness of LLM-assisted regex pattern generation.