張應(yīng)征

摘要：在可逆計(jì)算機(jī)研究過(guò)程中，可逆編程語(yǔ)言是尤為重要的內(nèi)容，通過(guò)可逆編程語(yǔ)言對(duì)程序進(jìn)行編寫(xiě)，能夠?qū)崿F(xiàn)正反兩個(gè)方向的運(yùn)行，以此不僅能夠獲得程序的結(jié)果，還能夠恢復(fù)輸入，所以對(duì)可逆編程語(yǔ)言的研究是非常有必要的?；诖?，該文就對(duì)可編程語(yǔ)言R-JAVA和其語(yǔ)言處理系統(tǒng)進(jìn)行設(shè)計(jì)及分析。

關(guān)鍵詞：可逆編程語(yǔ)言；語(yǔ)言處理；系統(tǒng)設(shè)計(jì)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）17-0063-02

可逆編程語(yǔ)言是可逆計(jì)算中的分支，通過(guò)其編寫(xiě)的程序段不僅能夠獲得正向運(yùn)行的結(jié)果，還能夠獲得方向運(yùn)行恢復(fù)的輸入，現(xiàn)在對(duì)可逆計(jì)算的研究主要包括可逆邏輯綜合、邏輯門及電路等硬件方面，但是關(guān)于軟件方面的研究卻非常少?？赡嫦到y(tǒng)的完整性主要包括硬件和軟件兩部分的可逆，但是目前流行的編程語(yǔ)言都是不可逆的，其編程程序在運(yùn)行過(guò)程中能夠?qū)π畔⑦M(jìn)行擦除，并且計(jì)算過(guò)程只有正向確定，沒(méi)有方向確定，所以可逆計(jì)算不能夠在軟件層實(shí)現(xiàn)。目前，如何實(shí)現(xiàn)可逆硬件平臺(tái)中軟件系統(tǒng)的研究是尤為重要的內(nèi)容。

1可逆編程語(yǔ)言R-JAVA的設(shè)計(jì)原則

1.1基本語(yǔ)句

1.2控制結(jié)構(gòu)

結(jié)構(gòu)化程序在設(shè)計(jì)過(guò)程中最常用的控制結(jié)構(gòu)包括分支、順序及循環(huán)，只要基本語(yǔ)句，那么就表示順序結(jié)構(gòu)可逆，但是循環(huán)和分支不可逆，因?yàn)閮烧叩膱?zhí)行流程圖具有執(zhí)行分支匯聚點(diǎn)，在逆向到匯聚點(diǎn)的時(shí)候，分支的選擇沒(méi)有依據(jù)。為了避免不可逆的出現(xiàn)，就要在分支匯聚點(diǎn)出現(xiàn)添加條件進(jìn)行判斷，在改造之后的可逆結(jié)構(gòu)及循環(huán)結(jié)構(gòu)見(jiàn)圖1。

1.3其他控制

可逆編程語(yǔ)言R-JAVA中不僅包括JAVA語(yǔ)言的傳統(tǒng)代碼，還包括R-JAVA定義的可逆代碼，兩者的形式為成員函數(shù)。成員函數(shù)還包括普通成員及可逆成員，為了避免將兩者弄混，那么就分別對(duì)兩者進(jìn)行定義。首先對(duì)普通成員進(jìn)行定義，之后對(duì)可逆成員進(jìn)行定義，從“reverse”標(biāo)識(shí)符定義可逆函數(shù)，使用JAVA語(yǔ)言對(duì)普通成員函數(shù)進(jìn)行編寫(xiě)，其不需要遵守可逆的原則；使用R-JAVA語(yǔ)言對(duì)可逆成員函數(shù)進(jìn)行編寫(xiě)，其需要遵守可你的原則。普通成員能夠?qū)崿F(xiàn)可逆成員的調(diào)用，但是可逆成員不能夠調(diào)用普通成員，可逆成員的不同函數(shù)能夠相互調(diào)用。可逆成員要有兩個(gè)對(duì)應(yīng)語(yǔ)義，分別為正向和反向兩種，調(diào)用可逆函數(shù)要以形式為基礎(chǔ)進(jìn)行區(qū)分。

2可逆編程語(yǔ)言R-JAVA語(yǔ)言處理系統(tǒng)的設(shè)計(jì)

2.1文法設(shè)計(jì)

文法的類型選擇與語(yǔ)法的分析具有一定的聯(lián)系，可逆編程語(yǔ)言使用的是遞歸下降的分析方法，其不僅直觀簡(jiǎn)單，還便于構(gòu)造。但是遞歸下降要求文法為L(zhǎng)L1型，也就是要在分析過(guò)程中向前預(yù)讀Token，從而決定使用哪種產(chǎn)生式，所以文法的規(guī)則不能夠具有左遞歸，并且還要具有文法可逆，這點(diǎn)是文法設(shè)計(jì)中尤為重要的內(nèi)容。可逆成員函數(shù)的開(kāi)頭一般都是“reverse”，并且沒(méi)有返回值及形參，函數(shù)體中與運(yùn)算變量有關(guān)的都是類成員變量，其中賦值右值的可逆運(yùn)算只包括異或及加減。條件及當(dāng)型兩個(gè)循環(huán)語(yǔ)句中的布爾條件有兩個(gè)，根據(jù)出現(xiàn)的順序分別對(duì)應(yīng)。在函數(shù)調(diào)用過(guò)程中，反向調(diào)用的后綴為“_rev”。遞歸下降能夠?qū)崿F(xiàn)語(yǔ)法分析器，其主要作用就是實(shí)現(xiàn)可逆成員的函數(shù)語(yǔ)法分析，并且生成中間代碼。語(yǔ)法分析器的代碼在Parser類中封裝，非終結(jié)符都具有對(duì)應(yīng)的處理過(guò)程，通過(guò)可逆程序符號(hào)實(shí)現(xiàn)語(yǔ)法分析，在遇到非終結(jié)符的時(shí)候，對(duì)相應(yīng)的處理進(jìn)行調(diào)用。在遇到終結(jié)符的時(shí)候，判斷是否匹配。

2.2設(shè)計(jì)語(yǔ)法分析器

在可逆編程語(yǔ)言處理系統(tǒng)中設(shè)計(jì)語(yǔ)法分析器是文法設(shè)計(jì)的重要內(nèi)容，兩者具有密切的聯(lián)系。語(yǔ)法分析器的主要目的就是分析可逆成員函數(shù)語(yǔ)法，并且生成賦值、調(diào)用及邊界等元語(yǔ)句，元語(yǔ)句的父類為Node原函數(shù)，邊界原函數(shù)的父類為Bound-Node。以源程序的成分向元語(yǔ)句類型轉(zhuǎn)換規(guī)則為基礎(chǔ)，語(yǔ)句塊表示為stmts，主要包括賦值、分支及循環(huán)等語(yǔ)句，通過(guò)對(duì)豫劇的調(diào)用使其能夠和元語(yǔ)句進(jìn)行轉(zhuǎn)換。通過(guò)可編程語(yǔ)言的文法規(guī)則可以看出來(lái)，文法的Parser中能夠處理非終結(jié)符，并且在Parser類中封裝語(yǔ)法分析器代碼。在進(jìn)行處理的時(shí)候，從可逆程序進(jìn)行語(yǔ)法分析，在遇到終結(jié)符的時(shí)候要和Token對(duì)比及匹配，判斷是否匹配；在遇到非終結(jié)符的時(shí)候，就要對(duì)相關(guān)的處理進(jìn)行調(diào)用。在處理的時(shí)候通過(guò)相應(yīng)的規(guī)則對(duì)元語(yǔ)句進(jìn)行匹配，在其中添加元語(yǔ)句組具有重要的作用。

2.3設(shè)計(jì)翻譯器

因?yàn)榭赡婧瘮?shù)不僅具有正向語(yǔ)義，還具有方向語(yǔ)義，所以翻譯器也要具有這兩種元語(yǔ)句組。正向翻譯是非常容易的，只需要實(shí)現(xiàn)元語(yǔ)句組的遍歷，將元語(yǔ)句翻譯為等價(jià)代碼。但是反向翻譯不僅要具有上述過(guò)程，還要轉(zhuǎn)換每條元語(yǔ)句翻譯，從而實(shí)現(xiàn)語(yǔ)義的反轉(zhuǎn)。每個(gè)語(yǔ)義都具有相應(yīng)的翻譯規(guī)則，每個(gè)翻譯規(guī)則的元語(yǔ)句翻譯都要通過(guò)正向及方向語(yǔ)義實(shí)現(xiàn)。翻譯器中的代碼都在Intepreter類中封裝，正向及方向的翻譯區(qū)別為正向翻譯的遍歷是從前到后實(shí)現(xiàn)的，反向翻譯則是相反。

3結(jié)束語(yǔ)

本文首先介紹了可逆編程語(yǔ)言的設(shè)計(jì)原則，之后對(duì)可逆編程語(yǔ)言R-JAVA處理系統(tǒng)的設(shè)計(jì)進(jìn)行了分析，此系統(tǒng)能夠?qū)⒖赡婢幊陶Z(yǔ)言的源文件轉(zhuǎn)變?yōu)镴AVA目標(biāo)文件，不僅能夠得到正向預(yù)算的結(jié)果，還能夠進(jìn)行逆向的恢復(fù)輸入。為了給基于可逆邏輯綜合、可逆電路技術(shù)的可逆硬件平臺(tái)設(shè)計(jì)可逆軟件系統(tǒng)，提出基于JDK的可逆編程語(yǔ)言RJAVA。首先總結(jié)可逆編程語(yǔ)言的設(shè)計(jì)原則然后為可逆語(yǔ)言R-JAVA設(shè)計(jì)文法規(guī)則和語(yǔ)言處理系統(tǒng)，其語(yǔ)言處理系統(tǒng)提取源程序中的可逆代碼段并將其翻譯成分別對(duì)應(yīng)正反語(yǔ)義的等價(jià)JAVA代碼，再將翻譯后的JA-VA代碼交由JDK解釋執(zhí)行。最后通過(guò)示例程序表明R-JAVA源程序中的可逆函數(shù)既可正向運(yùn)行，又可反向運(yùn)行，從軟件層次上實(shí)現(xiàn)了可逆計(jì)算。