轻量级正则表达式优化

发布时间：2020-12-13 21:53:58 所属栏目：百科来源：网络整理

导读：我有一个正则表达式,它是计算机程序的输出.它有类似的东西 (((2)|(9)))* 人类毫无疑问会把它写成 [29]* 所以我想要一个程序可以进行简单的转换,使正则表达式更具可读性.到目前为止,我一直在使用快速脚本 $r =~ s/(([0-9]))/$1/g;$r =~ s/(([0-9])|([0-9]

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

(((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]之外,我还标记了这个[常规语言]因为正则表达式只使用连接,交替和Kleene星,所以它实际上是常规的.

我觉得可能有办法通过将正则表达式转换为语法,将语法放入Chomsky Normal Form,合并常见的非终结符,并使用一些比较heurstic来寻找模式.如果你不把它放在“真正的”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)

Backsubstituting,

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)

然后,您可以只查找要删除的多余括号(注意连接是关联的,这将基本上将事物优化为连接正常形式,只需删除所有不包含| -delimited选项列表的括号… so以上变为

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

诀窍在于启发式,这可能无法完成所有可能的优化.我不知道它会如何表现.不过,它可能需要考虑.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!