5

私は、javascript で XML バリデーター (XSD) を開発するプロジェクトに 1 か月ほど取り組んでいます。私は本当に近づいてきましたが、問題に遭遇し続けています。

私がうまく行っている唯一のことは、DOM に保存するスキーマ構造を FSA に正規化することです。FSA に対して xml 構造を検証するためにいくつかの方法を試しましたが、毎回不足しています。

バリデーターは、クライアント側の WYSIWYG XML エディターを実行するために使用されているため、次の要件を満たす必要があります。

  • 効率的である必要があります (複雑なモデルでも要素の子ノード パターンを検証するのに 15 ミリ秒未満)
  • さまざまな時点でどの要素をドキュメントに挿入/削除できるかを判断し、ドキュメントの有効性を維持するためにクエリを実行できる Post Validation Schema Infoset (PSVI) を公開する必要があります。
  • xml 子ノード構造を検証できなければならず、無効な場合はどのコンテンツが予期されていたか、またはどのコンテンツが予期されていなかったかを返す必要があります。

-- 詳細情報 次の例を考えてみましょう --
最初に、名前空間に関して xs:group や xs:import などを正規化する一般的な FSA 表現にスキーマ構造を変換します。たとえば、次のことを考慮してください。

<xs:group name="group1">
    <xs:choice minOccurs="2">
         <xs:element name="e2" maxOccurs="3"/>
         <xs:element name="e3"/>
    </xs:choice>
</xs:group>
<xs:complexType>
    <xs:seqence>
        <xs:element name="e1"/>
        <xs:group ref="group1"/>
    </xs:sequence>
<xs:complexType>

同様の一般化された構造に変換されます。

<seq>
    <e name="e" minOccurs="2"/>
    <choice minOccurs="2">
         <e name="e2" maxOccurs="3"/>
         <e name="e3"/>
    </choice>
</seq>

XQuery と XSLT を使用して、これをすべてサーバー側で行います。

バリデーターを作成する最初の試みは、javascript の再帰関数を使用することでした。途中で、存在する可能性のあるコンテンツを見つけた場合は、それをグローバル PSVI シグナルに追加して、階層内の特定のポイントに追加できるようにします。

私の 2 回目の試行は反復的で、はるかに高速でしたが、どちらも同じ問題に悩まされていました。

どちらも単純なコンテンツ モデルを正しく検証できましたが、モデルがより複雑になり、非常にネストされるとすぐに失敗しました。

私は完全に間違った方向からこの問題に取り組んでいると考えています。私が読んだことによると、ほとんどの FSA は状態をスタックにプッシュすることによって処理されますが、私の状況でこれを行う方法がわかりません。

次の質問についてアドバイスが必要です。

  1. ステート マシンは適切なソリューションですか?
  2. ステート マシンを使用している場合、スキーマ構造を DFA に変換する最適な方法は何ですか? トンプソンアルゴリズム？これを機能させるには、DFA を最適化する必要がありますか。
  3. これをすべてJavaScriptで実装する最良の方法（または最も効率的な方法）は何ですか（最適化に注意してください。前処理はサーバーで実行できます）

ありがとう、

ケーシー

追加の編集:

ここでチュートリアルを見てきました: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspxは正規表現に焦点を当てています。私が必要としているものと非常に似ているようですが、正規表現用のパーサーの構築に焦点を当てています。これは、いくつかの興味深い考えをもたらします。

私は、xml スキーマがいくつかの演算子に分解されると考えています。

シーケンス -> 連結
の選択 -> ユニオン
minOccurs/maxOccurs - おそらく Kleene Closure よりも多くのものが必要ですが、この演算子を表現する最善の方法は完全にはわかりません。

4

1 に答える 1

5

同じ学習プロセスを経ていたとき、コンパイラー作成に関する本 (例えば、Aho & Ullman) を勉強する必要があることに気付きました。文法を実装するための有限状態マシンの構築は、標準的な教科書のようなものです。それは簡単でも直観的でもありませんが、文献で完全に説明されています - おそらく典型的な BNF 言語の文法では発生しない数値の minOccurs/maxOccurs を除いて、Thompson と Tobin によって十分にカバーされています。

于 2010-08-09T19:00:59.593 に答える