可逆編程語言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