6

Linq to XML に基づいた .Net ビルド用の優れた無料の XPath 2.0 実装がないため、(これも経験のために) 自分で実装することを考えました。しかし、明確にするために（存在するものを構築するのではなく）、これらは私が見つけたXPath 2.0の実装です：

  • サクソン.Net
  • Query Machine - これには問題がありました - 例の例外
  • XQSharp - 良いかもしれませんが、商用です (単一の開発者で ~300 $)

ここで、XPath 2.0 式などの言語を実装することがいかに難しいかについて考えてみたいと思います。XPath 2.0 式の EBNF を持つこのリンクを見つけました: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammarで、F# で作成することを考えています。 fslex/fsyacc の組み合わせ。

私のバックグラウンド(主観的): 以前にこれらのツールで遊んだことがありますが、いくつかの単純な式と非常に単純なプログラミング言語についてのみでした。さらに、Dragon book と Appel の最新コンパイラの ML 実装のほとんどを読みましたが、残念ながら、読みながら理論を実践していません。私は 1 年間コンピューター サイエンスを勉強しており、 ex とアルゴリズムに関する理論のコースを修了しfinite automatonてCFLいますが、大学に入る前から何年もの間開発者でした (プロの仕事で数年間 - 主に Web サイトのバックエンド)。

さて、解析の手順と私がカバーする傾向があるもの:

  1. Lex - 解析 - リダクション: FsLex/FsYacc。最初は Xpath 2.0 のすべてを適切にカバーするつもりはありませんが、少なくとも XPath 1.0 でできることのすべてに加えて、もう少し詳しく説明します。
  2. セマティック分析 - これにどれだけの意味があるかわかりません
  3. 最適化 - 私はこれをカバーする傾向がありません (少なくとも最初はそうではありません)。
  4. 実際のトラバースなど
  5. ...？

さて、上記に加えて具体的な質問：

  1. このサイズのパーサーを作成するのはどれほど難しいでしょうか? 私のバックグラウンドに基づいて、私はそれをすることができますか?
  2. 特に XPath 2.0 に関して見逃した重要な手順はありますか?
  3. 私が見逃したテクノロジーはありますか？XDocumentパーサーを作成するには、XPath 2.0 など以外のこともカバーする必要がありますか?

明確XDocumentにするために、XPath 2.0式パーサーを作成し、この解析された式でトラバースなどを行いたいと考えています。組み合わせたのはクエリエンジンだと思います。

更新:これを見つけました: http://www.w3.org/2007/01/applets/xpathApplet.htmlには、解析とトラバースのコードが含まれています。良いスタートや参考になると思います:-)

あなたの答えは高く評価されます。

4

3 に答える 3

5

私は XQSharp の開発者の 1 人なので、この分野での経験があります。XQSharp は、XQuery をサポートするように拡張する前に、実際には XPath の実装として誕生しました。

最初の実装には約 6 か月かかりましたが、当時取り組んでいたのはこれだけではありませんでした。

この後、機能が完成した実装ができました。これが完全に準拠していない多くの領域があり、標準の .NET メソッドが必要な仕様とまったく同じように動作しませんでした。この例としては、値と文字列、正規表現、多くの Unicode との間の変換、XML の .NET 表現の問題 (例: xml:base の処理) などがあります。

これを実装するには、いくつかの領域を実行する必要がありました。

解析: パーサー自体は簡単で、ほとんどが仕様の EBNF から生成されました。これは、最初は数週間の作業に相当すると見積もっています。

データ モデル: データの表現方法。XPath を完全に実装するには、多くの新しいデータ型 (xs:gDay など) を実装する必要があります。この場合、すべての項目が基本型から派生し、すべての式がこれらの列挙子を返します。また、アイテムのタイプが特定の XPath タイプと一致するかどうかを識別できる必要もあります。最初から静的型付けとスキーマ認識をサポートしていました。これらの機能がなければ、このセクションはおそらく些細なものになりますが、まだ数週間分の作業が必要です。

Expressions/Abstract Syntax Tree これは式自体のモデルです。XQuery Formal Semantics ドキュメントを使用して、さまざまな XPath コンストラクト (軸や述語など) からより単純なコア グラマー (if および typeswitch 式の膨大な数の let) へのマッピングを作成しました。最初の実装では、これらすべての式に評価メソッドがあり、式の最終的な表現もそうでした。私たちの場合、すべての式にも型チェック メソッドがありましたが、これは最初はスキップできます (これらの主な目的は最適化です)。これらすべての式を再度作成するのに数週間かかりました。

関数 前のコメンターが指摘したように、XPath の関数ライブラリはかなり大きいです。XPath ライブラリ全体を実装するのに数か月かかりました。

静的分析 少量の静的分析が必要です。変数参照と関数呼び出しは、正しい変数と関数にバインドする必要があります。ほとんどの XPath 実装はスタック ベースであるため、すべての変数にポインター (またはインデックス) を割り当てるには、スタック割り当てフェーズが必要です。この静的分析には 1 ～ 2 週間かかりました。ドラゴンブックは、これらの問題のほとんどを解決するために非常にうまくセットアップする必要があります.

おそらく、これらのカテゴリに直接分類されないすべての余分な作業について、さらに 1 か月分の作業を検討しているはずです。

このすべての作業の後、XPath のほぼ機能的な実装が残されました。しかし、実際に使用するには遅すぎました (.NET の XPath 1 よりも 100 倍遅いかもしれません)。この後は楽しい作業 - 最適化です。

エンジンを 100% 適合させ、最適化を追加するには、おそらくさらに 12 ～ 18 人月かかりました (ただし、最適化を少しやり過ぎた可能性があります!)。

私のアドバイスは、XPath のサブセット (おそらく前方軸のみと非常に限られた関数ライブラリ) に取り組むことから始めることです。1 か月か 2 か月で実装をまとめることができるかもしれませんが、本格的な XPath2 の実装は大きな投資になります。間に合います。

XPathNavigator には、基礎となる表現 (XPathDocument など) のインデックスを利用できる SelectChildren などのメソッドがあるため、ノード表現には必ず XPathNavigator を使用してください。

于 2010-08-27T17:05:39.737 に答える
4

私は3 年前に XSLT 2.0 で XPath 2.0 パーサーを完全に実装しました。

FXSLでLR 解析フレームワークを使用しましたが、これはそれほど難しくありませんでした。文法は非常に大きく、よく覚えていれば 209 の規則があります。YACCxと呼んでいる YACC の修正 (私が行った) を使用して、解析テーブルを XML として生成しました。これらは、XSLT で記述された一般的な LR Parserの入力です。

このような種類のプロジェクトでは、フルタイムで少なくとも 6 か月、場合によっては 1 年を割り当てる必要があります。難しいのは、膨大な関数ライブラリ ( F & O ) を実装することです。

また、XPath はスタンドアロンの言語ではありません。別の言語でホストする必要があります。この理由により、既存のホスティング言語を変更するアクセス、影響、および可能性がなかったため、このパーサーを意味のあるものには使用しませんでした。

ですから、これらすべての困難に備えてください。

于 2010-08-24T13:06:10.160 に答える
3

3 番目の具体的な質問に答えるために、Dragon Book は構文解析式文法 (PEG)/Packrat パーサー/パーサー コンビネーター ライブラリについて言及していません。これらは現在、特に関数型言語に関しては大流行しています。たとえば、 FParsecを参照してください。

于 2010-08-24T09:46:57.860 に答える