誰でも私のために任意の正規表現を同等のCFG規則セットに変換できるアルゴリズムを紹介できますか？任意の正規表現から文脈自由文法を生成するアルゴリズム
は、私は、次のような基本的なものに取り組むために方法を知っている（| 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)
しかし、私は特にすることができ、より複雑な式で適切なアルゴリズムにそれを正式いくつかの問題を抱えています多くのネストされた操作。
あなただけの理論的な観点から正規表現について話している場合は、これらの3つの構築物があります。
ab # concatenation
a|b # alternation
a* # repetition or Kleene closure
あなたがちょうど何ができるか：
S -> (fullRegex)(x)*をfullRegexに設定してルールX -> x XとX -> εを作成した後、(x)*を0123に置き換えます。交代毎(a|b|c)ためY -> a、Y -> bとY -> cを作成し、その後、Yで(a|b|c)を置き換えるだけで（すべてx,a、bとcはまだ複雑な正規表現できることに注意してください）再帰的にこれを繰り返します。もちろん、すべてのステップで一意の識別子を使用する必要があります。
これで十分です。これは確かに最もエレガントで効率的な文法を提供しませんが、これは正規化のためのものです（これを実行するには別のステップで行う必要があり、well-defined stepsがあります）。
一例：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
あなたはアルゴリズムの全体のアウトラインはお問い合わせ時に、私はあなたが冗談を願っています。あなたが気づいたように、それは多くの仕事になるでしょう。特定の問題に関する特定の質問がある場合は、お気軽にお問い合わせください。しかし、実際にコードを設計するよう求めないでください。 – Jasper
cfgを 'S - > a Sにするべきではありません。 S→b S; S→イプシロン？あなたが提供するcfgが一致する唯一の文字列は、それが受け入れる他の文字列が有限でないためです。 – Wug
これは本当にどの正規表現構文要素に許可したいのかによっても変わります。理論的に正規表現のみ？ほとんどのエンジンで使用されている拡張された意味での正規表現ですか？ –