同步語言Lustre的編譯前端的設(shè)計(jì)與實(shí)現(xiàn)

宋宇婷，孫小祥，冉 丹

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211100)

0 引 言

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，人們的工作、學(xué)習(xí)和生活各個(gè)方面都越來越依賴于計(jì)算機(jī)技術(shù)以及計(jì)算機(jī)技術(shù)的產(chǎn)物，它們已經(jīng)成為人們工作、學(xué)習(xí)和生活中不可分割的一部分。近年來，它們的安全性和正確性等方面也受到越來越多的關(guān)注。因?yàn)?，一個(gè)小小的錯(cuò)誤很可能造成很嚴(yán)重甚至是不可挽回的后果。為了保證系統(tǒng)設(shè)計(jì)的正確運(yùn)行，需要一種可靠的編譯器，它能夠檢測(cè)到詞法語法等方面的錯(cuò)誤，并將錯(cuò)誤反饋出來，幫助及時(shí)修改系統(tǒng)程序，保證系統(tǒng)的正確運(yùn)行。編譯器的構(gòu)建分為前端和后端兩大部分，前端主要是負(fù)責(zé)分析輸入的源代碼，對(duì)源程序進(jìn)行詞法分析、語法分析和語義分析[1-2]。同時(shí)，前端還會(huì)將分析的有效信息保存起來，傳遞給后端。

傳統(tǒng)的同步語言Lustre的編譯器前端大都采用OCaml語言編寫，OCaml語言是一種函數(shù)式編程語言[3]，適用度沒有C++語言[4-5]高，C++語言是開發(fā)人員和用戶們最易于使用和易于理解的語言之一。新型的Lustre語言的編譯前端采用C++語言進(jìn)行描述，可以準(zhǔn)確地編譯Lustre語言程序，保證Lustre語言所描繪的模型的正確運(yùn)行。這對(duì)航空航天、國防建設(shè)、核電建設(shè)、金融監(jiān)管等領(lǐng)域具有重要的意義。編譯前端所產(chǎn)生的抽象語法樹結(jié)構(gòu)的實(shí)際應(yīng)用也很廣泛，既可以應(yīng)用于編譯器后端的開發(fā)，也可以應(yīng)用于模型檢測(cè)、軟件驗(yàn)證等工具的開發(fā)。目前，國外比較成熟的是Kind和Kind2[6]，而國內(nèi)對(duì)同步語言Lustre及其編譯器的研究比較少，L2C編譯器是比較成熟的[7-8]。

1 系統(tǒng)分析

新型的Lustre語言的編譯前端，提供了一種新型的檢驗(yàn)Lustre語言所描述的模型是否正確的方法。如果Lustre語言所描述的模型是基本正確的，不存在任何詞法和語法的錯(cuò)誤，系統(tǒng)會(huì)正確地輸出Lustre語言模型的抽象語法樹；否則，系統(tǒng)會(huì)給出詞法或者語法錯(cuò)誤的提示。為了保證系統(tǒng)的正確性和可靠性，系統(tǒng)應(yīng)該具備如下的性能需求。

(1)詞法規(guī)則和語法規(guī)則的正確描述。系統(tǒng)在對(duì)Lustre語言模型進(jìn)行詞法分析和語法分析時(shí)，應(yīng)該嚴(yán)格按照Lustre語言的說明文檔進(jìn)行解析；否則，很可能造成無法正確解析Lustre語言模型，給出錯(cuò)誤結(jié)果，影響系統(tǒng)的正確運(yùn)行。

(2)信息處理的準(zhǔn)確性。當(dāng)Lustre語言模型存在任何詞法和語法錯(cuò)誤時(shí)，系統(tǒng)能夠及時(shí)快速地給出反饋信息，將模型的第幾行存在詞法錯(cuò)誤或者語法錯(cuò)誤的提示消息發(fā)送給用戶，保證用戶能夠及時(shí)進(jìn)行Lustre語言模型的更正。

2 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

2.1 同步語言Lustre

同步語言Lustre是一種常用的數(shù)據(jù)流語言，其基本的數(shù)據(jù)對(duì)象是流[5]。一個(gè)同步語言程序就是一個(gè)函數(shù)，具有零個(gè)或者更多的輸入流以及一個(gè)或者更多的輸出流，一個(gè)流就是一個(gè)變量值的序列。在同步語言Lustre程序中，任何變量和表達(dá)式都詮釋了一個(gè)流，一個(gè)流是由給定類型的變量的無窮多序列值和一個(gè)時(shí)鐘組成的[9-10]。流通常用(a,b,c,d,e)表示，括號(hào)內(nèi)的a,b,c,d,e表示流在某個(gè)時(shí)刻點(diǎn)所對(duì)應(yīng)的值。同步語言Lustre的時(shí)序操作符主要包括如下幾種：

(1)pre(previous):求變量或者表達(dá)式的前一時(shí)刻的序列值。比如，整數(shù)型變量X的當(dāng)前值為(x1,x2,…,xn,…)，那么，pre(x)=(nil,x1,x2,…,xn-1,…)。

(2)->(followed by):定義了前一個(gè)表達(dá)式被后一個(gè)表達(dá)式賦值之后的初始值。比如，X=(x1,x2,…,xn,…)和Y=(y1,y2,…,yn,…)是相同類型且具有相同時(shí)鐘的兩個(gè)表達(dá)式，那么X->Y是與X和Y具有相同類型和相同時(shí)鐘的表達(dá)式，且X->Y=(x1,y2,y3,…,yn,…)。這意味著，除了時(shí)鐘的第一時(shí)刻，X->Y總是等于Y。在Lustre語言中，時(shí)序操作符->也可以采用關(guān)鍵字fby的形式進(jìn)行表示，即：X->Y與XfbyY的含義是相同的。

(3)when:作為下一條語句執(zhí)行的條件，與C語言中的when類似。如果X是一個(gè)表達(dá)式，B是一個(gè)布爾表達(dá)式，而且它們有相同的時(shí)鐘，那么XwhenB是一個(gè)表達(dá)式，且它的時(shí)鐘由B決定。但是，要注意的是，XwhenB表達(dá)式的值是在B為true時(shí)所對(duì)應(yīng)的B的序列值。比如，B=(false，true，false，true，false，false，true)，X=(x1,x2,…,x7)，那么，XwhenB=( ,x2, ,x4, , ,x7)。

(4)current:求變量或表達(dá)式的當(dāng)前序列值?；趙hen時(shí)序操作符中的例子，假設(shè)Y=current (XwhenB)，那么，Y=(nil,x2,x2,x4,x4,x4,x7)，其中nil表示空值。

2.2 Lustre語言的詞法分析設(shè)計(jì)

詞法分析的主要任務(wù)是從左到右讀入源程序的輸入字符，然后根據(jù)構(gòu)詞規(guī)則識(shí)別單詞符號(hào)。實(shí)際上就是將源程序翻譯為詞法單元，并將詞法單元作為語法分析的輸入[11]。通常情況下，詞法單元分為如下的五大類。第一類是關(guān)鍵字詞法單元，程序語言中的每個(gè)關(guān)鍵字都有一個(gè)詞法單元，詞法單元名就是關(guān)鍵字的大寫。比如：Lustre語言中的VAR(var)、RETURNS(returns)等詞法單元。第二類是運(yùn)算符詞法單元，每個(gè)運(yùn)算符可以有一個(gè)獨(dú)立的詞法單元，也可以按照運(yùn)算符的階數(shù)或者含義進(jìn)行分類。比如：Lustre語言中的FOLLOWBY(->)、PRE(pre)等。第三類是表示所有標(biāo)識(shí)符的詞法單元，比如程序中定義的變量名和數(shù)組名等。第四類是表示常量的詞法單元，比如：INTEGER([1-9]+[0-9]*|0)。第五類是標(biāo)點(diǎn)符號(hào)詞法單元，而且，每個(gè)標(biāo)點(diǎn)符號(hào)都有一個(gè)詞法單元。比如：SEMI(;)、COMMA(,)等。除了關(guān)鍵字類的詞法單元名，其余類別的詞法單元名一般都是相應(yīng)符號(hào)的英文名稱的縮寫。在Lustre語言中，邏輯運(yùn)算符也是以關(guān)鍵字的形式表示的，所以，這類運(yùn)算符詞法單元要加入到關(guān)鍵字詞法單元中。而且，這些詞法單元都作為終結(jié)符號(hào)。Lustre語言詞法單元的部分定義如表1所示。

2.3 Lustre語言的語法分析設(shè)計(jì)

語法分析的主要任務(wù)是將單詞序列組合成各類語法短語，如“程序”、“語句”、“表達(dá)式”等等，實(shí)際上就是將詞法單元翻譯為抽象語法樹。語法分析的目的是判斷源程序在語法結(jié)構(gòu)上是否符合正確的語法規(guī)則，而源程序的結(jié)構(gòu)通常由上下文無關(guān)文法描述[11]。

Lustre語言的編譯前端的語法分析模塊主要是通過查找可以與當(dāng)前記號(hào)進(jìn)行匹配的規(guī)則來進(jìn)行操作。主要的算法思想為：當(dāng)語法分析模塊讀取符號(hào)時(shí)，每當(dāng)它讀取到的符號(hào)無法結(jié)束一條Lustre語法規(guī)則時(shí)，它會(huì)把這個(gè)符號(hào)壓入一個(gè)內(nèi)部堆棧，形成一個(gè)新的狀態(tài)，這個(gè)新的狀態(tài)能夠反映出剛剛讀取的字符。如果語法分析模塊發(fā)現(xiàn)壓入的所有字符正好可以組成語法規(guī)則的右部時(shí)，就將右部符號(hào)全部彈出堆棧，并將與語法規(guī)則右部對(duì)應(yīng)的語法規(guī)則的左部符號(hào)壓入堆棧，這個(gè)過程被稱為“規(guī)約”。持續(xù)上面的進(jìn)棧和規(guī)約過程，直到所有的Lustre語言的字符都已經(jīng)掃描完畢。最終，所有的Lustre語言模型都會(huì)被規(guī)約為“Program”。其中，“Program”代表著所有Lustre語言程序的開始符號(hào)。

為了避免在詞法分析和語法分析時(shí)出現(xiàn)二義性沖突，必須將關(guān)鍵字和特殊符號(hào)的定義與語法規(guī)則的相關(guān)定義進(jìn)行優(yōu)先處理。本次實(shí)驗(yàn)將關(guān)鍵字和特殊符號(hào)的定義放在標(biāo)識(shí)符的定義之前進(jìn)行判定和處理。

表1 詞法單元的定義

2.4 抽象語法樹的結(jié)構(gòu)設(shè)計(jì)

抽象語法樹類ASTNode[12-13]定義了五個(gè)屬性，一個(gè)用來記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)的變量parent；一個(gè)用來記錄節(jié)點(diǎn)的開始位置的變量location；一個(gè)用來記錄該節(jié)點(diǎn)在源程序中的位置startPosition，startPosition的初始值被設(shè)置為-1；一個(gè)bool類型的用來判斷該元素是否是必要的變量MANDATORY，此變量的初始值被設(shè)置為true(表示當(dāng)前的元素是必要的，不可缺少的)；一個(gè)bool類型的判斷操作的變量OPTIONAL，這個(gè)變量的初始值為false(表示當(dāng)前的操作是不可以為空的)。如果一個(gè)變量帶有OPTIONAL屬性，就表示這個(gè)變量可以為空，否則這個(gè)變量的值是不可能為空的。抽象語法樹類ASTNode還定義了幾個(gè)方法，主要包括一個(gè)設(shè)置父節(jié)點(diǎn)的函數(shù)setParent()，一個(gè)獲取父節(jié)點(diǎn)的函數(shù)getParent()，一個(gè)獲取根節(jié)點(diǎn)的函數(shù)getRoot()，一個(gè)刪除當(dāng)前節(jié)點(diǎn)的部分屬性的函數(shù)deleteNode()。

函數(shù)getRoot()的算法思想主要是先調(diào)用getParent()函數(shù)獲得當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，然后判斷這個(gè)父節(jié)點(diǎn)是否為空，如果父節(jié)點(diǎn)為空，就返回這個(gè)父節(jié)點(diǎn)，即：根節(jié)點(diǎn)；否則，就繼續(xù)循環(huán)地判斷這個(gè)父節(jié)點(diǎn)的父節(jié)點(diǎn)是否為空，直至滿足前邊的所有判斷條件為止。函數(shù)getRoot()的偽代碼如圖1所示。

圖1 getRoot()的偽代碼

類ASTNode中的函數(shù)deleteNode()的算法思想是首先調(diào)用getLocation()函數(shù)，獲取到節(jié)點(diǎn)的開始位置，然后判斷這個(gè)開始位置是否為空，如果為空，系統(tǒng)就什么都不做。再然后，判斷這個(gè)開始位置是否是ChildProperty類別的，如果屬于此類別，就先調(diào)用getParent()函數(shù)獲得當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，此父節(jié)點(diǎn)會(huì)調(diào)用setStructuralProperty()函數(shù)設(shè)置結(jié)構(gòu)屬性。最后，判斷這個(gè)開始位置是否是ChildListProperty類別的，如果屬于此類別，就先調(diào)用getParent()函數(shù)獲得當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，此父節(jié)點(diǎn)會(huì)調(diào)用getStructuralProperty()函數(shù)獲取結(jié)構(gòu)屬性，再將獲取到的結(jié)構(gòu)屬性賦值給孩子節(jié)點(diǎn)列表childList。刪除節(jié)點(diǎn)的屬性的函數(shù)deleteNode()的偽代碼如圖2所示。

圖2 deleteNode()的偽代碼

3 實(shí)驗(yàn)結(jié)果展示

同步語言Lustre的編譯前端系統(tǒng)的實(shí)驗(yàn)對(duì)象為圖3所描繪的Lustre語言模型，Lustre語言模型實(shí)例如圖3所示。

圖3描述的Lustre語言模型實(shí)例包含了四個(gè)node函數(shù)單元，第一個(gè)node函數(shù)單元名為compute，主要包含了算術(shù)運(yùn)算符加、減和乘；第二個(gè)node函數(shù)單元名為E，主要包含了時(shí)序操作符->和pre，以及邏輯運(yùn)算符與(and)；第三個(gè)node函數(shù)單元名為call_E，調(diào)用了第二個(gè)node函數(shù)單元，主要包含了邏輯運(yùn)算符非(not)；第四個(gè)node函數(shù)單元名為Switch，主要包含了if-then-else表達(dá)式。在同步語言Lustre中，if-then-else的使用比較特殊，它們不再代表常見語言C/C++中的if-then-else語句，而是以表達(dá)式的形式展現(xiàn)，通常作為賦值表達(dá)式的右部。

圖3 Lustre語言模型實(shí)例

圖4 Lustre語言模型的實(shí)驗(yàn)效果

圖4描述了基于圖3所描述的Lustre語言模型實(shí)例的部分實(shí)驗(yàn)效果。圖4中的所有大寫字母節(jié)點(diǎn)代表了程序中的終結(jié)符，都是抽象語法樹的葉子節(jié)點(diǎn)；其余節(jié)點(diǎn)都是進(jìn)行語法規(guī)則推導(dǎo)時(shí)需要按照語法規(guī)則說明定義的非終結(jié)符號(hào)。其中，每個(gè)孩子節(jié)點(diǎn)都會(huì)相對(duì)于它的父節(jié)點(diǎn)縮進(jìn)兩格輸出，兄弟節(jié)點(diǎn)的輸出則是處于同等水平的。比如，圖4中的“Program(1)”表示Lustre語言程序的整體定義是在源程序的第一行開始的，它的孩子節(jié)點(diǎn)為“decl_temp(1)”。節(jié)點(diǎn)“decl_temp(1)”的孩子節(jié)點(diǎn)為“decls(1)”，表示Lustre語言程序的聲明也是從源程序的第一行開始的。節(jié)點(diǎn)“ID:x”和節(jié)點(diǎn)“COMMA(1)”就是兄弟節(jié)點(diǎn)，表示標(biāo)識(shí)符x(node函數(shù)單元compute中定義的一個(gè)變量)和關(guān)鍵字分號(hào)(；)是同級(jí)別的。其余節(jié)點(diǎn)的含義以及節(jié)點(diǎn)之間的關(guān)系都與這幾個(gè)節(jié)點(diǎn)類似。

4 結(jié)束語

新型Lustre語言的編譯前端的設(shè)計(jì)與實(shí)現(xiàn)準(zhǔn)確地編譯運(yùn)行了Lustre語言程序，保證了Lustre語言程序不存在任何詞法和語法的錯(cuò)誤，為編譯后端和模型檢測(cè)等方面的研究提供了堅(jiān)實(shí)的基礎(chǔ)。經(jīng)過檢測(cè)，新型的Lustre語言的編譯前端可以準(zhǔn)確地檢測(cè)所有Lustre語言程序。由于新型的Lustre語言的編譯前端采用C++語言進(jìn)行設(shè)計(jì)，非常易于相關(guān)人員的理解和使用。未來，會(huì)有越來越多的計(jì)算機(jī)學(xué)者加入對(duì)同步語言Lustre進(jìn)行編譯和檢測(cè)研究的行列，也會(huì)出現(xiàn)更加成熟的Lustre語言編譯工具。