让我们构建一个浏览器渲染引擎吧-2

我正在构建一个玩具性的 HTML 渲染引擎 robinson，当然你也可以。本篇是这一系列文章的第二篇：

本篇博文讲述的是将 HTML 文档解析为 DOM 节点树。语法解析是一个很吸引人的话题，我不会花太多时间和篇幅来讲解它，你可以从任何有关编译器课程或书籍中更详细的了解它，也可以阅读你所选择的编程语言相关的语法解析器文档。

HTML 有自己特有的语法解析算法。与大多数编程语言和格式化文件不同，HTML 语法解析算法允许错误的输入，网页浏览器并不会加入错误处理的指令，即使对那些不符合语法规则的网页，浏览器也会将其如何显示保持一致。浏览器必须做到这一点：在网页出现的早期，不相容的 HTML 就已被支持了，并且现存的许多网页都是不相容的。

一个简单的 HTML 方言

我这里不会完成一个标准的 HTML 语法解析器，而是实现其子集的解析器。这个解析器可以解析以下文本：

<html>
    <body>
        <h1>Title</h1>
        <div id="main" class="test">
            <p>Hello <em>world</em>!</p>
        </div>
    </body>
</html>

有以下语法是允许的：

封闭式标签：...
带有引用值的属性：id="main"
文本节点：world

所有其他的语法是不支持的，包括：

注释
Doctype 声明
转意字符（比如 &）和 CDATA 段
自关闭标签： 或 
错误处理（比如：不平衡或不正确嵌套的标签）
命名空间和那些 XHTML 语法：<html:body>
字符编码检测

在这个工程的每一个阶段，我几乎只实现那些后续阶段所必须的功能。如果你想了解更多有关解析器的理论和工具，你可以加入更多的功能实现。

代码示例

接下来，让我们看一下我的玩具性 HTML 语法解析器，注意，它可能并不是最好的一种实现方式。它的结构多多少少基于 Servo 的 cssparser 库的 tockenizer 模块，它没有真正的错误处理，当遇到不能识别的语法，大多会中止运行。代码由 Rust 语言编写，但我希望对那些熟悉 Java，C++ 或 C# 的人来说，它具有相当的可读性。其中，也使用了第一篇中讲到的 DOM 数据结构。

解析器将其输入字符串和当前位置存放在一结构中，其中当前位置就是下一个尚未被处理的字符索引。

struct Parser {
    pos: usize, // "usize" is an unsigned integer, similar to "size_t" in C
    input: String,
}

我们可以实现一些简单的方法来读取、判断接下来的字符：

impl Parser {
    // Read the current character without consuming it.
    fn next_char(&self) -> char {
        self.input[self.pos..].chars().next().unwrap()
    }

    // Do the next characters start with the given string?
    fn starts_with(&self, s: &str) -> bool {
        self.input[self.pos ..].starts_with(s)
    }

    // Return true if all input is consumed.
    fn eof(&self) -> bool {
        self.pos >= self.input.len()
    }

    // ...
}

Rust 字符串存储在一个 UTF-8 编码的字节数组中，为了获取下一个字符，我们并不能简单的将位置索引加一，而应该利用 char_indices 来正确处理多字节字符。（UTF-8 编码为变长编码，一个字符可能有多字节构成，当我们使用固定宽度字符时，就可以将 pos 加一来索引字符。）

// Return the current character, and advance self.pos to the next character.
fn consume_char(&mut self) -> char {
    let mut iter = self.input[self.pos..].char_indices();
    let (_, cur_char) = iter.next().unwrap();
    let (next_pos, _) = iter.next().unwrap_or((1, ' '));
    self.pos += next_pos;
    return cur_char;
}

通常我们需要连续读取字符，而 consume_while 就是用来连续读取那些符合特定条件并将其返回方法的方法，其参数是一个返回 bool 类型的函数。

// Consume characters until `test` returns false.
fn consume_while<F>(&mut self, test: F) -> String
        where F: Fn(char) -> bool {
    let mut result = String::new();
    while !self.eof() && test(self.next_char()) {
        result.push(self.consume_char());
    }
    return result;
}

我们可以使用这个方法来读取空白字符或数字字母字符：

// Consume and discard zero or more whitespace characters.
fn consume_whitespace(&mut self) {
    self.consume_while(CharExt::is_whitespace);
}

// Parse a tag or attribute name.
fn parse_tag_name(&mut self) -> String {
    self.consume_while(|c| match c {
        'a'...'z' | 'A'...'Z' | '0'...'9' => true,
        _ => false
    })
}

现在我们可以来解析一段 HTML 文本了。为了解析一个 node，我们首先从它的第一个字符来判断其是否是一个 element 还是一个 text node。在我们的简化 HTML 方言里，一个 text node 可以包含除 < 之外的任何字符。

// Parse a single node.
fn parse_node(&mut self) -> dom::Node {
    match self.next_char() {
        '<' => self.parse_element(),
        _   => self.parse_text()
    }
}

// Parse a text node.
fn parse_text(&mut self) -> dom::Node {
    dom::text(self.consume_while(|c| c != '<'))
}

element 就有点复杂，它不仅包含开闭标签，而起在开闭标签间可以有任意数量的子结点：

// Parse a single element, including its open tag, contents, and closing tag.
fn parse_element(&mut self) -> dom::Node {
    // Opening tag.
    assert!(self.consume_char() == '<');
    let tag_name = self.parse_tag_name();
    let attrs = self.parse_attributes();
    assert!(self.consume_char() == '>');

    // Contents.
    let children = self.parse_nodes();

    // Closing tag.
    assert!(self.consume_char() == '<');
    assert!(self.consume_char() == '/');
    assert!(self.parse_tag_name() == tag_name);
    assert!(self.consume_char() == '>');

    return dom::elem(tag_name, attrs, children);
}

简化方言语法中解析属性很容易，在碰到 > 之前，我们重复寻找属性名，= 和被双引号引用的字符串：

// Parse a single name="value" pair.
fn parse_attr(&mut self) -> (String, String) {
    let name = self.parse_tag_name();
    assert!(self.consume_char() == '=');
    let value = self.parse_attr_value();
    return (name, value);
}

// Parse a quoted value.
fn parse_attr_value(&mut self) -> String {
    let open_quote = self.consume_char();
    assert!(open_quote == '"' || open_quote == '\'');
    let value = self.consume_while(|c| c != open_quote);
    assert!(self.consume_char() == open_quote);
    return value;
}

// Parse a list of name="value" pairs, separated by whitespace.
fn parse_attributes(&mut self) -> dom::AttrMap {
    let mut attributes = HashMap::new();
    loop {
        self.consume_whitespace();
        if self.next_char() == '>' {
            break;
        }
        let (name, value) = self.parse_attr();
        attributes.insert(name, value);
    }
    return attributes;
}

解析子节点，我们循环递归调用 parse_node 直到关闭标签。 parse_node 函数返回一个 Vec（Rust 语言中的一个可变长度数组类型）。

// Parse a sequence of sibling nodes.
fn parse_nodes(&mut self) -> Vec<dom::Node> {
    let mut nodes = Vec::new();
    loop {
        self.consume_whitespace();
        if self.eof() || self.starts_with("</") {
            break;
        }
        nodes.push(self.parse_node());
    }
    return nodes;
}

最后，我们把这些组合在一起来解析整个 HTML 文档为一个 DOM 树。如果没有明确的一个根节点，我们会为它生成一个，这类似于一个真正的 HTML 解析器：

// Parse an HTML document and return the root element.
pub fn parse(source: String) -> dom::Node {
    let mut nodes = Parser { pos: 0, input: source }.parse_nodes();

    // If the document contains a root element, just return it. Otherwise, create one.
    if nodes.len() == 1 {
        nodes.swap_remove(0)
    } else {
        dom::elem("html".to_string(), HashMap::new(), nodes)
    }
}

整个 robinson HTML 解析器代码就这些，大概 100 多行（不包括注释和空格）。如果你用现成的库或解析器，代码量会更少。

练习

这是其它你可以尝试的方式，像前面一样，你可以选择或忽略它们：

构造一个 HTML 子集的解析器生成一个节点树。（手写或利用现有库或解析器均可）
修改 robinson HTML 解析器添加更多解析功能，例如注释。或者重写一个更好的，也可用现有库或解析器。
写一个不符合语法规范的 HTML 文件，使你（我）的解析器报错。修改这个解析器可以解析这个错误并生成节点树。

捷径

如果你想忽略解析部分，你可以自己添加一些代码编写一个 DOM 树：

// <html><body>Hello, world!</body></html>
let root = element("html");
let body = element("body");
root.children.push(body);
body.children.push(text("Hello, world!"));

或者你可以将现有的解析器整合到你的代码中。

下一篇我们将会讲解 CSS 数据结构和解析。