5

任意の正規表現を同等のCFGルールのセットに変換できるアルゴリズムの概要を教えてもらえますか？

（a | b）*などの基本的なものに取り組む方法を知っています。

S -> a A
S -> a B
S -> b A
S -> b B
A -> a A
A -> a B
A -> epsilon
B -> b A
B -> b B
B -> epsilon
S -> epsilon (end of string)

ただし、特に多くのネストされた操作を持つ可能性のあるより複雑な式では、適切なアルゴリズムに形式化するのに問題があります。

4

1 に答える 1

12

理論的な観点から正規表現について話しているだけの場合、次の3つの構成があります。

ab       # concatenation
a|b      # alternation
a*       # repetition or Kleene closure

次にできること：

  • ルールを作成するS -> (fullRegex)
  • ルールを作成し、(x)*で繰り返される用語ごとに、を置き換えます。fullRegexX -> x XX -> ε(x)*X
  • 交代ごとに(a|b|c)ルールY -> aを作成Y -> bしY -> c、次に(a|b|c)、Y

これを再帰的に繰り返すだけです（すべてx, a、bおよびcは複雑な正規表現である可能性があることに注意してください）。もちろん、すべてのステップで一意の識別子を使用する必要があることに注意してください。

これで十分です。これは確かに最もエレガントで効率的な文法を提供しませんが、それが正規化の目的です（そして、これは別のステップで実行する必要があり、これを実行するための明確なステップがあります）。

一例：a(b|cd*(e|f)*)*

S -> a(b|cd*(e|f)*)*

S -> a X1; X1 -> (b|cd*(e|f)*) X1; X1 -> ε

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> cd*(e|f)*

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> c X2 (e|f)*; X2 -> d X2; X2 -> ε

... and a few more of those steps, until you end up with:

S  -> a X1
X1 -> Y1 X1
X1 -> ε
Y1 -> b
Y1 -> c X2 X3
X2 -> d X2
X2 -> ε
X3 -> Y2 X3
X3 -> ε
Y2 -> e
Y2 -> f
于 2012-10-30T13:38:36.527 に答える