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 が見つかりました。最初の 2 つは適用されず、3 番目には問題があります。force install Regexp::Optimizerまず、テストに合格しないため、cpanを使用しない限り使用できません。第二に、私がそれをしても、表情が窒息します。

注: [regex] に加えて [regular-language] というタグを付けたのは、正規表現が連結、代替、および Kleene スターのみを使用しているためで、実際には規則的です。

4

1 に答える 1

3

正規表現を文法に変換し、その文法をチョムスキー標準形に変換し、一般的な非終端記号をマージし、比較ヒューリスティクスを使用してパターンを探すことで、これを行う方法があると思います。「実際の」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)

トリックはヒューリスティックを考え出すことであり、これは可能なすべての最適化を行うとは限りません。どのように実行されるかわかりません。それでも、それは考慮すべきことかもしれません。

于 2011-08-19T19:37:35.223 に答える