薛慧君

（內(nèi)蒙古電子信息職業(yè)技術(shù)學(xué)院，內(nèi)蒙古呼和浩特，010070）

可逆編程語言R-JAVA及其語言處理系統(tǒng)的設(shè)計

薛慧君

（內(nèi)蒙古電子信息職業(yè)技術(shù)學(xué)院，內(nèi)蒙古呼和浩特，010070）

可逆編程語言是可逆計算研究中的重要內(nèi)容，利用可逆編程語言編寫的程序，能夠?qū)崿F(xiàn)正向和反向的雙向運(yùn)行，從而分別實(shí)現(xiàn)結(jié)果獲取和恢復(fù)輸入兩方面功能。因而，可逆編程語言的研究十分必要。

可逆編程語言R-JAVA；語言處理系統(tǒng)；設(shè)計

0 引言

Janus是現(xiàn)知最早的可逆編程語言，目前流行的計算機(jī)都存在邏輯上的不可逆，在其運(yùn)行計算時，會出現(xiàn)信息丟失等情況，且無法返回推前狀態(tài)，而理論上講，若是具備充足的存儲空間，則所有邏輯上的不可逆計算，都能夠成為可逆計算，Janus語言便是基于這一理論，所形成的可逆編程語言。其語法設(shè)計主要遵循基本語句可逆和控制結(jié)構(gòu)可逆兩方面原則，而R-JAVA也是如此。

1 可逆編程語言R-JAVA設(shè)計原則

1.1 遵循基本語句可逆原則

要想實(shí)現(xiàn)可逆計算，必須要在軟件層次和邏輯綜合層次找到適合的可逆變換函數(shù)[1]。軟件層次上，程序中語句執(zhí)行內(nèi)存的變量值為動態(tài)狀態(tài)，因而，在軟件層次中，程序段賦值語句為內(nèi)存狀態(tài)變換函數(shù)，即 Y = f (X ) ，其中，X為程序運(yùn)行前內(nèi)存的內(nèi)存狀態(tài)，Y則為程序運(yùn)行后的內(nèi)存狀態(tài)。在可逆邏輯綜合中，n變量布爾函數(shù) f (x

1, x2,

. .. ,xn) 要想實(shí)現(xiàn)可逆性，必須具備相應(yīng)的性質(zhì)。也就要求，n變量布爾多輸出函數(shù)必須具備可逆性。即如果輸出數(shù)等于輸入數(shù)且任一個輸出模式只有一個唯一的原象[2]?；谶@一性質(zhì)，結(jié)合軟件層次函數(shù)，則以上提到的函數(shù)只要是單射函數(shù)，便具有可逆性。即 f ( a ) = f (b ) ? a = b ， Y = f-1( X ) 。X能夠唯一確定Y，反之亦然。

可逆語言設(shè)計中，必須要使賦值語句作為單射的狀態(tài)變換函數(shù)。傳統(tǒng)語言中的賦值語句都是不可逆的，程序運(yùn)行后，無法再通過內(nèi)存狀態(tài)回推前狀態(tài)，因而，要想使其具備可逆性，則需要參照常用可逆邏輯門Toffoli門變換函數(shù) f ( t1,c1,c2)= (t1⊕ ( c1? c2), c1, c2，)使賦值語句遵循 f (x , y1,y2,. ..yn) = (x ⊕ g (y1,y2,.. .yn)) 規(guī)則。其中，“ ”為異或運(yùn)算，且 ⊕ ∈ { + ,- ,-} ，因所區(qū)運(yùn)算符需要對公式中第一⊕參數(shù)單射?！啊ぁ睘榕c運(yùn)算，x，y1，y2，...，yn都代表內(nèi)存中的變量。同時， g (y

1,y2,.. ., yn) 是對內(nèi)存中變量進(jìn)行任意計算的表達(dá)式，但是其中需要注意的一點(diǎn)是，不可以包括x，否則會影響可逆性。這一表達(dá)式無需可逆，能夠包含任何運(yùn)算符，主要通過臨時變量的添加，就可以實(shí)現(xiàn)所有不可逆賦值語句的可逆。例如就“x=x＊y+z”這一不可逆賦值表達(dá)式而言，要想使其具備可逆性，則只需要增加臨時變量t，使表達(dá)式變?yōu)?t = t-x ; x = x-( t ＊ y + z )，在保持原本表達(dá)能力的同時，賦予其可逆性。

1.2 遵循控制結(jié)構(gòu)可逆原則

結(jié)構(gòu)化程序設(shè)計中，主要包括三種控制結(jié)構(gòu)。第一種是順序結(jié)構(gòu)，只要實(shí)現(xiàn)基本語句可逆，則該結(jié)構(gòu)可逆。第二種是分支結(jié)構(gòu)、第三種是循環(huán)結(jié)構(gòu)，這兩種結(jié)構(gòu)由于其執(zhí)行流程圖中存在執(zhí)行分支匯聚點(diǎn)，在實(shí)現(xiàn)可逆的過程中，逆向運(yùn)行至匯聚點(diǎn)，沒有明確的指示命令其選擇哪一分支繼續(xù)運(yùn)行，因而即使基本語句可逆，這兩種結(jié)構(gòu)也無法實(shí)現(xiàn)可逆。為了解決這一情況，可以在匯聚點(diǎn)設(shè)置條件判斷，從而使其實(shí)現(xiàn)可逆。

2 R-JAVA語言處理系統(tǒng)設(shè)計

2.1 概要設(shè)計

R-JAVA語言處理系統(tǒng)輸入為R-JAVA源程序，而這一源程序既包含可逆成員函數(shù)，同時也包含普通成員函數(shù)。前者由R-JAVA編寫，后者則由JAVA編寫。其中的普通程序函數(shù)，系統(tǒng)會將其直接交由JDK，而可逆成員函數(shù)方面，系統(tǒng)則需要將其進(jìn)行翻譯，使其最終成為兩個分別對應(yīng)正向、反向語義的成員函數(shù)JAVA代碼。隨后，將得到的成員函數(shù)JAVA代碼與普通成員函數(shù)JAVA代碼進(jìn)行合并，從而形成目標(biāo)程序，并由JDK解釋運(yùn)行。

該系統(tǒng)主要包括三個模塊，第一個模塊是詞法分析器，這一模塊相對來說較為簡單，第二個模塊是語法分析器，第三個模塊是翻譯器，這兩個模塊需要在設(shè)計中加強(qiáng)重視。

2.2 語法分析器設(shè)計

R-JAVA文法設(shè)計是R-JAVA語言處理系統(tǒng)語法分析器設(shè)計中的重要部分，文法類型與語法分析方法息息相關(guān)，因而，在語法分析器設(shè)計中，首先需要進(jìn)行 R-JAVA文法設(shè)計。R-JAVA選用的遞歸下降分析法是一種易于構(gòu)造的語法分析方法，要求文法屬于LL（1）型。同時，要求文法規(guī)則不可以存在左遞歸，并需要保證文法可逆，因而其設(shè)計過程存在一定的難度。另外，文法表達(dá)是不要求可逆，因而，其文法規(guī)則與傳統(tǒng)語言相同。R-JAVA文法中，所有的可逆成員函數(shù)都應(yīng)將關(guān)鍵字“reverse”作為開頭，函數(shù)體中的變量都是類成員變量，條件語句中需包括兩個“布爾條件”，并且當(dāng)型循環(huán)語句也是如此，且需要按照出現(xiàn)順序分別對應(yīng)改造后的可逆分支結(jié)構(gòu)和可逆循環(huán)結(jié)構(gòu)程序中的布爾條件。同時，可逆成員函數(shù)都無形參和返回值，調(diào)用函數(shù)的過程中，若是不添加后綴“＿rev”則為正向調(diào)用，若是添加則為發(fā)向調(diào)用，且賦值語句最右值可逆運(yùn)算符中，僅能夠包含加、減、異或，其表達(dá)式中則能夠包含任意運(yùn)算符號。

R-JAVA語言處理系統(tǒng)中的語法分析器，主要能夠?qū)崿F(xiàn)可逆成員函數(shù)語法分析，并生成包含調(diào)用元語句、賦值元語句、邊界元語句等六種不同類型元語句的中間代碼-元語句組。其中，Node元語句是所有元語句的父類，BoundNode是邊界元語句的父類[3]。根據(jù)源程序中各成分向元語句類型的轉(zhuǎn)換規(guī)則可知，stmts代表語句塊，其主要包含分支語句、賦值語句、循環(huán)語句等成分，通過相應(yīng)成分的調(diào)用，能夠?qū)崿F(xiàn)其與元語句的轉(zhuǎn)換。而根據(jù)R-JAVA文法規(guī)則，能夠了解到文法中所有的非終結(jié)符在類Parser中都會進(jìn)行相應(yīng)的處理，語法分析器代碼也封裝在Parser類中。在處理過程中，語法分析從符號“可逆程序”出發(fā)，在遇到終結(jié)符時，會將其與Token進(jìn)行對比匹配，判斷其匹配適宜性，在遇到非終結(jié)符時，則會調(diào)用與之對應(yīng)的處理過程。

2.3 R-JAVA翻譯器設(shè)計

R-JAVA翻譯器能夠?qū)⒃Z句翻譯成等價的JAVA代碼。在R-JAVA翻譯器設(shè)計中，必須實(shí)現(xiàn)其對元語句組正反雙向翻譯的功能，而其中的反向翻譯難度較大，不僅遍歷順序改變，同時也需要對每條翻譯進(jìn)行適當(dāng)?shù)恼Z義反轉(zhuǎn)。按照翻譯規(guī)則，翻譯器對元語句進(jìn)行正向和反向雙向逐條翻譯。反向翻譯函數(shù)back-wd（）處理過程中，先將指針定位在元語句組的倒序第一條記錄，并向前遍歷至正序第一條記錄，從而實(shí)現(xiàn)所有元語句的反向翻譯。

3 結(jié)論

本文對可逆編程語言R-JAVA進(jìn)行了簡要介紹，并分析其設(shè)計原則，設(shè)計了可逆編程語言R-JAVA語言處理系統(tǒng)。該系統(tǒng)能夠?qū)崿F(xiàn)R-JAVA源文件向JAVA目標(biāo)文件的轉(zhuǎn)換，既能夠獲取正向運(yùn)行結(jié)果，也能夠?qū)崿F(xiàn)逆向運(yùn)行恢復(fù)輸入。

[1]高官濤，鄭小盈，李明齊.面向R語言的分布式流處理系統(tǒng)設(shè)計與實(shí)現(xiàn)[J].科學(xué)技術(shù)與工程，2016，2(2):208-213.

[2]衛(wèi)麗華.可逆編程語言相關(guān)理論及實(shí)踐研究[J].軟件導(dǎo)刊，2015，2(2):62-65.

[3]朱鵬程，管致錦.可逆乘除法指令的設(shè)計與仿真[J].計算機(jī)工程與設(shè)計，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