2

私が知っているように、HTML の構文解析は依存関係が強いため、並列化が困難です。

単一の HTML ドキュメントを並行して解析し、最終的に単一の DOM ツリーを生成できるように、並列 HTML パーサーが存在するか設計されていますか?

以前の HTML バージョンまたは最新の HTML5 のいずれかである可能性があります。

4

1 に答える 1

3

HTML の「強い依存関係」は、解析の観点からは、解析する可能性のある他の言語の強い依存関係と大差ありません。本当の問題は、ファイルの一部を解析することは、通常、左側のコンテキストに依存することです。並列パーサーの問題は、左のコンテキストを取得する方法ですか?

テキストをチャンクに分割し、それらを個別に解析し、パーツをつなぎ合わせることによって、並列パーサーを構築する方法についての一般的な理論があります。McKeeman の論文 (参照) は、N 個のプロセッサで 0.85N の速度向上を主張しています。

ファイルを両端から解析し、途中で会うことを提案した論文を覚えているようです。右向きのパーサーは左のコンテキストを生成しました。左向きのパーサーが右のコンテキストを生成しました。文法を逆にすることで比較的簡単に双方向スキャンを実行でき、順方向および逆方向の文法をパーサー ジェネレーターにフィードできます。それらを接着するには、参考文献に記載されているようなテクニックが必要になる可能性があります。

当社の DMS ソフトウェア リエンジニアリング ツールキットには、パイプライン処理を使用して字句解析段階を解析から分離する GLR パーサーがあり、完全な HTML4 パーサーが利用可能です。(DMS は並列基盤の上に構築されています。個々のファイルを並列に解析するように構成するのも比較的簡単です。) その HTML4 パーサーは、言語方言に対する DMS のサポートを使用して HTML5 に拡張できる可能性があります。

原則として、1 つのプログラム (または HTML) ファイルのみを解析する場合、この種の並列処理は、全体的なパフォーマンスに大きな影響を与えないため、それほど重要ではありません。ほとんどのパーサーは非常に高速であり、その時間の大部分は個々の文字を処理する作業によって占められています。ファイルをチャンクに分割し、チャンクを個別に字句解析することで、おそらく多くの高速化が得られるでしょう。特に、HTML ファイルの多くは無駄な空白であるためです。

大量の HTML ファイルを処理する必要がある場合は、解析するファイルごとに 1 つのスレッドを使用する方がよいでしょう。次に、各スレッドでかなり従来のパーサー テクノロジを使用できます。

于 2012-12-16T00:53:45.007 に答える