上一节我们讨论了两种渲染引擎的基本工作流程。这一节开始，我们将对流程中的每个步骤进行更详细的说明。因为分析是浏览器渲染引擎里非常重要的过程，我们会更深入的关注一下它里面的细节。我们先从一个小小的介绍开始。分析一个文档意味着把它翻译成一些有意义的结构—有时是一些能够理解和使用的代码。分析产生的结果通常是一棵代表着文档结构的由各种结点组成的树。这被称为分析树或是语法树。
例如，分析表达式“2+3-1”可能返回这个树：
图5：数学表达式树节点
语法
分析要遵循文档的语法规则—它用何种语法或格式编写的。每种你能分析的格式必须有确定的语法，由词汇和语法规则组成。它被称为上下文无关语法。人类语言不是这类语言，因此不能用传统分析技术处理。
分析器—词法分析器的组合
分析可以分成两个子过程—词法分析和语法分析。
词法分析是把输入分拆成语言符号的过程。语言符号是语言的词汇—有效结构的集合。在人类语言中它会包含该种语言的字典中出现的所有单词。
语法分析是语言语法规则的应用。
分析器通常在两个组件间分配工作—词法分析器（有时叫作分词器）负责把输入断成语言符号，语法分析器责任是依据语言的语法规则，通过分析文档结构构造出来处理树。词法分析器知道如何去除无关字符，比如空格和换行。
图6：从源文档到分析树的转换
分析过程是迭代的。语法分析器通常会请求词法分析器提供一个新的语言符号，尝试用语法规则适配这个语言符号。如果规则匹配上了，一个对应于这个语言符号的结点将被添加到分析树上，然后分析器会请求另一个语言符号。
如果没有规则匹配的上，分析器会内部存储这个语言符号，继续请求语言符号直到发现一个匹配得上所有内部存储符号的规则。如果找不到任何规则，那么分析器会引发一个异常。这意味着文档非法，包含语法错误。
转换
许多时候分析树并非最终产品，分析可能用于转换—把输入文档转换成另一种格式。一个例子是编译。把源码编译成机器码的编译器首先把它处理成分析树，然后把这棵树转换成机器码文件。
图7：编译流程
分析例子
在图5中我们从一个数学表达式建立了一个分析树。让我们尝试定义一个简单的数学语言，看看分析过程。
词汇表：我们的语言可以包括整数，加号和减号。
语法：
1 语言的语法结构是表达式，操作数和操作符。
2 我们的语言可以包含任何数量的表达式。
3 一个表达式定义为，操作数跟着一个操作符，操作符又跟着另一个操作数。
4 操作符是加号或者减号。
5 操作数可以是一个整数串或一个表达式。
让我们来分析输入“2+3-1”。
匹配规则的第一个子串是“2”，根据规则#5它是个操作数。第二个匹配是“2+3”，匹配第二个规则—操作数后面一个操作符，后面又有个操作数。下一个匹配只会在输入结尾时匹配上。“2+3-1”是个表达式，因为我们已经知道“2+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”识别成一个表达式（识别表达式的过程包括匹配其它规则，但起点是最高级的规则）。
自底而上的分析器会扫描输入直到一个规则匹配上。然后它会用规则替换掉匹配的输入。这会持续到输入结束。部分匹配上的表达式被放置在分析器栈中：
这种自底而上分析器被称为移位归约分析器，因为输入移位到了右边（想象一个指针指向输入开始处，然后移动到右边）并逐渐归约到语法规则。
自动生成分析器
有些工具能帮你生成一个分析器。它们被称为分析器生成器。你提供给他们你的语言的语法—它的词法和语法规则然后就能生成个能工作的分析器。创建个分析器需要对分析过程有深入的了解，手工创建个优化的分析器并不容易，所以分析器生成器非常有用。
Webkit使用两种广为人知的分析器生成器—Flex用来构建一个词法分析器，Bison用来创建一个语法分析器（你可能会遇到Lex和Yacc这样的名字）。Flex的输入是一个包含操作数的正则表达式定义的文件。Bison的输入是BNF格式的语言语法规则。
（待续）
原创文章，作者：苏葳，如需转载，请注明出处：https://www.swmemo.com/2016.html
