??? 摘 要：針對OSEK標(biāo)準(zhǔn)的應(yīng)用設(shè)計了一個從OIL代碼到C代碼的自動生成系統(tǒng)，該系統(tǒng)允許用戶輸入OIL配置文件信息,，讀取用戶的輸入轉(zhuǎn)換為標(biāo)準(zhǔn)的C程序,，返回給用戶，在具體應(yīng)用的時候,，文法限制嚴(yán)格,。該系統(tǒng)結(jié)合代碼自動生成的過程，提出了一些具體的解決過程,，消弱了對文法輸入的限制,，提高了對文法的適應(yīng)能力。
??? 關(guān)鍵詞: 代碼自動生成,；OIL,；LL(K)

?

??? 代碼自動生成是當(dāng)今自動化程序設(shè)計的一個熱點，代碼自動生成技術(shù)就是幫助程序員完成系統(tǒng)底層的,、重復(fù)性代碼的自動生成,，減少軟件開發(fā)中枯燥且重復(fù)的編碼工作，使得程序員將更多的時間花在系統(tǒng)架構(gòu)研究,、軟件工程學(xué)習(xí)等方面,，從而提高軟件系統(tǒng)健壯性、可擴(kuò)展性以及可維護(hù)性和生產(chǎn)率,，縮短項目開發(fā)時間,，節(jié)約項目的開發(fā)成本，降低項目開發(fā)風(fēng)險，提高軟件公司的信譽度,，贏得市場主導(dǎo)地位,，使公司獲得最大回報率。OIL配置文件是對OSEK標(biāo)準(zhǔn)的描述文件,，OSEK/VDX是應(yīng)用在模塊和靜態(tài)實時操作系統(tǒng)上的標(biāo)準(zhǔn),，由主要的汽車制造商和供應(yīng)商、研究機構(gòu)以及軟件開發(fā)商發(fā)起,。在具體的開發(fā)過程中,，往往要根據(jù)OIL文件的描述來進(jìn)行具體的編碼，將代碼自動生成技術(shù)應(yīng)用于OIL文件上,，可以減少程序員的大量手工開發(fā),，節(jié)省了大量的人力物力，具有相當(dāng)廣泛的工業(yè)應(yīng)用前景,。本文設(shè)計的系統(tǒng)接受用戶輸入的OIL配置文件,，然后經(jīng)過系統(tǒng)的分析生成相應(yīng)的C代碼，實現(xiàn)了從配置文件到具體程序的自動化,，節(jié)省了大量的人力物力,，并且在嵌入式開發(fā)的時候可以繼承到嵌入式開發(fā)環(huán)境中，提供了很大的便捷性,。
1 OIL代碼自動生成系統(tǒng)的設(shè)計與實現(xiàn)
1.1 OIL代碼自動生成系統(tǒng)的功能描述
??? 本文中代碼自動生成系統(tǒng)的設(shè)計模塊如圖1所示,。

?

??? (1) 詞法掃描,。詞法掃描程序?qū)υ闯绦蜻M(jìn)行掃描，從中收集到有意義的字符序列,，收集到記號中,。
??? (2) 語法分析。程序依據(jù)文法規(guī)則,，從掃描程序中獲取記號形式的源代碼,，完成程序結(jié)構(gòu)的語法分析，從而確定整個輸入串是否構(gòu)成一個語法上正確的程序,，并輸出語法樹,。
??? (3) 語義分析。審查源程序有無語義錯誤,，并為代碼生成收集必要的信息,。
??? (4) 代碼優(yōu)化程序。對于語義分析形成的注釋樹進(jìn)行遍歷,，取得需要的數(shù)據(jù),。
??? (5) 代碼生成部分。根據(jù)前面取得的信息將信息以符合C程序的形式組織起來形成C代碼,。
2 OIL代碼自動生成系統(tǒng)中關(guān)鍵技術(shù)的研究
??? 本系統(tǒng)采用的是自上而下的LL(K)分析方法,，所以本系統(tǒng)可以接受的文法必須是一個正確的、上下文無關(guān)文法,，該文法不僅能夠正確完整地反映出OIL的語法,，并且應(yīng)該符合自頂向下分析的要求，這個就要求該系統(tǒng)能夠處理以下幾種情況：
??? (1) 如何處理出現(xiàn)二義性；
??? (2) 克服左遞歸弊端,；
??? (3) 如何確定LL(K)中K的值以保證正確識別文法和效率之間的統(tǒng)一,。
??? 文法的二義性是指對于同一句子有兩種不同的語法樹，則稱該句子是二義性的,，稱產(chǎn)生該句子的文法為二義性文法,。解決二義性的方法有兩種：一種是設(shè)置一種規(guī)則，該規(guī)則指出在二義性的情況下哪種語法樹是正確的,，例如在ELSE問題上面,，規(guī)定每個ELSE和最近的沒有分配的IF匹配，這種方法的優(yōu)點是無需修改文法就可以克服文法的二義性,，缺點是此時語言的語法結(jié)構(gòu)就不能由文法單獨決定了,；另外一種方法就是對存在二義性的文法進(jìn)行改寫，如果一個二義產(chǎn)生式右部有非終結(jié)符出現(xiàn)一次以上,，可以利用產(chǎn)生式引入消除,，如產(chǎn)生式A→a BβBγ，可以變換為A→a BβA′,，A′→Bγ.如果多候選產(chǎn)生式的右部有一個是二義性的,，那么每個右部都要作為這個代換部分移除,例如A→aAβAγ|a₁|a₂|…|a_n,轉(zhuǎn)換為A→aA′βAγ| A′, A′→A′|a₁|a₂|…|a_n,消去其中的無用產(chǎn)生式后得到，A→aA′βAγ| A′, A′→a₁|a₂|…|a_n,。如果一個產(chǎn)生式有多個二義性產(chǎn)生式,，可以用上述方法重復(fù)變換。
　　左遞歸是指當(dāng)一個上下文無關(guān)文法G=(V_N ,V_T , P, S),其中V_N,、V_T,、P、S分別表示非終結(jié)符集,、終結(jié)符集,、產(chǎn)生式和開始字符，當(dāng)文法如下：(1)A→Aa|β,，其中A∈V_N, a, b∈V^*,，此時認(rèn)為這是直接左遞歸，(2)A→Ba,，B→Aβ|γ,，其中A∈V_N , α, β, γ∈V^*，此時稱為間接左遞歸,，當(dāng)出現(xiàn)左遞歸的時候,，由于本文采用的是LL(K)文法是采用從左到右的掃描方法，當(dāng)掃描到(1)中的A或者(2)中的B時,，此時無法確定LL(K)掃描中的FIRST集,，會導(dǎo)致掃描失敗,。對于兩步以上的左遞歸(2)可以轉(zhuǎn)換為直接左遞歸形式A→Aβa |γa，然后利用下面的算法消除,。此算法可以消除所有無循環(huán)推導(dǎo)和空產(chǎn)生式的文法中的左遞歸：
　　(1) 以某種順序排列非終結(jié)符A₁,A₂,...A_N,。
　　(2) For i = 1 to n do begin
????? 　　　For j = 1 to i-1 do begin
??????????????????? 用產(chǎn)生式A_i→δ₁γ/δ₂γ/…/δ_kγ代替每個形如A_i→A_jγ的產(chǎn)生式，其中A_j→δ₁/δ2/…/δ_k是當(dāng)前A_j的所有產(chǎn)生式
　????? 　　End
??? 消除A_j產(chǎn)生式中的直接左遞歸
??? End
??? 在使用LL(K)算法的時候,，如何確定步長是一個很關(guān)鍵的問題，如果步長過大,，那么每次掃描的時候向前看的單詞數(shù)過多,，會引起編譯效率的下降；如果步長過小,，當(dāng)兩個非終結(jié)符具有相同的FIRST(K)值會導(dǎo)致識別的失敗,。一般來說，選取K值為1的時候能滿足通常的識別要求,，但是在某些特定的情況下可能導(dǎo)致識別失敗,，不能保證系統(tǒng)的健壯性，例如在以下的情況下使用LL(1)就不能滿足要求:
??? (1) 當(dāng)出現(xiàn)A→αβ₁|αβ₂|…|αβ_n的時候,，此時如果要對產(chǎn)生式進(jìn)行展開的話,，采用LL(1)無法確定展開后應(yīng)該采用那個產(chǎn)生式。
??? (2) 當(dāng)出現(xiàn)左遞歸的時候或者步長為K的時候才能區(qū)別的產(chǎn)生式,。
??? (3) 當(dāng)根據(jù)以下規(guī)則進(jìn)行詞法分析：
??? Float：（DIGIT）+’.’+(DIGIT)*+,； 浮點型
??? ARRAY: （DIGIT）+’..’+(DIGIT)+;數(shù)組
??? 當(dāng)在這種情況下，由于兩個產(chǎn)生式都無法確定前面的DIGIT的個數(shù),，只有當(dāng)掃描到“.”或者“..”的時候才能確定該使用哪個產(chǎn)生式,，因此此時無法使用LL(1)進(jìn)行確定。
??? 當(dāng)出現(xiàn)(1)的情況時,，此時采取提取公因子的方式對產(chǎn)生式進(jìn)行改寫,，例如(1)中的產(chǎn)生式可以改寫為如下格式A→αA',A'→β₁|β₂|…|β_n的形式進(jìn)行轉(zhuǎn)化，此時采用LL(1)可以成功進(jìn)行掃描,，如果公因子比較長的話可以采取上述辦法進(jìn)行多重轉(zhuǎn)化,。
??? 對于左遞歸的情況上述已經(jīng)提到過解決方法了，對于步長為K才能區(qū)別的情況下,，此時可以將步長調(diào)整到K進(jìn)行掃描,，但是使用固定K值采用LL(K)的方法進(jìn)行掃描的時候，會要求對終結(jié)符的FIRST集進(jìn)行計算,，這樣對許多無需使用LL(K)的情況造成了資源的浪費,，使得掃描的效率降低。
??? 當(dāng)出現(xiàn)情況(3)的時候無論將K值定為多長都有可能出現(xiàn)K值不夠大而形成掃描失敗的情況,，此時應(yīng)該采取步長不確定的方式來進(jìn)行掃描：當(dāng)剛剛開始掃描的時候確定K的初始值為1,，當(dāng)掃描失敗的時候,，如果確定失敗的原因是由以上第三種情況導(dǎo)致的話，此時對K的值加1進(jìn)行掃描,，如果失敗再次加1直到掃描成功,。根據(jù)對OIL的語法進(jìn)行觀察，當(dāng)K值定為3的時候就能解決99%以上的掃描失敗問題,。對于少數(shù)為4的情況下可以采取提取公因子的情況進(jìn)行轉(zhuǎn)化,。
??? 采用遞歸下降分析程序掃描失敗后會返回失敗的節(jié)點，這種返回原節(jié)點的方式稱為回溯,，在編譯過程中這樣的現(xiàn)象被認(rèn)為是一種極大降低效率的現(xiàn)象,，因此要盡力避免回溯的出現(xiàn)。為了避免回溯的出現(xiàn),，在每次選擇產(chǎn)生式的時候采取預(yù)測分析的方法,，即禁止回溯，當(dāng)需要確定使用產(chǎn)生式的時候采取預(yù)測的方法,，使用預(yù)測的產(chǎn)生式,，如果失敗則報錯，這樣就避免了回溯的出現(xiàn),。預(yù)測是使用預(yù)測函數(shù)來實現(xiàn)的,，預(yù)測函數(shù)就是確定下一個待輸入的字符是否在當(dāng)前產(chǎn)生式A的預(yù)測函數(shù)中predict(A)中，如果在的話,，就選擇產(chǎn)生式A,，預(yù)測函數(shù)就是產(chǎn)生式A的向前看K個單詞，下列產(chǎn)生式A→X₁X₂X₃…X_N,如果向前看的單詞K個數(shù)為1的話,則此產(chǎn)生式的預(yù)測函數(shù)的定義為如下：

???
??? 如果兩個右部產(chǎn)生式的預(yù)測函數(shù)有非空交集的時候,，還需要往前看K個字符,，以上的方法一般表現(xiàn)為一個分析表，表的行表示非終結(jié)符,，表的列表示終結(jié)符,，表和列的交叉點就是當(dāng)非終結(jié)符遇到該終結(jié)符該使用哪個產(chǎn)生式去進(jìn)行擴(kuò)展。
??? 本文探討了代碼自動生成技術(shù)的一些步驟,，并提供了OIL代碼自動生成技術(shù)的系統(tǒng)模型,。文中提出了一些在OIL代碼自動生成詞法分析和語法分析過程中遇到的實際問題加以討論并提出了實際的解決辦法，為下一步語義注入提供了基礎(chǔ),。本系統(tǒng)的實際開發(fā)遵循了MVC開發(fā)方式,，保證了先進(jìn)性，并且為代碼自動生成技術(shù)提供了一些可以參考的思路,。
參考文獻(xiàn)
[1]?LOUNDER K C. 編譯原理及實踐[M]. 馮博琴, 馮嵐,，譯. 北京：機械工業(yè)出版社, 2000.
[2]?陳火旺, 劉春林. 程序設(shè)計語言編譯原理(第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.