Multi-modal Synthesis of Regular Expressions

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

REVIEW 3 major objections 7 minor 55 references

Multi-modal Synthesis of Regular Expressions

T0 review · 3 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Combining English with examples solves 80% of regex benchmarks, the paper reports.

desk verdict A solid synthesis paper with a genuinely new multi-modal idea, but the headline 80% accuracy number is an oracle-in-the-loop figure, not a one-shot user number. read the letter →

arxiv 1908.03316 v3 pith:I4SVOUHD submitted 2019-08-09 cs.PL

Qiaochu Chen , Xinyu Wang , Xi Ye , Greg Durrett , Isil Dillig This is my paper · ORCID

classification cs.PL

keywords regularexpressionsynthesisprogrammingbyexamplenaturallanguageunderstandinghierarchicalsketchesprogramsemanticparsingSMT-basedpruningmulti-modalspecification

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes Regel, a synthesizer that builds regular expressions from both an English description and positive/negative examples. It argues the two modalities complement each other: natural language alone is ambiguous, while examples alone underdetermine the intended pattern. The central mechanism parses the English text into a hierarchical sketch, a regex skeleton with constrained holes, and feeds that sketch to a programming-by-example engine that searches for a completion consistent with the examples. On 322 benchmarks, Regel solves 80% within four interaction rounds, compared with 43% for a language-only baseline and 26% for an example-only baseline. The paper also reports that sketch-guided pruning and symbolic-integer reasoning make its search roughly an order of magnitude faster than an adapted prior example-based synthesizer.

What carries the argument

The load-bearing object is the hierarchical sketch, or h-sketch: a regex abstract syntax tree in which leaves may be constrained holes, written $\square_d{S}$, meaning the unknown sub-regex has depth at most $d$ and must contain at least one of the hinted components in $S$ as a leaf. The h-sketch guides top-down enumerative search over partial regexes, and for each partial regex the engine computes over- and under-approximations from the sketch's hints to reject infeasible branches without losing completeness. Repeat bounds are represented as symbolic integers, encoded into an SMT formula over string lengths, and used to prune families of regexes at once rather than enumerating every constant. The sketch itself is produced from English by a semantic parser with a learned ranking over candidate derivations.

What would settle it

A controlled experiment in which human participants, not an oracle, provide the next examples after each incorrect regex on the same 322 benchmarks would settle whether the 80% accuracy survives realistic feedback; if the accuracy collapses toward the example-only baseline, the multimodal advantage depends on perfect counterexample selection rather than on the sketch mechanism itself.

Watch

Extended reading notes

Core claim

The paper's central claim is that a natural-language-derived hierarchical sketch is the decisive ingredient for regex synthesis: it lets a programming-by-example engine prioritize which partial regexes to expand and which to prune, and it supports a symbolic representation of repeat bounds that the engine refines with an SMT solver. The headline empirical claim is that, with up to four rounds of counterexample feedback, Regel synthesizes the intended regex for 80% of 322 benchmarks, whereas the English-only baseline succeeds on 43% and the example-only baseline on 26%. The paper also claims that both pruning ideas contribute measurably to speed, and that in a 20-participant user study users solved 73.3% of tasks with Regel versus 28.3% without it.

Load-bearing premise

The evaluation assumes that whenever Regel returns a wrong regex, an oracle immediately supplies two new examples guaranteed to rule out exactly that regex; real users cannot usually produce such perfectly targeted counterexamples without already knowing the answer.

Editorial extensions

If this is right

If the central claim holds, a multimodal specification is substantially more effective for regex synthesis than either English alone or examples alone, with accuracy roughly doubling over the language-only baseline.
The sketch-guided pruning and symbolic-integer reasoning make the search fast enough for interactive use, so a user can receive candidate regexes within seconds and refine them with new examples.
The synthesis method is agnostic to the particular NLP technique: any component that emits hierarchical sketches could replace the semantic parser without changing the PBE engine.
On the harder StackOverflow benchmark subset, Regel reaches 60.7% accuracy where the language-only baseline reaches 2.4%, suggesting the multimodal advantage grows with task difficulty.
The user-study result, if it transfers, implies that tool assistance roughly doubles the chance that a non-expert finishes a regex task correctly within a time budget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's headline accuracy depends on an oracle that, after every wrong regex, supplies two new examples guaranteed to rule out exactly that regex; real users cannot reliably produce such perfectly targeted counterexamples without already knowing the target pattern, so interactive accuracy in practice may be lower.
The same h-sketch-plus-PBE recipe could transfer to other synthesis domains where English gives structural hints but examples pin down details, such as data transformation or query synthesis.
A testable extension would replace the oracle with human-generated counterexamples on the same 322 benchmarks and measure how quickly the accuracy curve approaches 80%; the paper's user study measures task success, not this curve.
The failure analysis suggests the main ceiling is not search but sketch quality: failures cluster on high-level concepts like dates and ranges that the grammar does not know, so enriching the grammar with domain concepts is a plausible next step.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know about this paper. First, the core idea is real: parsing English into a hierarchical sketch and using that sketch to guide a regex PBE engine is a genuine step beyond NL-only or example-only synthesis, and the paper makes a convincing case that the two modalities complement each other. Second, the headline 80% is conditional in a way the abstract does not fully own: it is measured after up to four rounds of oracle-provided counterexamples that are guaranteed to rule out the previously returned regex. That is a much stronger assumption about user behavior than anything the user study tests.

What is actually good: the h-sketch representation is a nice bridge between semantic parsing and enumerative synthesis; the sketch-guided over- and under-approximation prunes more precisely than AlphaRegex's version; and the SMT-based handling of symbolic integers in Repeat constructs is clever. The ablation shows both techniques pull their weight, and the order-of-magnitude speedup over an adapted AlphaRegex is believable. The hand-written proofs in Appendix A cover the main correctness claims. On the empirical side, the evaluation spans two different datasets and a user study, and the user study does show a large effect (73% vs 28% success), even if the participant pool is small and skewed toward CS students.

The soft spots are real but not disqualifying. The 80% figure is the obvious one: on DeepRegex, Regel already solves 151/200 from the initial examples, and reaches 185/200 only after oracle iterations; the StackOverflow iteration-0 number is not reported at all, so the combined 80% is entirely a post-oracle number. The paper itself comes close to admitting this in Section 9.1, and the user study does not measure whether real users can produce counterexamples that discriminate the returned regex from the intended one. Also, the data is filtered (empty-language regexes removed from DeepRegex) and partly manually annotated (StackOverflow), and no artifact is released, which makes independent verification harder. The training sketches for DeepRegex are derived from the target regex's root operator, but on a separate training split, so this is a concern about tailoring, not circularity.

None of this sinks the qualitative conclusion that a hierarchical sketch helps a lot. It does mean the quantitative headline should be reported with iteration counts and, ideally, with a user study that isolates counterexample quality. I would send this to referees: the synthesis engine is a real contribution and the weaknesses are addressable. If I were reviewing, I would ask for iteration-by-iteration accuracy on both datasets, a clear statement about the oracle assumption, and a serious try at releasing code and data.

Referee Report

3 major / 7 minor

Summary. The paper presents Regel, a tool that synthesizes regular expressions from a combination of natural-language descriptions and positive/negative examples. The natural-language input is parsed into a hierarchical sketch (h-sketch) by a SEMPRE-based semantic parser, and a programming-by-example engine then searches for a concrete regex that completes the sketch and satisfies the examples. The search is made practical by sketch-guided over- and under-approximations for pruning, and by representing repetition counts as symbolic integers whose feasible ranges are constrained via an SMT encoding over string lengths. The paper evaluates Regel on 200 adapted DeepRegex benchmarks and 122 StackOverflow benchmarks, reporting that Regel solves 80% of the combined 322 benchmarks, versus 43% for DeepRegex and 26% for a PBE-only baseline. It also reports an ablation showing the PBE engine is substantially faster than an adapted AlphaRegex, and a 20-participant user study in which participants complete tasks more often with Regel than without it.

Significance. If the reported results hold, this is a useful contribution to program synthesis from weak specifications: the hierarchical-sketch idea is natural, the combination of semantic parsing with PBE is well motivated, and the appendices provide detailed correctness proofs for the approximation and SMT-encoding procedures. The evaluation is unusually careful in several respects: the authors disclose how the DeepRegex data set was filtered and adapted, they provide ablations isolating the two pruning mechanisms, and they include a user study with explicit disclaimers about its scope. The qualitative conclusion that adding a natural-language sketch to a PBE engine improves both success rate and speed is credible and well supported by the iteration-0 results on the DeepRegex set. However, the headline 80% accuracy number is not a user-attainable accuracy as stated, because it depends on an oracle that supplies perfectly targeted counterexamples over up to four interaction rounds; this is the central load-bearing issue for the paper's main quantitative claim.

major comments (3)

[Section 9.1, Result 1, and Abstract] The headline accuracy of 80% is achieved only after up to four rounds in which the evaluator provides 'two additional examples that are guaranteed to rule out the returned incorrect regex' (Section 9.1). Producing such examples requires knowing the intended regex, so this is an oracle simulation rather than a realistic user-facing accuracy. On the DeepRegex set, Regel already solves 151/200 at iteration 0 and reaches 185/200 only after oracle iterations; the combined iteration-0 accuracy over all 322 benchmarks is not reported in the text. The user study (Section 9.3 and Appendix F) does not close this gap: participants are allowed to enter any two new examples, and the study records only final task success, not whether participants could produce counterexamples that are guaranteed to discriminate the synthesized regex from the intended one. The abstract and Result 1 should report the iteration-0 accuracy as the primary user-facing number, or the paper should provide direct evidence about users' ability to supply discriminating counterexamples.
[Section 8 and Appendix C] The DeepRegex comparison is performed on a substantially adapted and filtered subset of the original DeepRegex data: benchmarks corresponding to the empty language were removed, examples inconsistent with the target regex were discarded, and only 200 of 800 annotated tasks were retained after filtering. This is a defensible way to construct a multi-modal benchmark, but it changes the difficulty and the input format relative to the original DeepRegex data set. The statement that 'DeepRegex solves only 43%' should be explicitly qualified as applying to this reconstructed, filtered set; otherwise a reader may reasonably interpret the number as a statement about DeepRegex on the original data set, where the task and inputs are different.
[Appendix E and Section 6.3] The semantic-parser training labels are derived from the target regexes. For the DeepRegex set, the h-sketches used for training are generated by replacing the root operator of the target regex with a hole; for the StackOverflow set, the h-sketches are manually constructed by the authors, who knew the target regex while reading each English description. This is not circular in the narrow sense that test-time sketches are produced by the parser, but it means the natural-language component is trained and evaluated on sketches that encode ground-truth structural information. The paper should discuss the sensitivity of the reported accuracy to the quality of the parser supervision; at minimum, an experiment with coarser or automatically derived sketches for the StackOverflow set would help establish that the multi-modal advantage is not an artifact of manually crafted sketches.

minor comments (7)

[Abstract and Conclusion] The abstract and conclusion should state that the 80% figure is obtained after up to four interaction rounds under the oracle-counterexample protocol; the current wording presents it as a single-shot accuracy.
[Figure 14] The combined iteration-0 counts for Regel and the baselines should be reported in the text; currently only the StackOverflow final value (74/122) is stated, and the initial values are only visible graphically.
[Section 9.2, Result 2] The '10x faster' claim is based on 'the first 1000 sketches that can be solved by all variants'; this is a selective workload, and reporting total solved versus time or area under the curve would make the comparison more robust.
[Related Work and Section 9.1] The paper cites SemRegex [50] as a recent NL-only regex synthesizer but does not compare against it, despite calling DeepRegex 'state-of-the-art'; the characterization should be qualified.
[Appendix A, Theorem A.3] The proof of Theorem A.3 refers to 'Theorem A' where it presumably means the correctness theorem for Encode (Theorem A.4); the cross-reference should be fixed.
[Section 5.2, footnote 5] Bounding every symbolic integer by MAX, the length of the longest example, is only complete when the repeated sub-regex cannot match the empty string; this assumption should be stated explicitly.
[Section 2 and Figure 5] The overview uses constrained holes written as □{S} without the depth parameter d that is introduced formally in Figure 5; aligning the notation early would reduce confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims are evaluated against external benchmarks with supervised training separated from test, and the SMT and approximation constraints are derived from examples and sketch semantics rather than from target regexes.

full rationale

Walking the derivation chain: the h-sketch language (Fig. 5) is defined by a grammar over DSL constructs and holes, with semantics in Fig. 6; a sketch denotes a family of regexes, and the target regex is not an input to that definition. The PBE engine (Fig. 7) enumerates completions and prunes using over/under-approximations (Fig. 9-10) and SMT constraints on string lengths derived from positive examples (Fig. 12). The correctness theorems (5.4, 5.7, A.2-A.4) state soundness and completeness with respect to the examples and sketch semantics; none of these equations assumes the intended regex. The NLP-to-sketch component is trained on labeled data: for the DeepRegex split the labels are generated by replacing the root operator of ground-truth regexes, but training uses 6,500 separate sentences and the 200 evaluation benchmarks are disjoint; for StackOverflow the labels are manually written from descriptions and evaluated with 5-fold cross-validation, so the parser's output on test sketches is not a re-statement of the test target. The interactive evaluation assumes an oracle that can supply two examples 'guaranteed to rule out the returned incorrect regex' (Section 9.1); this is a strong assumption about user behavior and the paper itself disclaims that the user study is not an in-the-wild study (Section 9.3), but it is an evaluation limitation, not a definitional or fitted-input circularity. The only self-citation, [10], is the arXiv version of the same paper and carries no load. I therefore find no step in which a prediction reduces by construction to its inputs.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the soundness of the underlying SMT and automaton libraries, on the assumption that the h-sketch semantics capture the target space, and on the assumption that the DSL is rich enough for the chosen benchmarks. The parser's accuracy depends on a fitted weight vector and on manually constructed training sketches for the StackOverflow set, which are the main empirical load-bearing elements. No new physical or mathematical entities are postulated.

free parameters (3)

Semantic parser feature weights theta = Learned from training data, values not reported
Ranking of h-sketches and hence end-to-end accuracy depends on this fitted vector (Section 6.3).
Time budget t and result-list size k = t=10s and k=1 for DeepRegex; t=60s and k=5 for StackOverflow
The reported success rate is defined as the intended regex appearing in the top k results within time budget t (Section 8); these choices directly affect the numbers.
MAX bound for symbolic integers = Length of the longest example in the current benchmark
Encode bounds each symbolic integer by MAX, which limits the search space and can in principle exclude regexes with repeat counts larger than any example length (Section 5.2, footnote 5).

assumptions (4)

domain assumption The Z3 SMT solver is sound for the nonlinear integer constraints generated by Encode.
The algorithm relies on Z3 models to prune symbolic integers (Section 5.2); unsound or incomplete behavior would remove valid regexes from the search.
domain assumption The Brics automaton library correctly implements membership and equivalence checks for the DSL, including And and Not at the automaton level.
Used for IsCorrect and feasibility checks (Section 7); a bug in the library would invalidate the correctness of the synthesizer.
domain assumption The h-sketch semantics in Figure 6 correctly characterize the space of target regexes for the chosen benchmarks.
Completeness claims in Theorems 5.4 and 5.7 depend on this formalization; if the semantics are wrong, the stated guarantees do not hold.
domain assumption The DSL (Figure 4) is expressive enough to represent the benchmark target regexes.
Appendix D notes that constructs such as lookahead are not expressible in the DSL and that ground truths were written in the DSL; real-world tasks requiring such constructs are outside the method's scope.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Multi-modal Synthesis of Regular Expressions." pith.science (2026). https://pith.science/paper/I4SVOUHD

@misc{pith2026190803316,
  author       = {Pith},
  title        = {Pith review of: Multi-modal Synthesis of Regular Expressions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I4SVOUHD}},
  note         = {Machine review of arXiv:1908.03316}
}

read the original abstract

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 PBE-only baselines achieve 43% and 26% respectively. We also compare our proposed PBE engine against an adaptation of AlphaRegex, a state-of-the-art regex synthesis tool, and show that our proposed PBE engine is an order of magnitude faster, even if we adapt the search algorithm of AlphaRegex to leverage the sketch. Finally, we conduct a user study involving 20 participants and show that users are twice as likely to successfully come up with the desired regex using Regel compared to without it.

Figures

Figures reproduced from arXiv: 1908.03316 by the authors.

**Figure 5.** Syntax of hierarchical sketch language where r is a concrete regex and κi is a symbolic integer. r = {r } f(S) = f(r) | ∀i∈|S| ri ∈ ⟦Si ⟧ [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗

**Figure 6.** Semantics of h-sketches. g ∈ Gn (resp. f ∈ Fn) is an n-ary operator in (resp. outside of) the Repeat family. 4 Hierarchical Sketches In this section, we present the syntax and semantics of hierarchical sketches (h-sketches) that we derive from the natural language. Intuitively, an h-sketch represents a family of regexes that conform to a high-level structure. As shown in [PITH_FULL_IMAGE:figures/full_fig_p004_6.png] view at source ↗

Figures from the paper (9 more)

**Figure 8.** Figure 8: Inference rules for Expand. In rule (2), C denotes all character classes in the DSL, Gi (resp. Fi ) denotes Repeat (resp. non-Repeat) constructs with arity i. Root(P) = v : S ⊢ S ↠ ⟨o,u⟩ ⊢ P { ⟨o,u⟩ (1) Root(P) = v : (f ∈ Fn \ {Not}) (v,vi) ∈ Edges(P) ⊢ Subtree(P,vi) {…

**Figure 9.** Figure 9: Inference rules for Approximate. Gn (resp. Fn) denotes arity n operators in (resp. not in) the Repeat family. Here, we use the notation r ∈ ⟦P⟧ to denote that r is a valid completion of P. Thus, o matches every string s that some completion of P can match and u only ma…

**Figure 10.** Figure 10: Inference rules for over- and underapproximating h-sketches. r denotes a concrete regex. . 1: procedure InferConstants(P0, E +, E −) input: a symbolic regex P0, examples E +, E −. output: a set of concrete regular expressions Π. 2: (ϕ0, x0) := Encode(P0); ψ0 := Ó s ∈…

**Figure 11.** Figure 11: shows the InferConstants procedure for obtaining a set of concrete regexes from a given symbolic regex ⊢ S ↠ ⟨o,u⟩ ⊢ □1{S} ↠ ⟨o,u⟩ (1) d > 1 ⊢ □d {S} ↠ ⟨⊤, ⊥⟩ (2) ⊢ S1 ↠ ⟨o,u⟩ ⊢ □1{S2, ··,S|S | } ↠ ⟨o ′ ,u ′ ⟩ ⊢ □1{S} ↠ ⟨Or(o, o ′ ), And(u,u ′ )⟩ (3) f ∈ Fn \ {Not} ⊢…

**Figure 12.** Figure 12: , our encoding makes use of a function Φ, shown also in [PITH_FULL_IMAGE:figures/full_fig_p007_12.png]

**Figure 13.** Figure 13: Examples of rules and the parse tree for one possible derivation generated from the given description. alternative h-sketch from the same text: Concat □{<num>}, □{<,>, Repeat(<num>,3)} (6) 6.3 Learning feature weights Since there are many different h-sketches for an …

**Figure 14.** Figure 14: Number of solved benchmarks over iterations. 0 1 2 3 4 0 1 2 3 4 # of Iterations Avg Time (s) Regel Regel-Pbe (A) DeepRegex data set 0 1 2 3 4 4 6 8 10 12 14 16 18 20 # of Iterations Avg Time (s) Regel Regel-Pbe (B) StackOverflow data set [PITH_FULL_IMAGE:figures/ful…

**Figure 15.** Figure 15: Average running time per solved benchmark over iterations. Time for DeepRegex’s seq2seq model is negligible. 9.1 Benefits of multi-modal synthesis To evaluate the benefits of leveraging two different specification modalities, we compare Regel against two baselines. O…

**Figure 16.** Figure 16: Number of solved sketches within a given time budget. For each StackOverflow benchmark, we take the top 25 sketches generated by the parser (or fewer than 25 if the parser does not generate 25). • Regel-Approx: This variant uses the pruning techniques described in Sec…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 50 canonical work pages

[1]

Class: Regexp (Ruby 2.4.0)

2016. Class: Regexp (Ruby 2.4.0). https://ruby-doc.org/core-2.4.0/Regexp.html

work page 2016
[2]

Pattern (Java Platform SE 8 )

2019. Pattern (Java Platform SE 8 ). https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html

work page 2019
[3]

Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recur- sive program synthesis. In International conference on computer aided verification. Springer, 934–950

work page 2013
[4]

Alquezar and A

R. Alquezar and A. Sanfeliu. 1994. Incremental Grammatical Inference From Positive And Negative Data Using Unbiased Finite State Au- tomata. In In Proceedings of the ACLâĂŹ02 Workshop on Unsupervised PL’18, January 01–03, 2018, New York, NY, USA Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig Lexical Acquisition. 291–300

work page 1994
[5]

Dana Angluin. 1978. On the complexity of minimum inference of regular sets. Information and Control 39, 3 (1978), 337 – 350

work page 1978
[6]

Dana Angluin. 1987. Learning Regular Sets from Queries and Coun- terexamples. Inf. Comput. 75, 2 (1987), 87–106

work page 1987
[7]

Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic Parsing on Freebase from Question-Answer Pairs. InProceed- ings of the 2013 Conference on Empirical Methods in Natural Language Processing. 1533–1544

work page 2013
[8]

James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. 2016. Optimizing synthesis with metasketches. In ACM SIGPLAN Notices, Vol. 51. ACM, 775–788

work page 2016

Show all 55 references

[9]

Bob Carpenter. 1998. Type-logical Semantics. MIT Press, Cambridge, MA, USA

1998
[10]

Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. 2019. Multi-modal Synthesis of Regular Expressions. arXiv:cs.PL/1908.03316

2019 arXiv
[11]

Yanju Chen, Ruben Martins, and Yu Feng. 2019. Maximal Multi-layer Specification Synthesis. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2019). ACM, New York, NY,...

2019
[12]

Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th Inter- national Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08/ETAPS’08). Springer-Verlag, 337–340

2008
[13]

Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. 2018. Pro- gram Synthesis Using Conflict-driven Learning. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). ACM, 420–435

2018
[14]

Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. 2017. Component-based Synthesis of Table Consolida- tion and Transformation Tasks from Examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PL...

2017
[15]

Feser, Swarat Chaudhuri, and Isil Dillig

John K. Feser, Swarat Chaudhuri, and Isil Dillig. 2015. Synthesiz- ing Data Structure Transformations from Input-output Examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15) . ACM, 229–239

2015
[16]

Laura Firoiu, Tim Oates, and Paul R. Cohen. 1998. Learning Regular Languages from Positive Evidence. In Proceedings of the Twentieth Annual Conference of the Cognitive Science Society . 350–355

1998
[17]

E Mark Gold. 1978. Complexity of automaton identification from given data. Information and Control 37, 3 (1978), 302 – 320

1978
[18]

Sumit Gulwani. 2011. Automating String Processing in Spreadsheets Using Input-output Examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). ACM, 317–330

2011
[19]

Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkate- san. 2011. Synthesis of Loop-free Programs. SIGPLAN Not. 46, 6 (June 2011), 62–73

2011
[20]

Sumit Gulwani and Mark Marron. 2014. NLyze: Interactive Program- ming by Natural Language for Spreadsheet Data Analysis and Manipu- lation. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD ’14) . ACM, 803–814

2014
[21]

Tihomir Gvero and Viktor Kuncak. 2015. Synthesizing Java Expres- sions from Free-form Queries. InProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2015) . ACM, 416–432

2015
[22]

Tihomir Gvero, Viktor Kuncak, Ivan Kuraj, and Ruzica Piskac. 2013. Complete Completion Using Types and Weights. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13). ACM, New York, NY, USA, 27–38. https: //doi.org/10.11...

2013
[23]

Po-Sen Huang, Chenglong Wang, Rishabh Singh, Wen-tau Yih, and Xiaodong He. 2018. Natural Language to Structured Query Generation via Meta-Learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Langu...

2018
[24]

Seshia, and Ashish Tiwari

Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-guided Component-based Program Synthesis. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 1 (ICSE ’10). ACM, New York, NY, USA, 215–224

2010
[25]

Nate Kushman and Regina Barzilay. 2013. Using Semantic Unification to Generate Regular Expressions from Natural Language. In Proceed- ings of the 2013 Conference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Language Technologies . Ass...

2013
[26]

Vu Le and Sumit Gulwani. 2014. FlashExtract: A Framework for Data Extraction by Examples. In Proceedings of the 35th ACM SIGPLAN Con- ference on Programming Language Design and Implementation (PLDI ’14). ACM, 542–553. https://doi.org/10.1145/2594291.2594333

2014
[27]

Mina Lee, Sunbeom So, and Hakjoo Oh. 2016. Synthesizing Regular Expressions from Examples for Introductory Automata Assignments. In Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2016) . ACM, 70–80

2016
[28]

A Solar Lezama. 2008. Program synthesis by sketching . Ph.D. Disserta- tion

2008
[29]

Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D. Ernst. 2018. NL2Bash: A Corpus and Semantic Parser for Natural Language Interface to the Linux Operating System. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC...

2018
[30]

Nicholas Locascio, Karthik Narasimhan, Eduardo De Leon, Nate Kush- man, and Regina Barzilay. 2016. Neural Generation of Regular Expres- sions from Natural Language with Minimal Domain Knowledge. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Pro...

2016
[31]

Bill Maccartney. 2009. Natural Language Inference. Ph.D. Dissertation. Stanford, CA, USA. Advisor(s) Manning, Christopher D. AAI3364139

2009
[32]

Mehdi Manshadi, Daniel Gildea, and James Allen. 2013. Integrat- ing programming by example and natural language programming. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press, 661–667

2013
[33]

Anders Møller. 2017. dk.brics.automaton – Finite-State Automata and Regular Expressions for Java. http://www.brics.dk/automaton/

2017
[34]

Le, Martín Abadi, Andrew McCallum, and Dario Amodei

Arvind Neelakantan, Quoc V. Le, Martín Abadi, Andrew McCallum, and Dario Amodei. 2016. Learning a Natural Language Interface with Neural Programmer. CoRR abs/1611.08945 (2016). arXiv:1611.08945 http://arxiv.org/abs/1611.08945

2016 arXiv
[35]

Nye, Luke B

Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. 2019. Learning to Infer Program Sketches. CoRR abs/1902.06349 (2019). arXiv:1902.06349 http://arxiv.org/abs/1902. 06349

2019 arXiv
[36]

Peter-Michael Osera and Steve Zdancewic. 2015. Type-and-example- directed program synthesis. In ACM SIGPLAN Notices, Vol. 50. ACM, 619–630

2015
[37]

Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D’Antoni. 2019. Auto- matic Repair of Regular Expressions.Proc. ACM Program. Lang. 3, OOP- SLA, Article 139 (Oct. 2019), 29 pages. https://doi.org/10.1145/3360565

2019 doi
[38]

Rajesh Parekh and Vasant Honavar. 1996. An incremental interactive algorithm for regular grammar inference. In Grammatical Interference: Learning Syntax from Sentences, Laurent Miclet and Colin de la Higuera (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 238–249

1996
[39]

Rajesh Parekh and Vasant Honavar. 2001. Learning DFA from Simple Examples. Machine Learning 44, 1 (01 Jul 2001), 9–35. https://doi.org/ 10.1023/A:1010822518073

2001 doi
[40]

Chris Quirk, Raymond Mooney, and Michel Galley. 2015. Language to Code: Learning Semantic Parsers for If-This-Then-That Recipes. In Proceedings of the 53rd Annual Meeting of the Association for Com- putational Linguistics and the 7th International Joint Conference on Natural L...

2015
[41]

Mohammad Raza, Sumit Gulwani, and Natasa Milic-Frayling. 2015. Compositional Program Synthesis from Natural Language and Exam- ples. In IJCAI

2015
[42]

R. L. Rivest and R. E. Schapire. 1989. Inference of Finite Automata Using Homing Sequences. In Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing (STOC ’89) . ACM, 411–420. Short Title PL’18, January 01–03, 2018, New York, NY, USA

1989
[43]

Ashish Tiwari, Adrià Gascón, and Bruno Dutertre. 2015. Program Synthesis Using Dual Interpretation. In Automated Deduction - CADE- 25, Amy P. Felty and Aart Middeldorp (Eds.). Springer International Publishing, 482–497

2015
[44]

Xinyu Wang, Sumit Gulwani, and Rishabh Singh. 2016. FIDEX: Filter- ing Spreadsheet Data Using Examples. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016) . ACM, 195–213

2016
[45]

Yushi Wang, Jonathan Berant, and Percy Liang. 2015. Building a se- mantic parser overnight. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th Interna- tional Joint Conference on Natural Language Processing (Volume 1: Long Pa...

2015
[46]

Navid Yaghmazadeh, Christian Klinger, Isil Dillig, and Swarat Chaud- huri. 2016. Synthesizing transformations on hierarchically structured data. In ACM SIGPLAN Notices, Vol. 51. ACM, 508–521

2016
[47]

Navid Yaghmazadeh, Yuepeng Wang, Isil Dillig, and Thomas Dillig
[48]

Zelle and Raymond J

John M. Zelle and Raymond J. Mooney. 1996. Learning to Parse Data- base Queries Using Inductive Logic Programming. In Proceedings of the Thirteenth National Conference on Artificial Intelligence - Volume 2 (AAAI’96). AAAI Press, 1050–1055

1996
[49]

Zettlemoyer and Michael Collins

Luke S. Zettlemoyer and Michael Collins. 2005. Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars. In Proceedings of the Conference on Uncertainty in Artificial Intelligence

2005
[50]

Zexuan Zhong, Jiaqi Guo, Wei Yang, Jian Peng, Tao Xie, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2018. SemRegex: A Semantics- Based Approach for Generating Regular Expressions from Natural Language Specifications. In Proceedings of the 2018 Conference on Em- pirical Methods...

2018
[52]

For any string s, suppose there exists a regexr∈ ⟦S⟧ such that r = StartsWith(r1) such that we haveMatch(r , s)

We first prove that o satisfies (i). For any string s, suppose there exists a regexr∈ ⟦S⟧ such that r = StartsWith(r1) such that we haveMatch(r , s). From the semantic of h-sketch from Figure 6, we know that r1 ∈ ⟦S1⟧. By induction, we know that (i) holds forS1. Thus, we have ...
[53]

For any string s, suppose Match(u, s) is true, then there exist a string s1 such that Match(u1, s1) and u = StartsWith(u1)

We now prove thatu satisfies (ii). For any string s, suppose Match(u, s) is true, then there exist a string s1 such that Match(u1, s1) and u = StartsWith(u1). From the inductive hypothesis, we know that Match(u1, s1) holds for any r1 ∈ ⟦S1⟧. Now consider any regex r∈ ⟦P⟧, beca...
[54]

Given a string s, sup- pose there exists a concrete regex r∈ ⟦S⟧ such that Match(r , s) is true

We first prove o satisfies (i). Given a string s, sup- pose there exists a concrete regex r∈ ⟦S⟧ such that Match(r , s) is true. From the semantic of Not, we know that ¬Match(r1, s), where r1 ∈ ⟦S1⟧. From the induction hypothesis, we know that ¬Match(u1, s), whereu1 is the und...
[55]

regex”, “regular expression

We then prove u satisfies (ii). For any string s, suppose Match(u, s) is true. Since we have u = Not(o1), whereo1 is the over-approximation forS1, Match(o1, s) is false (from the semantics of Not). From the inductive hypothesis, we know that for any r1∈ ⟦S1⟧,¬Match(r1, s). The...

2018
[2017]

SQLizer: Query Synthesis from Natural Language. Proc. ACM Program. Lang. 1, OOPSLA, Article 63 (Oct. 2017), 26 pages

2017

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Class: Regexp (Ruby 2.4.0)

2016. Class: Regexp (Ruby 2.4.0). https://ruby-doc.org/core-2.4.0/Regexp.html

work page 2016

[2] [2]

Pattern (Java Platform SE 8 )

2019. Pattern (Java Platform SE 8 ). https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html

work page 2019

[3] [3]

Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recur- sive program synthesis. In International conference on computer aided verification. Springer, 934–950

work page 2013

[4] [4]

Alquezar and A

R. Alquezar and A. Sanfeliu. 1994. Incremental Grammatical Inference From Positive And Negative Data Using Unbiased Finite State Au- tomata. In In Proceedings of the ACLâĂŹ02 Workshop on Unsupervised PL’18, January 01–03, 2018, New York, NY, USA Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig Lexical Acquisition. 291–300

work page 1994

[5] [5]

Dana Angluin. 1978. On the complexity of minimum inference of regular sets. Information and Control 39, 3 (1978), 337 – 350

work page 1978

[6] [6]

Dana Angluin. 1987. Learning Regular Sets from Queries and Coun- terexamples. Inf. Comput. 75, 2 (1987), 87–106

work page 1987

[7] [7]

Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic Parsing on Freebase from Question-Answer Pairs. InProceed- ings of the 2013 Conference on Empirical Methods in Natural Language Processing. 1533–1544

work page 2013

[8] [8]

James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. 2016. Optimizing synthesis with metasketches. In ACM SIGPLAN Notices, Vol. 51. ACM, 775–788

work page 2016