基于自动机的嵌入式HTML解析器的设计与实现

论文摘要

随着嵌入式系统的广泛应用和网络技术的快速发展,嵌入式浏览器已成为嵌入式平台上非常重要的的应用软件。嵌入式浏览器是一个网络信息浏览器,支持HTTP或者WAP等其他传输协议,支持HTML,XML,XHTML,JavaScript,WML等语言等。它可以广泛应用于机顶盒,手机,PDA,车载电脑等非PC的嵌入式设备上,通过实现特定的网络传输协议,根据系统设备的多样性进行修改,实现对文字,图像,声音等的需求。与桌面PC上的普通浏览器相比,嵌入式浏览器具有多样性的特点。不同的设备生产厂商在芯片选择,系统功能定义,显示设备,耗电限制有不同的要求,所以需要根据需求进行针对的开发。如由于显示器类型的不同,嵌入式浏览器需要针对具体的设备进行显示优化(如字体识别,字库,图形,页面的显示结构)。而且嵌入式浏览器只有有限的存储空间和内存空间可以利用,针对嵌入式系统的资源的有限性需要开发相应的算法,以保证高的运行速度和运行效率。本文设计的嵌入式浏览器是和深圳某公司合作的车载嵌入式系统的网络模块的一部分。该浏览器基于WinCE平台用EVC进行开发,支持中文显示,并且采用了分块解析的算法。本文开发设计了该嵌入式浏览器的网络传输的底层模型。用EVC的WinInet类实现基于HTTP协议的网页传输,支持网页的转向,用单独一个线程进行网页数据流的下载。针对嵌入式系统的资源的有限性需要开发了基于DFA的解析算法,用于浏览器解析模块的词法语法分析。首先我们抽象出HTML解析器的确定的有限自动机DFA(Deterministic Finite Automaton)的数学模型,基于此模型设计了一个最小化DFA的算法。其中的最小化算法的核心是把一个确定型有限自动机的状态集分成一些不相交的子集,使得任何不同两子集的状态都是可区别的,而同一子集中的任何两个状态都是等价的。也就是说,一台最小化的确定型有限自动机,它没有多余状态并且它的状态中没有两个互相等价。形成存储解析结果的DOM树,以便于结构化编辑(添加、删除、移动等等)HTML文档。本文的工作已经应用于深圳某公司的车载嵌入式系统,具有重要的实际应用价值和理论意义。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 嵌入式系统简介
• 1.2 嵌入式浏览器介绍
• 1.3 嵌入式浏览器研究现状
• 1.4 本文工作
• 1.5 本文组织结构
• 2 嵌入式浏览器架构
• 2.1 嵌入式浏览器原理
• 2.2 嵌入式浏览器基本模块
• 2.2.1 网络传输层模块
• 2.2.2 内存管理模块
• 2.2.3 HTML 解析模块
• 2.2.4 显示模块
• 2.3 本章小结
• 3 嵌入式浏览器网络模块实现的关键技术
• 3.1 HTTP 协议报文
• 3.1.1 HTTP 报文格式
• 3.1.2 Get 请求实例
• 3.2 基于HTTP 协议网络模型
• 3.3 本章小结
• 4 嵌入式浏览器解析模块的实现
• 4.1 XML 解析技术
• 4.1.1 XML 的历史与背景
• 4.1.2 XML 语法基础
• 4.1.3 XML 特点
• 4.1.4 DTD
• 4.2 DOM 解析
• 4.2.1 DOM 解析结构
• 4.2.2 DOM 标准
• 4.3 SAX 解析方法
• 4.4 XML 解析实例
• 4.4.1 SAX 解析结果
• 4.4.2 DOM 解析结果的物理形式
• 4.4.3 DOM 解析结果的逻辑形式
• 4.5 HTML 解析技术
• 4.5.1 HTML 的历史与背景
• 4.5.2 HTML 的缺点与局限性
• 4.5.3 HTML 与XML 的区别
• 4.5.4 HTML 文档结构
• 4.5.5 HTML 半结构化数据
• 4.6 HTML 解析器
• 4.6.1 编程语言的选用
• 4.6.2 解析词法分析
• 4.6.3 解析语法分析
• 4.6.4 正则表达式
• 4.6.5 正则表达式与自动机的转换
• 4.6.6 有限状态自动机
• 4.6.7 基于DFA 的HTML 解析器
• 4.7 解析结果
• 4.7.1 解析结果的DOM 树表示
• 4.7.2 解析结果在浏览器中的显示
• 4.8 本章小结
• 5 总结与展望
• 5.1 工作总结
• 5.2 工作展望
• 致谢
• 参考文献
• 附录