6

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

(((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。前两个不适用，第三个有问题。首先，它不会通过测试，所以除非我force install Regexp::Optimizer在 cpan 中，否则我不能使用它。其次，即使我这样做了，它也会让表情窒息。

注意：除了 [regex] 之外，我还标记了此 [regular-language]，因为 regexp 仅使用串联、交替和 Kleene 星号，因此它实际上是常规的。

4

1 回答 1

3

我觉得可能有一种方法可以通过将正则表达式转换为语法，将语法转换为乔姆斯基范式，合并常见的非终结符，并使用一些比较启发式寻找模式来做到这一点。如果你不把它放在“真正的”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*)

对于最终解决方案

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

然后，您可以只查找要删除的多余括号（注意连接是关联的，这将从本质上将事物优化为连接正常形式，只需删除所有不包含仅由 | 分隔的选项列表的括号......所以以上变成

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

诀窍是提出启发式方法，这可能无法完成所有可能的优化。我不知道它会如何表现。不过，这可能是需要考虑的事情。

于 2011-08-19T19:37:35.223 回答