三、解析和DOM树的构建 1、解析： 由于解析渲染引擎是一个非常重要的过程，我们将会一步步的深入，现在让我们来介绍解析。 解析一个文档，意味着把它转换为一个有意义的结构——代码可以了解和使用的东西，解析 的结果通常是一个树的节点集合，用来表示文档结构，它被称为解析树或者语法树。 例子： 解析表达式“2+3-1”，返回树如下图3.1
1)、语法： 解析是基于文档所遵循的语法规则——书写所用的语言或格式——来进行的。每一种可以解析的格式必须由确定的语法与词汇组成。这被称之为上下文无关语法。 人类语言并非此种语言，所以不能用常规的解析技术来解析。 2)、解析器——分析器组合： 解析器有两个处理过程——词法分析与语法分析。 词法分析负责把输入切分成符号序列，符号是语言的词汇——由该语言所有合法的单词组成。语法分析是对该语言语法法则的应用。 解析器通常把工作分给两个组件——词法分析程序（有时被叫分词器）负责把输入切分成合法符号序列，解析器负责按照语法规则分析文档结构和构建语法树。 词法分析程序知道如何过滤像空格，换行之类的无关字符。如下图3.1.2
解析过程是迭代的。解析器通常会从词法分析器获取新符号并尝试匹配句法规则。如果匹配成功，就在句法树上创建相应的节点，并继续从词法分析器获取下一个符号。 如果没有匹配的规则，解析器会内部保存这个符号，并继续从词法分析器获取符号，直到内部保存的所有符号能够成功匹配一个规则。 如果最终无法匹配，解析器会抛出异常。这意味着文档无效，含有句法错误。 3)、转换： 多数情况下，解析树并非是最终结果，解析经常被用于转换——输入文档转换为另一种格式，比如一个编译器要把源码编译成机器码，首先会解析成解析树，然后再转换成机器码，如下图3.1.3
4)、解析示例： 在图3.1中，我们构建了一个数学表达式解析树，让我们来试着定义一个简单的数学语言并看看解析是如何进行的。 词汇：我们的语言可以包含整数、加号和减号。 语法： 1>.语法由表达式、术语和操作符组成 2>.我们的语言能包含任何数字类型的表达式 3>.表达式定义为术语紧跟着操作符，再跟另外一个术语。 4>.操作符为一个加号和一个减号 5>.术语是一个整数或者表达式 现在让我们来分析输入“2+3-1”： 第一个符合规则的子字符串是”2″，根据规则#5它是一个术语。第二个匹配是”2 + 3″，符合第二条规则——一个术语紧跟一个操作符再跟另外一个术语。下一个匹配出现在输入结束时。”2 + 3 – 1″是一个表达式，因为我们已知“2+3”是一个术语，所以符合第二条规则。 “2 + + “不会匹配任何规则，所以是无效的输入。 5)、词法与句法的合法性定义： 词汇通常用正则表达式来表示。 比如我们的语言可以定义为: 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 6)、解析器的类型： 解析器有两种基本类型——自上而下解析器和自下而上解析器。主观上可以认为自上而下的解析器从上层句法结构开始尝试匹配句法；自下而上的则从输入开始，慢慢转换成句法规则，从底层规则开始，直到上层规则全部匹配。 让我们看看这两种解析器将怎样解析我们的例子： 自上而下解析器从上层规则开始，它会把”2 + 3″定义为表达式，然后定义”2 + 3 – 1″为表达式(定义表达式的过程中也会匹配其它规则，但起点是最高级别规则)。 自下而上的解析器会扫描输入，直到有匹配的规则，它会把输入替换成规则。这样一直到输入结束。部分匹配的规则会放入解析堆栈。如下图：3.1.6
7)自动创建解析器 有一些工具可以为你创建解析器，它们通常称为解析器生成器。你只需要提供语法——词汇与句法规则——它就能生成一个可以工作的解析器。创建解析器需要对解析器有深入的了解，并且手动创建一个优化的解析器并不容易，所以解析器生成工具很有用。 Webkit使用两款知名的解析器生成工具：Flex用于创建词法分析器，Bison用于创建解析器 (你也许会看到它们以Lex和Yacc的名字存在)。Flex的输入文件是符号的正则表达式定义，Bison的输入文件是BNF格式的句法定义。 2.HTML解析器： HTML解析器的工作是解析HTML标记到解析树 1)HTML语法定义 HTML的词汇与句法定义在w3c组织创建的规范中。当前版本是HTML4，HTML5的工作正在进行中。 2)不是上下文无关语法 在对解析器的介绍中看到，语法可以用类似BNF的格式规范地定义。不幸的是所有常规解析器的讨论都不适用于HTML（我提及它们并不是为了娱乐，它们可以用于解析CSS和JavaScript）。HTML无法用解析器所需的上下文无关的语法来定义。过去HTML格式规范由DTD (Document Type Definition)来定义，但它不是一个上下文无关语法。 HTML与XML相当接近。XML有许多可用的解析器。HTML还有一个XML变种叫XHTML，那么它们主要区别在哪里呢？区别在于HTML应用更加”宽容”，它容许你漏掉一些开始或结束标签等。它整个是一个“软”句法，不像XML那样严格死板。 总的来说这一看似细微的差别造成了两个不同的世界。一方面这使得HTML很流行，因为它包容你的错误，使网页作者的生活变得轻松。另一方面，它使编写语法格式变得困难。所以综合来说，HTML解析并不简单，现成的上下文相关解析器搞不定，ＸＭＬ解析器也不行。 3)HTML DTD HTML的定义使用DTD文件。这种格式用来定义SGML族语言，它包含对所有允许的元素的定义，包括它们的属性和层级关系。如我们前面所说，HTML DTD构不成上下文无关语法。 DTD有几种不同类型。严格模式完全尊守规范，但其它模式为了向前兼容可能包含对早期浏览器所用标签的支持。当前的严格模式ＤＴＤ：http://www.w3.org/TR/html4/strict.dtd 4)DOM 解析器输出的树是由DOM元素和属性节点组成的。DOM的全称为：Document Object Model。它是HTML文档的对象化描述，也是HTML元素与外界（如Javascript）的接口。 DOM与标签有着几乎一一对应的关系，如下： <html> <body> <p>hello world</p> <div><img src="aa.png"/></div> </body> </html> 其对应的DOM树如下3.2.4图：
与HTML一样，DOM规范也由w3c组织制订。参考：http://www.w3.org/DOM/DOMTR. 这是一个操作文档的通用规范。有一个专门的模块定义HTML特有元素: http://www.w3.org/TR/2003/REC-DOM-Level-2-HTML-20030109/idl-definitions.html. 当我们说树中包含DOM节点时，意思就是这个树是由实现了DOM接口的元素组成。这些实现包含了其它一些浏览器内部所需的属性。
5)解析算法
正如我们前面章节中看到，HTML不能使用常规的自上而下或者自下而上的解析器解析，其原因如下：
a>HTML是一种宽容性的语言
b>事实上，浏览器有传统的误差允许，以支持众所周知的情况下无效的HTML标签。
c>解析过程往复。通常在分析过程中，源一般不更改，但在的HTML脚本中含有“document.write”的标签可以添加额外的标记，所以在分析过程中实际上修改了输入。
无法使用常规的解析技术，浏览器创建自定义的解析器解析HTML。
在HTML5中这个解析算法被描述的很详细，该算法包含两个阶段——标记化算法和树构造算法，符号化是词法分析，语法分析令牌投入。其中HTML标记的开始标记，结束标记，属性名和属性值。
记号赋予识别令牌，将其提供给树构造和消耗的下一个字符的识别等等，直到输入下一个标记结束。如下3.2.5图（HTML解析流量（取自HTML5规范））
6)标记化算法 该算法的输出是一个HTML标记。该算法被表示为一个状态机。每个状态消耗的一个或多个字符输入流，根据这些字符更新下一个状态。这个决定是由当前的标记化状态和树建设状态的影响。这意味着在下一个正确的状态下消耗相同的字符会产生不同的结果， 这取决于当前的状态。算法越复杂，越充分，所以让我们来看看一个简单的例子，帮助我们进一步的理解。 基本的例子 - 标记化下面的HTML： <HTML> <BODY> 世界，你好 </BODY> </HTML> 初始状态是”Data state”，当遇到”<”时状态改为“Tag open state”。吃掉”a-z”字符组成的符号后产生了”Start tag token”，状态变更为“Tag name state”。我们一直保持此状态，直到遇到”>”。每个字符都被追加到新的符号名上。在我们的例子中，解出的符号就是”html”。 当碰到”>”时，当前符号完成，状态改回“Data state”。”<body>”标签将会以同样的方式处理。现在”html”与”body”标签都完成了，我们回到“Data state”状态。吃掉”H”（”Hello world”第一个字母）时会产生一个字符符号，直到碰到”</body>”的”<”符号，我们就完成了一个字符符号”Hello world”。 现在我们回到“Tag open state”状态。吃掉下一个输入”/”时会产生一个”end tag token”并变更为“Tag name state”状态。同样，此状态保持到我们碰到”>”时。这时新标签符号完成，我们又回到“Data state”。同样”</html>”也会被这样处理。具体流程如下图：3.2.6（输入源的分词处理）：
当解析器被创建时，文档对象也被创建了。在树的构建过程中DOM树的根节点（Documen）将被修改，元素被添加到上面去。每个分词器完成的节点都会被树构建器处理。规范中定义了每一个符号与哪个DOM对象相关。除了把元素添加到DOM树外，它还会被添加到一个开放元素堆栈。这个堆栈用于纠正嵌套错误和标签未关闭错误。这个算法也用状态机描述，它的状态叫做”insertion modes”。 让我们看看下面输入的树构建过程： <html> <body> Hello world </body> </html>树的构建过程中，输入就是分词过程中得到的符号序列。第一个模式叫“initial mode”。接收 html 符号后会变成“before html”模式并重新处理此模式中的符号。这会创建一个HTMLHtmlElement元素并追加到根文档节点。 然后状态改变为“before head”。我们收到”body”时，会隐式创建一个HTMLHeadElement，尽管我们没有这个标签，它也会被创建并添加到树中。 现在我们进入“in head”模式，然后是“after head”，Body会被重新处理，创建HTMLBodyElement元素并插入，然后进入“in body”模式。字符符号”Hello world”收到后会创建一个”Text”节点，所有字符都被一一追加到上面。收到body结束标签后进入 “after body” 模式，收到html结束标签后进入“after after body”模式。所有符号处理完后将终止解析。 如下图3.2.7（HTML树的创建）
8)当解析完成后的动作
在这一阶段浏览器会把文档标记为交互模式，并开始解析deferred模式的script。”deferred”意味着脚本应该在文档解析完成后执行。脚本处理完成后将进入”complete”状态，”load”事件发生。
HTML5规范中包含了完整的算法： http://www.w3.org/TR/html5/syntax.html#html-parser
9)浏览器容错
你永远不会看到HTML页面语法错误。浏览器会修正错误并继续。看看下面的例子：
<html>
<mytag>
</mytag>
<div>
<p>
</div>
Really lousy HTML
</p>
</html>
我一定违背了几百万条规则（”my tag”是非法标签，”p”与”div”元素嵌套错误等等），但浏览器仍然正确地显示，没有任何抱怨。所以很多解析器代码在修正这些HTML作者的错误。
浏览器的错误处理相当统一，惊人的是这并不是当前HTML规范的一部分，就像书签、前进、后退，只是多年以来在浏览器中开发出来的。有些无效的HTML结构出现在许多网站，浏览器会尝试用和其它各种浏览器一致的方式修复这些错误。
HTML5规范中应这一需求定义了一些东西，Webkit在它的HTML解析器类开头的注释中很好的做了摘要：
解析器分析输入符号生成文档，并构建文档树。如果文档格式良好，解析工作会很简单。不幸的是，我们要处理很多格式不良的HTML文档，解析器需要宽容这些错误。我们至少需要照顾下列错误：1. 元素必需被插入在正确的位置。未关闭的标签应该一一关闭，直到可以添加新元素。2. 不允许直接添加元素。用户可能会漏掉一些标签，比如：HTML HEAD BODY TBODY TR TD LI（我遗漏了什么？）。3. 在inline元素里添加block元素时，应关闭所有inline元素，再添加block元素。4. 如果以上不起作用，关闭所有元素，直到可以添加，或者忽略此标签。让我们来看一些Webkit容错的例子：
使用</br>代替<br>
有些站点使用</br>而不是<br>。为了更好的与IE和Firefox兼容，Webkit将其视为<br>。代码如下：
if (t->isCloseTag(brTag) && m_document->inCompatMode()) {
reportError(MalformedBRError);
t->beginTag = true;
}注意，这里的错误处理是内部的，并不会显示给用户。
迷失的表格
像下面的例子这样，一个表格包含在另外一个表格的内容中，但不是在外部表格的单元格里:
<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 = new HTMLFormElement(formTag, m_document);
}
过深的元素层级
注释不言自喻：
www.liceo.edu.mx是一个层级过深的典型，它用大量的<b>嵌套到1500个标签的深度。我们只允许同一标签连续出现20次，超过的话，所有此标签都会被忽略。bool HTMLParser::allowNestedRedundantTag(const AtomicString& tagName)
{
unsigned i = 0;
for (HTMLStackElem* curr = m_blockStack;
i < cMaxRedundantTagDepth && curr && curr->tagName == tagName;
curr = curr->next, i++) { }
return i != cMaxRedundantTagDepth;
}错误的html或body结束标签位置
注释仍然很明了：
支持真正的错误html
我们永远不关闭tag，因为有些愚蠢的网页在文档真正结束之前就关闭了它。
让我们用end()来关闭标签。if (t->tagName == htmlTag || t->tagName == bodyTag )
return;
所以网页作者们小心了，除非你想写一个Webkit容错的示例代码，否则请按正确格式书写HTML。
3.CSS解析
记得在介绍中的解析概念吗？CSS不像HTML，它是一个与上下文无关语法和能被在介绍中的解析器类型解析，其实CSS规范定义CSS的词法和句法语法。
让我们看一些例子：
每一个标记的词法语法通过一些正则表达式来定义：
注释 \/\*[^*]*\*+([^/*][^*]*\*+)*\/
数字 [0-9]+|[0-9]*"."[0-9]+
非AscII码 [\200-\377]
nmstart [_a-z]|{nonascii}|{escape}
nmchar [_a-z0-9-]|{nonascii}|{escape}
名称 {nmchar}+
ident {nmstart}{nmchar}*
ident 是一个短标记符，像一个类型一样，名称是一个元素的id
BNF中的句法描述如下：
ruleset
: selector [ ',' S* selector ]*
'{' S* declaration [ ';' S* declaration ]* '}' S*
;
selector
: simple_selector [ combinator selector | S+ [ combinator selector ] ]
;
simple_selector
: element_name [ HASH | class | attrib | pseudo ]*
| [ HASH | class | attrib | pseudo ]+
;
class
: '.' IDENT
;
element_name
: IDENT | '*'
;
attrib
: '[' S* IDENT S* [ [ '=' | INCLUDES | DASHMATCH ] S*
[ IDENT | STRING ] S* ] ']'
;
pseudo
: ':' [ IDENT | FUNCTION S* [IDENT S*] ')' ]
;
看一个列子
div.error , a.error{
color:red;
font-weight:bold;
}
div.error,a.error是选择器，在大括号内的部分包含这个规则集中的应用的规则。这种结构是在下面定义中正式定义：
ruleset
: selector [ ',' S* selector ]*
'{' S* declaration [ ';' S* declaration ]* '}' S*
;
这意味着一个规则集是一个选择器或可选数字选择器，这些选择器被coma和空格（S代表空格）分隔。规则集包含大括号内声明或可选的声明，这些声明用分号隔开。“声明”和“选择”将被定义在下面的BNF定义。
webkit CSS解析器：
webkit 使用 flex 和 bison 解析器发生器从CSS 语法文件去自动创建解析器，在解析器介绍中，bison创建一个自下而上的解析器。Firefox使用自上而下的手工编写解析器。在这两种情况下，每一个CSS文件被解析到一个样式表对象，每个对象都包含CSS规则。CSS规则对象包含选择器和声明对象和其他对象相对应的CSS语法。
如下图3.3（解析CSS）
4.解析脚本 将在javascript一章中详细介绍 5.处理脚本和样式表的顺序 脚本： web模式是同步模式，作者们期望当解析器解析到一个<script>标签时，脚本能被解析和立即执行。脚本被执行，文档的解析暂停，如果<script>脚本是由外部引入的，必须先从网络上获取——这也是同步的，解析暂停，直到资源被获取。这是多年来使用的模式，也被写入到HTML4和HTML5规范中。 作者可以给<script>标签添加一个defer=”defer“属性，这样不会暂停文档解析，文档解析完成后，再执行脚本。 HTML5，增加给<script>增加了一个属性async,可以使文档的解析和脚本的执行在不同的线程。 投机性解析： WebKit和火狐都这样做优化。执行脚本时，另一个线程解析文档的其余部分，并找出需要从网络加载的其他资源，并加载它们。在这些方式的资源可以被并行链接加载的整体速度是更好的。注意 - 投机解析器不修改DOM树，节点，主分析器，它仅仅解析外部脚本，样式表和图片等外部资源的引用。 样式表： 样式表在另一方面有不同的模式，从概念上讲，它似乎是因为样式表没有改变的DOM树，没有任何理由等待和停止解析文档。有一个问题，当文档解析时脚本访问样式信息，如果样式么有加载和解析，脚本将会得到错误的回答以及会引起一系列问题。这看起来像一种边缘情况，但是相当普遍， 火狐中有一个样式表一直在加载和解析时，会阻止所有脚本。Webkit的块的脚本，只有当他们试图访问某些可能卸载样式表的样式属性影响时，才会阻止所有脚本。