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

注:本系列博文译自 Matt Brubeck 的博客

我正在构建一个玩具性的 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>

有以下语法是允许的:

  • 封闭式标签:<p>...</p>
  • 带有引用值的属性:id="main"
  • 文本节点:<em>world</em>

所有其他的语法是不支持的,包括:

  • 注释
  • Doctype 声明
  • 转意字符(比如 &amp;)和 CDATA 段
  • 自关闭标签:<br/>或<br>
  • 错误处理(比如:不平衡或不正确嵌套的标签)
  • 命名空间和那些 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 多行(不包括注释和空格)。 如果你用现成的库或解析器,代码量会更少。

练习

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

  1. 构造一个 HTML 子集的解析器生成一个节点树。(手写或利用现有库或解析器均可)
  2. 修改 robinson HTML 解析器添加更多解析功能,例如注释。或者重写一个更好的,也可用现有库或解析器。
  3. 写一个不符合语法规范的 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 数据结构和解析。