現代の正規表現の方言は正規ではないのでしょうか?

Question

ここで、最新の正規表現が正規言語で表現できる範囲を超えているというコメントをいくつか見ました。どうしてそうなるのでしょうか？

最新の正規表現のどのような機能が正規ではないのでしょうか?例が役立つでしょう。

Answer 1

心に来る最初の事は後方参照されます：

(\w*)\s\1

例えば（空白文字と以前に一致し、同じグループに続く単語の文字のグループに一致）：hello helloの一致を、hello worldはしていません。

。

この構築物は、通常ではありません（例：正規文法にによって生成することができません） 。

<時間>

定期的ではないPerl互換正規表現（PCRE）でサポートされているもう一つの特徴は、再帰的なパターンです。

\((a*|(?R))*\)

これはウィキペディア）

Answer 2

いくつかの例:

• 正規表現はグループ化をサポートします。例えば。Rubyでは: /my (group)/.match("my group")[1] 「グループ」が出力されます。何かをグループに保存するには外部ストレージが必要ですが、有限オートマトンにはそれがありません。
• 多くの言語、例:C#、サポートキャプチャ、つまり各一致がスタック上にキャプチャされること (パターンなど) (?<MYGROUP>.)* 「」の複数のキャプチャを実行できます。同じグループで。
• グループ化は、上記のユーザー NullUserException で指摘されているように、後方参照に使用されます。逆参照には、プッシュダウン オートマトンの機能を備えた 1 つ以上の外部スタックが必要です (スタックに何かをプッシュし、後でそれをピークまたはポップできる必要があります)。
• 一部のエンジンには、外部スタックを個別にプッシュおよびポップし、スタックが空かどうかを確認する機能があります。.NETでは、実際には (?<MYGROUP>test) スタックをプッシュしますが、 (?<-MYGROUP>) スタックをポップします。
• .NET エンジンなどの一部のエンジンにはバランスの取れたグループ化の概念があり、外部スタックのプッシュとポップの両方を同時に行うことができます。バランスのとれたグループ化構文は次のとおりです。 (?<FIRSTGROUP-LASTGROUP>) これにより、LASTGROUP がポップされ、FIRSTGROUP スタック上の LASTGROUP インデックス以降のキャプチャがプッシュされます。これは実際に、無限にネストされた構造を照合するために使用できますが、これは明らかに有限オートマトンの力を超えています。

おそらく他にも良い例が存在するでしょう :-) 正規表現とバランスのとれたグループ化と組み合わせた外部スタックの実装の詳細、つまり有限オートマトンよりも高次のオートマトンにさらに興味がある場合は、私はかつてこれについて 2 つの短い記事を書きました (http:/ /www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx および http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

とにかく、有限かどうかは別として、この追加要素が通常の言語にもたらす力は素晴らしいと信じています :-)

Br.モルテン

Answer 3

は、決定論的または非決定性有限オートマトンを正規表現で記述されている普通の言語を認識します。正規表現の定義は単純です。 のS のは、アルファベットとします。その後、空集合、空の文字列、およびのS ののすべての要素は、（のS のオーバー）正規表現です。 のuはと V のこと正規表現をしてみましょう。その後、労働組合（のU の| V の）、連結（のUV の）、および閉鎖（のU の*）の< em>のU と V のはのS のオーバー正規表現です。この定義は簡単に正規言語に拡張されます。他の式は、正規表現ではありません。指摘したように、いくつかのバック参照が一例です。正規言語と表現上のWikipediaのページが良いの参照です。

特定の型のないオートマトンがそれらを認識するように構築することはできないので、

は本質的には、特定の「正規表現は、」定期的ではありません。例えば、言語

{^ I B ^ I I <= 0}

は、通常ではありません。受諾オートマトンは無限に多くの州が必要となるので、これはですが、正規言語を受け入れるオートマトンは、状態の有限数を持っている必要があります。