← 返回 2026-06-19

ReSyn：一个通用的递归正则表达式合成框架 ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

Seongmin Kim, Hyunjoon Cheon, Su-Hyeon Kim, Yo-Sub Han, Sang-Ki Ko 📅 2026-06-13 👍 2 2026-07-13 08:37
分治算法 归纳编程 正则表达式 神经符号AI 程序合成
arXiv HuggingFace PDF

提出递归分治框架和层次化集合编码器，解决复杂正则表达式的自动合成难题

前置知识

正则表达式（Regular Expression）

正则表达式是一种用于描述字符串模式的形式语言，由基本字符、字符类、连接（Concatenation，AB表示A后跟B）、联合（Union，A|B表示A或B）和重复（Kleene star，A*表示A重复零次或多次）等操作递归构成。例如，(a|b)+c*可以匹配'ac'、'bac'、'abbc'等字符串。正则表达式在文本处理、数据验证、网络安全等领域有广泛应用。

本文的核心任务是从输入输出示例自动合成正则表达式，因此必须理解正则表达式的语法结构、语义含义和组合方式，才能理解合成问题的复杂性和所提出方法的创新性。

Programming-by-Example（PBE，基于示例的程序合成）

PBE是一种程序合成范式，用户提供一组输入输出示例，系统自动推断出能够满足所有示例的程序。在正则表达式合成场景中，用户提供正例（应该匹配的字符串）和反例（不应该匹配的字符串），系统需要找到一个正则表达式R使得所有正例都属于L(R)且所有反例不属于L(R)。PBE避免了用户编写复杂程序的负担，特别适合正则表达式这类语法晦涩的场景。

本文研究的问题正是PBE在正则表达式合成中的应用，理解PBE的挑战（如欠约束问题、解空间爆炸）对于理解本文为何需要递归分解和特殊编码器设计至关重要。

抽象语法树（AST，Abstract Syntax Tree）

AST是源代码的树状表示，每个节点代表一个语法构造。对于正则表达式，AST包含原子节点（Literal、Character Class）和操作符节点（Concat、Union、Repetition）。例如，正则表达式(a|b)c*的AST根节点是Concat，左子节点是Union（两个Literal子节点a和b），右子节点是Repetition（子节点Literal c）。AST抽象掉了括号、优先级等语法细节，聚焦于结构层次。

本文的核心创新是处理真实正则表达式的深度嵌套结构，理解AST有助于理解作者如何量化结构复杂度（AST深度、节点数量）以及递归分解算法如何操作这些结构。

排列不变性（Permutation Invariance）

排列不变性是指函数的输出不依赖于输入的顺序。在数学上，函数f满足f(x1, x2, ..., xn) = f(xσ(1), xσ(2), ..., xσ(n))对任意排列σ成立。在正则表达式合成中，输入是一组示例集合{example1, example2, ...}，由于集合没有顺序，模型应该对示例顺序不敏感。传统的序列模型（如RNN、Transformer）将示例按固定顺序处理，会学习到虚假的顺序依赖，破坏了问题的本质对称性。

本文提出的SET2REGEX使用层次化集合编码器专门处理排列不变性，这是其参数效率高（10M vs 300M）的关键。理解这个概念有助于理解为何传统Seq2Seq模型在PBE任务上存在架构缺陷。

研究动机

现有的正则表达式合成系统存在根本性缺陷：首先，它们依赖过度简化的基准测试数据集。如表1所示，真实世界正则表达式（如RegExLib）的AST平均节点数为23.69，是合成数据集（6.45）和简化数据集（8.11-11.04）的2倍以上；深度≥5的高复杂实例占比显著，而其他基准测试集中在浅层区域。更重要的是，真实正则表达式大量使用Union操作符（RegExLib中占16.95%），而现有基准测试中Union占比不足3%。这种结构性差异导致最先进的模型过度拟合简化结构，无法泛化到真实世界的递归嵌套场景。其次，现有的神经序列到序列模型存在两个架构缺陷：一是将层次化AST扁平化为线性序列，丢失了长程依赖关系；二是将输入示例视为有序序列，违反了集合的排列不变性，强制模型学习虚假的顺序而非共享的结构模式。

本文的目标是本文的具体目标是设计一个能够处理真实世界复杂正则表达式的通用合成框架，该框架应该：(1) 能够处理深度嵌套的结构（AST深度≥6），(2) 灵活支持Union和Concatenation两种分解策略，(3) 保持参数效率（与大规模LLM相比），(4) 在多个基准测试上提升合成成功率，特别是在复杂的RegExLib数据集上。

与已有工作不同的是，本文的独特切入角度在于将"最优分解是NP难"这一理论洞察转化为学习式解决方案，而非依赖刚性启发式。现有分治方法（如FOREST、SPLITREGEX）假设顶层操作符总是Concatenation，这种刚性假设严重限制了递归分解能力。本文提出的RESYN框架通过一个可学习的ROUTER模块动态决定使用Segmentation（针对Concatenation）还是Partitioning（针对Union），实现了真正的递归分治。另一个独特角度是设计了层次化集合编码器（Hierarchical Set Encoder），通过PMA（Pooling by Multihead Attention）在两个粒度（字符级、字符串级）上实现排列不变性，从根本上解决了传统Seq2Seq模型的架构缺陷。

核心方法

RESYN框架由三个协同阶段组成：数据规范化、合成器无关的递归算法和专用基础模型。核心思想是借鉴分治策略，将复杂的合成问题分解为可管理的子问题，但与传统方法不同，RESYN使用神经模块学习如何分解而非依赖刚性规则。整体工作流程：输入正例集P和反例集N，如果P只有单个元素则直接返回转义字符串；否则ROUTER评估结构复杂度并决定策略（Synthesize/Segment/Partition）。如果选择Segment，SEGMENTER将每个字符串分割成k个段，形成有序的k个集合(P1,...,Pk)递归合成后用Concatenation组合。如果选择Partition，PARTITIONER将P分成m个不相交子集，每个子集递归合成后用Union组合。最后进行一致性验证。这种递归分解允许系统适应问题的复杂度，将巨大的搜索空间降维到基础合成器的能力范围内。

核心创新点有三个：(1) 理论贡献：证明了最优正则表达式合成问题是NP难的（通过将最短公共超序列问题归约到最优对齐问题），这意味着确定性算法在实践中不可行，学习式近似是必要的。(2) 架构创新：SET2REGEX的层次化集合编码器通过两层PMA聚合（字符级→字符串级→全局上下文），在10M参数下实现了与300M参数基线相当的性能，同时天然满足排列不变性。解码器使用双重注意力机制，先关注全局上下文c获取整体结构，再关注字符串嵌入{h'i}获取局部细节。(3) 算法创新：RESYN的递归分治框架包含三个专用模块。ROUTER只使用全局上下文向量c计算策略分布π(a|P)=Softmax(MLP(c))；PARTITIONER使用有序编码和指针网络预测簇分配；SEGMENTER使用标准Transformer编码器-解码器进行细粒度字符级对齐。这种模块化设计允许RESYN作为包装器赋能任何基础合成器。

方法步骤详情

方法步骤完整描述：步骤1-数据规范化（Regex Canonicalization）：收集正则表达式后过滤掉包含反向引用和环视断言的非正则特征，构建AST后应用规则优化器进行节点简化、结构扁平化和标准化，最后对长度≥2的字面量进行匿名化（替换为非可打印ASCII范围的Token）并随机化映射防止过拟合。步骤2-基础合成：使用SET2REGEX作为基础合成器。字符级Transformer和PMA将每个字符串压缩为固定大小嵌入hi，字符串级Transformer用类型嵌入替换位置编码，生成上下文化嵌入{h'i}，再通过PMA聚合为全局上下文c。解码器使用双重注意力生成正则表达式。步骤3-递归分解：调用RECURSIVESYNTHESIZE(P, N, prevType)函数。如果|P|=1，返回SYNTHESIZEFROMSINGLETON直接转义字符串。否则ROUTER预测策略a∈{Segment, Partition, Synthesize}。如果选择Segment且prevType≠SEG（防止连续相同策略），SEGMENTER返回(P1,...,Pk)，每个子集递归合成后返回R1·R2·...·Rk。如果选择Partition且prevType≠PART，PARTITIONER返回{P1,...,Pm}，如果所有子集都是单元素则调用启发式回退机制，否则递归合成后返回R1|R2|...|Rm。如果都不适用，调用SYNTHESIZEWITHFALLBACK先用基础合成器，失败则遍历预定义的常见模式表（优先级：\d, [a-z], [A-Z], [a-zA-Z], [0-9a-fA-F], \w, \s, \D, \W, \S, .）配合量词+和*找到第一个一致的模式。步骤4-最终验证：检查合成正则表达式R是否与(P,N)一致，不一致则返回FAILURE。

技术新颖性

技术新颖性分析：首先，本文是首个在正则表达式合成中证明理论复杂度下限（NP难）的工作，这为学习式方法提供了坚实的理论基础。其次，层次化集合编码器的双层PMA设计（字符级PMA生成hi，字符串级PMA聚合为c）是创新性的，它通过结构化而非暴力扩展参数量实现排列不变性，10M参数匹配300M基线的性能。第三，递归分治框架中的三个模块各司其职：ROUTER基于全局上下文而非细节做策略决策，避免信息过载；PARTITIONER使用有序编码保留簇间关系，同时用指针网络动态确定最优簇数而非固定k；SEGMENTER处理所有示例的联合编码而非独立处理，确保分割一致性。第四，启发式回退机制的优先级设计（从具体到通用：\d→[a-z]→.）保证了最小化语言原则，避免过度泛化。最后，框架的合成器无关性使其可以赋能任何现有合成器，提升的+29.33%成功率可以无缝迁移。

The architecture of SET2REGEX.
Figure 1: The architecture of SET2REGEX.
The overall workflow of the RESYN framework.
Figure A1: The overall workflow of the RESYN framework.
A running example of the RESYN framework process.
Figure A2: A running example of the RESYN framework process.

实验结果

实验结果包含四个核心发现：(1) RESYN框架显著提升神经合成器性能。在RegExLib数据集上，SET2REGEX单独成功率为38.93%，加入RESYN后提升至68.26%（+29.33%绝对提升）；Semantic Accuracy从30.99%提升至41.61%。PRAX单独成功率为42.24%，加入RESYN后提升至67.29%（+25.05%绝对提升）。(2) 递归分解对复杂正则表达式至关重要。如图3所示，当AST深度≤3时，递归和非递归方法性能相近；但深度≥4时，非递归方法（FOREST, SPLITREGEX）性能急剧下降，而RESYN在深度6+仍保持68.26%的高成功率。这证实了刚性启发式无法处理嵌套结构。(3) SET2REGEX的参数效率显著。SET2REGEX（10M）在StructuredRegex上成功率90.12%，超过PRAX（300M）的85.03%；在RegExLib上38.93% vs 42.24%差距微小。这证明层次化集合编码器通过消除虚假顺序学习有效利用了参数。(4) 与大规模推理模型竞争。使用beam search（k=500）时，SET2REGEX+RESYN（29.6M参数）在StructuredRegex上成功率100.00%，Semantic Accuracy 89.52%，超过GPT-5的96.71%/60.78%；在Snort上90.62%/63.64% vs GPT-5的85.23%/54.83%；在RegExLib上85.33%/50.29% vs GPT-5的90.07%/48.86%。这说明专用架构的归纳偏置在特定任务上比通用推理更有效。

Comparison of structural complexity.
Table 1: Comparison of structural complexity.
Comprehensive comparison of synthesis methods across benchmarks.
Table 2: Comprehensive comparison of synthesis methods across benchmarks.
Comparison between GPT-5 and RESYN using beam search decoding (k = 500).
Table 3: Comparison between GPT-5 and RESYN using beam search decoding (k = 500).
Ablation study on the RegExLib benchmark quantifying the impact of recursive modules.
Table 4: Ablation study on the RegExLib benchmark quantifying the impact of recursive modules.
Abstract Syntax Tree (AST) node types used in regex canonicalization.
Table A1: Abstract Syntax Tree (AST) node types used in regex canonicalization.
Detailed AST optimization rules for regex canonicalization.
Table A2: Detailed AST optimization rules for regex canonicalization.
Prioritized list of base patterns used in the fallback mechanism.
Table A3: Prioritized list of base patterns used in the fallback mechanism.
Comprehensive Dataset Comparison: Train, Validation, and Test Benchmarks breakdown.
Table A4: Comprehensive Dataset Comparison: Train, Validation, and Test Benchmarks breakdown.
Performance comparison across regex AST depth.
Figure 3: Performance comparison across regex AST depth.
查看结构化数据
任务指标本文基线提升
正则表达式合成（RegExLib） Synthesis Success Rate 68.26% (SET2REGEX + RESYN) 42.24% (PRAX 单独), 49.03% (SET2REGEX + FOREST) +26.23% vs PRAX, +19.23% vs FOREST
正则表达式合成（RegExLib） Semantic Accuracy 41.61% (SET2REGEX + RESYN) 33.68% (PRAX 单独), 35.62% (SET2REGEX + FOREST) +7.93% vs PRAX, +5.99% vs FOREST
正则表达式合成（RegExLib） MCC (Matthews Correlation Coefficient) 58.97 (SET2REGEX + RESYN) 39.71 (PRAX 单独), 44.92 (SET2REGEX + FOREST) +19.26 vs PRAX, +14.05 vs FOREST
正则表达式合成（StructuredRegex） Synthesis Success Rate 97.60% (SET2REGEX + RESYN) 85.03% (PRAX 单独) +12.57%
正则表达式合成（Snort） Synthesis Success Rate 79.55% (SET2REGEX + RESYN) 67.05% (PRAX 单独) +12.50%

局限与改进

局限性分析包含作者承认的和观察到的：作者承认当前评估指标存在缺陷。MCC可以惩罚结构正确的模型，因为反例缺乏结构边界情况，允许格式错误的正则表达式获得高分。例如在案例研究中，RESYN正确推导出(I{2,10}|V{2,10})[A-Z]{3,4}，但由于轻微的数字范围过拟合MCC为81.65；而SEGMENTER only折叠了Union，过度泛化为错误的正则表达式，反而达到MCC 90.45。这是因为基于编辑距离的反例生成（插入/删除/替换）无法捕捉结构边界。作者还提到由于计算成本，在巨大数据集上使用Rational Speech Act（RSA）等高级技术生成语义难例是不可行的。观察到的局限性：(1) 训练-评估数据的结构性差异。表A4显示训练集中Union操作仅占2.71%，但RegExLib测试集中占16.95%，这可能导致PARTITIONER训练不足。(2) 启发式回退机制虽然有效，但仅限于简单模式（11个基础字符类配合2种量词共22种组合），对于复杂模式如嵌套量词或转义序列无能为力。(3) 递归深度没有显式限制，可能对极端深度的正则表达式导致堆栈溢出。(4) Oracle变体的性能（RegExLib上82.53%成功率）表明仍有改进空间，ROUTER的策略预测与最优决策存在差距。

独立分析的弱点

独立分析的弱点和改进方向：弱点1-PARTITIONER训练数据不足。训练集中Union仅占2.71%，而RegExLib测试集中占16.95%，这种分布不匹配可能导致PARTITIONER在真实场景中表现不佳。改进方向：在数据增强阶段有意过采样Union操作的正则表达式，或者在训练时使用类别加权损失（如NLL损失中的wc∝1/Nc）。弱点2-启发式回退机制能力有限。当前回退仅支持11种基础模式，对于复杂的正则表达式如(a|b){2,5}或(?<=prefix)pattern等无能为力。改进方向：扩展回退模式表，增加常见的组合模式（如\d{2,4}、[A-Z]\w+等）或使用小型神经模型作为回退而非固定列表。弱点3-评估指标存在缺陷。基于编辑距离生成的反例无法捕捉结构语义，导致MCC误导性。改进方向：实施语义硬负样本挖掘（semantic hard-negative mining），使用更复杂的扰动策略如重排子模式、交换操作符优先级等生成结构性反例。弱点4-递归终止条件不完善。当前算法在连续应用相同分解策略时停止，但没有考虑子问题复杂度阈值。改进方向：添加基于示例集大小、字符串长度方差等启发式的终止条件，防止过度分解。弱点5-可解释性不足。虽然ROUTER的决策是可学习的，但难以解释为何选择某个策略。改进方向：添加注意力可视化或决策路径解释工具，帮助用户理解分解逻辑。

未来方向

未来研究方向：作者提出的方向：(1) 探索语义硬负样本挖掘技术，改进评估指标，解决MCC误导性问题。(2) 将分治方法论扩展到正则表达式以外的程序合成任务，特别是当目标程序具有递归结构时（如树变换、串处理程序）。基于成果可延伸的方向：(3) 将RESYN框架应用于其他归纳编程任务，如SQL查询合成、代码补全、API调用序列生成等，这些任务也具有组合性和结构嵌套特性。(4) 研究多模态PBE，将自然语言描述与输入输出示例结合，利用类似Chen et al. (2023)的方法但用RESYN的递归分解替代草图生成。(5) 探索主动学习框架，让系统主动请求最有区分性的示例来解决欠约束问题，借鉴Rational Speech Act（RSA）理论但采用更高效的实现。(6) 将RESYN与符号推理结合，例如在叶子节点使用约束求解器而非神经合成器，提高精确性。(7) 研究跨领域迁移学习，将在一个领域（如URL模式）学到的分解策略迁移到新领域（如文件路径）。

复现评估

复现评估：开源情况良好，完整源代码、数据集和预训练模型检查点已公开在https://github.com/mrseongminkim/ReSyn。数据集构建过程详细（附录G），包含过滤标准（长度≤110字符、Union分支≤10）、训练/验证分割（9:1比例，AST签名去重）、正例生成（IntXeger库，每regex最多10例，60秒超时）、反例生成（基于编辑距离的变异）、子串扩展（递归分割，仅顶层Concat/Union）和去冗余（AST签名过滤）。三个评估基准：StructuredRegex（334实例，合成）、Snort（352实例，真实）、RegExLib（1752实例，真实）。算力需求：服务器配备4张NVIDIA RTX A6000 GPU，训练配置：隐藏层维度256，8个注意力头，AdamW优化器，批大小64，学习率5×10^-4，线性预热1000步+余弦退火，梯度裁剪1.0，最多100轮，早停耐心10轮。复现难度：中等。虽然论文提供了详细超参数和算法伪代码（Algorithm 1），但一些实现细节（如具体的优化规则表、匿名化Token范围、回退模式优先级）在附录中需要仔细阅读。此外，数据集构建涉及正则表达式解析、AST操作、示例生成等多个步骤，完整复现可能需要数天时间。但作者提供的预训练模型检查点降低了直接使用RESYN的门槛。

论文图表

Structural Complexity Comparison across Benchmarks.
Figure 2: Structural Complexity Comparison across Benchmarks.

Figure 2包含两个子图：顶部使用堆叠柱状图展示三个基准测试（StructuredRegex、Snort、RegExLib）的顶层操作符分布（Concat、Union、Repetition、Character Class）。StructuredRegex和Snort主要由Concatenation主导（99.10%和98.01%），而RegExLib表现出多样性（74.83% Concat, 16.95% Union, 6.45% Repetition, 1.77% Character Class）。底部使用热力图/渐变条展示AST深度分布，颜色越深表示深度越大。RegExLib包含显著比例的高复杂实例（Depth≥5），而其他基准集中在浅层区域（Depth≤4）。

这张图对理解论文动机至关重要，它量化地展示了真实世界正则表达式与现有基准之间的结构性鸿沟，解释了为何现有模型在RegExLib上表现不佳。Union操作符和深度的分布差异直接证明了作者批评的"过度简化基准测试"问题。