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

Question

「正規表現」のパターンマッチングは、文脈に敏感な文法マッチングというだけで、ますますパワフルになっています。それは文脈自由文法マッチングの変形/拡張ですか？それは今どこにあるのですか？古い、制限的な "正規表現"の代わりに、それを単に呼び出すのはなぜですか？

Answer 1

特に、カッコをキャプチャする後方参照は、正規表現を文脈自由文法や文脈依存文法よりも複雑にします。名前は単に歴史的に（多くの単語として）成長しています。 Wikipediaのthis sectionとPerlのexplanation with an exampleも参照してください。

Answer 2

私はそれを参照してください方法：

• 正規言語：
  • ステートマシンで一致しました。唯一の変数が一致する文法に現在 「位置」を表すために使用することができる：スタックマシンで一致
    • ：再帰は
  • 文脈自由言語を実装することができません。文法の現在の「場所」は、1つまたは別の形式のスタックで表されます。すべてのほとんどの人間の言語
私は定期の

知っています

• ほとんどのプログラミング言語
• ：

文脈依存言語の前に発生したものを "記憶" することはできませんパーサーがすでに遭遇したことと照合することを可能にする式パーサーnsitive文法。

ただし、洗練された正規表現パーサーは、文脈自由文法の明確な要件である規則の再帰的な適用を考慮していません。

用語正規表現は、私の意見では、主にそれらの正規文法（星と疑問符）を発現するために使用さ構文を指します。

Answer 3

最新の正規表現の実装には、classic regular expression definitionの規則を破る機能があります。例えばMicrosoft’s .NET Balancing Group(?<name1-name2> …)について

：

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

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