可逆编程语言R-JAVA及其语言处理系统的设计

薛慧君

（内蒙古电子信息职业技术学院，内蒙古呼和浩特，010070）

可逆编程语言R-JAVA及其语言处理系统的设计

薛慧君

（内蒙古电子信息职业技术学院，内蒙古呼和浩特，010070）

可逆编程语言是可逆计算研究中的重要内容，利用可逆编程语言编写的程序，能够实现正向和反向的双向运行，从而分别实现结果获取和恢复输入两方面功能。因而，可逆编程语言的研究十分必要。

可逆编程语言R-JAVA；语言处理系统；设计

0 引言

Janus是现知最早的可逆编程语言，目前流行的计算机都存在逻辑上的不可逆，在其运行计算时，会出现信息丢失等情况，且无法返回推前状态，而理论上讲，若是具备充足的存储空间，则所有逻辑上的不可逆计算，都能够成为可逆计算，Janus语言便是基于这一理论，所形成的可逆编程语言。其语法设计主要遵循基本语句可逆和控制结构可逆两方面原则，而R-JAVA也是如此。

1 可逆编程语言R-JAVA设计原则

1.1 遵循基本语句可逆原则

要想实现可逆计算，必须要在软件层次和逻辑综合层次找到适合的可逆变换函数[1]。软件层次上，程序中语句执行内存的变量值为动态状态，因而，在软件层次中，程序段赋值语句为内存状态变换函数，即 Y = f (X ) ，其中，X为程序运行前内存的内存状态，Y则为程序运行后的内存状态。在可逆逻辑综合中，n变量布尔函数 f (x

1, x2,

. .. ,xn) 要想实现可逆性，必须具备相应的性质。也就要求，n变量布尔多输出函数必须具备可逆性。即如果输出数等于输入数且任一个输出模式只有一个唯一的原象[2]。基于这一性质，结合软件层次函数，则以上提到的函数只要是单射函数，便具有可逆性。即 f ( a ) = f (b ) ⇒ a = b ， Y = f-1( X ) 。X能够唯一确定Y，反之亦然。

可逆语言设计中，必须要使赋值语句作为单射的状态变换函数。传统语言中的赋值语句都是不可逆的，程序运行后，无法再通过内存状态回推前状态，因而，要想使其具备可逆性，则需要参照常用可逆逻辑门Toffoli门变换函数 f ( t1,c1,c2)= (t1⊕ ( c1• c2), c1, c2，)使赋值语句遵循 f (x , y1,y2,. ..yn) = (x ⊕ g (y1,y2,.. .yn)) 规则。其中，“ ”为异或运算，且 ⊕ ∈ { + ,- ,-} ，因所区运算符需要对公式中第一⊕参数单射。“·”为与运算，x，y1，y2，...，yn都代表内存中的变量。同时， g (y

1,y2,.. ., yn) 是对内存中变量进行任意计算的表达式，但是其中需要注意的一点是，不可以包括x，否则会影响可逆性。这一表达式无需可逆，能够包含任何运算符，主要通过临时变量的添加，就可以实现所有不可逆赋值语句的可逆。例如就“x=x＊y+z”这一不可逆赋值表达式而言，要想使其具备可逆性，则只需要增加临时变量t，使表达式变为 t = t-x ; x = x-( t ＊ y + z )，在保持原本表达能力的同时，赋予其可逆性。

1.2 遵循控制结构可逆原则

结构化程序设计中，主要包括三种控制结构。第一种是顺序结构，只要实现基本语句可逆，则该结构可逆。第二种是分支结构、第三种是循环结构，这两种结构由于其执行流程图中存在执行分支汇聚点，在实现可逆的过程中，逆向运行至汇聚点，没有明确的指示命令其选择哪一分支继续运行，因而即使基本语句可逆，这两种结构也无法实现可逆。为了解决这一情况，可以在汇聚点设置条件判断，从而使其实现可逆。

2 R-JAVA语言处理系统设计

2.1 概要设计

R-JAVA语言处理系统输入为R-JAVA源程序，而这一源程序既包含可逆成员函数，同时也包含普通成员函数。前者由R-JAVA编写，后者则由JAVA编写。其中的普通程序函数，系统会将其直接交由JDK，而可逆成员函数方面，系统则需要将其进行翻译，使其最终成为两个分别对应正向、反向语义的成员函数JAVA代码。随后，将得到的成员函数JAVA代码与普通成员函数JAVA代码进行合并，从而形成目标程序，并由JDK解释运行。

该系统主要包括三个模块，第一个模块是词法分析器，这一模块相对来说较为简单，第二个模块是语法分析器，第三个模块是翻译器，这两个模块需要在设计中加强重视。

2.2 语法分析器设计

R-JAVA文法设计是R-JAVA语言处理系统语法分析器设计中的重要部分，文法类型与语法分析方法息息相关，因而，在语法分析器设计中，首先需要进行 R-JAVA文法设计。R-JAVA选用的递归下降分析法是一种易于构造的语法分析方法，要求文法属于LL（1）型。同时，要求文法规则不可以存在左递归，并需要保证文法可逆，因而其设计过程存在一定的难度。另外，文法表达是不要求可逆，因而，其文法规则与传统语言相同。R-JAVA文法中，所有的可逆成员函数都应将关键字“reverse”作为开头，函数体中的变量都是类成员变量，条件语句中需包括两个“布尔条件”，并且当型循环语句也是如此，且需要按照出现顺序分别对应改造后的可逆分支结构和可逆循环结构程序中的布尔条件。同时，可逆成员函数都无形参和返回值，调用函数的过程中，若是不添加后缀“＿rev”则为正向调用，若是添加则为发向调用，且赋值语句最右值可逆运算符中，仅能够包含加、减、异或，其表达式中则能够包含任意运算符号。

R-JAVA语言处理系统中的语法分析器，主要能够实现可逆成员函数语法分析，并生成包含调用元语句、赋值元语句、边界元语句等六种不同类型元语句的中间代码-元语句组。其中，Node元语句是所有元语句的父类，BoundNode是边界元语句的父类[3]。根据源程序中各成分向元语句类型的转换规则可知，stmts代表语句块，其主要包含分支语句、赋值语句、循环语句等成分，通过相应成分的调用，能够实现其与元语句的转换。而根据R-JAVA文法规则，能够了解到文法中所有的非终结符在类Parser中都会进行相应的处理，语法分析器代码也封装在Parser类中。在处理过程中，语法分析从符号“可逆程序”出发，在遇到终结符时，会将其与Token进行对比匹配，判断其匹配适宜性，在遇到非终结符时，则会调用与之对应的处理过程。

2.3 R-JAVA翻译器设计

R-JAVA翻译器能够将元语句翻译成等价的JAVA代码。在R-JAVA翻译器设计中，必须实现其对元语句组正反双向翻译的功能，而其中的反向翻译难度较大，不仅遍历顺序改变，同时也需要对每条翻译进行适当的语义反转。按照翻译规则，翻译器对元语句进行正向和反向双向逐条翻译。反向翻译函数back-wd（）处理过程中，先将指针定位在元语句组的倒序第一条记录，并向前遍历至正序第一条记录，从而实现所有元语句的反向翻译。

3 结论

本文对可逆编程语言R-JAVA进行了简要介绍，并分析其设计原则，设计了可逆编程语言R-JAVA语言处理系统。该系统能够实现R-JAVA源文件向JAVA目标文件的转换，既能够获取正向运行结果，也能够实现逆向运行恢复输入。

[1]高官涛，郑小盈，李明齐.面向R语言的分布式流处理系统设计与实现[J].科学技术与工程，2016，2(2):208-213.

[2]卫丽华.可逆编程语言相关理论及实践研究[J].软件导刊，2015，2(2):62-65.

[3]朱鹏程，管致锦.可逆乘除法指令的设计与仿真[J].计算机工程与设计，2015，7(7):1800-1807.

Design of reversible programming language R-JAVA and its language processing system

Xue Huijun
（Inner Mongolia Electronic Information Vocational Technical College, Inner Mongolia Hohhot,010070）

reversible programming language is the important content in the research of reversible computing, using reversible programming language program, to achieve two-way running forward and reverse, which respectively obtain and recover the input function two. Therefore, it is necessary to study the reversible programming language.

reversible programming language R-JAVA; language processing system; design