面向VxWorks的嵌入式浏览器解析和布局技术研究

杨建红,舒江波

(1.武汉工业学院 计算机信息与工程系,湖北 武汉 430023;2.华中师范大学 计算机科学系,湖北 武汉 430079)

许多嵌入式浏览器都是基于开源浏览器进行Linux平台的移植或改进,而对于其他一些嵌入式平台相关的嵌入式浏览器开发,如实时的VxWorks嵌入式平台下的嵌入式浏览器产品还相当的匮乏.VxWorks相比Linux的一个较大的区别就在于VxWorks是一个硬实时性操作系统,而Linux是一个软实时性操作系统,VxWorks能更加容易的提供实时性保证,降低了依靠庞大的实时性代码开发风险,这对于嵌入式浏览器的实时性要求是非常有利的.另外,嵌入式浏览器的两个关键的问题就是数据的解析和布局显示.经过分析,发现诸多现有的嵌入式浏览器中,在解析模块和布局模块中穿插着显示模块GUI的调用,显示模块与其他模块紧密耦合在一起,相互之间缺乏层次感,如果想在后续开发中进行跨平台的移植或是进行二次开发扩展功能都比较困难.

针对上述应用需求以及存在的问题,本文中主要探讨面向VxWorks的嵌入式浏览器解析和布局技术.

1 嵌入式浏览器的整体架构

图1 嵌入式浏览器的整体架构

嵌入式浏览器一般采用C/S结构,浏览器软件安装在客户端后,当用户输入有效URL标识后,浏览器的用户交互模块即向控制模块发出URL指令,通过HTTP协议在网络传输层建立TCP/IP网络协议的连接,借助于Socket套接字的传输方式,从Web服务器端的80端口抓取HTML网页资源,然后对网页数据分段进行解析、布局、最后将Web页面显示在屏幕上,展现给用户[1].图1给出了嵌入式浏览器的整体架构.其中,解析模块负责将网页传输模块处接收到的网页数据依次通过词法分析、语法分析、语义分析处理,最后生成DOM树结构的解析数据结构链表.在解析模块生成解析数据结构DOM树后,布局模块将会对每一个可显示的DOM树中的HTML标记进行布局排版.

2 解析技术

图2 词法解析状态转换图

根据各个阶段的功能,嵌入式浏览器的解析分为词法分析,语法分析和语义分析3个阶段.首先由词法分析负责完成简单的HTML标记名称的匹配工作,然后由语法分析对标记的语法进行检测,判断解析出的标记对是否符合HTML语法规则,最后在语义分析阶段完成语法检测过的HTML标记的属性名及属性值信息的提取,并生成解析数据结构链表.由于大多数嵌入式浏览器解析中语法分析和语义分析的过程相同,我们不作讨论,这里重点讨论词法分析.

词法分析是嵌入式浏览器的解析过程的第一步,也是非常重要的一步,其主要功能是从接收的网页数据字符流中识别出有意义的符号字符串.词法分析的效率、准确性与容错性关系到整个浏览器设计的质量.我们用有限自动机来表示词法分析的过程与步骤[2],词法解析状态转换如图2所示,其中,各个状态符号的含义为:init:初始状态;erase:剔除状态,用于跳过注释及文档类型说明字符串;parse:解析状态,进行相关HTML标记类型的判断;startTag:开始标记分类状态,用于区分开始标记、结束标记、空元素标记,并负责处理开始标记和空元素标记;endTag:结束标记状态,处理结束标记的相关操作,如标记出栈等;text:解析内容状态;over:终止状态.

在词法分析模块中还有涉及到一个非常关键的技术即标记的识别算法,HTML4.0规范中定义的标记有91个,在解析过程中需要频繁对它们进行查找判定接收的字串是否为规范中定义的标记,因此,需要设计一种高效快速的查找算法来识别解析文本中的标记,我们试图采用哈希表的设计思想,通过建立哈希表进行静态哈希映射查询,而设计哈希表时一个重要的问题就是防止冲突. H(name)=Len+conv(name[0])+conv(name[Len-1])是一个无冲突的哈希函数,但是,通过对其测试,发现对HTML4.0中定义的91个标记名进行哈希时,其字符到数字的转换表是一个自定义的、离散的字符与数字之间的映射关系集合,因此每次在执行字符到数字的转换时,都要对转换表集合中的字符数字对应关系进行遍历,最差情况下是遍历完毕所有的关系组合.因此这种哈希算法效率与直接对HTML4.0标准中定义的标记名称进行字符串匹配判别的方式相比,没有很大的效率提升,因为每次在进行网页字符串是否为合法标记名称判别时,都需要对自定义的关系集合进行遍历，且更大的弊端就是不具有扩展性,如果HTML标准中扩充了新的标记名称,那么就有可能导致其自定义的字符数字映射关系不再适用,而需要进行重新评估与修正,进而建立一种新的映射关系.

图3 哈希映射处理示意

我们借鉴一种经典的Hash公式,该哈希函数有一个哈希模式参数,它能够通过修改其中的哈希模式参数值,得到对同一个字符串的不同的哈希值.利用这种思想,可以实现将一个字符串经过3次不同的哈希模式哈希后,表示在3个定长的哈希表中,通过3个哈希值共同标识出一个字符串.这样处理后,其发生哈希值冲突的几率大致为1/1022.3.另外,使用位图充当哈希表,每一种HTML标记类型通过哈希函数映射到位图中一个bit位上,位图中的bit位为1,等价为将HTML标记类型名称存入哈希表,表示该位映射有HTML标记类型;如果为0,则表示该位没有对应的HTML标记,等价为哈希表中为空的元素.通过位图的位移操作,可以轻易实现对HTML标记类型的判断,相比使用哈希表中的字符串匹配进行判别的方式,时间复杂度要更低.已知VxWorks在32位机中int整型占4个字节,即32位,因此在计算哈希表长度时是以32为基数计算的,针对HTML4.0中定义的91个标记类型,取哈希表长度为:[(91/32)+1]*32=96,即哈希表长度为96.哈希映射处理过程如图3所示.词法分析算法如下:

(1)初始化位图结构bitmap_hash1,bitmap_hash2,bitmap_hash3,将位图中的各位清0,将HTML4.0中所有HTML标记名字符串经哈希函数映射到3个位图中相应的bit位上.

(2)当前字符游标Char指向接收到的HTML数据字符串首字符.

(3)如果当前自如Char为’<’字符,则转向(4)处理,否则,读取Char后续字符直至遇到’<’字符或’’,将该字符序列记为str,移动Char字符游标,定位到str字符序列后的下一字符位置,转入(7),由text状态处理函数处理str.

(4)读取当前字符Char的后续字符序列,直至遇到字符’>’,记为字符串str,判断str是否包括字符序列”