2014年8月11日

让我们构建一个浏览器引擎!

第2部分: HTML

这是关于构建玩具浏览器渲染引擎的系列文章中的第二篇:

第1部分: 入门

第2部分: HTML

第3部分: CSS

第4部分: style

第5部分: 盒子

第6部分: 块布局

第7部分: 绘画101

本文是关于解析的HTML源代码生成DOM节点树. 解析是一个引人入胜的话题,但我没有时间或专业知识给它应有的介绍. 您可以从任何好课程获得解析的详细介绍要么书关于编译器. 或者通过浏览解析器生成器文档获得实际操作,取决于您选择的编程语言.

HTML有自己的独特之处解析算法. 与大多数编程语言和文件格式的解析器不同,HTML解析算法不会拒绝无效输入. 相反,它包含特定的错误处理指令,因此Web浏览器可以就如何显示每个网页达成一致,即使是那些不符合语法规则的网页. Web浏览器必须这样做才能使用: 由于Web早期就支持不符合标准的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解析器,记住这只是一种方法 (可能不是最好的方法) . 它的结构基于松散的标签生成器-tokenizer来自Servo的cssparser库. 它没有真正的错误处理; 在大多数情况下,它只是在遇到意外语法时中止. 代码在rust,但我希望任何使用类似 Java,C ++或C# 等类似语言的人都能理解它. 它利用了来自第1部分的DOM数据结构.

解析器存储其输入字符串和字符串中的当前位置. 该位置是我们尚未处理的下一个字符的索引.

    struct Parser {
        pos: usize, //"usize"是无符号整数，在 C 中比 "size_t" 小
        input: String,
    }

我们可以使用它来实现一些简单的方法来查看输入中的下一个字符:

    impl Parser {
        //读取当前字符而不消耗它。
        fn next_char(&self) -> char {
            self.input[self.pos..].chars().next().unwrap()
        }

        //下一个字符是否以给定的 string字符开头?
        fn starts_with(&self, s: &str) -> bool {
            self.input[self.pos ..].starts_with(s)
        }

        //如果消耗了所有输入，则返回true。
        fn eof(&self) -> bool {
            self.pos >= self.input.len()
        }

        //...
    }

Rust字符串存储为UTF-8字节数组. 要转到下一个字符,我们不能只前进一个字节. 相反,我们使用char_indices它正确处理多字节字符. (如果我们的字符串使用固定宽度字符,我们可以增加pos从1开始.)

    //返回当前字符，并将self.pos推进到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方法使用满足给定条件的字符,并将它们作为字符串返回. 这个方法的参数是一个带一个char的函数 1⃣️,并返回一个bool.

    //使用字符直到`test`返回false。
    fn consume_while<F>(&mut self, test: F) -> String
            where F: Fn(char) -> bool { // 1⃣️
        let mut result = String::new();
        while !self.eof() && test(self.next_char()) {
            result.push(self.consume_char());
        }
        return result;
    }

我们可以使用它来忽略一系列空格字符,或者使用一串字母数字字符:

    //消耗并丢弃零个或多个空格字符.
    fn consume_whitespace(&mut self) {
        self.consume_while(CharExt::is_whitespace);
    }

    //解析标签或属性名称。
    fn parse_tag_name(&mut self) -> String {
        self.consume_while(|c| match c {
            'a'...'z' | 'A'...'Z' | '0'...'9' => true,
            _ => false
        })
    }

现在我们已经准备好开始解析HTML了. 要解析单个节点,我们会查看其第一个字符,以查看它是元素还是文本节点. 在我们的简化版HTML中,文本节点可以包含除<以外的任何字符.

    //解析单个节点。
    fn parse_node(&mut self) -> dom::Node {
        match self.next_char() {
            '<' => self.parse_element(),
            _   => self.parse_text()
        }
    }

    //解析文本节点。
    fn parse_text(&mut self) -> dom::Node {
        dom::text(self.consume_while(|c| c != '<'))
    }

元素更复杂. 它包括开始和结束标签,以及它们之间的任意数量的子节点:

    //解析单个元素，包括其开放标签，内容, 和闭合标签.
    fn parse_element(&mut self) -> dom::Node {
        //打开标签。
        assert!(self.consume_char() == '<');
        let tag_name = self.parse_tag_name();
        let attrs = self.parse_attributes();
        assert!(self.consume_char() == '>');

        //内容。
        let children = self.parse_nodes();

        //关闭标签。
        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);
    }

在我们的简化语法中,解析属性非常简单. 直到我们到达开头标签的末尾 (>) 我们反复寻找一个名字=,然后是一个用引号括起来的字符串.

    //解析单个 name="value" 对。
    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);
    }

    //解析一个引用的值。
    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;
    }

    //解析 name ="value" 对的列表，用空格分隔.
    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;
    }
``` rust
为了解析子节点,我们递归调用`parse_node`循环,直到我们到达结束标签. 这个函数返回一个`Vec`,这是Rust的可扩展数组的名称. 
``` rust
    //解析一系列兄弟节点。
    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解析器所做的.

    //解析HTML文档并返回根元素。
    pub fn parse(source: String) -> dom::Node {
        let mut nodes = Parser { pos: 0, input: source }.parse_nodes();

        //如果文档包含根元素，则只需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的子集作为输入并生成DOM节点树.
修改robinson 的HTML解析器以添加一些缺少的功能,例如注释. 或者用更好的解析器替换它,可能是用库或生成器构建的.
创建一个无效的HTML文件,导致您的解析器 (或我的) 失败. 为您的测试文件修改解析器以从错误和生成DOM树中恢复.

快捷键

如果你想完全跳过解析,你可以通过编程方式构建一个DOM树,方法是在程序中添加这样的代码 (伪代码;调整它以匹配你在第1部分中编写的DOM代码) :

    //<html> <body>你好，世界！<
    let root = element("html");
    let body = element("body");
    root.children.push(body);
    body.children.push(text("Hello, world!"));

或者,您可以找到现有的HTML解析器并将其合并到您的程序中.

该下一篇文章本系列将介绍 CSS数据结构和解析.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

1.zh.md

1.zh.md

让我们构建一个浏览器引擎!

第2部分: HTML

简单的HTML方言

示例代码

练习

快捷键

Files

1.zh.md

Latest commit

History

1.zh.md

File metadata and controls

让我们构建一个浏览器引擎!

第2部分: HTML

简单的HTML方言

示例代码

练习

快捷键