计算机科学与探索 ›› 2015, Vol. 9 ›› Issue (7): 793-802.DOI: 10.3778/j.issn.1673-9418.1410009

• 系统软件与软件工程 • 上一篇    下一篇

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

吴阳怿1,2,吴逸鸣1,2,熊英飞1,2+   

  1. 1. 北京大学 信息科学技术学院 软件研究所,北京 100871
    2. 北京大学 高可信软件技术教育部重点实验室,北京 100871
  • 出版日期:2015-07-01 发布日期:2015-07-07

Reversible Transformation Model Based on Context-Free Grammars

WU Yangyi1,2, WU Yiming1,2, XIONG Yingfei1,2+   

  1. 1. Institute of Software, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
    2. Key Laboratory of High Confidence Software Technologies of Ministry of Education, Peking University, Beijing 100871, China
  • Online:2015-07-01 Published:2015-07-07

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

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

Abstract: Data transformation problems like reversible transformation and bidirectional transformation have been a research focus in recent years, a large number of different transformation languages and models have been proposed. But they are often based on a new computation model, which leads a non-trivial learning cost to understand the new computation model. On the other hand, as an essential tool in language parsing, context-free grammar is familiar to most programmers. This paper proposes a computation model to construct reversible transformation for string data based on context-free grammars, and discusses its properties and computability. This paper also implements the model in Scheme, and evaluates the model by developing a pair of assembler and disassembler of MIPS instruction set. The evaluation result shows that the model is expressive and can implement the assembler and disassembler of MIPS instruction set with the help of a small data transformation module.

Key words: reversible transformation, context-free grammar, string data