regex - 現代のプログラミング言語の「正規表現」は本当に「文脈依存文法」ですか?

Question

何年にもわたって、「正規表現」パターン マッチングはますます強力になり、疑問に思うところまで来ました。それは本当に単なる文脈依存文法マッチングなのでしょうか? 文脈自由文法マッチングのバリエーション/拡張ですか? それは今どこにあるのでしょうか?古い制限的な「正規表現」の代わりに、単にそれと呼んでみませんか?

Answer 1

特に、括弧をキャプチャするための後方参照により、正規表現は、通常の文脈自由文法または文脈依存文法よりも複雑になります。名前は単に歴史的に（多くの単語として）成長しました。ウィキペディアのこのセクションと、Perlの例を使用したこの説明も参照してください。

Answer 2

私の見立てでは：

• 通常の言語:
  • ステート マシンによって照合されます。照合する文法内の現在の「場所」を表すために使用できる変数は 1 つだけです: 再帰は実装できません
• 文脈自由言語:
  • スタック機でマッチング。文法における現在の「位置」は、1 つまたは別の形式のスタックによって表されます。以前に起こったことを「思い出す」ことができない
• 状況依存言語:
  • ほとんどのプログラミング言語
  • すべての最も人間的な言語

パーサーが既に遭遇したものと照合して、文脈依存文法のようなものを実現できる正規表現パーサーを知っています。

それでも、正規表現パーサーは、どんなに洗練されていても、規則の再帰的な適用を許可していません。これは、文脈自由文法の明確な要件です。

私の意見では、 regexという用語は、主にこれらの通常の文法 (星印と疑問符) を表現するために使用される構文を指します。

Answer 3

最新の正規表現の実装には、従来の正規表現の定義のルールを破る機能があります。

たとえば、Microsoft の .NET Balancing Group (?<name1-name2> … ) :

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

これは言語L ₀₁ = { ε , 01, 0011, 000111, … } と一致します。しかし、この言語はPumping Lemmaによると規則的ではありません。