基于上下文无关文法的可逆变换模型

作     者：吴阳怿 吴逸鸣 熊英飞 WU Yangyi;WU Yiming;XIONG Yingfei

作者机构：北京大学信息科学技术学院软件研究所 北京大学高可信软件技术教育部重点实验室 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2015年第9卷第7期

页      面：793-802页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 国家重点基础研究发展计划(973计划) 国家高技术研究发展计划(863计划)~~ 

主　　题：可逆变换 上下文无关文法 字符串数据 

摘      要：可逆变换和双向变换等数据转换问题一直是近年来的研究热点,研究人员针对该问题提出了大量相关的语言和模型。但是,这些实现往往建立在一种新的计算模型上,从而导致需要花费较大的学习成本去了解计算模型。另一方面,作为语法解析的基本工具,上下文无关文法对于绝大多数程序员来说都是不陌生的。提出了一种基于上下文无关文法的计算模型,用来构造字符串上的可逆变换,并对其性质和表达能力进行了探讨。采用Scheme语言实现了该计算模型,并通过在MIPS指令集上进行汇编和反汇编开发验证了该模型。验证结果表明,该模型具有较强的表达能力,在添加小型的公共数值变换模块后,可以完整地实现MIPS指令集上的汇编和反汇编。