【毕业学位论文】（Word原稿）Web浏览器语法解析算法的并行化研究-软件工程

览器语法解析算法的并行化研究 览器语法解析算法的并行化研究 摘要 网络浏览器作为一个 算密集型的应用程序，已经成为掌上移动设备上的重要应用之一，但同时又受到掌上移动设备较弱的 算能力的制约。由于散热能耗等限制，在掌上移动设备单个计算单元运算能力很难显著提升的条件下，网络浏览器并行化成为提高浏览器性能的可行途径之一。 语法解析器是网络浏览器的重要组成部分，负责将词法解析器从文本解析得到的符号序列解析成为符合某种语法 (通常是 法 )的语法解析树，以便之后布局引擎等使用。据调查，语法解析器的解析工作在许多主流浏 览器的整个网页处理过程中，占据了非常可观的运行时间，因此对语法解析算法的并行化是网络浏览器并行化非常重要的部分。 语法解析问题是针对上下文无关语法及其语言的解析问题，目前比较常用的是 法解析技术和 法解析技术，这两种技术在编译器方面得到广泛应用并且经过多种优化，已经趋于成熟。相比之下，很早被提出的通用解析算法 法和 法在这方面的应用并不多，主要是由于虽然这两种算法是通用的解析方法，但相比上面提到的技术，在效率上要相差很多，不过着这个仅仅是在串行化解析的角度下而言的。 法和 并行化方面更具有潜力。 法作为通用的解析算法，可以处理所有上下文无关语法，但前提条件是需要将语法转化为符合乔姆斯基范式定义的形式。乔姆斯基范式对于语法形式的要求很严格，一般定义的语法很难符合，转化过程也较为繁琐。设计中，通过使用 写工具完成了一般语法向乔姆斯基范式转化的功能，工具使用了管道模型，通过不同的语法过滤器将远语法中违反乔姆斯基范式定义的规则删除，以此成功地将裁剪后的 法转化为符合乔姆斯基范式的形式。需要指出的是，语法在转化之后在规模上 扩大了许多，尤其是非终结符数量和规则数量，经过试验发现主要是由于删除单元规则时大量的规则复制造成的。 语法的转换引入了解析后语法树与原语法存在差异的问题。通过分析原语法与转化后语法的不一致性以及语法树中不一致结点出现的原因，参考语法转化的逆过程，我们提出了一套语法树还原的方案，保证了解析前后语法与语法树的一致，使得 法的使用对外界透明。 之后在 ，使用 C+完成了利用 法并行解析符合乔姆斯基范式语法的工具。通过对 法中子问题依赖关系的梳理，找出算法中能够进行并行计算的部分，利用 持的 能最终实现算法的并行化。 在虚拟机下的测试表明，使用并行化算法的同步开销会使得单核以及双核情况下，并行算法的效率反而要低于串行算法。而当运算符单元的数量上升之后，并行算法的优势才得以体现。 法与 法相似，也是通用的上下文无关语法解析算法。本次设计中没能够进行实现，仅仅是对其进行了考察。 法是将语法解析问题转化为对 合中的 的计算。 法相比 法，不需要对语法进行转化，可以直接作用于任何上下文无关文法，包括具有二义 性的文法，这样就避免了 法中繁琐的语法转 览器语法解析算法的并行化研究 化和语法树还原工作。并且 法中的 具有较直观的含义，可以利用计算过程中的中间项目提高语法解析部分的响应速度，虽然不一定是最终正确的结果，缺可以提高用户体验。另一方面， 法中的子问题划分要比 法中困难的多，而且为了能够使得 法并行化，在每个分段输入的开始进行了预测，这样导致的结果是并行算法要比串行算法计算更多的可能性，增加了问题的规模。 关键词： 网络浏览器，上下文无关语法，语法解析，并行化 览器语法解析算法的并行化研究 of in eb as a of in its by of of a by t be in a its to by is an of It by a be by to we to is to of is its At LL R in to in To we YK a as a of as a we to be is Its a in a to In 览器语法解析算法的并行化研究 In we a to is in of We to of in in to we of of We its by in of By of of in to we a of to to YK of + to YK by of of In of is of s YK is to is be is a of in YK on 览器语法解析算法的并行化研究 YK to of in a of be in of to n On is in YK in to be to of is a is to of 览器语法解析算法的并行化研究 目 录 第一章 绪论 络浏览器的架构 下文无关语法的解析 上下文无关语法 法解析技术 法解析技术 二章 符合乔姆斯基范式语法的转化 姆斯基范式 化方法 消除开始符号规则 消除空串规则 消除单元规则 消除混合规则 消除长规则 用 写的语法转换工具 用工具转化 法 三章 利用 法进行语法解析 法介绍 法的并行化实现 体实现 法树的还原 问题的产生 问题的解决方案 四章 考察 法 法介绍 法的并行化 章小结 考文献 辞 览器语法解析算法的并行化研究 第 1 页 共 19 页 第一章 绪论 随着网络的发展，网络浏览器已经成为移动掌上设备不可缺少的应用之一。它在运行过程中，同时扮演着 译器，网页布局引擎以及 释器的角色，是较为典型的 制应用，对 计算能力有很 高的要求。但由于移动掌上设备相对较弱的运算能力，很大程度上限制了网络浏览器的功能。对于这个问题，考虑到电耗散热等因素，掌上设备上单个计算单元的运算能力很难在短期内有较大提升，因此使用多个计算单元来提高设备整体的运算能力成为了相对可行的方案。这时，网络浏览器本身的并行化成为了迫切需要解决的问题。 在网络浏览器对网页的解析工程中，第一步是将 本解析成为语法树。这项工作又分为词法解析和语法解析两步。 析在整个网页处理过程中占据了可观的份额。在“ s in 提到解析工 作在 整个处理过程中占据 3%到 10%的时间。而据“ 的测试， 是将 40%的时间用于解析 1。由此可见，对于语法解析算法的改进能够在很大程度上提升网络浏览器的性能。 络浏览器的架构 这一节简要介绍一下目前网络浏览器的大体架构，可能与具体某个网络浏览器的架构有所出入。如图 1示，网络浏览器主要包括八个部分：用户接口、浏览引擎、渲染引擎、网络模块、 释器、 析器、显示后端和数据持久模块 2。 图中箭头表示各个部分之间的依赖关系。 图 1络浏览器架构示意图 (1)用户接口是位于用户和浏览引擎之间的模块。他为用户提供了诸如工具栏，下载，打印等功能接口。有时候，他可能会与用户的桌面环境相集成以此与其他应用进行通信。 (2)浏览引擎作为一个可嵌入组件，提供访问渲染引擎的高层次接口。它能够载入一个给定的 且提供诸如前进、后退、重载等操作。同时，外部模块能够利用浏览引擎提供的钩子查看当前浏览会话的各种状态，比如目前页面的载入进程以及 警告。它还为渲染引擎设置选项的查询 和修改提供了入口。 览器语法解析算法的并行化研究 第 2 页 共 19 页 (3)渲染引擎可以说是网络浏览器最重要的部分，它为一个 供可视化显示。通常，它可以显示 者 档，这些文档中可能还包括诸如图片等嵌入对象，也有可能被 行修饰。这一模块需要对整个显示页面进行布局，决定每个元素在页面中的具体位置。 析器作为这个模块的一部分，把 者 本文档转化成结构化的数据结构。 (4)网络模块的职责是实现如 网络协议。同时还要再不同的字符集之间进行转化，解决 体类型文件类型的问题，他可能会为最近使用的资源 实现一个缓存。 (5)如它的名字，用于解释嵌入在网页中的 发的一个面向对象的脚本语言。某些 能，比如弹出窗口等，有时会被浏览引擎或者渲染引擎处于安全性考虑而屏蔽。 (6)析器用于将 档解析为 。这个模块可能是整个网络浏览器中被重用的最多的模块。事实上，几乎所有浏览器都是使用现有的析器而不是从头创建一个自己的 析器。 (7)显示后端为最终的显示提供用户界面组件，字体等一些通常与操作系统密切绑定的元素。 (8)数据持久模块将一些与浏览会话相关的数据存储在磁盘上。这些数据可能是如书签、工具栏设置此类的高层次数据，也有可能是如 存等底层数据。 下文无关语法的解析 语法可以用上下文无关语法（ 表示。对 语法解析也可以认为是对特定上下文无关语法的解析工作。由于语法解析工作中对文本解释需要依赖于之前的文本，因此这项工作通常是顺序完成的。 下文无关 语法 一个上下文无关语法 G，可以被表示为形如 四元组。其中， N 表示非终结符的集合； 表示终结符的集合，同时需要保证 N 与 总不含共有元素，即 N=； P 表示N 到 ( N)*1的关系的集合； S 表示开始符。 通常情况下，为了方便表示，我们使用 V 表示 N， 使用英文大写字母（如 A， B，C）来表示非终结符集合 N 中的元素，使用小写英文字母（如 a， b， c）表示终结符集合 中的元素，使用希腊字母（如 ， ）表示任意终结符和非终结符的序列 。 L(G)表示语法 G=的语言集合，有 L(G)=w *： S*w 。 一个特定上下文无关语法 G 的识别器能够判断一个任意的字符串是否是 L(G)中的元素。在此基础上，语法 G 的解析器能够为识别的字符串生成语法解析树。尽管生成语法树的工作要比仅仅识别字符串困难一些，但是通常我们在设计实现解析器时仅仅把识别问题纳入考虑范畴，因为这两者联系紧密，在识别问题被解决时，往往只需要修改一些数据结构，记录识别过程中的一些信息，就可以构造一个解析器 3。 用的上下文无关语法解析方法 法分析技术 4 法分析技术中的第一个 L 表示对输入进 行从左到有的扫描，第二个 L 表示构造最1 *表示 号运算，之后若无特殊说明，均为此意 览器语法解析算法的并行化研究 第 3 页 共 19 页 左推导序列。 LL(k)语法分析技术中最常用的是 )语法分析，这里 1 表示从输入序列中向前看一个输入符号来确定用于展开的产生式。 一个语法是 )的，当且仅当语法 G 中任意两个形如 A | 规则满足以下条件时： 1)不存在终结符 a 使得 和 都能推倒出以 a 开始的串。 2) 和 中最多只能有一个推导出空串。 3)如果 可以推导出空串，那么 不能推导出任何以 )2中某个终结符开始的串。同理，当 可以推导出空串时，这条规则对 也适用。 可以说 )对于语法的要求还是相对 较严格的，很多直观的语法定义并不能满足 )的语法要求，而使用 LL(k2)的方法解析，效率又很难令人满意。所以 )语法分析有时会与 LL(k2)语法分析混合使用，在大多数情况下使用 )而在局部不满足 )语法要求的地方多向前看几个输入符号，使用 LL(k2)完成工作。比较典型的一个例子是 法分析技术 4 法分析技术中的 L 表示对输入进行从左到右的扫描， R 表示反向的构造出一个最右推导序列。目前最流行的自底向上的语法分析器都是基于 LR(k)语法分析的概念。这里 常取 k=0 和 k=1，具备较强的实践意义。 法分析器是表格驱动的，这一点与非递归的 法分析器很相似。 法分析器主要具有以下的优点： 1)对于大多数程序设计语言，只要能够写出上下文无关语法，就能够构造出对应的 然确实存在非 上下文无关语法，但通常情况下，特别是对于程序设计语言，在设计构造是都可以避免使用这样的语法。 2)法分析方法是已知的最通用的无回溯移入 且他的实现能够和其他更加原始的移入 3)一个 法分析器能够在对输入进行从左到右的扫描时尽早地发现错误。 4)能够使用预测方法或者 法进行语法分析的语法都可以使用 语法分析器分析。一个语法是 LR(k)语法的条件是党我们在一个最右句型看到某个产生式的右部时，如果我们向前再看 k 个字符，就能够决定是否使用这个产生式进行规约。而这个条件要比 LL(k)语法宽松很多。相应的，在面对 LL(k)语法时，我们在决定是否要使用某个产生式展开，需要向前看改产生式右边推导出的串的 k 个字符。因此 法能够比 法描述更多的语言。 当然， 法也存在缺点。当为一个具体的语 言语法手动构造一个 法分析器的工作量是非常巨大的，需要特殊的工具进行辅助。 2 )表示在某些句型中可以紧跟在 A 后面的终结符的集合 览器语法解析算法的并行化研究 第 4 页 共 19 页 第二章 符合乔姆斯基范式语法的转化 姆斯基范式 (下简称 乔姆斯基范式是上下文无关语法的一个自己，我们说一个语法是乔姆斯基范式的当且仅当一个文法的规则 P 中所有元素属于以下情况中的一种： AAa S 在这里 A， B， C 是非终结符， a 是终结符， S 是开始符号， 是空串。需要指出的是，B 和 C 都不能够是开始符号。 乔姆斯基范式的一个重要特点是，所有上下文无关语 法都可以通过一定变换转化为符合乔姆斯基范式的形式。 化方法 需要将一个语法 么该语法的规则集合 先要做的就是将这些违反定义的规则归类，再为每类规则寻找转化为符合定义形式的方法 5。 我们将违反 义的规则分为五类，具体如下： (1)开始符号规则（ 即在规则右边出现了开始符号，而 义中明确指出规则右边是不能出现开始符号的。形如 A其中 S 是开始符号 ， u,v V*。 (2)空串规则（ 即非开始符推出空串， 定义中只有开始符号允许推出空串。形如 A ，其中 A 为除了开始符号的非终结符， 为空串。 (3)单元规则（ 即由一个非终结符推出另一个非终结符， 义中当规则右边为非终结符时，数量必须为两个。形如 AB ，其中 A， B 都是非终结符。 (4)混合规则 （ ， 即规则右边存在至少一个终结符和非终结符， 义中终结符必须单独出现在规则右边。形如 Aw ，其中 w V*并且 w 中包含终结符和非终结符至 少各一个。 (5)长规则（ 即规则右边符号数量大于两个， 义中当规则为非终结符时，数量必须为两个。形如 Aw ，其中 w V*并且 |w|2。 在对违反 义的规则进行分类后，我们就可以根据这些规则的特点，在保证变换等价的情况下，逐一消除这些规则，达到将原有语法转化为等价的 法。下面将介绍具体方法。 假设原有语法为 G，变换后的语法为 除开始符号规则 消除开始符号规则的做法十分简单。 为了使得在 开始符号不再出现在规则右边，我们引入新的符号 为 开始 符号，同时添加规则 。由于 新添加的符号，它不可能出现在其他规则中，那么自然地，它也不可能出现在其他规则的右边。而 S 已经不再是 开始符号了，所以经过转化后，新的语法 将没有开始符号规则。 验证变换后 L(= L(G)。如果 w L(G)，那么必然有 S*w ，由于在 有 ，则有 w ，所以 w L(；相反的，有 w L(由于 一能够推出的就是 S，则 览器语法解析算法的并行化研究 第 5 页 共 19 页 显然的，对于每一个 w 必然是以 *w 的形式出现，也就有 S*w ，即 w L(由此可见， L(= L(G)。 除空串规则 消除空串规则的做法相对复杂。首先我们需要定义哪些非终结符是可为空的，修改这些可为空的符号出现的规则。 第一步：可为空定义：如果存在规则 A ，那么称 A 是可为空的；如果存在规则AB 1中 部可为空，那么 A 是可为空的。我们将所有可为空符号组成的集合记为 E。 第二步：对于 G 中的规则，我们将它们分成三类，进行不同的处理，构建新的语法 如 A 的规则，我们简单将其删除，不加入新语法 于 A 已经被记录到 E 中，之后 会进行处理保证变换的等价。形如 Aw ，其中 w N*，如果 w 中的符号都不可为空，那么，我们在新语法中保留这个规则。之后是最关键的一步，如果规则不属于上述两种情况，则规则具有 Aw ，其中 w N*，并且 w 中包含可为空的符号，那么 w 可以表示为形式中 示可为空的符号， 不包含可为空的符号。对于 们枚举所有 在与不存在的组合，在 生成对应的 2n 条规则。例如A其中 B， C 可为空，那么生成规则 A A A AD 。 第三步：如果开始符号 S 也出现在 E 中，那么向 的规则中添加 S 。 除单元规则 与消除空串规则相似的，我们首先定义二元组 (A,B)，称为单元对。一个单元对 (A,B)代表的含义是 A*B 。为了之后操作的方便，我们将所有 (A,A)也定义为单元对，其中 A N。可以通过如下操作找出语法 G 中的所有单元对： 1)简单地定义所有 (A,A)为单元对，其中 A N。 2)如果 (A,B)是一个单元对，并且存在规则 BC 那么我们认为 (A,C)也是一个单元对。 之后我们构造新的语法 于单元对 (A,B)，如 果在 G 中存在规则 Bw ， w V*，那么我们将规则 Aw 加入 们注意到，由于之前我们将 (A,A)也作为单元对，在剔除AB 形式的规则的同时，原有符合定义的规则将会被复制到 去。 除混合规则 相比之前两个规则的消除，混合规则的消除相比要简单的多。这里我们的目的是要去除混合规则中的终结符，使之成为一个长规则，待由下一步消除长规则时彻底除去。对于一个混合规则 Aw ， w V*，我们可将 w 写成形式 里 表终结符号，对于每个出现的终结符，我 们添加新的非终结符 造新规则 i，利用替代原有规则中的 得原来的规则成为 A 样以后，所有混合规则都被转化为符合 义的规则或者长规则。 除长规则 由于经过上一步的变化，这里处理的长规则的右部全部为非终结符。即具有形式AB 1中 非终结符。这里，我们通过引入新的帮助非终结符，将一个长规则切割成许多符合 义的短规则，具体做法如下： 我们加入帮助非终结符 2,.,原有规则变为 AB 1 2 过这部变换后，原有语法中所有不符合 义的规则都被消除了，转化得到的新语法即符合 定义。 用 写的语法转换工具 由于将一般语法转化为符合 义的形式需要大量工作，而且设计中使用的是裁剪的 法，规模也比较大，使用手工转化工作量巨大而且容易出错，于是决定使用 览器语法解析算法的并行化研究 第 6 页 共 19 页 写工具完成转化工作。 工具按照上一节中的方法对语法进行转换。工具使用了管道模型，针对上一节中的每一种规则的消除 ，编写一个语法过滤器，这些语法过滤器共同继承接口 个接口有一个方法 个方法接受一个 代表一个上下文无关语法的数据结构，并是些了对于语法操作的一些基本方法，比如添加规则，复制语法等 )并返回一个经过修改的语法。我们从文件中读入原始语法，将其构造成为构，再将五个语法过滤器串联，使得原始语法依次通过这些语法过滤器，我们就可以得到一个符合 义的语法。 图 1法转化工具示意图 这里五个语法过滤器 分别为 应五种规则的移除工作。 用工具转化 法 作为只有 法解析的输入语法，我们需要对裁剪过的 除了标签的属性）进行转化，使其符合 义的形式。这里我们使用工具对其进行处理并记录下各个阶段中各种规则的数量，语法规模的变化等数据。 从表 2我们可以看到，原有语法的非终结符号会在消除空串规则的时候被删除，这是不能接受 的，因为以后的模块可能需要用到这些符号，而这些符号所代表的含义也丢失了，在之后的章节中我们会详细描写如何找回这些丢失的结点。同时我们看到规则的数量在去除单元规则的时候数量发生了爆炸，扩大了五倍之多。引起这个现象的主要原因是 们看到在初始语法中就包含了 123 条单元规则，而消除单元规则我们采取的是复制规则的方式使得前后语法能够保持等价，如果单元规则右边的非终结符拥有大量导出规则，那么他们将会全部被复制给左边的非终结符号，因此会导致规则数目的急剧增加。而且我们可以观察到， 每个转化规则并不是完全将对应需要去除的规则直接转化为符合 义的形式，有时会先转化为尚未被处理的不符合范式定义的规则，交由之后的语法过滤器处理，这就解释了为什么单元规则，混合规则以及长规则在转化过程中有增加的情况，同时也说明了各个语法过滤器的使用是有先后次序的。 览器语法解析算法的并行化研究 第 7 页 共 19 页 表 2化过程中的语法各项数据的变化 原语法 去除开始规则 去除空串规则 去除单元规则 去除混合规则 去除长规则 终结符 172 172 172 172 172 172 非终结符 293 293 291 291 294 373 规则 396 396 466 2026 2029 2108 开始规则 0 0 0 0 0 0 空串规则 20 20 0 0 0 0 单元规则 123 123 131 0 0 0 混合规则 10 10 10 65 0 0 长规则 73 73 79 912 912 0 第三章 利用 法进行语法解析 法介绍 法是 由 人提出的算法 6，用于判断一个字符串是否属于某个上下文无关语法。这个算法采用了自底向上和动态规划的方法。对于输入长度 为n 的字符串， 法可以在多项式时间内 O(决解析问题。同时 法可以解决任意上下文无关语法的解析问题，但需要首先将语法转化为符合 义的形式。 下面给出的是这个算法的伪代码。 我们注意到在伪代码 3，主要解决的问题就是 Pn,n,m数组的取值问题。这里说明下 Pn,n,m的值所代表的含义，如果 Pi,j,k的值为 么表示 .以被解释为 .法以终结符规则作为起始，由于 义 中的非终结符规则的右边仅仅有两个非终结符，我们很容易就能够实行自底向上的归并。如下图 3果 以被解释为 B，而 以被解释为 C，同时又有 A那么 。 览器语法解析算法的并行化研究 第 8 页 共 19 页 图 3法伪代码 图 3法规约示意图 为了说明这个算法，我们首先 定义算法的输入： 输入长度为 n 的字符串 入 符合 义的 语法 G，其中包含 m 个非终结符 2,.,了方便表述，将 形如 A 其中 A,B,C 为非终结符）称为非终结符规则；形如 Aa （ 其中 A 为非终结符， a 为终结符）称为终结符规则；形如 S （ 其中S 为开始符号， 为空串 ）称为空串规则。 Pn,n,m i = 1 to n j = 1 to n k = i to m Pi,j,ki = 1 to n 对于所有终结符规则 Njs i，执行 Pi,1,ji = 2 to n j = 1 to k = 1 to 于所有的非终结符规则 果有 Pj,k,b和 Pj+k,c的值同时为 么执行 Pj,i