HTMLパーサを作りたい　の0

mosh

最近id:higeponがwebkitの移植に取り組んでいるらしい( http://d.hatena.ne.jp/higepon/20110812/1313157918 )。まぁ世間にはSDLなWebKitもいくつか有るので、まともなC++ランタイムとビルドシステムのcmakeサポート、SDLやcurlがあればそれなりの手間で動くはず。。
と、言うわけで

  • WebKitを移植するのとブラウザを書くのはどっちが早いか対決

という非常に趣味の悪い企画を考えたので暫くWebブラウザを作ることに。
もちろん上記はウソで単にHTMLの理解を深めましょうというのが主旨です。テキストブラウザくらいは作りたいけど。

HTML5仕様

HTML5はかなり厳格に"入力ストリームの前処理" "tokenizeの仕方" "DOMツリーの構築"を規定しているので、仕様書を読んで仕様書通りに実装すればそれなりに互換性のあるHTMLリーダができるようになっている。
(実際にはXMLで書かれたWebページには別途対応する必要がある)

HTML以外にCSSなども読まないといけないが後回しにする。

HTML5のtokenizer仕様をS式に変換する

もちろん、上記の仕様書を手で実装することもできるが、変更に追従するためには仕様書と個々のステートの実装を一致させておくことが肝要。というわけで、仕様書を処理してステートマシンのスケルトンを生成し、それに肉付けしてトークナイザを作っていくことにする。

のconv.spsをnmoshで実行すると、

((rcdata-state "8.2.4.3 " "RCDATA state")
 (p "Consume the " (next-input-character) ":")
 (rule ((#\&)
        "Switch to the "
        (ref character-reference-in-rcdata-state
             "character reference in RCDATA   state")
        ".")
       ((#\<)
        "Switch to the "
        (ref rcdata-less-than-sign-state
             "RCDATA less-than sign state")
        ".")
       ((#\nul)
        (parse-error)
        ". Emit a U+FFFD REPLACEMENT CHARACTER   character token.")
       (("EOF") "Emit an end-of-file token.")
       (("Anything else")
        "Emit the "
        (current-input-character)
        " as a character   token.")))

のようなS式を生成する。
当然、生成されたS式はプログラムではないので、さらにこのS式から情報を抽出し、必要に応じて解釈を加えてプログラムにしていく必要がある。

HTML5トークナイザの状態遷移図を描く

ステートマシンを生成したらすぐGraphvizすると面白いのでもちろんGraphvizした。
dot.spsを実行すると、Graphviz向けのdotを生成する。

こりゃすごい。全体で68ステートもある。
というのは、HTML自体が色々な記法を内包していることに原因がある。DOCTYPEやスクリプトを含んだコメント、スクリプト等。
また、HTMLは人間によって書かれる可能性もあるので、破損した記述にも対処する必要がある。破損した記述は単にエラーで良いXMLとは対照的に思える。