簡易的な自作ブラウザを作成した際にパーサーを実装したので考え方を共有したいと思います。
htmlをパースするときの考え方
<h1> text </h1>
例えばこのタグをパースする場合、カーソルを用意し頭から一文字ずつ確認して行きます。
<h1> text </h1>
↑
一文字目が<であればタグの始まりと認識させます。
<h1> text </h1>
↑
一文字先をみて/で無ければ閉じタグではないので処理を続行させます。
<h1> text </h1>
↑
そして>が見つかるまでカーソルを動かします。この時点でh1というタグ名がわかっているのでそれを持っておきます。
<h1> text </h1>
↑
次に<が見つかるまでカーソルを動かします。この時点でタグの中身のtextが取得できています。
<h1> text </h1>
↑
もう一つカーソルを動かすと/が見つかるのでこれが終了タグであることがわかります。
もし見つからない場合はインナーの開始タグであることがわかります。その場合は上の処理からまた繰り返します。
オプショナルなタグ
開始タグや閉じタグを省略できる仕様がHTMLにはあります。
どこまで対応するかは実装次第ですが今回は基本的にテキスト関係のものは閉じタグが省略可としています。
属性
<h1 class="bigger-text"> text </h1>
↑
タグの中に属性がある場合があります。この場合は<にカーソルが入った時点でフラグを立てます。
<h1 class="bigger-text"> text </h1>
↑
タグ中で>以外が見つかった場合に属性名として処理します。
<h1 class="bigger-text"> text </h1>
↑
カーソルを進めて=が見つかればその先は属性の中身として処理を行います。見つからない場合は属性名のみとして処理します。
実装
具体的な実装は長くなりそうなので考え方を中心に例としてコード書いて行きます。
ノードを用意する
HTMLは木構造で表現できるのでノードの構造体を用意します。
pub struct Nodes {
pub tag_name: String,
pub text: String,
pub attributes: Vec<Attribute>,
pub child: Vec<Nodes>,
}
ノードです。
tag_nameにはタグの名前、textにタグの中身、childに入れ子になっているノードが入ります。
ルートhtmlタグになるのでルートの構造体は用意していません。
パーサーの実際のコード
html.htmlにHTML全体が入っています。
pub fn parse_node(mut html: &mut Html) -> Nodes {
let mut nodes: Nodes = Nodes::new();
if html.html.len() < 1 {
return nodes;
}
if html.html.chars().nth(0).unwrap() == '<' {
if html.html.chars().nth(1).unwrap() == '/' {
loop {
remove_close_tag(&mut html);
if html.html.len() == 0 || html.html.chars().nth(1).unwrap() != '/' {
break;
}
}
return nodes;
}
let (tag_name, tag_text, node, attr) = parse_element(&mut html);
nodes.tag_name = tag_name.trim().to_string();
nodes.text = tag_text.trim().to_string();
if !attr.is_empty() {
nodes.attributes = attr;
}
if node.tag_name != "" {
nodes.child.push(node);
}
if !nodes.child.is_empty()
&& html.tag.len() > 0
&& nodes.child[0].tag_name == html.tag[html.tag.len() - 1]
{
let node = parse_node(&mut html);
if node.tag_name != "" {
nodes.child.push(node);
}
}
loop{
if html.html.len() == 0 {
break;
}
if html.tag.last().unwrap() == &nodes.tag_name {
let node = parse_node(&mut html);
nodes.child.push(node);
}else{
break;
}
}
loop {
if html.html.len() == 0 {
break;
}
if nodes.tag_name == "body" {
let node = parse_node(&mut html);
nodes.child.push(node);
} else {
break;
}
}
}
return nodes;
}
このコードでは上の考え方に従って実装してあります。ただしカーソルは文字列から必要なくなった場所を削除することで実現しています。
長いので一部切り出して解説します。
if html.html.chars().nth(0).unwrap() == '<' {
if html.html.chars().nth(1).unwrap() == '/' {
loop {
remove_close_tag(&mut html);
if html.html.len() == 0 || html.html.chars().nth(1).unwrap() != '/' {
break;
}
}
return nodes;
}
}
ここでタグの始まるか終了タグかを判定しています。
let (tag_name, tag_text, node, attr) = parse_element(&mut html);
始まりであればタグ名、タグの中身を取得します。またparse_element関数で開始タグを発見した場合、中でparse_nodeを実行します。
loop{
if html.html.len() == 0 {
break;
}
if html.tag.last().unwrap() == &nodes.tag_name {
let node = parse_node(&mut html);
nodes.child.push(node);
}else{
break;
}
}
loop {
if html.html.len() == 0 {
break;
}
if nodes.tag_name == "body" {
let node = parse_node(&mut html);
nodes.child.push(node);
} else {
break;
}
}
ここではHTMLの文字数が0になるので上記の処理を繰り返し最終的的にlenが0になればパース完了になります。
詳しい実装はリポジトリをご覧ください。
リポジトリ
Discussion