Легкая оптимизация регулярных выражений

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. Первые два не применяются, а у третьего есть проблемы. Во-первых, он не пройдет свои тесты, поэтому я не могу использовать его, если я не force install Regexp::Optimizer в cpan. Во-вторых, даже когда я это сделаю, оно задыхается от выражения.

---

Примечание: я пометил этот [обычный язык] в дополнение к [регулярному выражению], потому что регулярное выражение использует только конкатенацию, чередование и звезду Клини, так что на самом деле оно является регулярным.

Answer 1

Я чувствую, что мог бы быть способ сделать это путем преобразования регулярного выражения в грамматику, помещения грамматики в нормальную форму Хомского, объединения общих нетерминалов и поиска шаблонов с использованием некоторого эвристического сравнения.Вы могли бы даже получить более краткие ответы, если не поместите его в «настоящий» CNF ... Я бы оставил лямбды / эпсилоны внутри.

  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)

Трюк с эвристикой,и это не может сделать все возможные оптимизации. Я не знаю, как это будет работать. Тем не менее, это может быть что-то, чтобы рассмотреть.