3.4 词法分析
下面从浏览器的词法分析开始，来探究Sizzle选择器引擎的设计原理。
3.4.1 浏览器解析概述
网页从加载到显示是一个复杂的过程，主要包含两个阶段：重绘和重排。各浏览器引擎的工作原理虽略有不同，但基本规则都是一样的。
第1步，当文档初次加载时，引擎会解析HTML文档，构建DOM树。
第2步，根据DOM元素的几何属性，构建一个用于渲染的树。
提示：渲染树的每个节点都有大小和边距等属性，即CSS盒模型。由于隐藏元素不需要显示，渲染树中不包含DOM树中隐藏的元素。
第3步，当构建完渲染树，浏览器就将元素放置到正确的位置，再根据渲染树节点的样式属性在页面中进行绘制。
提示：在默认情况下，浏览器采用流布局，对渲染树的计算通常只需遍历一次就可以完成。
【示例1】一个简单的HTML文档解析成DOM树后，结构如下：
如果想要操作其中的checkbox，需要有一种表达方式，使得通过这个表达式让浏览器知道要操作的节点。这个表达式就是CSS选择器，它可以这样表示：
div > p+.sub input[type="checkbox"]
简单描述就是，在div子元素中找到p，再找到它的相邻兄弟节点，节点的class为sub，然后在它的后代元素中找input元素，且其属性type为checkbox。
使用CSS 3的读者都应该知道，CSS 3选择器的类型是非常多的，其组合形式也是千变万化。但是对于JavaScript引擎来说，最终都会通过下述接口来实现查找。
另外，高级浏览器还提供下述接口：
由于低级浏览器未提供这些高级接口，所以才催生了Sizzle CSS选择器引擎。Sizzle引擎提供的接口与document.querySelectorAll是一样的，都是根据CSS选择器字符串匹配符合规则的DOM节点列表，因此首先要分析这个输入的选择器。
【示例2】在页面中设计4段文本，然后引入Sizzle引擎，输入下面JavaScript脚本，使用浏览器查看，在控制台可以看到相同的查询结果，如图3.3所示。
图3.3 使用Sizzle和querySelectorAll分别查询span元素
使用Sizzle查询的结果为一个Array，包含一个元素，为<span class='red'>；使用querySelectorAll查询的结果为NodeList，包含一个元素，为<span class='red'>。虽然返回数据类型不同，一个是数组，另一个是类数组，但是它们都是数据集合，可以相互转换。
3.4.2 CSS选择器解析顺序
HTML经过解析后，生成DOM树；在CSS解析后，将解析结果与DOM树进行分析，建立渲染树，最后在页面上绘图。
渲染树中的元素与DOM树中的元素相对应，但不是一一对应：一个DOM元素可能会对应多个渲染树中的元素。例如，文本折行后，不同的行会成为渲染树中不同的元素；也有DOM元素被渲染树忽略，如display:none的元素。
在建立渲染树时，浏览器根据CSS的解析结果，要为每个DOM元素确定生成怎样的渲染元素。对于每个DOM元素，必须在所有样式规则中找到符合的CSS选择器，并将对应的规则进行合并层叠。CSS选择器的解析实际上就是在这里执行的。在遍历DOM树时，从样式规则中查找对应的渲染元素。
在HTML文档中，样式规则数量可能会很庞大，也可能不会匹配到当前的DOM元素，因此浏览器一般会建立样式规则索引树，这时如何快速判断一个CSS选择器不匹配当前元素，是极其重要的。
浏览器解析方式有以下两种：
（1）正向匹配。例如，div div p em，先在HTML中检查当前元素，找到最上层的div后再往下找，如果遇到不匹配的元素，就必须返回到最上层的div，然后往下匹配选择器中的第一个div，回溯若干次后，才能确定匹配与否，执行效率很低。
（2）逆向匹配。如果当前的DOM元素是div，而不是em，那么只要一步就能排除。只有在匹配时，才会不断向上找父节点进行验证。
由于匹配的情况远远低于不匹配的情况，所以逆向匹配带来的优势是很大的。在这种情况下，尾部选择符越具体，执行效率就越高。如果在选择器尾部加上通配符“*”，就会大大降低这种优势。
总之，浏览器从右到左进行查找的优势是可以尽早过滤掉一些无关的样式规则和元素。
【示例】以3.4.1节示例为基础，解析下面CSS选择器字符串。
div > div.sub p span.red
如果从左到右进行查找，则解析步骤如下：
第1步，先找到所有div元素。
第2步，在第1个div元素内找到所有div子元素，且class为sub。
第3步，按顺序逐层匹配p span.red元素。
第4步，如果遇到不匹配的情况，就要回溯到开始点div或者p元素，然后搜索下个节点，依次重复操作。
这种方式对于一个只匹配很少节点的选择器来说，效率是极低的，因为花费了大量时间在回溯匹配不符合规则的节点。
如果从右到左进行查找，则解析步骤如下：
第1步，先查找所有<span class='red'>元素。
第2步，在匹配到的节点中进行过滤，逐个判断左侧相邻节点是否为p，这样可以过滤掉部分元素，只有符合当前的子规则才会再匹配上一条子规则。
第3步，依此类推，逐层上溯，进行过滤。
对于DOM树来说，一个元素可能包含若干子元素，如果每个都去判断显然性能很低；而一个子元素只有一个父元素，所以过滤的速度会非常快。
所以，浏览器在解析CSS选择器时就是根据从右到左的算法去解析。
3.4.3 CSS选择器解析机制
JavaScript解析过程包含两个阶段：预编译和执行阶段。在预编译期，通过词法分析、语法分期，完成对规则的预处理。
Sizzle对CSS选择器的解析也借用了JavaScript的解析思路。CSS选择器是一串字符串，Sizzle先通过词法分析，找出这段字符串对应的规则。在Sizzle中，词法分析主要定义了一个tokenize处理器，用来对CSS选择器进行词法分组。
【示例】下面以3.4.1节示例为基础简单分析tokenize的处理结果。
第1步，在Sizzle源码中找到下面一行代码：
if ( (support.qsa = rnative.test( document.querySelectorAll )) ) {
修改为下面形式：
if ( (support.qsa =false && rnative.test( document.querySelectorAll )) ) {
目的：阻止浏览器优先使用querySelectorAll接口，rnative.test(document.querySelectorAll)用来获取当前浏览器是否支持querySelectorAll，然后把检测结果存入support.qsa，后面代码将根据这个标志变量决定是否优先调用querySelectorAll()方法。如果该属性值为false，则Sizzle将采用过去的算法进行设计，这样读者才可以观察到tokenize处理器的工作状态。
第2步，在IE浏览器中预览test1.html。
第3步，按F12键，打开开发工具窗口，切换到“脚本”选项卡。
第4步，选择sizzle.js，在搜索文本框中输入“tokens.push”，在源代码中找到该行代码。
第5步，在窗口左侧边沿单击，添加一个断点，以便实时进行观察。
第6步，在工具栏中单击“启动测试”按钮，准备测试。
第7步，在窗口右侧面板选择“监视”选项卡，分别增加4个变量，如图3.4所示。
图3.4 使用调试工具进行调试
第8步，在IE浏览器中单击“刷新”按钮，开始调试代码。
第9步，在调试窗口中连续单击“继续”按钮（按F5键），可以在“监视”面板中观察到变量的变化过程，如图3.5所示。
图3.5 监视变量变化过程
经过tokenize处理器处理后分解为一个数组对象（tokens），每个元素（token）为一个匹配对象。Sizzle的Token格式如下：
Token:{
value:'匹配到的字符串',
type:'对应的Token类型',
matches:'正则匹配到的一个结构'
}
Sizzle获取到匹配后的结构Token，就可以进行后期相关处理。
3.4.4 tokenize处理器
tokenize处理器是一个词法解析函数。通过词法解析，分解CSS选择器字符串形成组，每组再按序分解选择符。
参数说明如下：
selector：CSS选择器字符串。
parseOnly：是否仅做语法解析。如果为true，则仅做语法解析，函数返回0；否则返回一个选择器字符串分组的二维数组。
tokenize处理器返回一个Token序列的二维数组groups；数组元素为tokens数组，tokens数组是一个token序列，每个token是一个对象。token对象的格式如下：
{
value:'匹配到的字符串', //如"div"
type:'对应的Token类型', //如"TAG"
matches:'正则匹配到的一个结构', //如["div", index: 0, input: "div > div.sub p span.red"]
}
【示例】假设传入CSS选择器为“div > p+.sub[type="checkbox"], #id:first-child”，可以分为两个规则，即“div > p+.sub[type="checkbox"]”和“#id:first-child”，则groups对象数组长度为2。
完整代码如下：
例如，针对“title,div > :nth-child(even)”选择器，解析后的分组信息如下：
有多少个分组选择器，就有多少个数组，数组里面包含拥有value与type的对象。