arxiv-1608-03000 SRC-0249 · paper

Neural Generation of Regular Expressions from Natural Language with Minimal Domain Knowledge

Nicholas Locascio, Karthik Narasimhan, Eduardo DeLeon, Nate Kushman, Regina Barzilay

Created: 2016-08-09 · Ingested: 2026-09-19

This paper explores the task of translating natural language queries into regular expressions which embody their meaning. In contrast to prior work, the proposed neural model does not utilize domain-specific crafting, learning to translate directly from a parallel corpus. To fully explore the potential of neural models, we propose a methodology for collecting a large corpus of regular expression, natural language pairs. Our resulting model achieves a performance gain of 19.6% over previous state-of-the-art models.

In brief

A generic attention LSTM sequence-to-sequence model, trained only on text-regex pairs, beats a semantic parser built around regex-specific semantic equivalence checks. That cuts against the assumption that formal-language generation needs domain-specific machinery.

The model (Deep-RegEx) is 6 layers: 1 embedding, 2 encoder LSTM layers, 2 decoder layers, 1 dense output, width 512, global attention, dropout 0.25, 20 epochs. It is compared to Semantic-Unify (Kushman and Barzilay 2013) and a bag-of-words nearest-neighbour baseline on KB13 (824 pairs) and on NL-RX, a new 10,000-pair corpus built by generating regexes from a 15-non-terminal, 6-terminal grammar with synthetic verbalizations, then having Mechanical Turk workers paraphrase them.

On NL-RX-Turk test, DFA-equality accuracy is 58.2% versus 38.6% for Semantic-Unify and 16.4% for BoW-NN. On NL-RX-Synth it is 88.7% versus 46.3%. On KB13 the two are near-tied, 65.6% versus 65.5%.

The comparison is measured with a shared DFA-equivalence checker and the baseline was retrained with the original authors' input. There is no ablation of attention, depth, or the paraphrase step, and only 1 architecture family is tested.

The gain is partly a dataset story: KB13 has only 45% unique regexes against 97% for NL-RX-Turk, so the older benchmark rewards memorisation. Accuracy also scales with training size, so the headline margin is tied to having 10,000 examples.

If you were assuming formal-syntax targets need hand-built semantics, check whether your benchmark is just small and duplicated.

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.

supportsFor translating English descriptions into regular expressions, a generic attention-based sequence-to-sequence model trained only on description/regex pairs matches a domain-engineered semantic parser on a small corpus (814 examples) and beats it by a wide margin once the training corpus is scaled to 10,000 pairs, with no semantic-equivalence machinery built in.