资源描述：
《基于上下文无关文法的可逆变换模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1基于上下文无关文法的可逆变换模型1,21,21,2+吴阳怿,吴逸鸣,熊英飞1(北京大学信息科学技术学院软件研究所,北京100871)2(北京大学高可信软件技术教育部重点实验室,北京100871)+通讯作者，邮件：xiongyf@pku.edu.cn摘要:可逆变换和双向变换等数据转换问题一直是近年来的研究热点,研究人员针对该问题提出了大量相关的语言和模型.通过使用这些语言,程序员可以只写一个程序而产生正向和逆向两个变换,不仅提高了程序的健壮性,同时也降低了编写程序的工作量.但是,这些实现往往是建立在一种新的计算模型之上,从而导致需要花费较大的学习成本去了解其计算模型.另一方面,上
2、下文无关文法被广泛使用于编译技术,且有着等价于下推自动机的可计算性.作为语法解析的基本工具,上下文无关文法对于绝大多数程序员来说都是不陌生的.本文提出了一种基于上下文无关文法的计算模型,用来构造字符串上的可逆变换,并对其性质和表达能力进行了探讨.关键词:可逆变换;上下文无关文法1引言数据变换是计算机应用的一个常见内容,很多软件的开发都涉及到了数据变换.比如汇编程序把汇编代码变换成机器码,压缩算法把原始数据转换成压缩后的数据,加密算法把明文数据变成密文,程序维护时把ini配置文件转成XML配置文件等等.在很多场景下,我们不仅需要一个单向的数据变换,也需要该变换的逆变换.换句话说,如
3、果我们把数据变换看成是从输入映射到输出的一个函数f,我们同时也需要这个函数的反函数f-1.比如,给定一个汇编程序,我们同时会需要一个反汇编,他们互为逆变换.同样的,我们也可能需要压缩的逆变换解压缩,加密的逆变换解密程序,以及把XML配置文件转换回ini配置文件的工具.对于这类互逆的变换程序,现有的主流开发方法需要写两个程序,一个做正向变换,另一个做逆向变换.互为反函数的一对变换往往含有大量的重复部分,写两个变换不仅存在很多重复劳动,还会增加出现低级错误的可能性,从而导致更多的调试时间和精力的浪费.为了解决这个问题,近年来研究人员提出了采用领域特定的语言来构造一对相关的数据变换,其
4、中代表性的工作包括可逆语言(ReversibleLanguages)[1]和能力更强一点的双向语言(BidirectionalLanguage)1[2].通过使用这些语言,程序员只需写一段程序,就可以同时得到正向和逆向两个变换.一方面避免了重复劳动,另一方面保证了所生成的两个变换互逆,避免了出现低级错误的可能.为了实现这个目标,现有的可逆语言和双向语言往往需要提出新的计算模型.比如,Foster等人设计的双向变换语言Boomerang[3]提出了一套基于组合子的计算模型,Glück等人设计的可逆语言[1]采用了基于可逆图灵机的计算模型.由于这些计算模型和传统模型往往差别较大,程序
5、员使用这些新型语言需要较大的学习成本.虽然可逆语言和双向语言有良好的性质,但目前在实践中的运用还比较少.在本文中我们提出一种使用上下文无关文法来构造字符串上的可逆变换的方法,我们的方法主要基于如下观察:很多变换的核心内容是数据格式的变换,比如,在配置文件的转换中,是在XML的保存格式和ini的保存格式之间转换,而数据的内容没有变化.在现有技术中,适合描述数据格式的工具就是上下文无关文法.上下文无关文法是绝大部分程序员所熟知的一种表示方式,采用上下文无关文法来描述可逆变换可以使得学习成本大大降低.本文的主要贡献如下:1双向变换和可逆变换的主要区别是，双向变换不要求转换的两个数据域包
6、含的信息是对等的，一个数据域可以包含不和另一侧共享的信息。但可逆变换要求两个数据域包含的信息是严格对等的。2本文提出了一种新的计算模型来描述字符串上的可逆变换.使用该计算模型,程序员定义一个抽象数据结构并且使用上下文无关文法描述该数据结构和具体的字符串格式之间的对应关系.然后我们的方法可以自动从该描述中导出一对互逆的parser和printer,完成具体字符串和该抽象结构的表示.通过描述抽象结构和两个具体格式的对应关系,我们就可以实现两个不同格式之间的可逆变换.我们将我们的计算模型实现为一个基于Scheme的领域特定语言,并且采用该语言完成了大型实例研究:我们用我们的语言实现
7、了MIPS指令集上汇编和反汇编.我们的语言能够完整的覆盖MIPS指令集从汇编格式到机器格式之间的对应关系,并且以较精简的代码就能完成该实例变换.该实例研究说明,我们的语言已经具有较好的表达能力,可以描述比较大型的可逆变换程序.本文的剩余部分按如下方式组织:首先,我们用一个例子来展现我们方法的主要内容;其次,我们给出计算模型的精确定义,并证明我们的方法达到了生成可逆计算这一目标;再次,我们描述我们模型的实现和在MIPS汇编指令上所进行的验证;最后,我们讨论相关工作并且给出论文结论.
