1

次のテストを実行する必要があります: 式に '{' が含まれている場合、別の '}' が見つかった場合にのみ式を受け入れます。有効な式は 'aaa{aaa}aaa'、'{aa}' 、'a{aa' です。 {aa}aa}aa'、'{a{a}a}' など...どうすればいいですか?

問題がある場合は、XSD ドキュメント内でこのテストを実行します...

4

2 に答える 2

2

あなたが記述している言語 (Dyck 言語と密接に関連している) は文脈自由であり、規則的ではありません (チョムスキー階層のタイプ 2)。とはいえ、基本的な正規表現を使用してこの言語の単語のアクセプターを構築することは不可能です。

ただし、スタック マシンは、記述した言語のタイプの単語問題を決定できます。これを実装するには、文字列を文字にトークン化し、各文字を反復処理し、開き括弧が見つかった場合は、0 に初期化されたカウンターを 1 ずつ増やします。閉じ括弧を見つけたら、それを 1 減らします。実行全体で不変式counter >= 0が保持され、カウンターの最終状態が 0 の場合は、単語を受け入れます。

于 2012-10-05T12:21:37.983 に答える
1

Michael Schmeißer が概説する理由により、質問で説明されている言語は XSD 正規表現では認識できません。(おそらく、クラス 3 言語を長い間置き去りにしてきた Perl 互換のパターンによって認識される可能性がありますが、XSD は、Perl 式に特別な力を与える後方参照やその他のデバイスを使用しません。)

正則近似

MS の回答に対するあなたのコメントは、質問で説明されている言語への通常の近似値に落ち着く可能性があることを示唆しています。その場合、元の言語の単語のみを受け入れるが、一部の単語を誤って拒否する可能性のある通常のサブセット言語か、その言語のすべての単語を受け入れるが、一部の非言語を誤って受け入れる通常のスーパーセット言語のいずれかを選択できます。言葉も。

コメントの近似

MSの回答に対するコメントで与えられた表現は、通常のサブセットです。これには 3 つの明らかな制限があります。

  • ブレースは最大 3 つの深さまで入れ子にすることができます。
  • 少なくとも 1 対の中かっこが必要です (文字列 " aaa" は受け入れません)。
  • 入れ子の各レベルで最大 1 組の中かっこを使用できます (" " は受け入れませんa{a}a{a}a)。

これらの最初のような制限は避けられません。3 よりも大きい数を選択できますが、通常のサブセットではネストの深さが常に最大になります。ただし、他の 2 つは必須ではなく、サブセット式の体系的な開発によって回避できます。

サブセット表現を体系的に開発する

BNFから始める

簡単にするために、元の投稿で説明されている言語を使用すると、次のように BNF のような表記で表現できます。

<S> ::= <empty> | <S> a | <S> { <S> } .
<empty> ::= .

または、拡張 BNF では:

S ::= (a|{S})*

ネスト レベルを明示的にするために書き直します

次に、これを次のように (接辞文法のスタイルで) 入れ子を追跡するように書き直すことができます。

S ::= (a|{S1})*
S1 ::= (a|{S2})*
S2 ::= (a|{S3})*
etc.

選択したレベルnで、次のようにして再帰を終了できます (したがって、言語を正規化できます)。

Sn ::= a*

LHS を RHS に置き換える

次に、一度に 1 レベルずつ代入して正規表現を作成できます。

S = (a|{S1})*
  = (a|{(a|{S2})*})*
  = (a|{(a|{(a|{S3})*})*})*
etc.

この場合、要約すると次のようになります: nレベルの深さのネストを許可するには、文字列 " " のn 個のコピーで開始し、" (a|{" で続行し、文字列 " " のn 個のコピーでa*終了します。以外の文字を許可するには、代わりに で書き換えます。 })*a[^{}]a

n = 4の結果

ネストされた 4 つのレベルの中括弧で置換を停止すると、次の式が得られます。

([^{}]|{([^{}]|{([^{}]|{([^{}]|{[^{}]*})*})*})*})*

代替としてのスーパーセット式

[^{}]*正当な表現が拒否されないことが重要な場合は、中央を.*orに置き換えることで、これをスーパーセット表現に変えることができ(.|\n)*ます。次に、(a) 正しくネストされた中括弧が 4 つ以下の深さの文字列と、(b) 最も内側のレベル (したがって、5、6、または n入れ子のレベルは必ずしも正しいとは限りません)。 

([^{}]|{([^{}]|{([^{}]|{([^{}]|{[(.|\n)*})*})*})*})*

対照的に、不正な式が決して受け入れられないことが重要である場合は、サブセット式に固執することをお勧めします。

于 2012-10-10T02:09:16.773 に答える