03
2013
04

浏览器工作原理 - 浏览器解析原理

在浏览器的工作原理中,由于解析是渲染引擎中一个很重要的过程,我们会讲的略深入一些。让我们从一个小的解析介绍开始。

解析一个文档意味着把它翻译成有意义的结构以供代码使用。解析的结果通常是一个节点构成的树,它代表这个文档的结构,我们称它为解析树或句法树。

示例——解析表达式“2 + 3 - 1”可以返回下面的树:

image009.png


数学表达式树节点

文法

解析是基于语法规则的,文档被写入的语言或则格式必须遵从。每一种可以解析的格式必须由确定的语法规则与词汇表组成。这被称之为上下文无关文法。这不同于人类语言,所以不能用传统的解析技术来解析。

解析器——词法分析器组合(Lexer combination)

解析能被分为两个过程:词法分析语法分析

词法分析就是处理把输入切分成符号(tokens)。这些符号(tokens)就是语言中的词汇表——有效构建块的一个集合(the collection of valid building blocks)。如果在人类语言中,它就是所有包含在字典中的单词。

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

解析器通常把工作分为两部分:词法分析器lexer(有时候称为分词器:tokenizer)输入切分成有效的符号(tokens),解析器负责根据语言语法分析文档的结构并构建解析树。词法分析器知道如何去过滤不相干的字符,例如空格和换行符。

image011.png

从原始文档到解析树

(文档,词法分析,语法分析,解析树)

解析是一个迭代的过程。解析器通常是想词法分析器获取一个新的符号(token),然后拿它去尝试匹配语法规则。如果匹配成功,则在解析树中建立一个响应的节点,并继续向词法分析器获取另一个符号。

如果没有匹配成功,解析器将内部存储这个符号,并保持到从词法分析器获取另一个符号直到有一条匹配的规则能在内部存储的符号中找到相应的符号。如果最终没有规则匹配,解析器将抛出一个异常。这意味着文档是无效的,包含语法错误。

转换

很多时候解析树并不是最终产物。解析经常使用于转换——将输入文档转变为另一种格式。举个编译的例子,编译器编译一份源码成机器码,首先会解析他到一个解析树,然后把解析树转换成机器码文档。

image013.png

编译流程(源码,解析,解析树,转换,机器码)

解析例子

在【图 编译流程】我们用数学表达式构建了一个解析树。现在让我们尝试定义一个简单的数学语言去看这个解析过程。

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

语法:

1.        语言语法构建块是表达式(expressions),术语(terms)和操作(operations)。

2.        我们语言能够包含任何数量表达式。

3.        一个表达式定义成一个术语(term)跟着一个操作(operation)再跟着另一个术语。

4.        一个操作是一个加号符号或则一个减号符号

5.        一个术语是一个整数符号或则是一个表达式

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

第一个匹配规则的子串是“2”,根据规则#5,它是一个术语。第二个匹配规则的是“2+3”,这里匹配第二的规则是#3。下一个匹配将定位在输入的最后。“2+3-1”是一个表达式,因为我们已经知道“2+3”是一个术语,所以根据#3它符合语法。“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

解析器的类型

有两种基本的解析器类型:自上而下的解析器和自下而上的解析器。一种直观的解释是:自上而下的解析器是从语法的高层开始尝试匹配它们。自下而上的解析器从输入开始逐步的转换成语法规则,开始从底层规则到高层规则匹配。

从我们的例子出发,看看两种类型的解析器是如何进行解析的。

自上而下的解析器将从高层规则开始,它将确定“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解析器(shift reduce parser),因为输入是向右移动(想象一下一个指针从指向输入开始逐渐向右移动) 并逐渐简化到语法规则。

自动化生成解析器

解析器生成器这个工具能为你生成一个解析器。你只需要指定语言的文法——词汇表及语法规则,它就可以生成一个解析器。创建一个解析器需要对解析有深入的理解,而且手动的创建一个由较好性能的解析器并不容易,所以解析生成器很有用。

Webkit使用两个知名的解析生成器——用于创建词法分析器的Flex和创建解析器的Bison(你可能接触过Lex和Yacc)。Flex的输入是一个包含了符号定义的正则表达式,Bison的输入是用BNF格式表示的语法规则。

« 上一篇下一篇 »

评论列表:

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。