浅谈Sizzle的“编译原理”

Sizzle，是jQuery作者John Resig写的DOM选择器引擎，速度号称业界第一。作为一个独立全新的选择器引擎，出现在jQuery 1.3版本之后，并被John Resig作为一个开源的项目。Sizzle是独立的一部分，不依赖任何库，如果你不想用jQuery，可以只用Sizzle，也可以用于其他框架如：Mool, Dojo，YUI等。

前几天在准备一个关于jQuery的分享PPT，问同事关于jQuery除了使用方法之外还有没有其他特别想了解一下的，有人提到了想了解下它的选择器是怎么实现的，也有人提到jQuery的查询速度跟其他框架比怎么样。关于速度，sizzle的官方网站上可以下载测试的例子，速度确实很有优势。但是它为什么会有这样高效的运行速度，就跟这里想探讨的实现原理有关系了。

在了解Sizzle之前必须要先了解它的选择器是怎么回事，这里有一个简单的例子，熟悉jQuery的同学也一定很熟悉这样的选择器格式：

代码如下:
tag #id .class , a:first

它基本上是从左到右层层深入过滤去查找匹配的dom元素，这个语句还不算复杂。假设我们自己来实现这一条查询语句的话，也不难。但是，查询语句只有基本的规则，没有固定的选择符个数和顺序，我们自己写代码怎样能适应这种随意的排列组合？Sizzle就能做到各种情况的正常解析、执行。

Sizzle的源码确实错综复杂不容易理清楚它的思路。先抛开外面层层的包裹，直接看看我个人认为整个实现里很核心的三个方法：

第一个核心方法。源码第1052行有一个tokenize函数：

代码如下:
function tokenize(selector, parseOnly ) { }

第二个参数parseOnly为false的意思是只做token序列化操作，不返回结果，这个情况下序列化的结果会被缓存起来备用。Selector就是查询语句了。

经过这个函数处理后，比如selector="#idtag.class , a:first"传进去，可以得到一个格式类似于下面的结果：

[[{matches:" id ",type:"ID"},{matches:" tag ",type:"TAG"},{matches:" class ",type:"CLASS"},...],[    {matches:" a",type:"TAG"},    ...],[…],…]

看到tokenize这个函数的命名和它的作用，让我很容易就联想起“编译原理”这个词了。这里就有点像是词法分析了，不过这个词法分析比程序编译时做的词法分析简单。

tokenize方法会根据selector里面的逗号，空格和关系选择符的正则表达式做“分词”，得到一个二维数组(请允许我冒用这个不是很准确的称呼)，其中第一维数组是根据逗号分隔出来的，在源代码里面被称作groups。

我们再看源代码第405行开始有一个Expr = Sizzle.selectors = {}的定义，其中到567行的时候有一个filter的定义，这里我们能找到基本的过滤类型："ID"、"TAG"、"CLASS"、"ATTR"、"CHILD"、"PSEUDO"，tokenize最终分类出来的type也就是这几种。