??? 摘 要：針對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)生成的過程，提出了一些具體的解決過程，消弱了對文法輸入的限制，提高了對文法的適應(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配置文件是對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所示。

?

??? (1) 詞法掃描。詞法掃描程序?qū)υ闯绦蜻M(jìn)行掃描，從中收集到有意義的字符序列，收集到記號(hào)中。
??? (2) 語法分析。程序依據(jù)文法規(guī)則，從掃描程序中獲取記號(hào)形式的源代碼，完成程序結(jié)構(gòu)的語法分析，從而確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序，并輸出語法樹。
??? (3) 語義分析。審查源程序有無語義錯(cuò)誤，并為代碼生成收集必要的信息。
??? (4) 代碼優(yōu)化程序。對于語義分析形成的注釋樹進(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)一。
??? 文法的二義性是指對于同一句子有兩種不同的語法樹，則稱該句子是二義性的，稱產(chǎn)生該句子的文法為二義性文法。解決二義性的方法有兩種：一種是設(shè)置一種規(guī)則，該規(guī)則指出在二義性的情況下哪種語法樹是正確的，例如在ELSE問題上面，規(guī)定每個(gè)ELSE和最近的沒有分配的IF匹配，這種方法的優(yōu)點(diǎn)是無需修改文法就可以克服文法的二義性，缺點(diǎn)是此時(shí)語言的語法結(jié)構(gòu)就不能由文法單獨(dú)決定了；另外一種方法就是對存在二義性的文法進(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γ|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。如果一個(gè)產(chǎn)生式有多個(gè)二義性產(chǎn)生式，可以用上述方法重復(fù)變換。
　　左遞歸是指當(dāng)一個(gè)上下文無關(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^*，此時(shí)認(rèn)為這是直接左遞歸，(2)A→Ba，B→Aβ|γ，其中A∈V_N , α, β, γ∈V^*，此時(shí)稱為間接左遞歸，當(dāng)出現(xiàn)左遞歸的時(shí)候，由于本文采用的是LL(K)文法是采用從左到右的掃描方法，當(dāng)掃描到(1)中的A或者(2)中的B時(shí)，此時(shí)無法確定LL(K)掃描中的FIRST集，會(huì)導(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γ代替每個(gè)形如A_i→A_jγ的產(chǎn)生式，其中A_j→δ₁/δ2/…/δ_k是當(dāng)前A_j的所有產(chǎn)生式
　????? 　　End
??? 消除A_j產(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→αβ₁|αβ₂|…|αβ_n的時(shí)候，此時(shí)如果要對產(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í)采取提取公因子的方式對產(chǎn)生式進(jìn)行改寫，例如(1)中的產(chǎn)生式可以改寫為如下格式A→αA',A'→β₁|β₂|…|β_n的形式進(jìn)行轉(zhuǎn)化，此時(shí)采用LL(1)可以成功進(jìn)行掃描，如果公因子比較長的話可以采取上述辦法進(jìn)行多重轉(zhuǎn)化。
??? 對于左遞歸的情況上述已經(jīng)提到過解決方法了，對于步長為K才能區(qū)別的情況下，此時(shí)可以將步長調(diào)整到K進(jìn)行掃描，但是使用固定K值采用LL(K)的方法進(jìn)行掃描的時(shí)候，會(huì)要求對終結(jié)符的FIRST集進(jìn)行計(jì)算，這樣對許多無需使用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í)對K的值加1進(jìn)行掃描，如果失敗再次加1直到掃描成功。根據(jù)對OIL的語法進(jìn)行觀察，當(dāng)K值定為3的時(shí)候就能解決99%以上的掃描失敗問題。對于少數(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→X₁X₂X₃…X_N,如果向前看的單詞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.