现代浏览器的工作原理2

  categories:资料  author:

来源:互联网

1. 解析 Parsing-general

既然解析是渲染引擎中一个非常重要的过程,我们将稍微深入的研究它。首先简要介绍一下解析。

解析一个文档即将其转换为具有一定意义的结构——编码可以理解和使用的东西。解析的结果通常是表达文档结构的节点树,称为解析树或语法树。

例如,解析“2+3-1”这个表达式,可能返回这样一棵树。

wps_clip_image-30798[3][1]

图5:数学表达式树节点

文法 Grammars

解析基于文档依据的语法规则——文档的语言或格式。每种可被解析的格式必须具有由词汇及语法规则组成的特定的文法,称为上下文无关文法。人类语言不具有这一特性,因此不能被一般的解析技术所解析。

解析器-词法分析器 Parser-Lexer combination

解析可以分为两个子过程——语法分析及词法分析

词法分析就是将输入分解为符号,符号是语言的词汇表——基本有效单元的集合。对于人类语言来说,它相当于我们字典中出现的所有单词。

语法分析指对语言应用语法规则。

解析器一般将工作分配给两个组件——词法分析器(有时也叫分词器)负责将输入分解为合法的符号,解析器则根据语言的语法规则分析文档结构,从而构建解析树,词法分析器知道怎么跳过空白和换行之类的无关字符。

wps_clip_image-1722[3][1]

图6:从源文档到解析树

解析过程是迭代的,解析器从词法分析器处取道一个新的符号,并试着用这个符号匹配一条语法规则, 如果匹配了一条规则,这个符号对应的节点将被添加到解析树上,然后解析器请求另一个符号。如果没有匹配到规则,解析器将在内部保存该符号,并从词法分析器 取下一个符号,直到所有内部保存的符号能够匹配一项语法规则。如果最终没有找到匹配的规则,解析器将抛出一个异常,这意味着文档无效或是包含语法错误。

转换 Translation

很多时候,解析树并不是最终结果。解析一般在转换中使用——将输入文档转换为另一种格式。编译就是个例子,编译器在将一段源码编译为机器码的时候,先将源码解析为解析树,然后将该树转换为一个机器码文档。

wps_clip_image-28701[3][1]

图7:编译流程

解析实例 Parsing example

图5中,我们从一个数学表达式构建了一个解析树,这里定义一个简单的数学语言来看下解析过程。

词汇表:我们的语言包括整数、加号及减号。

语法:

1. 该语言的语法基本单元包括表达式、term及操作符

2. 该语言可以包括多个表达式

3. 一个表达式定义为两个term通过一个操作符连接

4. 操作符可以是加号或减号

5. term可以是一个整数或一个表达式

现在来分析一下“2+3-1”这个输入

第一个匹配规则的子字符串是“2”,根据规则5,它是一个term,第二个匹配的是“2+3”,它符合第2条规则——一个操作符连接两个term,下一次匹配发生在输入的结束处。“2+3-1”是一个表达式,因为我们已经知道“2+3”是一个term,所以我们有了一个term紧跟着一个操作符及另一个term。“2++”将不会匹配任何规则,因此是一个无效输入。

词汇表及语法的定义

词汇表通常利用正则表达式来定义。

例如上面的语言可以定义为:

INTEGER:0|[1-9][0-9]*

PLUS:+

MINUS:-

正如看到的,这里用正则表达式定义整数。

语法通常用BNF格式定义,我们的语言可以定义为:

expression := term operation term

operation := PLUS | MINUS

term := INTEGER | expression

如果一个语言的文法是上下文无关的,则它可以用正则解析器来解析。对上下文无关文法的一个直观的定义是,该文法可以用BNF来完整的表达。可查看http://en.wikipedia.org/wiki/Context-free_grammar。

解析器类型 Types of parsers

有两种基本的解析器——自顶向下解析及自底向上解析。比较直观的解释是,自顶向下解析,查看语法的最高层结构并试着匹配其中一个;自底向上解析则从输入开始,逐步将其转换为语法规则,从底层规则开始直到匹配高层规则。

来看一下这两种解析器如何解析上面的例子:

自顶向下解析器从最高层规则开始——它先识别出“2+3“,将其视为一个表达式,然后识别出”2+3-1“为一个表达式(识别表达式的过程中匹配了其他规则,但出发点是最高层规则)。

自底向上解析会扫描输入直到匹配了一条规则,然后用该规则取代匹配的输入,直到解析完所有输入。部分匹配的表达式被放置在解析堆栈中。

Stack

Input

2 + 3 – 1

term

+ 3 – 1

term operation

3 – 1

expression

- 1

expression operation

1

expression

自底向上解析器称为shift reduce 解析器,因为输入向右移动(想象一个指针首先指向输入开始处,并向右移动),并逐渐简化为语法规则。

自动化解析 Generating parse

解析器生成器这个工具可以自动生成解析器,只需要指定语言的文法——词汇表及语法规则,它就可以生成一个解析器。创建一个解析器需要对解析有深入的理解,而且手动的创建一个由较好性能的解析器并不容易,所以解析生成器很有用。Webkit使用两个知名的解析生成器——用于创建语法分析器的Flex及创建解析器的Bison(你可能接触过Lex和Yacc)。Flex的输入是一个包含了符号定义的正则表达式,Bison的输入是用BNF格式表示的语法规则。rs automatically

HTML解析器 HTML Parser

HTML解析器的工作是将html标识解析为解析树。

HTML文法定义 The HTML grammar definition

W3C组织制定规范定义了HTML的词汇表和语法。

非上下文无关文法 Not a context free grammar

正如在解析简介中提到的,上下文无关文法的语法可以用类似BNF的格式来定义。

不幸的是,所有的传统解析方式都不适用于html(当然我提出它们并不只是因为好玩,它们将用来解析css和js),html不能简单的用解析所需的上下文无关文法来定义。

Html 有一个正式的格式定义——DTD(Document Type Definition 文档类型定义)——但它并不是上下文无关文法,html更接近于xml,现在有很多可用的xml解析器,html有个xml的变体——xhtml,它们间的不同在于,html更宽容,它允许忽略一些特定标签,有时可以省略开始或结束标签。总的来说,它是一种soft语法,不像xml呆板、固执。

显然,这个看起来很小的差异却带来了很大的不同。一方面,这是html流行的原因——它的宽容使web开发人员的工作更加轻松,但另一方面,这也使很难去写一个格式化的文法。所以,html的解析并不简单,它既不能用传统的解析器解析,也不能用xml解析器解析。

HTML DTD

Html适用DTD格式进行定义,这一格式是用于定义SGML家族的语言,包括了对所有允许元素及它们的属性和层次关系的定义。正如前面提到的,html DTD并没有生成一种上下文无关文法。

DTD有一些变种,标准模式只遵守规范,而其他模式则包含了对浏览器过去所使用标签的支持,这么做是为了兼容以前内容。最新的标准DTD在http://www.w3.org/TR/html4/strict.dtd

DOM

输出的树,也就是解析树,是由DOM元素及属性节点组成的。DOM是文档对象模型的缩写,它是html文档的对象表示,作为html元素的外部接口供js等调用。

树的根是“document”对象。

DOM和标签基本是一一对应的关系,例如,如下的标签:

<html>

<body>

<p>

Hello DOM

</p>

<div><imgsrc=”example.png” /></div>

</body>

</html>

将会被转换为下面的DOM树:

wps_clip_image-20335[3][1]

图8:示例标签对应的DOM树

和html一样,DOM的规范也是由W3C组织制定的。访问http://www.w3.org/DOM/DOMTR,这是使用文档的一般规范。一个模型描述一种特定的html元素,可以在http://www.w3.org/TR/2003/REC-DOM-Level-2-HTML-20030109/idl-definitions.htm 查看html定义。

这里所谓的树包含了DOM节点是说树是由实现了DOM接口的元素构建而成的,浏览器使用已被浏览器内部使用的其他属性的具体实现。

解析算法 The parsing algorithm

正如前面章节中讨论的,hmtl不能被一般的自顶向下或自底向上的解析器所解析。

原因是:

1. 这门语言本身的宽容特性

2. 浏览器对一些常见的非法html有容错机制

3. 解析过程是往复的,通常源码不会在解析过程中发生改变,但在html中,脚本标签包含的“document.write ”可能添加标签,这说明在解析过程中实际上修改了输入

不能使用正则解析技术,浏览器为html定制了专属的解析器。

Html5规范中描述了这个解析算法,算法包括两个阶段——符号化及构建树。

符号化是词法分析的过程,将输入解析为符号,html的符号包括开始标签、结束标签、属性名及属性值。

符号识别器识别出符号后,将其传递给树构建器,并读取下一个字符,以识别下一个符号,这样直到处理完所有输入。

wps_clip_image-4797[3][1]

图9:HTML解析流程

符号识别算法 The tokenization algorithm

算法输出html符号,该算法用状态机表示。每次读取输入流中的一个或多个字符,并根据这些字符转移到下一个状态,当前的符号状态及构建树状态共同影响结果,这意味着,读取同样的字符,可能因为当前状态的不同,得到不同的结果以进入下一个正确的状态。

这个算法很复杂,这里用一个简单的例子来解释这个原理。

基本示例——符号化下面的html:

<html>

<body>

Hello world

</body>

</html>

初始状态为“Data State”,当遇到“<”字符,状态变为“Tag open state”,读取一个a-z的字符将产生一个开始标签符号,状态相应变为“Tag name state”,一直保持这个状态直到读取到“>”,每个字符都附加到这个符号名上,例子中创建的是一个html符号。

当读取到“>”,当前的符号就完成了,此时,状态回到“Data state”,“<body>”重复这一处理过程。到这里,html和body标签都识别出来了。现在,回到“Data state”,读取“Hello world”中的字符“H”将创建并识别出一个字符符号,这里会为“Hello world”中的每个字符生成一个字符符号。

这样直到遇到“</body>”中的“<”。现在,又回到了“Tag open state”,读取下一个字符“/”将创建一个闭合标签符号,并且状态转移到“Tag name state”,还是保持这一状态,直到遇到“>”。然后,产生一个新的标签符号并回到“Data state”。后面的“</html>”将和“</body>”一样处理。

wps_clip_image-18933[3][1]

图10:符号化示例输入

树的构建算法 Tree construction algorithm

在树的构建阶段,将修改以Document为根的DOM树,将元素附加到树上。每个由符号识别器识别生成的节点将会被树构造器进行处理,规范中定义了每个符号相对应的Dom元素,对应的Dom元素将会被创建。这些元素除了会被添加到Dom树上,还将被添加到开放元素堆栈中。这个堆栈用来纠正嵌套的未匹配和未闭合标签,这个算法也是用状态机来描述,所有的状态采用插入模式。

来看一下示例中树的创建过程:

<html>

<body>

Hello world

</body>

</html>

构建树这一阶段的输入是符号识别阶段生成的符号序列。

首先是“initial mode”,接收到html符号后将转换为“before html”模式,在这个模式中对这个符号进行再处理。此时,创建了一个HTMLHtmlElement元素,并将其附加到根Document对象上。

状态此时变为“before head”,接收到body符号时,即使这里没有head符号,也将自动创建一个HTMLHeadElement元素并附加到树上。

现在,转到“in head”模式,然后是“after head”。到这里,body符号会被再次处理,将创建一个HTMLBodyElement并插入到树中,同时,转移到“in body”模式。

然后,接收到字符串“Hello world”的字符符号,第一个字符将导致创建并插入一个text节点,其他字符将附加到该节点。

接收到body结束符号时,转移到“after body”模式,接着接收到html结束符号,这个符号意味着转移到了“after after body”模式,当接收到文件结束符时,整个解析过程结束。

wps_clip_image-29204[3][1]

图11:示例html树的构建过程

解析结束时的处理 Action when the parsing is finished

在这个阶段,浏览器将文档标记为可交互的,并开始解析处于延时模式中的脚本——这些脚本在文档解析后执行。

文档状态将被设置为完成,同时触发一个load事件。

Html5规范中有符号化及构建树的完整算法(http://www.w3.org/TR/html5/syntax.html#html-parser)。

浏览器容错 Browsers error tolerance

你从来不会在一个html页面上看到“无效语法”这样的错误,浏览器修复了无效内容并继续工作。

以下面这段html为例:

<html>

<mytag>

</mytag>

<div>

<p>

</div>

Really lousy HTML

</p>

</html>

这段html违反了很多规则(mytag不是合法的标签,p及div错误的嵌套等等),但是浏览器仍然可以没有任何怨言的继续显示,它在解析的过程中修复了html作者的错误。

浏览器都具有错误处理的能力,但是,另人惊讶的是,这并不是html最新规范的内容,就像书签及前进后退按钮一样,它只是浏览器长期发展的结果。一些比较知名的非法html结构,在许多站点中出现过,浏览器都试着以一种和其他浏览器一致的方式去修复。

Html5规范定义了这方面的需求,webkit在html解析类开始部分的注释中做了很好的总结。

解析器将符号化的输入解析为文档并创建文档,但不幸的是,我们必须处理很多没有很好格式化的html文档,至少要小心下面几种错误情况。

1. 在未闭合的标签中添加明确禁止的元素。这种情况下,应该先将前一标签闭合

2. 不能直接添加元素。有些人在写文档的时候会忘了中间一些标签(或者中间标签是可选的),比如HTML HEAD BODY TR TD LI等

3. 想在一个行内元素中添加块状元素。关闭所有的行内元素,直到下一个更高的块状元素

4. 如果这些都不行,就闭合当前标签直到可以添加该元素。

下面来看一些webkit容错的例子:

</br>替代

一些网站使用</br>替代<br>,为了兼容IE和Firefox,webkit将其看作<br>。

代码:

if(t->isCloseTag(brTag) && m_document->inCompatMode()) {

reportError(MalformedBRError);

t->beginTag =true;

}

Note-这里的错误处理在内部进行,用户看不到。

迷路的表格

这指一个表格嵌套在另一个表格中,但不在它的某个单元格内。

比如下面这个例子:

<table>

<table>

<tr><td>inner table</td></tr>

</table>

<tr><td>outer table</td></tr>

</table>

webkit将会将嵌套的表格变为两个兄弟表格:

<table>

<tr><td>outer table</td></tr>

</table>

<table>

<tr><td>inner table</td></tr>

</table>

代码:

if(m_inStrayTableContent && localName == tableTag)

popBlock(tableTag);

webkit使用堆栈存放当前的元素内容,它将从外部表格的堆栈中弹出内部的表格,则它们变为了兄弟表格。

嵌套的表单元素

用户将一个表单嵌套到另一个表单中,则第二个表单将被忽略。

代码:

if(!m_currentFormElement) {

m_currentFormElement =newHTMLFormElement(formTag, m_document);

}

太深的标签继承

http://www.liceo.edu.mx/是一个由嵌套层次的站点的例子,最多只允许20个相同类型的标签嵌套,多出来的将被忽略。

代码:

boolHTMLParser::allowNestedRedundantTag(constAtomicString& tagName)

{

unsigned i = 0;

for(HTMLStackElem* curr = m_blockStack;

i < cMaxRedundantTagDepth && curr && curr->tagName == tagName;

curr = curr->next, i++) { }

returni != cMaxRedundantTagDepth;

}

放错了地方的html、body闭合标签

又一次不言自明。

支持不完整的html。我们从来不闭合body,因为一些愚蠢的网页总是在还未真正结束时就闭合它。我们依赖调用end方法去执行关闭的处理。

代码:

if(t->tagName == htmlTag || t->tagName == bodyTag )

return;

所以,web开发者要小心了,除非你想成为webkit容错代码的范例,否则还是写格式良好的html吧。

原文: http://taligarsiel.com/Projects/howbrowserswork1.htm

翻译:http://blog.csdn.net/zzzaquarius/article/details/6532299



快乐成长 每天进步一点点      京ICP备18032580号-1