3

基本的に、特定の XSD スキーマを正規表現で置き換えることができるかどうかを知りたいです。XML スキーマ言語は、有効な XML インスタンスのセットが任意のタイプの言語 (コンテキスト依存であっても) である XSD を生成できることを知っています。「正規表現と同等」のスキーマを特定したいと思います。次の問題に取り組んだ後、この質問を思いつきました。

特定のテキスト形式を解析する必要があり、最初に正規表現を試してみたところ、正規表現で十分に解析できることがわかりました。次に、この形式で受信したメッセージの XML 表現を作成したかったので、正規表現グループを XML 要素にマップしました。次に、正規表現の構造に基づいて XSD スキーマを手動で作成しました。最終的に、スキーマから元の正規表現を構築できるという意味で、正規表現を置き換えることができるスキーマができました。逆のこともできました。正規表現からスキーマを自動的に作成します。そのため、メッセージを XML に変換し、同時に検証することができました。私の質問は次のとおりです。

  1. すべての正規表現を XSD スキーマで表現できますか? (つまり、XSD スキーマを生成できる正規表現が与えられた場合)

  2. 任意の XSD スキーマが与えられた場合、与えられたスキーマを表現する正規表現があるかどうかを判断する方法はありますか?

    編集：おそらく最初の質問への答えはイエスです。なぜなら、特定の正規表現に依存しない方法で正規表現を使用したからです（これはすべての正規表現の証明ではありません）。

4

1 に答える 1

1

XML スキーマ言語は通常の言語のスーパーセットですが、明らかに XML ドキュメントのドメイン内に限られます。

＃1の場合：正規表現が整形式のXMLドキュメントと一致するという条件が追加されていますが、そうです。

＃2の場合：はい、通常の言語で許可されているXSDの機能を確認することです。正規表現を見つけるのはもっと大変です。

通常の言語には、非公式に、かなり単純な定義があります。

  • 空集合/文字列
  • リテラル (「シングルトン言語」)、たとえば「x」
  • 正規言語 A の場合、A* も正規言語です。
  • 正規言語 A および B の場合、A|B (結合) および AB (連結) は正規です。

基本的に、すべての連結と代替は問題ありませんが、再帰は不可能であり、後方参照や「メモリ」はありません。choice/ all/自身または親の型を参照する要素を要素型に含めるelementことはできず、解析プロセスで以前に見つけた情報を利用することはできません。

再帰の制限は、any禁止される要素にまで及びます。定義により、サブ要素を持つ要素を含め、あらゆる要素を受け入れます。この未知の要素のネストの深さがわからないため、それに一致する再帰パターンが必要ですが、通常の言語ではそれを行うことができません。

後方参照の制限は、「ある数の 'A' の後に同じ数の 'B' が続く」(A{n}B{n}) のようなことはできないことを意味します。これは XSD でも可能だとは思いませんが、少なくともどのように行うかは考えられません。

正規表現では、数値の制限 (例: minInclusive) はできません。

このall要素は、子要素のすべての可能な順序を受け入れる必要があるという点で問題があります。これにより、正規表現が指数関数的に拡張されます (二項係数、(n/k)^k <= n!/k!(nk)! < = (ne/k)^k) を子要素の数と一致させ、正規表現の一致はその長さで超線形です。要素内の属性の順序はスキーマによって制約されないため、属性の認識にも同じ問題があります。もちろん、正規表現が存在するかどうかだけに関心があり、正規表現を見つけることには関心がないのであれば、それは問題ではありません。

于 2011-03-28T23:33:19.510 に答える