22

PCRE には再帰パターンと呼ばれる機能があり、ネストされたサブグループの照合に使用できます。たとえば、「文法」について考えてみましょう。

Q -> \w | '[' A ';' Q* ','? Q* ']' | '<' A '>'
A -> (Q | ',')*
// to match ^A$.

パターンを使用してPCREで実行できます

^((?:,|(\w|\[(?1);(?2)*,?(?2)*\]|<(?1)>))*)$

(テストケースの例: http://www.ideone.com/L4lHE )

一致する必要があります:

abcdefg abc,def,ghi abc,,,def ,,,,,, [abc;] [a,bc;] sss[abc;d] as[abc;d,e] [abc;d,e][fgh;j,k] <abc> [<a>b;<c,d>,<e,f>] <a,b,c> <a,bb,c> <,,,> <> <><> <>,<> a<<<<>>><a>> <<<<<>>>><><<<>>>> <z>[a;b] <z[a;b]> [[;];] [,;,] [;[;]] [<[;]>;<[;][;,<[;,]>]>]

一致しない:

<a bc> <abc<de> [a<b;c>;d,e] [a] <<<<<>>>><><<<>>>>> <<<<<>>>><><<<>>> [abc;def;] [[;],] [;,,] [abc;d,e,f] [<[;]>;<[;][;,<[;,]>]]> <z[a;b>]

.NET には再帰パターンはありません。代わりに、単純なネストされたパターンを照合するためのスタックベースの操作用のバランシング グループを提供します。

上記の PCRE パターンを .NET Regex スタイルに変換することは可能ですか?

（はい、これには正規表現を使用しないほうがよいことはわかっています。これは単なる理論上の質問です。）

参考文献

4

2 に答える 2

13

再帰パターンに代わる .Net はスタックです。ここでの課題は、スタックに関する文法を表現する必要があることです。
これを行う1つの方法を次に示します。

文法のわずかに異なる表記法

  • まず、文法規則が必要です (問題のAandQのように)。
  • 1 つのスタックがあります。スタックにはルールのみを含めることができます。
  • 各ステップで、スタックから現在の状態をポップし、照合する必要があるものを照合し、さらにルールをスタックにプッシュします。状態が終了したら、何もプッシュせずに前の状態に戻ります。

この表記法は、ルールをスタックにプッシュするCFGとプッシュダウン オートマトンの間のどこかにあります。

例：

a n b nという簡単な例から始めましょう。この言語の通常の文法は次のとおりです。

S -> aSb | ε

表記に合うように言い換えることができます。

# Start with <push S>
<pop S> -> "a" <push B> <push S> | ε
<pop B> -> "b"

言葉で：

  • スタックから始めSます。
  • スタックからポップSすると、次のいずれかを実行できます。
    • 何も一致しないか、または...
    • 「a」に一致しますが、状態Bをスタックにプッシュする必要があります。これは、「b」に一致する約束です。次にS、必要に応じて "a" を一致させ続けることができるように、プッシュも行います。
  • 十分な数の "a" を一致させたらB、スタックから s をポップし始め、それぞれに "b" を一致させます。
  • これが完了すると、偶数の「a」と「b」が一致しました。

または、より大まかに：

S の場合は、"a" に一致し、B を押してから S を押すか、何も一致しません。
ケース B の場合は、"b" に一致します。

いずれの場合も、現在の状態をスタックからポップします。

パターンを .Net 正規表現で記述する

何らかの形でさまざまな状態を表す必要があります。'1' '2' '3'または'a' 'b' 'c'を選択することはできません。これらは入力文字列で使用できない可能性があるためです。文字列に存在するもののみを照合できます。
1 つのオプションは、州に番号を付けることです (上記の例でSは、州番号 0、B州 1 です)。
状態 S の場合文字をスタックにプッシュできます。便宜上、文字列の先頭から最初の文字をプッシュします。繰り返しますが、これらの文字が何であるかは気にしません。何人いるかだけです。

プッシュ状態

.Net では、文字列の最初の 5 文字をスタックにプッシュする場合、次のように記述できます。

(?<=(?=(?<StateId>.{5}))\A.*)

これは少し複雑です:

  • (?<=…\A.*)は、文字列の先頭までずっと続く後読みです。
  • 開始時には、次のような見通しがあります(?=…)。これは、現在の位置を超えて一致できるようにするために行われます。位置2にいる場合、前に 5 文字はありません。だから私たちは振り返り、楽しみにしています。
  • (?<StateId>.{5})5 文字をスタックにプッシュし、ある時点で状態 5 に一致させる必要があることを示します。

ポップ状態

私たちの表記法によれば、常にスタックから最上位の状態をポップします。それは簡単です: (?<-StateId>).
しかし、それを行う前に、それがどのような状態であったか、またはキャプチャされた文字数を知りたいと考えています。より具体的には、switch/caseブロックのように、各状態を明示的にチェックする必要があります。したがって、スタックが現在状態 5 を保持しているかどうかを確認するには、次のようにします。

(?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
  • 繰り返し(?<=…\A.*)ますが、最初からずっと行きます。
  • (?=.{5}…)これで5文字進みます...
  • そして、別の後読みを使用(?<=\A\k<StateId>)して、スタックに実際に 5 文字あることを確認します。

これには明らかな欠点があります。文字列が短すぎると、大きな状態の数を表すことができません。この問題には解決策があります:

  • とにかく、言語の短い単語の数は最終的なものなので、手動で追加できます。
  • 単一のスタックよりも複雑なものを使用します。それぞれが 0 または 1 文字の複数のスタックを使用して、効果的に状態のビットを表すことができます (最後に例があります)。

結果

a n b nのパターンは次のようになります。

\A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State B, Index = 1
                (?<=(?=(?<StateId>.{1}))\A.*)
                a
                # Push State A, Index = 0
                (?<StateId>)
                |

            )
        )
        |
        (?:
            # When In State B, Index = 1
            (?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            b
        )
        |\Z
    ){2}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))

Regex Storm での作業例

ノート：

  • (?:(?:…){2})+状態の量指定子は、(状態数)×(入力長) であることに注意してください。の代替も追加しました\Z。それには立ち入りませんが、これは .Net エンジンの煩わしい最適化の回避策です。
  • 同じことを次のように書くことができます(?<A>a)+(?<-A>b)+(?(A)(?!))- これは単なる演習です。

質問に答えるには

質問の文法は次のように書き換えることができます。

# Start with <push A>
<pop A> -> <push A> ( @"," | <push Q> ) | ε
<pop Q> -> \w
           | "<" <push Q2Close> <push A>
           | "[" <push Q1Close> <push QStar> <push Q1Comma> <push QStar> <push Q1Semicolon> <push A>
<pop Q2Close> -> ">"
<pop QStar> -> <push QStar> <push Q> | ε 
<pop Q1Comma> -> ","?
<pop Q1Semicolon> -> ";"
<pop Q1Close> -> "]"

パターン：

\A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State A, Index = 0
                (?<StateId>)
                (?:
                    ,
                    |
                    # Push State Q, Index = 1
                    (?<=(?=(?<StateId>.{1}))\A.*)
                )
                |

            )
        )
        |
        (?:
            # When In State Q, Index = 1
            (?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                \w
                |
                <
                # Push State Q2Close, Index = 2
                (?<=(?=(?<StateId>.{2}))\A.*)
                # Push State A, Index = 0
                (?<StateId>)
                |
                \[
                # Push State Q1Close, Index = 6
                (?<=(?=(?<StateId>.{6}))\A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q1Comma, Index = 4
                (?<=(?=(?<StateId>.{4}))\A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q1Semicolon, Index = 5
                (?<=(?=(?<StateId>.{5}))\A.*)
                # Push State A, Index = 0
                (?<StateId>)
            )
        )
        |
        (?:
            # When In State Q2Close, Index = 2
            (?<=(?=.{2}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            >
        )
        |
        (?:
            # When In State QStar, Index = 3
            (?<=(?=.{3}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q, Index = 1
                (?<=(?=(?<StateId>.{1}))\A.*)
                |

            )
        )
        |
        (?:
            # When In State Q1Comma, Index = 4
            (?<=(?=.{4}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            ,?
        )
        |
        (?:
            # When In State Q1Semicolon, Index = 5
            (?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            ;
        )
        |
        (?:
            # When In State Q1Close, Index = 6
            (?<=(?=.{6}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            \]
        )
        |\Z
    ){7}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))

残念ながら、URL に収めるには長すぎるため、オンラインの例はありません。

1 文字または 0 文字の「バイナリ」スタックを使用すると、次のようになります: https://gist.github.com/kobi/8012361

以下は、すべてのテストに合格したパターンのスクリーンショットです: http://i.stack.imgur.com/IW2xr.png

ボーナス

A.Net エンジンは、バランスを取るだけでなく、またはの各インスタンスをキャプチャすることもできますQ。これには、パターンhttps://gist.github.com/kobi/8156968を少し変更する必要があります。
groups と をパターンに追加したことに注意してくださいStart。AただしQ、それらはフローの影響を受けず、純粋にキャプチャに使用されます。

結果: たとえば、 string の場合、次の s"[<a>b;<c,d>,<e,f>]"を取得できます。Capture

Group A
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-4) <a>b
    (2-2) a
    (7-9) c,d
    (13-15) e,f
Group Q
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-3) <a>
    (2-2) a
    (4-4) b
    (6-10) <c,d>
    (7-7) c
    (9-9) d
    (12-16) <e,f>
    (13-13) e
    (15-15) f

未解決の質問

  • すべての文法を状態スタック表記に変換できますか?
  • (状態数)×(入力長) のステップ数は、すべての単語に一致するのに十分ですか? 他にどのような式が機能しますか?

ソースコード

これらのパターンとすべてのテスト ケースを生成するために使用されるコードは、https://github.com/kobi/RecreationalRegexにあります。

于 2013-12-17T21:04:24.193 に答える
10

答えは（おそらく）イエスです。

この手法は再帰呼び出しよりもはるかに複雑です(?1)が、結果は文法の規則とほぼ 1 対 1 で一致します。スクリプト化されていることが簡単にわかるような方法で作業しました。基本的に、ブロックごとにマッチし、スタックを使用して現在位置を追跡します。これはほとんど機能するソリューションです。

^(?:
    (\w(?<Q>)) # Q1
    |
    (<(?<Angle>))  #Q2 - start <
    |
    (\>(?<-Angle>)(?<-A>)?(?<Q>))  #Q2 - end >, match Q
    |
    (\[(?<Block>))  # Q3 start - [
    |
    (;(?<Semi-Block>)(?<-A>)?)  #Q3 - ; after [
    |
    (\](?<-Semi>)(?<-Q>)*(?<Q>))  #Q3 ] after ;, match Q
    |
    ((,|(?<-Q>))*(?<A>))   #Match an A group
)*$
# Post Conditions
(?(Angle)(?!))
(?(Block)(?!))
(?(Semi)(?!))

でコンマを許可する部分が欠落してQ->[A;Q*,?Q*]おり、何らかの理由で を許可するため、 and[A;A]と一致[;,,]し[abc;d,e,f]ます。残りの文字列は、テスト ケースと同じように一致します。
もう 1 つのマイナーな点は、空のキャプチャでスタックにプッシュする際の問題です。そうではありません。AØ を受け入れるので、(?<-A>)?キャプチャされたかどうかを確認するために使用する必要がありました。

正規表現全体は次のようになりますが、ここでもバグがあるため役に立ちません。

なぜ機能しないのですか？

スタックを同期する方法はありません。 と をプッシュする(?<A>)と(?<B>)、それらを任意の順序でポップできます。そのため、このパターンは<z[a;b>]...<z[a;b]>すべてに対して 1 つのスタックが必要です。
これは単純なケースでは解決できますが、ここではもっと複雑な問題があります。"<" や "[" だけでなく、全体Qまたはです。A

于 2010-07-28T20:08:03.373 に答える