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

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