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

摘要：

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

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

分类号：TP311.56(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61202071,61121063, U1201252;the National Basic Research Program of China under Grant No.2011CB302604国家重点基础研究发展计划973计划;the National High Technology Research and Development Program of China under Grant No.2013AA01A605国家高技术研究发展计划863计划

在线出版日期：2015-07-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：793-802