??? 摘 要:針對(duì)OSEK標(biāo)準(zhǔn)的應(yīng)用設(shè)計(jì)了一個(gè)從OIL代碼到C代碼的自動(dòng)生成系統(tǒng),,該系統(tǒng)允許用戶輸入OIL配置文件信息,,讀取用戶的輸入轉(zhuǎn)換為標(biāo)準(zhǔn)的C程序,,返回給用戶,,在具體應(yīng)用的時(shí)候,,文法限制嚴(yán)格,。該系統(tǒng)結(jié)合代碼自動(dòng)生成的過程,,提出了一些具體的解決過程,,消弱了對(duì)文法輸入的限制,提高了對(duì)文法的適應(yīng)能力,。
??? 關(guān)鍵詞: 代碼自動(dòng)生成,;OIL;LL(K)
?
??? 代碼自動(dòng)生成是當(dāng)今自動(dòng)化程序設(shè)計(jì)的一個(gè)熱點(diǎn),,代碼自動(dòng)生成技術(shù)就是幫助程序員完成系統(tǒng)底層的,、重復(fù)性代碼的自動(dòng)生成,減少軟件開發(fā)中枯燥且重復(fù)的編碼工作,,使得程序員將更多的時(shí)間花在系統(tǒng)架構(gòu)研究,、軟件工程學(xué)習(xí)等方面,從而提高軟件系統(tǒng)健壯性,、可擴(kuò)展性以及可維護(hù)性和生產(chǎn)率,,縮短項(xiàng)目開發(fā)時(shí)間,節(jié)約項(xiàng)目的開發(fā)成本,,降低項(xiàng)目開發(fā)風(fēng)險(xiǎn),,提高軟件公司的信譽(yù)度,贏得市場主導(dǎo)地位,,使公司獲得最大回報(bào)率,。OIL配置文件是對(duì)OSEK標(biāo)準(zhǔn)的描述文件,OSEK/VDX是應(yīng)用在模塊和靜態(tài)實(shí)時(shí)操作系統(tǒng)上的標(biāo)準(zhǔn),,由主要的汽車制造商和供應(yīng)商,、研究機(jī)構(gòu)以及軟件開發(fā)商發(fā)起。在具體的開發(fā)過程中,,往往要根據(jù)OIL文件的描述來進(jìn)行具體的編碼,將代碼自動(dòng)生成技術(shù)應(yīng)用于OIL文件上,,可以減少程序員的大量手工開發(fā),,節(jié)省了大量的人力物力,具有相當(dāng)廣泛的工業(yè)應(yīng)用前景,。本文設(shè)計(jì)的系統(tǒng)接受用戶輸入的OIL配置文件,,然后經(jīng)過系統(tǒng)的分析生成相應(yīng)的C代碼,實(shí)現(xiàn)了從配置文件到具體程序的自動(dòng)化,,節(jié)省了大量的人力物力,,并且在嵌入式開發(fā)的時(shí)候可以繼承到嵌入式開發(fā)環(huán)境中,,提供了很大的便捷性。
1 OIL代碼自動(dòng)生成系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
1.1 OIL代碼自動(dòng)生成系統(tǒng)的功能描述
??? 本文中代碼自動(dòng)生成系統(tǒng)的設(shè)計(jì)模塊如圖1所示,。
?
??? OIL代碼自動(dòng)生成系統(tǒng)的輸入模塊主要是提供兩種方式讓用戶輸入OIL配置文件:一是用戶輸入完OIL配置文件后提供保存功能,,此時(shí)將用戶輸入的配置文件保存到用戶制定的文件夾內(nèi);二是提供選擇功能,,讓用戶選擇已經(jīng)保存好的配置文件或者是使用其他工具生成的配置文件,,將文件讀取進(jìn)系統(tǒng)。
??? 當(dāng)用戶確定輸入的配置文件并點(diǎn)擊生成按鈕后,,此時(shí)由分析模塊對(duì)用戶輸入的配置文件進(jìn)行分析,,系統(tǒng)根據(jù)系統(tǒng)規(guī)定好的產(chǎn)生式規(guī)則進(jìn)行判定,首先對(duì)配置文件進(jìn)行分詞,,系統(tǒng)根據(jù)輸入好的正則表達(dá)式提供有窮自動(dòng)機(jī)的功能,,對(duì)用戶的配置文件進(jìn)行詞法分析,將用戶輸入的字符串分割成符合OIL規(guī)范的字符集作為下一步語法分析的輸入,,此時(shí)得到的文件應(yīng)該是具有標(biāo)記的字符串集合,。隨后的語法分析模塊對(duì)詞法分析得到的結(jié)果進(jìn)行分析,根據(jù)預(yù)先設(shè)定的正則表達(dá)式來判定句子是否符合語法規(guī)則,,采用LL(K)進(jìn)行產(chǎn)生式匹配,,并且在匹配后建立相對(duì)應(yīng)的語法樹,為后面的C代碼生成打基礎(chǔ),。此后再進(jìn)行語義分析,,通過對(duì)語法樹進(jìn)行分析,得到帶有注釋的語法樹,,方便后面的轉(zhuǎn)換模塊進(jìn)行遍歷,。
??? 轉(zhuǎn)換模塊的工作主要是收集要生成的C程序中必要的數(shù)據(jù),例如CPU的信息,、消息間的相互聯(lián)系,、以及中斷和警告的信息等,通過對(duì)這些必要信息的記錄來實(shí)現(xiàn)從配置文件到C程序的數(shù)據(jù)的映射,,通過對(duì)前面OIL語法樹的遍歷得到這些數(shù)據(jù),。
??? 結(jié)果輸出模塊是主要是進(jìn)行模板構(gòu)造,對(duì)轉(zhuǎn)換模塊中得到的需要的數(shù)據(jù)和設(shè)定的模板相結(jié)合,,然后輸出,,得到最后要生成的C程序。
1.2 OIL代碼自動(dòng)生成系統(tǒng)的核心工作流程
??? OIL代碼自動(dòng)生成系統(tǒng)的工作流程如圖2所示,,圖2描述出了整個(gè)系統(tǒng)的核心工作流程:從用戶輸入代碼到輸入模塊,,一直到輸出C代碼返回給用戶。
?
??? (1) 詞法掃描。詞法掃描程序?qū)υ闯绦蜻M(jìn)行掃描,,從中收集到有意義的字符序列,,收集到記號(hào)中。
??? (2) 語法分析,。程序依據(jù)文法規(guī)則,,從掃描程序中獲取記號(hào)形式的源代碼,完成程序結(jié)構(gòu)的語法分析,,從而確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序,,并輸出語法樹。
??? (3) 語義分析,。審查源程序有無語義錯(cuò)誤,,并為代碼生成收集必要的信息。
??? (4) 代碼優(yōu)化程序,。對(duì)于語義分析形成的注釋樹進(jìn)行遍歷,,取得需要的數(shù)據(jù)。
??? (5) 代碼生成部分,。根據(jù)前面取得的信息將信息以符合C程序的形式組織起來形成C代碼,。
2 OIL代碼自動(dòng)生成系統(tǒng)中關(guān)鍵技術(shù)的研究
??? 本系統(tǒng)采用的是自上而下的LL(K)分析方法,所以本系統(tǒng)可以接受的文法必須是一個(gè)正確的,、上下文無關(guān)文法,,該文法不僅能夠正確完整地反映出OIL的語法,并且應(yīng)該符合自頂向下分析的要求,,這個(gè)就要求該系統(tǒng)能夠處理以下幾種情況:
??? (1) 如何處理出現(xiàn)二義性,;
??? (2) 克服左遞歸弊端;
??? (3) 如何確定LL(K)中K的值以保證正確識(shí)別文法和效率之間的統(tǒng)一,。
??? 文法的二義性是指對(duì)于同一句子有兩種不同的語法樹,,則稱該句子是二義性的,稱產(chǎn)生該句子的文法為二義性文法,。解決二義性的方法有兩種:一種是設(shè)置一種規(guī)則,,該規(guī)則指出在二義性的情況下哪種語法樹是正確的,例如在ELSE問題上面,,規(guī)定每個(gè)ELSE和最近的沒有分配的IF匹配,,這種方法的優(yōu)點(diǎn)是無需修改文法就可以克服文法的二義性,缺點(diǎn)是此時(shí)語言的語法結(jié)構(gòu)就不能由文法單獨(dú)決定了,;另外一種方法就是對(duì)存在二義性的文法進(jìn)行改寫,,如果一個(gè)二義產(chǎn)生式右部有非終結(jié)符出現(xiàn)一次以上,可以利用產(chǎn)生式引入消除,,如產(chǎn)生式A→a BβBγ,可以變換為A→a BβA′,A′→Bγ.如果多候選產(chǎn)生式的右部有一個(gè)是二義性的,,那么每個(gè)右部都要作為這個(gè)代換部分移除,例如A→aAβAγ|a1|a2|…|an,轉(zhuǎn)換為A→aA′βAγ| A′, A′→A′|a1|a2|…|an,消去其中的無用產(chǎn)生式后得到,,A→aA′βAγ| A′, A′→a1|a2|…|an。如果一個(gè)產(chǎn)生式有多個(gè)二義性產(chǎn)生式,,可以用上述方法重復(fù)變換,。
左遞歸是指當(dāng)一個(gè)上下文無關(guān)文法G=(VN ,VT , P, S),其中VN、VT,、P,、S分別表示非終結(jié)符集、終結(jié)符集,、產(chǎn)生式和開始字符,,當(dāng)文法如下:(1)A→Aa|β,其中A∈VN, a, b∈V*,,此時(shí)認(rèn)為這是直接左遞歸,,(2)A→Ba,B→Aβ|γ,,其中A∈VN , α, β, γ∈V*,,此時(shí)稱為間接左遞歸,當(dāng)出現(xiàn)左遞歸的時(shí)候,,由于本文采用的是LL(K)文法是采用從左到右的掃描方法,,當(dāng)掃描到(1)中的A或者(2)中的B時(shí),此時(shí)無法確定LL(K)掃描中的FIRST集,,會(huì)導(dǎo)致掃描失敗,。對(duì)于兩步以上的左遞歸(2)可以轉(zhuǎn)換為直接左遞歸形式A→Aβa |γa,然后利用下面的算法消除,。此算法可以消除所有無循環(huán)推導(dǎo)和空產(chǎn)生式的文法中的左遞歸:
(1) 以某種順序排列非終結(jié)符A1,A2,...AN,。
(2) For i = 1 to n do begin
????? For j = 1 to i-1 do begin
??????????????????? 用產(chǎn)生式Ai→δ1γ/δ2γ/…/δkγ代替每個(gè)形如Ai→Ajγ的產(chǎn)生式,其中Aj→δ1/δ2/…/δk是當(dāng)前Aj的所有產(chǎn)生式
????? End
??? 消除Aj產(chǎn)生式中的直接左遞歸
??? End
??? 在使用LL(K)算法的時(shí)候,,如何確定步長是一個(gè)很關(guān)鍵的問題,,如果步長過大,那么每次掃描的時(shí)候向前看的單詞數(shù)過多,,會(huì)引起編譯效率的下降,;如果步長過小,當(dāng)兩個(gè)非終結(jié)符具有相同的FIRST(K)值會(huì)導(dǎo)致識(shí)別的失敗,。一般來說,,選取K值為1的時(shí)候能滿足通常的識(shí)別要求,但是在某些特定的情況下可能導(dǎo)致識(shí)別失敗,,不能保證系統(tǒng)的健壯性,,例如在以下的情況下使用LL(1)就不能滿足要求:
??? (1) 當(dāng)出現(xiàn)A→αβ1|αβ2|…|αβn的時(shí)候,此時(shí)如果要對(duì)產(chǎn)生式進(jìn)行展開的話,采用LL(1)無法確定展開后應(yīng)該采用那個(gè)產(chǎn)生式,。
??? (2) 當(dāng)出現(xiàn)左遞歸的時(shí)候或者步長為K的時(shí)候才能區(qū)別的產(chǎn)生式,。
??? (3) 當(dāng)根據(jù)以下規(guī)則進(jìn)行詞法分析:
??? Float:(DIGIT)+’.’+(DIGIT)*+; 浮點(diǎn)型
??? ARRAY: (DIGIT)+’..’+(DIGIT)+;數(shù)組
??? 當(dāng)在這種情況下,,由于兩個(gè)產(chǎn)生式都無法確定前面的DIGIT的個(gè)數(shù),,只有當(dāng)掃描到“.”或者“..”的時(shí)候才能確定該使用哪個(gè)產(chǎn)生式,因此此時(shí)無法使用LL(1)進(jìn)行確定,。
??? 當(dāng)出現(xiàn)(1)的情況時(shí),,此時(shí)采取提取公因子的方式對(duì)產(chǎn)生式進(jìn)行改寫,例如(1)中的產(chǎn)生式可以改寫為如下格式A→αA',A'→β1|β2|…|βn的形式進(jìn)行轉(zhuǎn)化,,此時(shí)采用LL(1)可以成功進(jìn)行掃描,,如果公因子比較長的話可以采取上述辦法進(jìn)行多重轉(zhuǎn)化。
??? 對(duì)于左遞歸的情況上述已經(jīng)提到過解決方法了,,對(duì)于步長為K才能區(qū)別的情況下,,此時(shí)可以將步長調(diào)整到K進(jìn)行掃描,但是使用固定K值采用LL(K)的方法進(jìn)行掃描的時(shí)候,,會(huì)要求對(duì)終結(jié)符的FIRST集進(jìn)行計(jì)算,,這樣對(duì)許多無需使用LL(K)的情況造成了資源的浪費(fèi),使得掃描的效率降低,。
??? 當(dāng)出現(xiàn)情況(3)的時(shí)候無論將K值定為多長都有可能出現(xiàn)K值不夠大而形成掃描失敗的情況,,此時(shí)應(yīng)該采取步長不確定的方式來進(jìn)行掃描:當(dāng)剛剛開始掃描的時(shí)候確定K的初始值為1,當(dāng)掃描失敗的時(shí)候,,如果確定失敗的原因是由以上第三種情況導(dǎo)致的話,,此時(shí)對(duì)K的值加1進(jìn)行掃描,如果失敗再次加1直到掃描成功,。根據(jù)對(duì)OIL的語法進(jìn)行觀察,,當(dāng)K值定為3的時(shí)候就能解決99%以上的掃描失敗問題。對(duì)于少數(shù)為4的情況下可以采取提取公因子的情況進(jìn)行轉(zhuǎn)化,。
??? 采用遞歸下降分析程序掃描失敗后會(huì)返回失敗的節(jié)點(diǎn),,這種返回原節(jié)點(diǎn)的方式稱為回溯,在編譯過程中這樣的現(xiàn)象被認(rèn)為是一種極大降低效率的現(xiàn)象,,因此要盡力避免回溯的出現(xiàn),。為了避免回溯的出現(xiàn),在每次選擇產(chǎn)生式的時(shí)候采取預(yù)測分析的方法,,即禁止回溯,,當(dāng)需要確定使用產(chǎn)生式的時(shí)候采取預(yù)測的方法,使用預(yù)測的產(chǎn)生式,,如果失敗則報(bào)錯(cuò),,這樣就避免了回溯的出現(xiàn),。預(yù)測是使用預(yù)測函數(shù)來實(shí)現(xiàn)的,預(yù)測函數(shù)就是確定下一個(gè)待輸入的字符是否在當(dāng)前產(chǎn)生式A的預(yù)測函數(shù)中predict(A)中,,如果在的話,,就選擇產(chǎn)生式A,預(yù)測函數(shù)就是產(chǎn)生式A的向前看K個(gè)單詞,,下列產(chǎn)生式A→X1X2X3…XN,如果向前看的單詞K個(gè)數(shù)為1的話,則此產(chǎn)生式的預(yù)測函數(shù)的定義為如下:
???
??? 如果兩個(gè)右部產(chǎn)生式的預(yù)測函數(shù)有非空交集的時(shí)候,還需要往前看K個(gè)字符,,以上的方法一般表現(xiàn)為一個(gè)分析表,,表的行表示非終結(jié)符,表的列表示終結(jié)符,,表和列的交叉點(diǎn)就是當(dāng)非終結(jié)符遇到該終結(jié)符該使用哪個(gè)產(chǎn)生式去進(jìn)行擴(kuò)展,。
??? 本文探討了代碼自動(dòng)生成技術(shù)的一些步驟,并提供了OIL代碼自動(dòng)生成技術(shù)的系統(tǒng)模型,。文中提出了一些在OIL代碼自動(dòng)生成詞法分析和語法分析過程中遇到的實(shí)際問題加以討論并提出了實(shí)際的解決辦法,,為下一步語義注入提供了基礎(chǔ)。本系統(tǒng)的實(shí)際開發(fā)遵循了MVC開發(fā)方式,,保證了先進(jìn)性,,并且為代碼自動(dòng)生成技術(shù)提供了一些可以參考的思路。
參考文獻(xiàn)
[1]?LOUNDER K C. 編譯原理及實(shí)踐[M]. 馮博琴, 馮嵐,,譯. 北京:機(jī)械工業(yè)出版社, 2000.
[2]?陳火旺, 劉春林. 程序設(shè)計(jì)語言編譯原理(第3 版)[M]. 北京:國防工業(yè)出版社, 2001.
[3]?呂映芝, 張素琴. 編譯原理[M]. 北京:清華大學(xué)出版社, 1998.
[4]?APPEL A W, PALSBERG? J. Modern compiler implementation in java[M]. 高等教育出版社, 2003.
[5]?APPEL A W. 現(xiàn)代編譯原理C 語言描述[M] . 趙克佳, 黃春, 沈志宇,譯. 北京:人民郵電出版社出版,2006.