# InfeRE: Step-by-Step Regex Generation via Chain of Inference

Shuai Zhang, Xiaodong Gu, Yuting Chen, Beijun Shen  School of Electronic
Information and Electrical Engineering, Shanghai Jiao Tong University,
Shanghai, China
{zhangshuai2000, xiaodong.gu, chenyt<EMAIL_ADDRESS>
###### Abstract

Automatically generating regular expressions (abbrev. regexes) from natural
language description (NL2RE) has been an emerging research area. Prior studies
treat regex as a linear sequence of tokens and generate the final expressions
autoregressively in a single pass. They did not take into account the step-by-
step internal text-matching processes behind the final results. This
significantly hinders the efficacy and interpretability of regex generation by
neural language models. In this paper, we propose a new paradigm called
InfeRE, which decomposes the generation of regexes into chains of step-by-step
inference. To enhance the robustness, we introduce a self-consistency decoding
mechanism that ensembles multiple outputs sampled from different models. We
evaluate InfeRE on two publicly available datasets, NL-RX-Turk and KB13, and
compare the results with state-of-the-art approaches and the popular tree-
based generation approach TRANX. Experimental results show that InfeRE
substantially outperforms previous baselines, yielding 16.3% and 14.7%
improvement in DFA@5 accuracy on two datasets, respectively.

###### Index Terms:

Regex Generation, Chain of Inference, Self-Consistency Decoding

##  I Introduction

††footnotetext: * Beijun Shen is the corresponding author

Regular expressions (abbrev. regexes) have been highly effective tools for
text matching and manipulation, with extensive use in a broad range of fields.
They enjoy robust support across nearly all programming languages [1], and are
crucial to many practical applications such as performance testing tool
JMeter, command lines in Linux, and database operations that require powerful
and flexible text processing. Despite the wide utility of regexes, however,
regexes can be complex, opaque, and challenging to compose, even for
experienced programmers [2].

Automatically generating regexes from natural language descriptions (NL2RE)
has been an emerging research area [3, 4, 5, 6, 7, 8, 9, 10, 11]. Aside from
earlier work on semantic parsing [3], existing studies mainly treat NL2RE as a
sequence-to-sequence learning problem and utilize an autoregressive language
model. For example, Deep-Regex [4] employs an encoder-decoder model based on
LSTM with attention. SemRegex extends the LSTM encoder-decoder model with
reinforcement learning [5], which rewards the model for generating diverse
regexes. S2RE [11] augments SemRegex by a new rewarding strategy to encourage
the model to generate syntactically correct regexes.

One common downside of existing studies is that they generate the entire
regexes autoregressively. On the one side, autoregressive models generate
regex one token at a time. Hence, they may not capture the real order of text
processing behind the regexes. The generated tokens can violate the structure
of regexes. Moreover, it is difficult to interpret the underlying processes
and reasoning behind the generation.

Figure 1: A motivation example of regex generation.

Figure 1 shows an example of regex generation by conventional autoregressive
models and the real text matching order. The integer numbers under the regex
indicate the order for emitting each token. In conventional autoregressive
models, the decoder generates tokens one by one based on previously decoded
tokens. Right from the beginning, the decode must possess a comprehensive
understanding of the entire output in order to give the correct quantity of
left brackets before generating the genuinely semantically meaningful tokens.
In reality, the text-matching process does not follow a left-to-right order as
the conventional sequence-to-sequence model assumes. For example, the first
left bracket is emitted lastly when we consider the and operator. This example
shows that conventional autoregressive models often fail to generate regex in
the order of real text processing.

Recent research [12, 13] for large language models (LLMs) has shown that
_chain-of-thought prompting_ , which decomposes a complex problem into a
series of reasoning steps, can engage the reasoning capability of LLMs,
resulting in substantial improvement in model performance. Additionally,
multi-step generation allows for better interpretability of LLMs, since it
provides understandable and transparent insights into how language model
arrives at its predictions. However, directly applying chain-of-thought
prompting to the regex generation task is challenging, primarily due to the
wide range of domains encompassed by existing LLMs, as well as the
considerable expense associated with the manual formulation of prompts [14].

Inspired by the strengths of chain-of-though prompting, we propose InfeRE, a
novel formulation of regular expressions called _chain-of-inference_ , with
each chain representing a sub-regex that indicates a specific text-matching
procedure. Instead of generating plain regexes autoregressively, we formulate
regex generation as step-by-step inference of internal processes for text
matching.

InfeRE rationalizes the text-processing order through step-by-step generation.
Particularly, the original problem is decomposed into several simple
subproblems by explicitly intermediate steps and the order in which these
subproblems are addressed is consistent with the actual order of text
processing. As Figure 1(b) shows, for the plain regex
(([a-z])(.*))&((.*)([AEIOUaeiou])), the generation of a regex can be
decomposed into 5 steps, with the step description (middle) and the internal
results (right). Each step indicates a specific text-matching procedure, such
as step1=<low> and step2=startwith(<low>). Then, we train a language model to
generate inference chains from natural language. Additionally, to enhance the
robustness of model performance [15], we design a self-consistency decoding
mechanism, aiming to ensemble multiple outputs and select the most consistent
ones.

We evaluate InfeRE on two benchmark datasets, NL-RX-Turk and KB13, and compare
the results with state-of-the-art approaches and the popular tree-based
generation approach TRANX. Experimental results show that InfeRE substantially
outperforms previous baselines, yielding 16.3% and 14.7% improvement in DFA@5
accuracy on two datasets, respectively. Particularly, InfeRE outperforms the
popular tree-based generation approach by 18.1% and 11.3% on both datasets,
respectively, in terms of DFA@5 accuracy. Ablation studies on components,
backbone language models, and data sizes indicate that the proposed chain of
inference and self-consistency decoding are effective and robust in various
configurations. InfeRE also demonstrates strong ability in low-resource regex
generation.

In our paper, we mainly explore the application of InfeRE to regex generation,
but we believe that it is suggestive and may be broadly applied to other areas
such as SQL generation, as they all follow a certain structural order.

The contributions of this work are as follows:

  * •

We introduce _chain-of-inference_ , a novel representation format for regular
expressions. Each chain indicates a specific text-matching procedure.

  * •

We propose a novel paradigm of regex generation via chain of inference. In
comparison with existing autoregressive approaches, InfeRE builds sub-regexes
in a manner that is similar to the human thought process.

  * •

We evaluate InfeRE on two publicly available datasets and compare the results
with state-of-the-art regex generation approaches as well as tree-based code
generation methods. Experimental results show that InfeRE substantially
outperforms existing techniques on the datasets.

This paper is organized as follows: Section II presents the related work.
Section III presents the algorithm and the implementation of two main
mechanisms of InfeRE, chain of inference and self-consistency decoding.
Sections IV and V evaluate InfeRE against state-of-the-art approaches on two
benchmark datasets. Section VI concludes.

Figure 2: Overview of InfeRE.

##  II Related Work

###  II-A Automatic Regex Generation

Automatically generating regexes has gained much attention due to the
popularity and significance of regexes [16, 17, 2]. Early researches attempt
to generate regexes from examples [18, 19, 20, 21, 22, 23]. They enumerate all
possible regexes that are consistent with the provided examples and perform
exhaustive searches with constraints. For example, AlphaRegex [18] synthesizes
regexes by pruning out a large enumerative search space using over- and under-
approximations of regexes. However, AlphaRegex can only generate simple
regexes in specific forms. RegexGenerator++ [19] generates regexes based on
genetic programming, but the correctness of generated regex is not guaranteed.
FLASHREGEX [20] reduces the ambiguity of generated regexes by deterministic
regex constraints. There is also a large number of studies that infer regexes
from examples using XML schemas [21, 22, 23]. A strong restriction of example-
based approaches is that they rely heavily on high-quality examples. Hence,
the systems tend to overfit when the examples provided by users are incorrect
or limited.

Recently, there has been emerging research on NL2RE, i.e., regex generation
from natural language descriptions. Ranta [24] firstly developed a tool to
convert NL queries to regexes based on abstract syntax rules. Kushman and
Barzilay [3] parsed natural language queries into regex by utilizing semantic
unification. They also built the first benchmark and the DFA (deterministic
finite automatons) metric for evaluating regex generation. Locascio et al. [4]
proposed Deep-Regex, which is the first approach to employ deep learning for
regex generation and provided another dataset of 10,000 natural language
descriptions and regex pairs. Deep-Regex treats NL2RE as a machine translation
task and employs an LSTM-based sequence-to-sequence model. SemRegex [5] alters
the syntax-based training objective of Deep-Regex to a semantics-based
objective by using reinforcement learning, which maximizes the DFA semantic
correctness of generated regexes. SoftRegex introduces an additional reward
model to compute and soften the similarity of two regexes in SemRegex. Both
SemRegex and Deep-Regex can generate correct regexes that may not resemble the
ground truth benefiting from their reinforcement learning method. S2RE [11]
further improves the policy gradient to ensure the validity of generated
regexes by rewarding the model if it generates valid regexes.

To the best of our knowledge, InfeRE is the first attempt to employ pre-
trained language models (PLM) in the field of automatic regex generation.
Moreover, unlike current autoregressive models, InfeRE first leverages the
idea of chain of thought for regex generation, which considers the real order
of text processing and enhances the interpretability of large language models.

###  II-B Chain-of-Thought Prompting

Recent research has shown that chain-of-thought prompting, i.e., prompting by
step-by-step rationale, can significantly improve the performance of large
language models on reasoning tasks, such as arithmetic, commonsense, and
symbolic reasoning [13, 25, 26, 27]. These approaches leverage a large
language model to jointly generate the task output as well as the explanations
to mimic the process of human reasoning. More importantly, chain-of-thought
prompting requires no modifications to the architecture or training procedures
of a large PLM.

Related research reveals that the quality of chains of inference significantly
affects the final model performance [28], and theirs effects vary in different
downstream tasks [13]. Wiegreffe et al. [26] proposed an over-generation and
filtration pipeline for producing model-generated rationales by utilizing
GPT-3. They conducted a series of human studies and found that crowdworkers
often prefer model-generated explanations to crowdsourced explanations. The
follow-up study further indicates the sub-optimality of manually provided
rationales increases sensitivity of large language models, and the ensemble of
model-generated and human-written chains of inference can reduce this
sensitivity [27]. Therefore, appropriate chains of inference designed for
specific downstream task are crucial.

Comparatively, InfeRE adopts the idea of chain of thought and generates the
step-by-step process of human reasoning instead of the final regex. However,
InfeRE is not a prompting method. That means, the generated sub-regexes are
not taken as prompts to large language models. Instead, we leverage a large
language model to generate chains of thought directly.

##  III Approach

###  III-A Overview

For a given natural language query $x$ = $x_{1},...,x_{N}$, the goal of NL2RE
is to generate a regex $y$ = $y_{1},...,y_{T}$ that aligns with the text
transformation implied by the query. This problem can be realized using any
sequence-to-sequence model, such as the Transformer [29]. However,
autoregressively generating the plain regex violates the real order of
generation. Therefore, we design a novel _chain-of-inference_ paradigm for
regex generation: as opposed to directly generating $y$, we generate its chain
of inference $s$ = $s_{1}$, …,$s_{K}$, where each $s_{t}$ represents an
internal text-matching process involved in the final regex.

Figure 2 shows the framework of our approach. The pipeline involves three main
steps. First, we decompose plain regexes into chains of inference, namely,
step-by-step operations in the regexes. Second, we train a sequence-to-
sequence model to generate the chains of inference. These chains of inference
are assembled into plain regexes. Third, we design a self-consistency decoding
mechanism that ensembles multiple inference chains.

###  III-B Decomposing Regexes into Chains of Inference

Our goal becomes how to convert a query $x$ into a chain of inference $s$. A
straightforward idea is to create a parallel corpus of ($x$, $s$) pairs and
train a language model $p(s|x)$ on the corpus. However, our datasets are in
the form of ($x$, $y$) pairs. It is impractical to label the chains of
inference manually. Hence, we want to decompose the original regex $y$ into
chains of processes $s$ automatically. The decomposition must satisfy two
objectives: first, the decomposed chains must express the step-by-step text-
matching process clearly; second, the chains cannot be redundant. Otherwise,
the inferred chains may have extraordinary lengths, which degenerate the
performance in turn.

Our solution is simple: since regexes are tree-structured [10] and the top-
down hierarchy in the parsing trees explicitly delineates the step-by-step
construction process of a regex [4], we can decompose the original problem
into small sub-problems by leveraging this inherent tree hierarchy.

Input: $y$: original regex; $Op$: a dictionary of all operators and their
corresponding number of operands

1 $NodeStack=(),C=(),B_{operand}=(),i=1$;

2 Parse $y$ into a tree $T(y)$;

3 Post-order traverse $T(y)$ and add nodes to $NodeStack$ in turn;

4 Reverse $NodeStack$;

5

6while  _$NodeStack.size()\neq 1$_ do

7 $node=NodeStack.pop()$;

8 if  _$node$ is operator_ then

/* Build one step in a chain of inference */

9 $N_{node}=Op[node]$ //Lookup the operands number for a node

10 $s_{step}$=”step” + $i$ \+ ”=(”;

11 for  _$i=0$ to $N_{node}$_ do

12 $o_{i}=B_{operand}.pop()$;

13 $s_{step}$ = $s_{step}$ \+ $o_{i}$ \+ ”,”;

14

15 end for

16 $s_{step}$ = $s_{step}$ \+ ”)”;

17 $C.add(s_{step})$;

18 $B_{operand}.add($”step” + $i)$;

19 $i=i+1$;

20

21 else

22 $B_{operand}.add(node)$;

23

24 end if

25

26 end while

Output: $C$: chain of inference

Algorithm 1 Convert Plain Regexes to Chains of Inference

Figure 3: An illustration of creating chains of inference from plain regexes.

Algorithm 1 describes the decomposition process. First, we parse the original
plain regex $y$ into trees based on predefined rules defined in [10]. Nodes in
the trees represent operators while edges represent the relationships between
two sub-regexes. Table I lists all the rules for parsing plain regex into
parenthetical notation for trees [7, 10]. The rules involve all operators and
operands that appear in the benchmark datasets. Notably, the obtained
parenthetical notation for trees can be readily mapped back to plain regex
based on these established rules.

TABLE I: Rules for parsing plain regex into parenthetical notation for trees [7, 10]. Operator r := |
---|---
startwith ($r$) |  $r.*$
endwith($r$) |  $.*r$
contain($r$) |  $.*r.*$
not($r$) |  $\sim r$
optional($r$) |  $r?$
star($r$) |  $r*$
concat($r_{1}$, $r_{2}$) |  $r_{1}r_{2}$
and($r_{1}$, $r_{2}$) |  $r_{1}$ & $r_{2}$
or($r_{1}$, $r_{2}$) |  $r_{1}$ — $r_{2}$
rep($r$, $k$) |  $r\\{k\\}$
repeat_least($r$, $k$) |  $r\\{k,\\}$
rep_range($r$, $k_{1}$, $k_{2}$) |  $r\\{k_{1},k_{2}\\}$
Operand := |
<let$\textgreater$ |  [A-Za-z]
<cap$\textgreater$ |  [A-Z]
<low$\textgreater$ |  [a-z]
<num$\textgreater$ |  [0-9]
<any$\textgreater$ |  .
<spec$\textgreater$ |  [-,;+:!@#_$%&*=^]

Having obtained the parsing tree, we then traverse the tree in a post-order.
Whenever we encounter an operator node, we regard the sub-regex corresponding
to its sub-tree as a step in the chain of inference. For the $i$-th node, we
represent the sub-regex as step $i$ in the chain of inference. Then, we
replace the sub-tree of the current operator with a step-i node. The size of
the regex tree decreases continuously as the traversal proceeds. We repeat
this process until there is only a single $step$ node left in the tree, which
means the completion of the chain of inference.

Figure 3 illustrates an example. For a pair of (query, regex) in the training
set, training a sequence-to-sequence model to generate chain of inference is
difficult. Hence, we parse the regex $y$=(([A-Za-z]){3,})&(.*[0-9].*) into a
tree and traverse the tree in post-order. When we encounter the first
nonterminal node <letter> we create a sub-regex step1=[A-Za-z] in the chain of
inference to indicate the first inferred matching process. The sub-tree rooted
at <letter> is replaced with a special node step1 to indicate the internal
results after step 1. Next, we replace the sub-tree repeat_atleast(step1,3)
with a special node step2 when we encounter the node repeat_atleast. Next, we
replace the third occurred node <num> with a node step 3 and append
step3=[0-9] in the chain of inference. The traversal continues until meeting
the root node and, where we generate step5=and(step2,step4) in the chain of
inference and replace the sub-tree with step5.

The decomposition step above is reminiscent of tree-based models in code
generation such as TRANX [30]. Although both techniques generate code in a
tree-based fashion, our architecture and training method are significantly
different. TRANX decomposes the tree into three types of actions and
calculates their corresponding probabilities. This process deviates from the
pre-training task of current PLMs, which makes it challenging to engage with
large-scale language models. In contrast, InfeRE conforms to both the tree
generation laws and the pre-training task of language models. Notably, InfeRE
does not require any modifications to the underlying model structure or
training process, making it highly flexible and adaptable to various corpora
and models.

###  III-C Learning and Generation

Having parsed all regexes into chains of inference, we obtain a parallel
corpus of (query, chain) pairs. We regard the generation of chains as a
sequence-to-sequence learning task and leverage the Transformer model for the
generation, where the encoder represents the input query as vectors while the
decoder generates the target sequence (i.e., a chain of inferred regexes)
based on the encoded hidden vectors.

In order to leverage large domain knowledge on texts, we use T5 [31], a
popular PLM for sequence-to-sequence generation. T5 is first pre-trained on
large corpora of texts using self-supervision. The pre-training enables T5 to
gain rich generic knowledge, while the fine-tuning phase adapts the model to
domain-specific tasks such as regex generation. Specifically, we take the
open-source T5 model111https://github.com/google-research/text-to-text-
transfer-transformer#released-model-checkpoints as the backbone of InfeRE and
further fine-tune it on the (query, chain) pairs as a text generation task by
minimizing the cross-entropy loss.

During the inference phase, we generate the chains of inference
autoregressively by feeding the natural language query to the fine-tuned
model. Then, we revert the generated chains to regex trees. We initialize the
tree with the last step in the chain of inference, e.g.,
step5=and(step2,step4). For each $step$-$i$ node, we replace the $step$-$i$
node in the sequence with its original sub-regex in the chain of inference.
This process may introduce new $step$-$i$ node, so we repeat this process
until there is no $step$ node left and get corresponding parenthetical
notation for trees. Finally, we convert the parenthetical notation for trees
into plain regex using the rules in Table I. The whole procedures are
summarized in Algorithm 2.

Input: $C$: chain of inference;

1 $re=C.pop()$;

2 while  _‘ $step$-$i$’ in $re$_ do

3 get the corresponding sub-regex $subre_{i}$ of $step$-$i$ from $C$[$i$];

4 $re$ = $re$.replace($step$-$i$, $subre_{i}$) ;

5

6 end while

7Convert $re$ to plain regex based on rules defined in Table I;

Output: $re$: plain regex

Algorithm 2 Revert Chains of Inference to Plain Regexes

###  III-D Self-Consistency Decoding

Figure 4: Illustration of self-consistency decoding.

Since we formulate regex generation as a chain of inference for text matching,
it is natural to suppose that there are multiple chains that lead to the same
text matching. Moreover, if multiple chains reach the same matching, that
means the generated chains are more convincing [32]. In other words, multiple
wrong chains are unlikely to reach the same answer. Therefore, we can sample a
group of inference chains from the language model, revert them to plain
regexes, and select the most consistent ones (i.e., chains of inference that
lead to the same regexes) as the final results.

Based on this idea, we propose a self-consistency decoding mechanism that
selects the most consistent answer by sampling in the output space of language
model [15]. Figure 4 illustrates the process of self-consistency decoding.

First, we employ two language models: a chain PLM which is trained on (x, s)
pairs to generate chains of inference, and a tree PLM which is trained on (x,
y) pairs to generate the parsing trees in parenthetical notation (e.g.,
and(startwith(<low>, endwith(<vow>))).

At the decoding phase, each language model samples $k$ outputs. The total $2k$
outputs are reverted to plain regexes and are used to select the final regex
using a plurality vote strategy. Since different regexes may represent the
same semantic, we take a plurality vote based on semantic consistency.222We
measure the semantic consistency using the DFA-EQ metric introduced in Section
IV-C. One output represents one vote. Regexes with the same semantics will
share the votes, and we randomly select one of them as the representative.
Finally, InfeRE chooses the regex that receives the most votes as the final
output. If there is more than one answer with equal votes, we take the answer
first encountered.

Compared with standard decoding methods, self-consistency encourages
correctness and diversity at the same time [15].

It is worth noting that our idea is different from previous studies [15, 27]
on diversity driven decoding, i.e., introducing randomness in the input and
output space of a single model. We train multiple language models to generate
both regexes and chains of inference. The different forms of output can
greatly enrich the input and output space of language models and thus enhance
the self-consistency decoding mechanism.

##  IV Experimental Setup

###  IV-A Research Questions

We evaluate InfeRE by addressing the following research questions:

  * •

RQ1: How effective is InfeRE in generating regexes from natural language
descriptions? We evaluate the performance of InfeRE on two widely used
datasets and compare it against state-of-the-art regex generation approaches
and a tree-based code generation approach.

  * •

RQ2: What is the effect of chain of inference? We conduct an ablation study on
the efficacy of the chain of inference. We further apply chain of inference to
different PLMs.

  * •

RQ3: What is the effect of self-consistency decoding and how the number of
output samples affects the performance of self-consistency decoding? We
conduct an ablation study to analyze the effect of self-consistency decoding
mechanism. As the self-consistency decoding relies heavily on the number $k$
of output samples, we further vary the number $k$ to explore the performance
of self-consistency decoding.

  * •

RQ4: How does different backbone PLMs impact the performance of InfeRE? We
study the effect of different backbone PLMs on performance. We replace the
backbone with popular PLMs of different types and sizes and compare their
performance.

  * •

RQ5: What is the impact of data size on the performance of regex generation?
In practical applications, sufficient high-quality parallel corpora are
difficult to obtain. To answer this question, we aim to study the effect of
data size on performance. We vary the size of the training set and compare the
performance of various approaches under different data sizes.

###  IV-B Comparison Methods

We compare InfeRE with five regex generation methods, including the state-of-
the-art method S2RE [11]. Since S2RE is not pre-trained, we extend S2RE to
S2RE-T5 by replacing the LSTM backbone with T5. InfeRE is also related to
tree-based generation models. Therefore, we compare it with TRANX [30], a
popular tree-based code generation method. Specifically, we compare InfeRE
with the following baselines.

  * •

Semantic-Unify [3]: a grammar-based approach that directly parses natural
language description into regexes. Semantic-Unify learns a combinatory
categorial grammar, which consists of words or phrases with their
corresponding regular expression functions.

  * •

Deep-Regex [4]: an LSTM sequence-to-sequence model with attention. Deep-Regex
regards regex generation as a 1-to-1 translation task without considering
semantically equivalent regexes with different forms. The model can be trained
by either maximizing likelihood (Deep-RegexMLE [4]) or maximizing marginal
likelihood (Deep-RegexMML [6]).

  * •

SemRegex [5]: the same model as Deep-Regex, but trained using policy gradient
[33] to reward the model for generating equivalent regexes in different forms.

  * •

SoftRegex [6]: an extension of SemRegex by training an additional reward model
(EQ_Reg), which measures the equivalence probability of two regexes and then
uses the probability to reward the sequence-to-sequence model.

  * •

S2RE [11]: an LSTM sequence-to-sequence model trained via policy gradient.
S2RE introduces both syntactic and semantic validity to generate more valid
regexes. To our knowledge, S2RE is the state-of-the-art approach for regex
generation.

  * •

S2RE-T5 [11]: a variant of S2RE by replacing LSTM with T5, which is a PLM with
a larger number of parameters. For fair comparison, we implement S2RE-T5 using
the configurations in [11].

  * •

TRANX [30]: a tree-based code generation model that is widely used in recent
studies [34, 35, 36, 37]. Similar to InfeRE, TRANX decouples code generation
as a series of tree construction actions using user-defined, task-dependent
grammar.

We reproduce the results of Deep-Regex, SoftRegex, and TRANX using their
officially published code. For S2RE-T5, we initialize the parameters by pre-
training the model on the (query,regex) pairs training set and leverage policy
gradient to train the model with the semantics-based and syntactic-based
objective. For baselines that are not open-source, we directly excerpt the
statistics from the original paper and leave blanks if the results are not
reported.

###  IV-C Evaluation Metrics

We measure the performance of regex generation using two commonly used
metrics:

DFA-EQ [3]. Since regexes in different forms may represent the same semantic,
DFA-EQ converts regexes to deterministic finite automatons (DFAs) and measures
their semantic equivalence by comparing their DFAs. If their DFAs exactly
match, the two regexes are semantically equivalent. DFA-EQ@m measures the
proportion of cases for which the top-$m$ generated regexes contain at least
one regex that is semantically equivalent to the ground truth. In our
experiments, we compute the top-m DFA-EQ accuracy with m = 1 and 5.

EM (Exact Match). EM measures the ratio of regexes that exactly match ground-
truth regexes. Different from the DFA-EQ, EM compares two regexes in plain
texts.

###  IV-D Datasets

We evaluate InfeRE on two widely used datasets, namely, NL-RX-Turk [4] and
KB13 [3]. The statistics of the two datasets are presented in Table II.

TABLE II: Statistics of the datasets. Dataset |  Train | Dev | Test
---|---|---|---
NL-RX-Turk | 6,500 | 1,000 | 2,500
KB13 | 618 | 206 | 206
TABLE III: Performance of various approaches on regex generation (SC=Self-Consistency; CI=Chain of Inference). Approach | NL-RX-Turk | KB13
---|---|---
DFA-EQ@1(%) | DFA-EQ@5(%) | EM(%) | DFA-EQ@1(%) | DFA-EQ@5(%) | EM(%)
Semantic-Unify | 38.6 | — | — | 65.5 | — | —
Deep-RegexMLE | 60.3 | 76.0 | 40.7 | 66.5 | 75.7 | 55.8
Deep-RegexMML | 62.4 | 76.8 | 39.2 | 68.2 | 77.7 | 56.8
SemRegex | 62.3 | — | — | 78.2 | — | —
SoftRegex | 62.8 | 72.1 | 41.5 | 78.2 | 79.6 | 62.1
S2RE | 62.8 | — | — | 78.2 | — | —
S2RE-T5 | 67.6 | 85.7 | 54.4 | 82.0 | 88.8 | 71.4
TRANX | 58.8 | 75.6 | 44.0 | 73.8 | 82.0 | 61.2
InfeRE (ours) | 69.2 | 89.3 | 53.4 | 82.5 | 91.3 | 69.4
\- $w/o$ SC | 67.8 | 85.9 | 55.5 | 81.6 | 87.9 | 72.3
\- $w/o$ SC+CI | 67.2 | 85.5 | 54.2 | 82.0 | 88.8 | 70.4

NL-RX-Turk is the largest dataset which contains 10,000 regexes with natural
language annotations. Due to the heavy workload of manual labeling, Locascio
et al. employ a generate-and-paraphrase process for annotating data
automatically [4]. They initially generated 10,000 regexes with natural
language descriptions stochastically based on manually-crafted grammar. Then,
human annotators were asked to paraphrase the synthetic natural language
descriptions.

KB13 is a smaller and easier dataset comprising 824 (query, regex) pairs. The
dataset was created by crowdsourcing: the authors first asked crowdsource
workers to write natural language queries. Then, each query was presented to
experienced programmers who wrote the corresponding regexes. On average, the
length of natural language descriptions in NL-RX-Turk is 50% longer than KB13.
Following previous studies [4, 5, 6, 11], we split the original dataset into
train, develop, and test sets.

###  IV-E Implementation Details

We build our models on top of the T5 using the same configuration as T5-base
(d_ff $=3072$, d_kv $=64$, d_model $=768$). Both the encoder and decoder
consist of 12 blocks with a dropout probability of 0.1. On both datasets, the
batch size is set to 12 per GPU. We optimize the model using Adam optimizer
with a learning rate of 3e-5 and an epsilon of 1e-8. For the self-consistency
decoding, following previous studies [15], we set the number $k$ of outputs
sampled from each model to 40.

We train the models for 30 and 60 epochs on NL-RX-Turk and KB13, respectively.
The checkpoint that obtains the best performance on the development set is
selected for testing. All experiments are carried out on a workstation with 2
RTX 2080Ti GPUs and an operating system of Ubuntu 18.04.4 LTS.

##  V Results

###  V-A Effectiveness of InfeRE in Regex Generation (RQ1)

Table III compares the performance of various methods on the two datasets.
Overall, InfeRE achieves the best performance among all the approaches.

Compared with state-of-the-art NL2RE methods, InfeRE demonstrates strong
strength, with the top-5 DFA-EQ accuracy increased by 16.3% and 14.7% against
S2RE on NL-RX-Turk and KB13, respectively. A more significant improvement can
be observed in the EM metric, which is increased by 33.7% and 16.4% on two
datasets compared to S2RE.

We notice that InfeRE also surpasses S2RE-T5, a PLM with the same number of
parameters as InfeRE. The DFA@1 and DFA@5 are improved by 2.3% and 4.2% on NL-
RX-Turk. The results indicate that the improvement does not solely come from
pre-training, which affirms the effectiveness of the proposed chain of
inference and self-consistency decoding mechanisms.

Compared with the tree-based code generation model TRANX, InfeRE gains 13.2%,
14.7%, and 22.1% improvement in the three metrics, respectively, demonstrating
the superiority of InfeRE over the traditional tree-based method.

One notable phenomenon is that the improvement is more significant on NL-RX-
Turk than on KB13. One main reason is that NL-RX-Turk is larger and more
complex than KB13, allowing the model to capture richer knowledge from the
chains of inference.

TABLE IV: Generated regex examples by various approaches. The middle column shows the final regexes. For ease of analysis, we also present the intermediate trees in a parenthetical notation in the right column. All results are generated via greedy decoding except InfeRE with self-consistency decoding. Example 1. | Query: either start with string <M0$\textgreater$ or end with any number.
---|---
Gold: | ((.*)([0-9]))—((<m0>)(.*)) | or(endwith(<num>),startwith(<m0>))
Deep-RegexMML: | ((<m0>)—((.*)([0-9])))(.*) |  startwith(or(<m0>,endwith(<num>)))
SoftRegex: | ((<m0>)—(.*)([0-9]))(.*) |  startwith(or(<m0>,endwith(<num>)))
InfeRE-w/o SC+CI: | ((<m0>)—((.*)([0-9])))(.*) |  startwith(or(<m0>,endwith(<num>)))
InfeRE-w/o SC: | ((<m0>)(.*))—((.*)([0-9])) | or(startwith(<m0>),endwith(<num>))
InfeRE: | ((<m0>)(.*))—((.*)([0-9])) | or(startwith(<m0>),endwith(<num>))
Example 2. | Query: lines with the string <M0$\textgreater$ ending in zero or more of a capital letter.
Gold: | (<m0>)(((.*)([<A-Z>]))*) | concat(<m0>,star(endwith(<cap>)))
Deep-RegexMML: | ((<m0>)(1,))—((.*)([A-Z])) |  or(repeat_least(<m0>,1),endwith(<cap>))
SoftRegex: | ((<m0>)(1,))&((.*)([A-Z])) | and(repeat_least(<m0>,1),endwith(<cap>))
InfeRE-w/o SC+CI: | (.*(.*<m0>.*))* | star(endwith(contain(<m0>)))
InfeRE-w/o SC: | (<m0>)(((.*)([<A-Z>]))*) | concat(<m0>,star(endwith(<cap>)))
InfeRE: | (<m0>)(((.*)([<A-Z>]))*) | concat(<m0>,star(endwith(<cap>)))
Example 3. | Query: items with a any letter preceding <M0>.
Gold: | (([A-Z])—([a-z]))(<m0>) | concat(or(<low>,<cap>),<m0>)
Deep-RegexMML: | (([a-z])&([a-z] ))(<m0>) | concat(and(<low>,<low>),<m0>)
SoftRegex: | ([a-z])(<m0>) | concat(<low>,<m0>)
InfeRE-w/o SC+CI: | (([A-Z])&([a-z]))(<m0>) | concat(and(<low>,<cap>),<m0>)
InfeRE-w/o SC: | (([A-Z])&(([a-z])&(a-zA-Z)))(<m0>) | concat(and(and(<low>,<cap>),<let>),<m0>)
InfeRE: | (([A-Z])—(([a-z])—(a-zA-Z)))(<m0>) | concat(or(or(<low>,<cap>),<let>),<m0>)

We further qualitatively analyze concrete regexes generated by various
approaches. Three examples are listed in Table IV.

  * •

In Example 1, the query “either start with string <M0$\textgreater$ or end
with any number” involves two steps, namely, “start with string <M0>” and “end
with any number”, which are successfully predicted by InfeRE. By contrast, all
language models without chain of inference mistakenly put the ”or” operator in
the middle, despite the correct operators and operands. This suggests that the
chain of inference captures the real text-matching processes of regexes better
than plain regex and parenthetical notation for regex trees.

  * •

Example 2 compares the generated regexes for the query “lines with the string
<M0$\textgreater$ ending in zero or more of a capital letter”. The query is
clearly relevant to “capital letter”. However, Deep-RegexMML and SoftRegex
mistakenly omit the “zero or more” information. Both InfeRE and its variant
without self-consistency correctly generate the gold regex, because the chain
of inference decomposes the regex into multiple easier sub-regexes, and
therefore helps the language model understand the complete information of the
query.

  * •

Example 3 shows the results of “items with a any letter preceding <M0>”. The
ground truth is “or(<low>,<cap>)”, while Deep-RegexMML and SoftRegex
misunderstand “any letter” as any lower case letter, and the variants of
InfeRE misunderstand the keyword letter as “and(<low>,<cap>)”. Although both
variants generate the wrong regexes when decoding greedily, InfeRE with self-
consistency predicts the right answer.

These examples demonstrate the superiority of InfeRE in regex generation,
affirming the effectiveness of chain of inference and self-consistency
decoding.

Answer to RQ1: InfeRE can achieve better DFA-EQ and EM accuracy than the
state-of-the-art regex generation methods and popular tree generation method.
Even if we replace the backbone of S2RE with T5, InfeRE achieves better
performance. The advantage of InfeRE is more obvious on the complex datatset
NL-RX-Turk.

###  V-B Effect of Chain of Inference (RQ2)

We conduct a number of ablation experiments to explore the effect of chain of
inference.

####  V-B1 Chain of inference in InfeRE

We compare two variants to verify the efficacy of chain of inference, namely,
InfeRE without self-consistency (-w/o SC) and InfeRE with neither self-
consistency nor chain of inference (-w/o SC+CI). The former is built with a
chain PLM that only generates chains of inference, while the latter is built
with a PLM that directly generates trees in the form of parenthetical notated
sequences. The results are shown in the bottom half of Table III.

As we can see, chain of inference, by step-by-step rationale, can greatly
enhance the performance of regex generation. Compared with a simple PLM (-w/o
SC+CI), InfeRE without self-consistency (-w/o SC) gains visible improvements
in most metrics. For example, the EM increases by about 2.4% and 2.7% on NL-
RX-Turk and KB13, respectively.

####  V-B2 Chain of inference with different PLMs

We further explore the generalizability of the chain of inference with
different PLMs. Specifically, we train GPT2, BART-small, BART-base, T5-small,
and T5-base on both (query, regex) and (query, chain) pairs, respectively, and
evaluate their DFA-EQ@1 accuracy on the NL-RX-Turk dataset. The results are
presented in Table V. As the results show, most PLMs perform better when
trained with chains of inference than trained with regexes in the form of
parenthetical notated sequences. The improvement from the chain of inference
is most significant on GPT2, BART-small, and BART-base, which are about 7.1%,
7.6%, and 6.9%. We conjecture that these models do not fully understand the
regex in the format of parenthetical notated sequences, so the chain of
inference can greatly increase their performance. Comparatively, the T5 model
has achieved high performance on NL-RX-Turk, which obscures the improvement
brought by the chain of inference.

The results corroborate previous findings that median-sized language models
like T5-base can also solve certain multi-step problems through inference
[38], as compared to ultra-large language models such as ChatGPT. Unlike using
chain-of-thought prompting for large language models, we fine-tune T5 using a
sufficient number of automatically generated chains of inference. Such task-
specific fine-tuning can be seen as an effective way to stimulate the
reasoning ability of T5-base on downstream tasks [38].

Answer to RQ2: Chain of inference makes an appreciable contribution to the
performance of InfeRE in regex generation. In addition, chain of inference can
lead to considerable performance improvements on different PLMs.

(a) NL-RX-Turk

(b) KB13

Figure 5: Performance of InfeRE under different numbers of sampled outputs.  TABLE V: Effectiveness of chain of inference with different PLMs. We evaluate DFA-EQ@1(%) on the NL-RX-Turk dataset.$w/o$ CI: the model trained on (query, regex) pairs; $w/$ CI: the model trained on (query, chain) pairs. Approach | GPT2 | BART-small | BART-base | T5-small | T5-base
---|---|---|---|---|---
\- $w/o$ CI | 52.0 | 55.4 | 55.9 | 65.6 | 67.2
\- $w/$ CI | 55.7 | 59.6 | 59.8 | 65.2 | 67.8

###  V-C Effect of Self-Consistency Decoding (RQ3)

We conduct an ablation experiments to explore the effect of self-consistency
decoding. Specially, we compare InfeRE against InfeRE without self-consistency
(-w/o SC) to study the effect of self-consistency decoding. The results are
shown in the bottom half of Table III.

As the result shows, self-consistency decoding demonstrates its effectiveness.
InfeRE significantly outperforms the variant without self-consistency (-w/o
SC), with 1.6% and 3.9% improvement on average in terms of DFA-EQ@1 and DFA-
EQ@5. The improvement is more significant when self-consistency decoding and
chain of inference mechanisms are used together, e.g., 4.4% in terms of DFA-
EQ@5 on NL-RX-Turk.

However, we have also observed that InfeRE without self-consistency gains the
best EM score. The reason for this, in addition to the chain of inference, is
that self-consistency decoding takes semantic consistency as the metric. Hence
it boosts the generation of more regexes with different syntax but the same
semantics, which leads to a decrease in the EM accuracy. The performance
degradation on EM metric does not affect the actual application, since we are
more concerned with semantically correct regexes in regex generation task.

Impact of number of output samples: As the self-consistency decoding relies on
the number $k$ of output samples, we vary $k$ and evaluate the DFA-EQ accuracy
of our approach on the two datasets. Besides InfeRE, which employs both a
chain PLM and a tree PLM to perform self-consistency decoding, we also
evaluate InfeRE with only one single PLM, i.e., tree PLM or chain PLM. The
results are shown in Figure 5.

As the number of outputs sampled increases, all three models tend to perform
better. The two variants with only single PLM achieve 68.6% and 68.3% DFA-
equal accuracy on NL-RX-Turk relying on self-consistency respectively,
outperforming the result 67.8% and 67.2% when decoding greedily. InfeRE with
multi PLMs achieve the best performance, 69.2% DFA-equal accuracy. Specially,
we can see that when $k$ exceeds 15, InfeRE with multi PLMs consistently
outperforms two variants with a single PLM. The reason is that self-
consistency decoding aggregates the outputs from different PLMs and thus
reduces the variance of the final results.

Besides, InfeRE with only chain PLM achieves stronger performance than that
with tree PLM under almost all numbers of output samples. The difference is
more significant when $k$ is relatively small. This indicates that the chain
of inference enhances the stability of the model in regex generation, which
helps the self-consistency decoding to sample correct answer even when output
samples are insufficient.

Answer to RQ3: Self-consistency decoding can significantly help InfeRE
generate semantically correct regexes, achieving 1.6% and 3.9% improvement on
average in terms of DFA-EQ@1 and DFA-EQ@5 metrics, and the effect of self-
consistency decoding becomes much more apparent as the number of ouput samples
increases.

###  V-D Impact of Different Backbone PLMs (RQ4)

We further assess the impacts of different backbone PLMs on the performance of
InfeRE. We experiment with two types of backbone models with two sizes on the
NL-RX-Turk dataset, including BART-base, BART-small, T5-small, and T5-base.
The results are shown in Table VI.

Overall, T5 surpasses BART in the regex generation task. The pre-training
tasks of BART include document-level denoising autoencoding. We conjecture
that its pre-training objectives and pre-training data make it inappropriate
for structured expression generation. In particular, T5-base performs the best
in terms of all metrics. Clearly, larger language models boost greater
performance in regex generation.

Answer to RQ4: The type and size of backbone PLM strongly affects the
performance of InfeRE and InfeRE with T5-base backbone performs best.

TABLE VI: Ablation results of backbone PLMs on NL-RX-Turk.  Model | DFA-EQ@1(%) | DFA-EQ@5(%) | EM(%)
---|---|---|---
T5-base | 69.2 | 89.3 | 55.5
T5-small | 66.8 | 88.9 | 51.7
BART-base | 59.4 | 79.9 | 43.6
BART-small | 60.9 | 70.9 | 42.3

###  V-E Impact of Data Size (RQ5)

We also study the effect of training data size on the NL-RX-Turk dataset. We
vary the size of data from 100 to full data, i.e., 6500, and investigate its
effect on the DFA-EQ accuracy of regex generation. Specifically, we compare
InfeRE, InfeRE (-w/o SC), InfeRE (-w/o SC+CI), SoftRegex and DeepRegexMML.
Figure 6 shows the results.

(a) Size from 100 to 1000

(b) Size from 2000 to 6500

Figure 6: Performance under different training set sizes on NL-RX-Turk.

As we can see, InfeRE and its variants consistently outperform baseline models
under different training sizes. Notably, when the training data gets smaller
(e.g., $\textless$1000), the improvement becomes much more significant. This
indicates that our approach has a strong ability in a low-resource generation.
We also observe a more profound advantage of the self-consistency decoding in
the low-resource setting, as opposed to the chain of inference mechanism,
which exhibits a more substantial improvement under conditions of sufficient
data. This phenomenon may be attributed to the fact that the low-resource
setting tends to result in less robust performance, which can be alleviated
through integrated sampling via the self-consistency decoding mechanism.
Conversely, the chain of inference mechanism is much more suitable for
enabling a language model to learn structural information in situations where
sufficient data is available.

Answer to RQ5:  InfeRE outperforms the baseline models under all data sizes.
In particular, self-consistency decoding exhibits a more significant advantage
in low-resource settings, while the chain of inference contributes more to the
performance when sufficient data is available.

###  V-F Threats to Validity

We have identified the following threats to our approach:

####  V-F1 The format of inference chains

In our experiments, we represent chain of inference as nodes of parsing trees.
Results show that our chain of inference has little effect on the performance
when the training data size is extremely limited. Hence it remains to
investigate whether other formats of inference chains can lead to better
performance.

####  V-F2 Generalization

We evaluate the efficacy of the chain of inference on two regex datasets. In
theory, the chain of inference we propose can be extended to any tree-based
generation task. We leave the evaluation on other related tasks for future
work.

##  VI Conclusion

This paper introduces InfeRE, a novel approach to generate regular expressions
from natural language descriptions. InfeRE formulates the process of regex
generation as a chain of thought and leverages pre-trained language models to
generate step-by-step internal processes. The internal processes chains are
assembled into the final regexes using a self-consistency decoding mechanism,
which combines the sampled outputs to enhance the robustness of the generated
regexes. Our experimental results demonstrate that InfeRE achieves remarkable
improvements on two benchmark datasets. In the future, we will explore the
chain of inference in other forms and apply it to more code intelligent tasks.
For example, a program can be regarded as a chain of module interaction. The
introduction of the chain of inference has the potential to improve the
capability of existing models to generate a large complete program instead of
function-level code.

Source code and dataset to reproduce our work are available at
https://github.com/Smallqqqq/InfeRE.

## Acknowledgment

This research is supported by National Natural Science Foundation of China
(Grant No. 62232003, 62102244, 62032004 and 62272296) and CCF-Tencent Open
Research Fund (RAGR20220129).

## References

  * [1] J. C. Davis, L. G. Michael IV, C. A. Coghlan, F. Servant, and D. Lee, “Why aren’t regular expressions a lingua franca? an empirical study on the re-use and portability of regular expressions,” in _Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2019, pp. 443–454.
  * [2] B. Luo, Y. Feng, Z. Wang, S. Huang, R. Yan, and D. Zhao, “Marrying up regular expressions with neural networks: A case study for spoken language understanding,” _arXiv preprint arXiv:1805.05588_ , 2018.
  * [3] N. Kushman and R. Barzilay, “Using semantic unification to generate regular expressions from natural language,” in _Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 9-14, 2013, Westin Peachtree Plaza Hotel, Atlanta, Georgia, USA_ , 2013, pp. 826–836.
  * [4] N. Locascio, K. Narasimhan, E. DeLeon, N. Kushman, and R. Barzilay, “Neural generation of regular expressions from natural language with minimal domain knowledge,” in _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016_ , 2016, pp. 1918–1923.
  * [5] Z. Zhong, J. Guo, W. Yang, J. Peng, T. Xie, J. Lou, T. Liu, and D. Zhang, “Semregex: A semantics-based approach for generating regular expressions from natural language specifications,” in _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , 2018, pp. 1608–1618.
  * [6] J. Park, S. Ko, M. Cognetta, and Y. Han, “Softregex: Generating regex from natural language descriptions using softened regex equivalence,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , 2019, pp. 6424–6430.
  * [7] X. Ye, Q. Chen, I. Dillig, and G. Durrett, “Benchmarking multimodal regex synthesis with complex structures,” _arXiv preprint arXiv:2005.00663_ , 2020\.
  * [8] Q. Chen, X. Wang, X. Ye, G. Durrett, and I. Dillig, “Multi-modal synthesis of regular expressions,” in _Proceedings of the 41st ACM SIGPLAN conference on programming language design and implementation_ , 2020, pp. 487–502.
  * [9] X. Ye, Q. Chen, I. Dillig, and G. Durrett, “Optimal neural program synthesis from multimodal specifications,” _arXiv preprint arXiv:2010.01678_ , 2020\.
  * [10] X. Ye, Q. Chen, X. Wang, I. Dillig, and G. Durrett, “Sketch-driven regular expression generation from natural language and examples,” _Trans. Assoc. Comput. Linguistics_ , vol. 8, pp. 679–694, 2020.
  * [11] Y. Li, S. Li, Z. Xu, J. Cao, Z. Chen, Y. Hu, H. Chen, and S. Cheung, “TransRegex: multi-modal regular expression synthesis by generate-and-repair,” in _43rd IEEE/ACM International Conference on Software Engineering, ICSE 2021, Madrid, Spain, 22-30 May 2021_. IEEE, 2021, pp. 1210–1222.
  * [12] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa, “Large language models are zero-shot reasoners,” _arXiv preprint arXiv:2205.11916_ , 2022\.
  * [13] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou, “Chain of thought prompting elicits reasoning in large language models,” _arXiv preprint arXiv:2201.11903_ , 2022.
  * [14] M. Pourreza and D. Rafiei, “Din-sql: Decomposed in-context learning of text-to-sql with self-correction,” _arXiv preprint arXiv:2304.11015_ , 2023\.
  * [15] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou, “Self-consistency improves chain of thought reasoning in language models,” _arXiv preprint arXiv:2203.11171_ , 2022.
  * [16] E. Spishak, W. Dietl, and M. D. Ernst, “A type system for regular expressions,” in _Proceedings of the 14th Workshop on Formal Techniques for Java-like Programs_ , 2012, pp. 20–26.
  * [17] X. Liu, Y. Jiang, and D. Wu, “A lightweight framework for regular expression verification,” in _2019 IEEE 19th International Symposium on High Assurance Systems Engineering (HASE)_. IEEE, 2019, pp. 1–8.
  * [18] M. Lee, S. So, and H. Oh, “Synthesizing regular expressions from examples for introductory automata assignments,” in _Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences_ , 2016, pp. 70–80.
  * [19] A. Bartoli, A. De Lorenzo, E. Medvet, and F. Tarlao, “Inference of regular expressions for text extraction from examples,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 28, no. 5, pp. 1217–1230, 2016.
  * [20] Y. Li, Z. Xu, J. Cao, H. Chen, T. Ge, S.-C. Cheung, and H. Zhao, “Flashregex: deducing anti-redos regexes from examples,” in _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2020, pp. 659–671.
  * [21] G. J. Bex, F. Neven, T. Schwentick, and S. Vansummeren, “Inference of concise regular expressions and dtds,” _ACM Transactions on Database Systems (TODS)_ , vol. 35, no. 2, pp. 1–47, 2010.
  * [22] G. J. Bex, W. Gelade, F. Neven, and S. Vansummeren, “Learning deterministic regular expressions for the inference of schemas from xml data,” _ACM Transactions on the Web (TWEB)_ , vol. 4, no. 4, pp. 1–32, 2010.
  * [23] D. D. Freydenberger and T. Kötzing, “Fast learning of restricted regular expressions and dtds,” in _Proceedings of the 16th International Conference on Database Theory_ , 2013, pp. 45–56.
  * [24] A. Ranta, “A multilingual natural-language interface to regular expressions,” in _International Workshop on Finite State Methods in Natural Language Processing_ , 1998, p. 79–90.
  * [25] S. Narang, C. Raffel, K. Lee, A. Roberts, N. Fiedel, and K. Malkan, “Wt5?! training text-to-text models to explain their predictions,” _arXiv preprint arXiv:2004.14546_ , 2020.
  * [26] S. Wiegreffe, J. Hessel, S. Swayamdipta, M. Riedl, and Y. Choi, “Reframing human-ai collaboration for generating free-text explanations,” _arXiv preprint arXiv:2112.08674_ , 2021.
  * [27] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou, “Rationale-augmented ensembles in language models,” _arXiv preprint arXiv:2207.00747_ , 2022.
  * [28] X. Ye and G. Durrett, “The unreliability of explanations in few-shot in-context learning,” _arXiv preprint arXiv:2205.03401_ , 2022.
  * [29] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems_ , 2017, pp. 5998–6008.
  * [30] P. Yin and G. Neubig, “Tranx: A transition-based neural abstract syntax parser for semantic parsing and code generation,” _arXiv preprint arXiv:1810.02720_ , 2018.
  * [31] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu, “Exploring the limits of transfer learning with a unified text-to-text transformer,” _J. Mach. Learn. Res._ , vol. 21, pp. 140:1–140:67, 2020.
  * [32] K. E. Stanovich and R. F. West, “Individual differences in reasoning: Implications for the rationality debate?” _Behavioral and brain sciences_ , vol. 23, no. 5, pp. 645–665, 2000.
  * [33] R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” _Machine learning_ , vol. 8, no. 3, pp. 229–256, 1992.
  * [34] H. Jiang, L. Song, Y. Ge, F. Meng, J. Yao, and J. Su, “An ast structure enhanced decoder for code generation,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 30, pp. 468–476, 2021.
  * [35] Y. Dong, G. Li, and Z. Jin, “Antecedent predictions are dominant for tree-based code generation,” _arXiv preprint arXiv:2208.09998_ , 2022.
  * [36] N. Beau and B. Crabbé, “The impact of lexical and grammatical processing on generating code from natural language,” _arXiv preprint arXiv:2202.13972_ , 2022.
  * [37] S. Shen, X. Zhu, Y. Dong, Q. Guo, Y. Zhen, and G. Li, “Incorporating domain knowledge through task augmentation for front-end javascript code generation,” in _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2022, pp. 1533–1543.
  * [38] N. Ho, L. Schmid, and S.-Y. Yun, “Large language models are reasoning teachers,” _arXiv preprint arXiv:2212.10071_ , 2022.