SoftRegex: Generating Regex from Natural Language Descriptions using Softened Regex Equivalence

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 6425–6431, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 6425 SoftRegex: Generating Regex from Natural Language Descriptions using Softened Regex Equivalence Jun-U Park Yonsei University Seoul, Republic of Korea junupark@yonsei.ac.kr Sang-Ki Ko Kangwon National University Kangwon, Republic of Korea narame7@gmail.com Marco Cognetta∗ Yonsei University Seoul, Republic of Korea cognetta.marco@gmail.com Yo-Sub Han Yonsei University Seoul, Republic of Korea emmous@yonsei.ac.kr Abstract We continue the study of generating semanti- cally correct regular expressions from natural language descriptions (NL). The current state- of-the-art model, SemRegex, produces regular expressions from NLs by rewarding the rein- forced learning based on the semantic (rather than syntactic) equivalence between two reg- ular expressions. Since the regular expression equivalence problem is PSPACE-complete, we introduce the EQ Reg model for computing the similarity of two regular expressions us- ing deep neural networks. Our EQ Reg model essentially softens the equivalence of two reg- ular expressions when used as a reward func- tion. We then propose a new regex generation model, SoftRegex, using the EQ Reg model, and empirically demonstrate that SoftRegex substantially reduces the training time (by a factor of at least 3.6) and produces state-of- the-art results on three benchmark datasets. 1 Introduction Regular expressions are an efficient tool to rep- resent structured data with specific rules in a va- riety of fields such as natural language process- ing or text classification. However, it is not al- ways an easy task to write an exact regular ex- pression for those who do not have a deep knowl- edge of regular expressions or when the expres- sion is very complicated, and incorrect or sloppy regular expressions may cause unexpected con- sequences in practice (Bispo et al., 2006; Zhang et al., 2018). Indeed, even a single character differ- ence between regular expressions can cause them ∗Now at Google. to represent completely different sets of strings. As such, researchers have begun working on a system than generates a regular expression from a natural language description provided by a hu- man while reducing possible errors caused by in- correct regular expressions (Liu et al., 2019). Re- cently, Locascio et al. (2016) designed the Deep- Regex model based on the sequence-to-sequence (Seq2Seq) model (Sutskever et al., 2014) using minimal domain knowledge during the learning phase while still accurately predicting regular ex- pressions from NLs. Later, Zhong et al. (2018a) improved the performance by training on not only syntactic content of the expressions (i.e. the ex- act textual representation of the expression that was used), but also the semantic content (the regular language described by the expression). However, the reward function in the SemRegex model (Zhong et al., 2018a) that determines if the predicted regular expression is semantically equiv- alent to the ground truth expression is known to be PSPACE-complete and is a bottleneck in prac- tice (Stockmeyer and Meyer, 1973). Thus, if we can solve this problem (even …

Content truncated to 500 words