{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T06:28:10Z","timestamp":1772692090255,"version":"3.50.1"},"reference-count":42,"publisher":"MIT Press - Journals","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> 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. Real-world regexes are complex, hard to describe with brief sentences, and sometimes require examples to fully convey the user\u2019s 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. <jats:sup>1<\/jats:sup> <\/jats:p>","DOI":"10.1162\/tacl_a_00339","type":"journal-article","created":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T20:07:06Z","timestamp":1605211626000},"page":"679-694","source":"Crossref","is-referenced-by-count":16,"title":["Sketch-Driven Regular Expression Generation from Natural Language and Examples"],"prefix":"10.1162","volume":"8","author":[{"given":"Xi","family":"Ye","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at Austin."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiaochu","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Austin."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyu","family":"Wang","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department, University of Michigan, Ann Arbor."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isil","family":"Dillig","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Austin."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Greg","family":"Durrett","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Austin."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"bib1","volume-title":"2013 Formal Methods in Computer-Aided Design (FMCAD)","author":"Alur R.","year":"2013"},{"key":"bib2","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Artzi Yoav","year":"2015"},{"key":"bib3","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR)","author":"Balog M.","year":"2017"},{"key":"bib4","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Berant Jonathan","year":"2013"},{"key":"bib5","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Li Dong","year":"2016"},{"key":"bib6","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Li Dong","year":"2018"},{"key":"bib7","volume-title":"Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)","author":"Feng Yu","year":"2018"},{"key":"bib8","volume-title":"Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)","author":"Gulwani Sumit","year":"2011"},{"key":"bib9","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Guu Kelvin","year":"2017"},{"key":"bib10","volume-title":"Proceedings of the 2015 ACM SIGPLAN International Conference on Object- Oriented Programming, Systems, Languages, and Applications (OOPSLA)","author":"Gvero Tihomir","year":"2015"},{"key":"bib11","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Iyer Srinivasan","year":"2019"},{"key":"bib12","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Iyer Srinivasan","year":"2017"},{"key":"bib13","volume-title":"International Conference on Learning Representations (ICLR)","author":"Kalyan Ashwin","year":"2018"},{"key":"bib14","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR)","author":"Kingma Diederik P.","year":"2015"},{"key":"bib15","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NeurIPS)","author":"Kulal Sumith","year":"2019"},{"key":"bib16","volume-title":"Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)","author":"Kushman Nate","year":"2013"},{"key":"bib17","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Kwiatkowski Tom","year":"2013"},{"key":"bib18","volume-title":"Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE)","author":"Lee Mina","year":"2016"},{"key":"bib19","volume-title":"Proceedings of the International Conference on Language Resources and Evaluation LREC","author":"Xi Victoria Lin","year":"2018"},{"key":"bib20","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Ling Wang","year":"2016"},{"key":"bib21","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Locascio Nicholas","year":"2016"},{"key":"bib22","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Luong Thang","year":"2015"},{"key":"bib23","unstructured":"Anders M\u00f8ller. 2017. dk.brics.automaton\u2014finite-state automata and regular expressions for Java. http:\/\/www.brics.dk\/automaton\/"},{"key":"bib24","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Nye Maxwell","year":"2019"},{"key":"bib25","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR)","author":"Odena Augustus","year":"2020"},{"key":"bib26","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing and the International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)","author":"Park Jun-U","year":"2019"},{"key":"bib27","volume-title":"Advances in Neural Information Processing Systems (NeurIPS)","author":"Paszke Adam","year":"2019"},{"key":"bib28","volume-title":"Workshop at the International Conference on Learning Representations (ICLR Workshop)","author":"Polosukhin Illia","year":"2018"},{"key":"bib29","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing (EMNLP-IJCAI)","author":"Quirk Chris","year":"2015"},{"key":"bib30","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Rabinovich Maxim","year":"2017"},{"key":"bib31","volume-title":"Finite State Methods in Natural Language Processing","author":"Ranta Aarne","year":"1998"},{"key":"bib32","volume-title":"Advances in Neural Information Processing Systems (NeurIPS)","author":"Shin Richard","year":"2019"},{"key":"bib33","unstructured":"Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph.D. thesis, University of California at Berkeley."},{"key":"bib34","volume-title":"Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)","author":"Suhr Alane","year":"2018"},{"key":"bib35","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing and the International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)","author":"Wang Bailin","year":"2019"},{"key":"bib36","volume-title":"Proceedings of the 2016 ACM SIGPLAN International Conference on Object- Oriented Programming, Systems, Languages, and Applications (OOPSLA)","author":"Wang Xinyu","year":"2016"},{"key":"bib37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3133887","volume":"1","author":"Yaghmazadeh Navid","year":"2017","journal-title":"Proceedings of the ACM on Programming Languages"},{"key":"bib38","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Yin Pengcheng","year":"2017"},{"key":"bib39","volume-title":"Proceedings of the Joint Conference of the Annual Meeting of the Association for Computational Linguistics ACL","author":"Zettlemoyer Luke","year":"2009"},{"key":"bib40","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Zhong Ruiqi","year":"2020"},{"key":"bib41","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Zhong Zexuan","year":"2018"},{"key":"bib42","volume-title":"Workshops at the AAAI Conference on Artificial Intelligence (AAAI)","author":"Zhong Zexuan","year":"2018"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:39:46Z","timestamp":1615585186000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/96479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":42,"alternative-id":["10.1162\/tacl_a_00339"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00339","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}