• home > webfront > SGML > html >

    HTML解析里的标记化算法—HTML文档解析和DOM树的构建

    Author:zhoulujun@live.cn Date:

    该算法使用状态机来表示。每一个状态接收来自输入信息流的一个或多个字符,并根据这些字符更新下一个状态。当前的标记化状态和树结构状态会影响进入下一状态的决定。这意味着,即使接

    HTML解析,为啥常规解析器都不适用?

    HTML 无法用常规的自上而下或自下而上的解析器进行解析。为什么呢?

    1. 语言的宽容本质。

    2. 浏览器历来对一些常见的无效 HTML 用法采取包容态度。

    3. 解析过程需要不断地反复。源内容在解析过程中通常不会改变,但是在 HTML 中,脚本标记如果包含 document.write,就会添加额外的标记,这样解析过程实际上就更改了输入内容。

    于不能使用常规的解析技术,浏览器就创建了自定义的解析器来解析 HTML。

    HTML5 规范详细地描述了解析算法。此算法由两个阶段组成:标记化和树构建

    标记化是词法分析过程,将输入内容解析成多个标记。HTML 标记包括起始标记、结束标记、属性名称和属性值。

    标记生成器识别标记,传递给树构造器,然后接受下一个字符以识别下一个标记;如此反复直到输入的结束。

    标记化算法的输出结果是 HTML 标记

    标记化算法算法使用状态机来表示

    每一个状态接收来自输入信息流的一个或多个字符,并根据这些字符更新下一个状态。

    当前的标记化状态和树结构状态会影响进入下一状态的决定。

    这意味着,即使接收的字符相同,对于下一个正确的状态也会产生不同的结果,具体取决于当前的状态。该算法相当复杂,无法在此详述,所以我们通过一个简单的示例来帮助大家理解其原理。

    浏览器解析html文档生成DOM树的过程,以下是一段html代码,以此为例来分析解析HTML文档的原理

    <html>
    <body>
    Hello world
    </body>
    </html>

    初始状态是数据状态。

    1. 遇到字符<时,状态更改为“标记打开状态”:

      1.  接收一个a-z字符会创建“起始标记”,状态更改为“标记名称状态”,并保持到接收>字符。此期间的字符串会形成一个新的标记名称。接收到>标记后,将当前的新标记发送给树构造器,状态改回“数据状态”

      2. 接收下一个输入字符/时,会创建关闭标记打开状态,并更改为“标记名称状态”。直到接收>字符,将当前的新标记发送给树构造器,并改回“数据状态”。

    2. 遇到a-z字符时,会将每个字符创建成字符标记,并发送给树构造器。

    现在我们回到“标记打开状态”。接收下一个输入字符 / 时,会创建 end tag token 并改为“标记名称状态”。我们会再次保持这个状态,直到接收 >。然后将发送新的标记,并回到“数据状态”。</html> 输入也会进行同样的处理。

    1. 遇到字符 < 时,状态更改为“标记打开状态”。

    2. 接收一个a-z字符会创建“起始标记”,状态更改为“标记名称状态”。

      这个状态会一直保持到接收 > 字符。在此期间接收的每个字符都会附加到新的标记名称上。

      在本例中,我们创建的标记是html标记

    3. 遇到 > 标记时,会发送当前的标记,状态改回“数据状态”。<body> 标记也会进行同样的处理。目前 html 和 body 标记均已发出。现在我们回到“数据状态”。接收到 Hello world 中的 H 字符时,将创建并发送字符标记,直到接收 </body> 中的 < 。我们将为 Hello world 中的每个字符都发送一个字符标记。

    对示例输入进行标记化

    DOM树构建

    当标签解析器解析出标签后会发送到DOM树构建器,我们可以认为DOM树构建器主要有以下两部分组成:

    • DOM树

    • 一个存放标签名的栈

    现,HTML5被指定为针对不正确的标签嵌套、排序、未关闭的标签、缺失的属性和所有其他在旧浏览器中可能出现的问题的恢复过程。为了解决这些问题,该规范要求使用树构建器来驱动词法分析器。从本质上讲,如果没有DOM,就无法正确标记化HTML(分割为单独的标签)。

    Cloudflare的HTML解析历史(上)

    用如下代码演示生成DOM树的过程:

    <html>
    <body>
    <h1>HelloWorld</h1>
    <div>
      <div>
        <p>picture:</p>
        <img src="example.png"/>
      </div>
      <div>
        <p>A paragraph of explanatory text...</p>
      </div>
    </div>
    </body>
    </html>

    首先树构建器接收到标签解析器发来的起始标签名后,会加入到栈中,图1是解析到<h1>标签的栈中压入的内容,共有<html><body><h1>三个标签,此时还未向DOM树中添加任何结点(图中黑色实线框代表开始标签,红色虚线框代表结束标签,结束标签不会入栈)。

    DOM树构建示例

    继续向下解析,接收到一个</h1>结束标签,此时查询栈顶元素,如果和传入的结束标签属于同种类型的p标签(如图2),则将栈顶元素弹出,向DOM树中加入此节点,然后继续向下解析(如图3)。


    如果遇到的是没有封闭标签的元素如<img/>,则直接加入DOM树中即可,无需入栈。


    依次向下解析,当栈为空,即<html>根节点也加入到DOM树中,DOM树构建完毕。

    参考文章:

    HTML解析里的标记化算法 http://www.nowamagic.net/academy/detail/48110322

    HTML文档解析和DOM树的构建 https://blog.csdn.net/Alan_1550587588/article/details/80297765  

    Cloudflare的HTML解析历史 https://www.4hou.com/posts/jOWY






    转载本站文章《HTML解析里的标记化算法—HTML文档解析和DOM树的构建》,
    请注明出处:https://www.zhoulujun.cn/html/webfront/SGML/htmlBase/2015_1213_366.html