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

来源：计算机科学与探索杂志2015年第7期北京时间：

作者：吴阳怿，吴逸鸣，熊英飞

单位：1. 北京大学 信息科学技术学院 软件研究所，北京 1008712. 北京大学 高可信软件技术教育部重点实验室，北京 100871

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

关键词：可逆变换,上下文无关文法,字符串数据