27

ここで、SO の人々は時々、「X は正規表現ではないため、X を正規表現で解析することはできません」のようなことを言います。しかし、私の理解では、最新の正規表現エンジンは、チョムスキーの意味で正規言語以上のものと一致させることができます。私の質問:

サポートする正規表現エンジンが与えられた場合

  • 後方参照
  • 無制限の幅のルックアラウンド アサーション
  • のような再帰(?R)

どのような言語を解析できますか? 文脈自由言語を解析できますか?そうでない場合、反例は何でしょうか?

(正確には、「解析」とは、「文法 X によって生成されたすべての文字列を受け入れ、他のすべての文字列を拒否する単一の正規表現を構築する」ことを意味します)。

追加: 私は、最新の正規表現エンジン (Perl、Net、Python 正規表現モジュール) が解析できないコンテキストフリー言語の例を見ることに特に興味があります。

4

3 に答える 3

19

私は最近、このトピックについてかなり長い記事を書きました：正規表現の真の力。

要約する：

  • 再帰的なサブパターン参照をサポートする正規表現は、すべての文脈自由言語に一致する可能性があります（例a^n b^n）。
  • ルックアラウンドアサーションとサブパターン参照を持つ正規表現は、少なくとも一部の状況依存言語（egwwおよびa^n b^n c^n）と一致する可能性があります。
  • アサーションの幅が無制限の場合（あなたが言うように）、すべての状況依存文法を一致させることができます。後読みに関する固定幅の制限はありませんが（同時にサブパターン参照をサポートしています）、正規表現のフレーバーはわかりません。
  • 後方参照のある正規表現はNP完全であるため、他のNP問題は、正規表現を使用して解決できます（多項式時間変換を適用した後）。

いくつかの例：

  • 文脈自由言語のマッチング{a^n b^n, n>0}：

    /^(a(?1)?b)$/
# or
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x

  • 状況依存言語のマッチング{a^n b^n c^n, n>0}：

    /^
    (?=(a(?-1)?b)c)
    a+(b(?-1)?c)
$/x
# or
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x
于 2012-07-08T11:06:51.507 に答える
9

最新の正規表現エンジンは、通常の言語セットよりも多くの言語セットを解析できます。つまり、4 つの古典的なチョムスキー集合のどれも、正規表現によって正確に認識されません。すべての正規言語は、正規表現によって明確に認識されます。正規表現で認識できない古典的な文脈自由言語がいくつかあります。たとえば、括弧のバランスがとれた言語a^n b^nなどです。ただし、正規表現wwは文脈依存の言語を解析できます。

実際、形式言語理論における正規表現は、正規表現とはわずかにしか関連していません。無制限の後方参照を持つ正規表現のマッチングは、最も一般的なケースでは NP 完全であるため、十分に強力な正規表現のすべてのパターン マッチング アルゴリズムは、少なくとも一般的なケースでは指数関数的です。ただし、ほとんどの場合、ほとんどの入力は非常に高速です。文脈自由言語の照合はせいぜい よりも高速であることが知られているn^3ため、正規表現には文脈自由ではない言語 ( などww) がいくつかありますが、すべての文脈自由言語を正規表現で解析できるわけではありません。タイプ 0 言語は一般に決定不可能であり、son 正規表現はそこに到達しません。

したがって、あまり決定的ではない結論として、正規表現は、すべての正規言語、および一部の文脈自由言語と文脈依存言語を含む広範な言語セットを解析できますが、これらのセットのいずれとも完全に等しいわけではありません。より正確な答えを見つけることができる言語の他のカテゴリや他の分類法がありますが、言語の階層の適切なサブセットとしてコンテキストフリー言語を含む分類法は、正規表現によって正確に認識される単一の言語を提供できません。ある部分で文脈自由言語と交差するだけであり、どちらも他方の適切なサブセットではありません。

于 2012-07-05T19:54:15.117 に答える
2

正規表現については、ラルフW.ファソルド、ジェフコナーリントンP.477による言語と言語学の紹介で読むことができます。

チョムスキー階層：

Type0> = Type1> = Type2> = Type3

計算言語学は主にタイプ2と3の文法を特徴としています

•タイプ3の文法：

–正規表現と有限状態オートマトン（別名、有限状態マシン）を含める

–この講演の残りの部分の焦点

•タイプ2の文法：

–一般的に自然言語パーサーに使用されます

–多くの言語理論で構文構造をモデル化するために使用されます（多くの場合、他のメカニズムによって補完されます）

–構文解析に関する次の講演で重要な役割を果たします。

相互関係リンクを持つMicrosoftDGML （Directed Graph Markup Language）のようなほとんどのXMLは、正規表現が役に立たないサンプルです。

そして、この3つの答えが役立つかもしれません：

1- does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions

2-正規表現-arent

3- where-do-most-regex-implements-fall-on-the-complexity-scale

于 2012-07-06T07:48:14.470 に答える