xml - sax パーサーは dtd に対してどのように検証しますか?

Question

xml ファイルと dtd が定義されています。sax パーサーについての私の理解では、xml ドキュメント全体 (DOM など) をメモリに格納するのではなく、イベントを処理します。たとえば、< name> ... // 約 200 万行 < /name> のような宣言を含む xml ファイルがあるとします。この場合、sax パーサーはメモリに何を格納するのでしょうか? 終了タグ名が発生することをどのように認識しますか。そして今、本当の問題は、sax パーサーが dtd に対してどのように検証するのかということです。詳細な説明は求めていませんが、検証がどのように行われるかについての一般的な考え方を探しています。

Answer 1

通常、DTDは有限状態オートマトンのセットに変換されます。BNF文法を決定論的FSAに変換するための標準アルゴリズムがあります。これは、AhoやUllmannなどのコンパイラの教科書にあります。これにより、各要素のコンテンツモデルに対して1つのFSAが生成されます。したがって、解析/検証の現在の状態は、開いている要素ごとに1つのFSA（現在の状態を含む）を保持するスタックによって表されます。パーサーは開始タグを検出すると、その開始タグが最上位のFSAで有効な遷移を表しているかどうかを確認し、この遷移を行うことでそのFSAの現在の状態を変更します。また、新しい要素のコンテンツモデルのFSAに対応するスタックに新しいFSAを追加します。終了タグを検出すると、最上位のFSAの現在の状態が最終状態であるかどうかを確認し、このFSAをスタックからポップします。