HTMLパーサーの設計・実装ノート (2) 構文解析
- (1) 字句解析
- (2) 構文解析
構文解析の基本概念
トークナイザの出力に基づいてDOMツリーを構築するのが構文解析フェーズです。
まず注意すべき点として、構文解析中もJavaScriptによってDOMツリーが無茶苦茶に操作される可能性があるという点が挙げられます。静的なパーサーであればこのような問題の大部分は無視できますが、規格で冗長に書かれている部分はしばしばこういったケースを念頭に置いているので頭の片隅に置いておくとよいでしょう。
以上の理由から、パーサーの挙動は静的な構文木の構築ではなくDOMノードの作成と書き換え処理として記述されます。
たとえば初期状態で <p> が入力されると、挿入モードが "in body" まで遷移し以下のようなDOMツリーが構築されます。 (読みやすさのため空白ノードの位置を改変しています)
<html>
<head>
</head>
<body>
<p></p>
</body>
</html>
そして、このDOMツリー上の <html> 要素、 <body> 要素、 <p> 要素への参照がこの順にスタック (stack of open elements) に積まれた状態になります。
このスタックは多くの場合、DOM上の親子関係を反映していますが、親子関係が必ず成立するわけではありません。主に以下のような理由で親子関係にない要素がstack of open elements上で隣接する場合があります。
- JavaScriptによってDOMが改変されている場合
- table要素から里親に出された (foster parenting) 要素がある場合
たとえば <table><p> が入力されると、「html要素」「body要素」「table要素」「p要素」がこの順にstack of open elementsに積まれますが、pはtableの子要素にはなりません。
そのほか、パーサーを設計する上での困難が多数存在するため、以下でひとつひとつ列挙していきます。
開始タグ・終了タグの省略
これは正当なHTML文書でも可能な仕組みで、パーサーでの対応も比較的簡単です。
まず以下の基本構造に出てくるタグ (<html>, <head>, </head>, <body>, </body>, </html>) は全て一定条件で省略可能です。
<html>
<head>
<!-- base, basefont, bgsound, link, meta, noframes, noscript, script, style, template, title のみここに入る -->
</head>
<body>
<!-- 大多数の要素は自動的にこの位置に入る -->
</body>
</html>
内容モデルにより特定の要素の下にしか入れない場合の親要素の開始タグが省略できる場合もあります。 <colgroup> や <tbody> の省略がそれにあたります。 (正確には、 <tbody> は内容モデル上はなくても問題なく、HTML構文特有の制限という位置付けのようです)
また多くの場面で終了タグが省略できます。たとえば <p>, <li>, <td> などはネストできないため、同じ要素を隣接させるときは終了タグを省略できます。
開始タグ・終了タグの省略は、単に文脈に応じて存在しないタグを復元すればよいので、 (ルールが多いので大変ではありますが) ストリーミングパーサーを設計する上ではそれほど問題ではありません。
<html>, <body> のマージ
html要素とbody要素は原則として文書に1つずつしか存在できません。 (templateなどを除く)
不正な <html>/<body> 開始タグが発見されると、そのタグ自体は無視されますが、タグ内の属性が既存の対応する要素にコピーされます。
<!DOCTYPE html>
<h1>私のホームページへようこそ</h1>
<p>blah blah blah...</p>
<!-- ↓末尾に書いても、先頭のhtml要素の属性に影響がある -->
<html lang="ja">
これは最後まで読まなければ最初のタグの内容すら確定できないという非常に凶悪な仕様です。ストリーミングパーサーを作るにあたってはこの挙動をどのようにユーザーに見せるかをよく考える必要があるでしょう。
head内、body内、html内への回帰
HTML文書構造上の閉じタグである </head>, </body>, </html> をパーサーは認識しますが、これらは完全に信用されてはいません。これらの閉じタグの後に不正な要素が検出された場合、条件次第では閉じられる前の状態に(一時的にまたは恒久的に)回帰することがあります。
-
</head>から<body>までの間 (after head)-
<base>,<basefont>,<bgsound>,<link>,<meta>,<noframes>,<script>,<style>,<template>,<title>→ 一時的に<head>内に戻って挿入される-
<noscript>は対象外 (body側に入る)
-
-
-
</body>から</html>までの間 (after body)-
</html>以外のほぼ全てのタグ →<body>内に戻って挿入される - 空白以外のテキスト →
<body>内に戻って挿入される
-
-
</html>以降 (after after body)- ほぼ全てのタグ →
<body>内に戻って挿入される - 空白以外のテキスト →
<body>内に戻って挿入される
- ほぼ全てのタグ →
たとえば以下の文書
</html>
<!-- foo -->
<p>bar</p>
<!-- baz -->
では、パースされると順番が bar→baz→</html>→foo に入れ替わります。ストリーミングパーサーはこれをユーザーにどう見せるか考える必要があるでしょう。
framesetモードへのフォールバック
<frameset> 要素は <body> 要素と共存できません。基本的には先に生成されたほうが勝ちますが、以下の条件を満たすときは既存の <body> 要素を削除して <frameset> を優先する挙動になります。
- 明示的な
<body>タグが存在しない。 - かつ、
<template>要素が存在しない。 - かつ、暗黙的に生成された
<body>にまだ内容が存在しない。これはpalpable contentとよく似た条件で、以下のようなノードを含まないことを要求している。- 空白以外のテキスト
- リスティング用要素
<pre>,<listing>,<xmp> - 列挙アイテム
<li>,<dd>,<dt> - フォームコントロール要素
<input>,<textarea>,<select>,<button>,<keygen> - 埋め込みコンテント
<img>,<area>,<iframe>,<object>,<embed>,<applet> - レイアウトに影響のある要素
<br>,<wbr>,<hr>,<table>,<marquee>
たとえば以下の例では <frameset> が勝ちます。
<!DOCTYPE html>
<p><p><p><p><p><p><p><p><p><p><p><p><p><p><p>
<frameset>
一方、以下の例では <body> が勝ちます。
<!DOCTYPE html>
<p><p><p><p><p><p><p><p><p><p><p><p><p><p><p>p
<frameset>
一度作った要素を削除するルールなので、ストリーミングパーサーでは以下のどちらかの対応が必要になるでしょう。
- 要素の削除をユーザーにハンドルさせる
- frameset okフラグがnot okになるまでは出力をバッファリングする
Discussion