リテラル、正と負の文字クラス、順序付けられた代替、貪欲な量指定子?、*、 をサポートする正規表現言語があるとし+ます。(これは基本的に、後方参照、ルックアラウンド アサーション、または他のいくつかの凝ったビットのない PCRE のサブセットです。) 非貪欲な量指定子??、*?、およびを追加すると+?、この形式主義の表現力が向上しますか?
別の言い方をすれば、貪欲でない量指定子を含むパターン S が与えられた場合、そのパターンを、貪欲でない量指定子を含まない同等のパターン T に書き換えることができますか?
この質問が文献で検討されている場合は、誰でも提供できる参考文献をいただければ幸いです。拡張正規表現形式の表現力に関する理論的な研究はほとんど見つけることができませんでした (後方参照がどのように通常の言語から文脈自由文法に移行するかについての通常の事柄を超えて)。
「正規表現」と言うときは、いくつかの手法を指しています。これは、基礎となる理論の問題だけではありません。「この文字列は与えられた正規表現と一致しますか?」という質問を考えてみましょう。このような質問の場合、「貪欲」という概念は単なる実装の詳細です。一般的な (しかし非効率的な) バックトラッキング実装の 1 つを使用している場合、これはパフォーマンスに影響を与える可能性がありますが、出力には影響しません。同様に、「この文字列には一致が含まれていますか?」という質問も同様です。貪欲な量指定子と非貪欲な量指定子の影響を受けません。この最初のタイプの正規表現は、set-membership の抽象的な概念に関係しています。つまり、一致する文字列の言語を定義します。
では、貪欲でない量指定子が存在するのはなぜでしょうか? 正規表現は単に照合に使用されるわけではありません。一般的な実装では、一致する場所と、正規表現のどの部分が出力のどの部分と一致するかを特定できます。これを行うことで、ユーザーは複雑な実装に依存することになりますが、これは些細なことではありません。この 2 番目のタイプの正規表現は、他の方法ではチューリング完全な言語のコンテキストで、数ビットのテキストをより実用的な表現にすることに関係しています。
一般に、正規表現の形式主義の強さについて話すときは、最初の世界について話しています。つまり、コンピューターが単純な「はい」または「いいえ」で答える世界です。仕様が明確なので話しやすいです。貪欲な量指定子と貪欲でない量指定子について話すとき、それは第二の世界について話している - 実際にはたくさん使われているが、実際の問題を解決するための計画をあまり立てずに拡張された仕様であり、後方互換性のおかげで標準となっている。 . この第 2 の世界では、まったく異なる問題が解決されています。ここで「表現力」が何を意味するのかさえ、私には明確ではありません。確かに、貪欲でないことは実用的です。それがポイントのようなものです...
貪欲でない量指定子は、最初のタイプの表現力に対しては何もしませんが、2 番目のタイプの表現力に対しては何もしませんが、「表現力」がここで何を意味するのかははっきりしていません。