中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
学科主题: 计算机科学技术基础学科
题名:
受限正规树文法与基于正则表达式包含判定的类型检查
作者: 陈雷
答辩日期: 2010-01-25
导师: 陈海明
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 硕士
关键词: XML ; 树文法 ; 类型检查 ; 子类型 ; 正则表达式 ; 包含判定
摘要: XML简单灵活的特性使得XML在网络服务、关系数据库以及形式化研究等领域得到应用。同时,XML处理的技术不断发展,近期的研究表明静态类型化的处理方式在XML处理的有关方面有重要的优势。静态类型化XML处理技术是将XML的模式语言作为程序语言的基本数据类型,在程序运行之前进行静态的类型检查,从而确保运行时的类型安全。目前大多数静态类型系统采用正则表达式类型作为基本类型,正则表达式类型与树自动机是一一对应的。 子类型关系判定是类型检查中的核心问题。语义子类型的方法在静态类型化XML处理中有很多优点。在这种子类型判定方法中,类型被看成是值的集合,子类型关系判定转化为集合的包含判定。目前广泛应用的XML的模式语言如DTD、XML Schema等都是正规树语言的子类。正规树语言的包含问题是可判定的。在类型检查中,正则表达式类型的实现是基于树自动机的,子类型关系判定转化为树自动机的包含判定,效率较低。 本文提出了一种基于正则表达式包含判定的类型检查方法。由于DTD是目前使用最普遍的XML模式语言,因此本文首先提出针对DTD的类型检查方法,然后在此基础上进行扩展,提出了产生式不相交的正规树文法的概念以及针对该受限树文法的类型检查方法。DTD以及XML Schema等常用的XML模式语言均可由该树文法直接描述。在本文的方法中,子类型关系判定的过程不需要构造树自动机,而是根据类型表达式的树状结构自下而上地进行检查,每一层的检查基于正则表达式的包含判定,同时在判定过程中利用了树文法中的标号与类型之间的联系。该方法可以针对不同种类的正则表达式使用不同的包含判定算法。通过采用一种称为消除局部递归类型的策略,使得对并类型的子类型关系判定比基于树自动机的类型检查方法更加简单。本文实现了上述类型检查方法,并通过相应的实验说明该方法的可行性以及有效性。同时分析比较了已有的XML类型检查的方法与基于正则表达式包含判定的类型检查方法的优缺点。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/654
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
受限正规树文法与基于正则表达式包含判定的类型检查.pdf(2122KB)----限制开放 联系获取全文

Recommended Citation:
陈雷. 受限正规树文法与基于正则表达式包含判定的类型检查[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2010-01-25.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[陈雷]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[陈雷]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace