学位论文 > 优秀研究生学位论文题录展示

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

作　者: 岳珂
导　师: 雷跃明
学　校: 重庆大学
专　业: 计算机软件与理论
关键词: 嵌入式浏览器 DOM 解析器确定的有限自动机
分类号: TP393.092
类　型: 硕士论文
年　份: 2008年
下　载: 152次
引　用: 3次
阅　读: 论文下载

内容摘要

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

全文目录

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

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

内容摘要

全文目录

相似论文