«

»

浏览器的分析与DOM树构造

浏览器 渲染 分析上一节我们讨论了两种渲染引擎的基本工作流程。这一节开始,我们将对流程中的每个步骤进行更详细的说明。因为分析是浏览器渲染引擎里非常重要的过程,我们会更深入的关注一下它里面的细节。我们先从一个小小的介绍开始。分析一个文档意味着把它翻译成一些有意义的结构—有时是一些能够理解和使用的代码。分析产生的结果通常是一棵代表着文档结构的由各种结点组成的树。这被称为分析树或是语法树。

例如,分析表达式“2+3-1”可能返回这个树:

浏览器的分析与DOM树构造

图5:数学表达式树节点

语法

分析要遵循文档的语法规则—它用何种语法或格式编写的。每种你能分析的格式必须有确定的语法,由词汇和语法规则组成。它被称为上下文无关语法。人类语言不是这类语言,因此不能用传统分析技术处理。

分析器—词法分析器的组合

分析可以分成两个子过程—词法分析和语法分析。

词法分析是把输入分拆成语言符号的过程。语言符号是语言的词汇—有效结构的集合。在人类语言中它会包含该种语言的字典中出现的所有单词。

语法分析是语言语法规则的应用。

分析器通常在两个组件间分配工作—词法分析器(有时叫作分词器)负责把输入断成语言符号,语法分析器责任是依据语言的语法规则,通过分析文档结构构造出来处理树。词法分析器知道如何去除无关字符,比如空格和换行。

浏览器的分析与DOM树构造

图6:从源文档到分析树的转换

分析过程是迭代的。语法分析器通常会请求词法分析器提供一个新的语言符号,尝试用语法规则适配这个语言符号。如果规则匹配上了,一个对应于这个语言符号的结点将被添加到分析树上,然后分析器会请求另一个语言符号。

如果没有规则匹配的上,分析器会内部存储这个语言符号,继续请求语言符号直到发现一个匹配得上所有内部存储符号的规则。如果找不到任何规则,那么分析器会引发一个异常。这意味着文档非法,包含语法错误。

转换

许多时候分析树并非最终产品,分析可能用于转换—把输入文档转换成另一种格式。一个例子是编译。把源码编译成机器码的编译器首先把它处理成分析树,然后把这棵树转换成机器码文件。

浏览器的分析与DOM树构造

图7:编译流程

分析例子

在图5中我们从一个数学表达式建立了一个分析树。让我们尝试定义一个简单的数学语言,看看分析过程。

词汇表:我们的语言可以包括整数,加号和减号。

语法:

1 语言的语法结构是表达式,操作数和操作符。

2 我们的语言可以包含任何数量的表达式。

3 一个表达式定义为,操作数跟着一个操作符,操作符又跟着另一个操作数。

4 操作符是加号或者减号。

5 操作数可以是一个整数串或一个表达式。

让我们来分析输入“2+3-1”。

匹配规则的第一个子串是“2”,根据规则#5它是个操作数。第二个匹配是“2+3”,匹配第二个规则—操作数后面一个操作符,后面又有个操作数。下一个匹配只会在输入结尾时匹配上。“2+3-1”是个表达式,因为我们已经知道“2+3”是一个操作数,所以我们有一个操作数跟着一个操作符再跟着一个操作数。“2++”不会匹配任何规则因此是个无效输入。

词法和语法的形式定义

词法通常用正则表达式表示。

例如我们的语言可以这样定义:

如你所见,整数用一个正则表达式定义。

语法通常用一种称作BNF(巴科斯范式)的格式定义。我们的语言会定义成:

我们说过一种语言可以被常规分析器处理,只要它的语法是上下文无关语法。一个上下文语法的直观定义是这种语法能完全被BNF表达。官方定义请查看http://en.wikipedia.org/wiki/Context-free_grammar

分析器的类型

有两种类型的基本分析器—自顶而下分析器和自底而上分析器。直观的解释是自顶而下分析器查看语法的高级结构,尝试匹配上其中之一。自底而上分析器从输入开始,逐步将其转换成语法规则,从低级规则开始,直到遇到高级规则。

让我们看下两种类型的分析器如何处理我们的例子:

自顶而下的分析器将从高级规则开始—它会先把“2+3”识别成一个表达式。然后把“2+3-1”识别成一个表达式(识别表达式的过程包括匹配其它规则,但起点是最高级的规则)。

自底而上的分析器会扫描输入直到一个规则匹配上。然后它会用规则替换掉匹配的输入。这会持续到输入结束。部分匹配上的表达式被放置在分析器栈中:

浏览器的分析与DOM树构造

这种自底而上分析器被称为移位归约分析器,因为输入移位到了右边(想象一个指针指向输入开始处,然后移动到右边)并逐渐归约到语法规则。

自动生成分析器

有些工具能帮你生成一个分析器。它们被称为分析器生成器。你提供给他们你的语言的语法—它的词法和语法规则然后就能生成个能工作的分析器。创建个分析器需要对分析过程有深入的了解,手工创建个优化的分析器并不容易,所以分析器生成器非常有用。

Webkit使用两种广为人知的分析器生成器—Flex用来构建一个词法分析器,Bison用来创建一个语法分析器(你可能会遇到Lex和Yacc这样的名字)。Flex的输入是一个包含操作数的正则表达式定义的文件。Bison的输入是BNF格式的语言语法规则。

(待续)

1 星2 星3 星4 星5 星 (尚无评分)
Loading...Loading...

相关文章

浏览器中元素的定位类型 网页中元素的定位用由position属性确定,分为绝对定位,相对定位。除此之外还有浮动定位。position的取...
浏览器中CSS的盒模型 首先是CSS中画布的概念,根据CSS2规范,名词“画布”描述为“格式化的结构渲染所用的空间”---也就是浏览器...
浏览器的绘制阶段 在浏览器的绘制阶段,会遍历渲染者树,并调用渲染者的“paint”方法在屏幕上显示内容。绘制需要用到UI基础...
浏览器的布局 下来就是浏览器的布局过程。当渲染者被创建并且增加到树上时,它并没有位置和尺寸。计算这些值被称为布...
浏览器样式表的规则匹配和级联顺序 浏览器中CSS样式的匹配并非总是那么简单,某些情况下可能需要对规则加以处理以使匹配更容易。下面是几个...
浏览器中使用规则树来计算样式 当计算某个元素的样式内容时,我们首先计算规则树里的一条路径或是使用一条已经存在的路径。接下来就开...
浏览器的样式计算 建立渲染树时需要计算每个渲染对象的可视化属性。这是通过计算每个元素的样式属性来实现的。样式包含HTM...
浏览器中渲染树的构造 当DOM树被构造的同时,浏览器构造了另外一棵树,渲染树。这是棵按其显示顺序排列的可视化元素构成的树。...

发表评论

电子邮件地址不会被公开。