轻量正则表达式优化

Question

我有一个正则表达式，它是计算机程序的输出。它具有

(((2)|(9)))*

人类无疑会写成的

[29]*

东西，所以我想要一个可以进行简单转换的程序，使正则表达式更具可读性。到目前为止，我一直在使用一个快速脚本

$r =~ s/\(([0-9])\)/$1/g;
$r =~ s/\(([0-9])\|([0-9])\)/[$1$2]/g;
$r =~ s/\(([0-9]|\[[0-9]+\])\)\*/$1*/g;
$r =~ s/\((\[[0-9]+\]\*)\)/$1/g;
$r =~ s/\|\(([^()]+)\)\|/|$1|/g;

来缩短长度，但结果仍然包含类似的片段

(ba*b)|ba*c|ca*b|ca*c

，应该简化为

[bc]a*[bc]

我搜索 CPAN 并找到 Regexp::List、Regexp::Assemble 和 Regexp::Optimizer。前两个不适用，第三个有问题。首先，它不会通过测试，因此除非我在 cpan 中强制安装 Regexp::Optimizer，否则我无法使用它。其次，即使我这样做了，它的表达也会让人窒息。

---

注意：除了 [regex] 之外，我还标记了这个 [regular-language]，因为正则表达式仅使用连接、交替和 Kleene 星号，所以它实际上是正则表达式。

Answer 1

我觉得可能有一种方法可以做到这一点，将正则表达式转换为语法，将语法放入乔姆斯基范式，合并常见的非终结符，并使用一些比较启发式寻找模式。如果你不把它放在“真正的”CNF 中，你甚至可能会得到更简洁的答案......我会把 lambdas/epsilons 留在里面。

  ba*b|ba*c|ca*b|ca*c

  S -> bAb | bAc | cAb | cAc
  A -> aA | lambda

  S -> BAB | BAC | CAB | CAC
  A -> AA | a | lambda
  B -> b
  C -> c

  S -> DB | DC | EB | EC
  A -> AA | a | lambda
  B -> b
  C -> c
  D -> BA
  E -> CA

此时，也许您会发现一个识别

  S -> (D+E)(B+C)

回代的启发式方法，

  S -> (BA|CA)(b|c) -> (ba*|ca*)(b|c)

在子表达式上重复此操作，例如，

  S' -> bA' | cA'
  A' -> aA' | lambda

  S' -> B'A' | C'A'
  A' -> A'A' | a | lambda
  B' -> b
  C' -> c

现在认识到 S -> (B|C)(A)，我们可以得到

 S' -> (B'|C')(A') -> (b|c)(a*)

对于 Then 的最终解决方案

 S -> ((b|c)a*)(b|c)

，你可以只寻找多余的括号来删除（注意串联是关联的，这本质上会将事物优化为串联范式，只需删除所有括号即可不只包含 | 分隔的选项列表...所以上面的

  (b|c)a*(b|c)

技巧是启发式的，这可能无法完成所有可能的优化，我不知道它会如何。不过，这可能是值得考虑的事情。