摘要:在編譯程序的語法分析中,含有左遞歸的文法,無法采用自頂向下的方法來進(jìn)行語法分析,該文從遞歸的角度出發(fā),討論遞歸對自頂向下語法分析的影響。
關(guān)鍵詞:編譯器 ;語法分析;遞歸;左遞歸;右遞歸
中圖分類號:TP314.51 文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2018)04-0231-02
語法分析是編譯程序的核心部分,語法分析方法有多種,每一種語法分析方法只能處理某一種形式的文法,為了適應(yīng)所選擇的語法分析方法,常常需要對原始文法進(jìn)行改造。比如含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析,本文從遞歸的角度出發(fā),討論遞歸對自頂向下語法分析的影響。
1 遞歸的定義
遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用,程序調(diào)用自身的編程技巧稱為遞歸,遞歸可把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原始問題相似的規(guī)模較小的問題來求解,只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算,大大地減少了程序的代碼量。遞歸的主要優(yōu)勢在于用有限的語句來定義對象的無限集合。其缺點(diǎn)是遞歸算法相對于非遞歸算法效率低,在遞歸調(diào)用的過程中系統(tǒng)需要為每一層的返回點(diǎn)、局部變量等開辟棧來存儲,如果遞歸次數(shù)過多容易造成棧溢出。
2 文法中的遞歸
若文法中存在一個(或多個)非終結(jié)符號,它可以推導(dǎo)出含有其自身的符號串,則稱該非終結(jié)符號是遞歸的。一個文法中如果含有遞歸的非終結(jié)符號,則此該文法稱為遞歸文法。
文法中遞歸的分類:
假設(shè)A是文法G的某個語法變量,如果存在推導(dǎo)AαAβ,則稱文法是遞歸的;
1) 當(dāng)α=ε時,稱之為左遞歸;當(dāng)β=ε時,稱之為右遞歸;
2) 如果AαAβ需要兩步以上推導(dǎo),則稱文法G是間接遞歸;并且當(dāng)α=ε時,稱之為間接左遞歸;當(dāng)β=ε時,稱之為間接右遞歸;
3) 如果文法G中存在形如A→αAβ的產(chǎn)生式,則稱文法G是直接遞歸;當(dāng)α=ε時,稱之為直接左遞歸,當(dāng)β=ε時,稱之為直接右遞歸。
3 遞歸對自頂向下語法分析的影響
3.1 消除左遞歸引起的無窮推導(dǎo)問題
使用自頂向下語法分析法進(jìn)行語法分析時,假設(shè)文法中存在非終結(jié)符A,并且有AAa左遞歸,此文法是不能使用自頂向下的方法進(jìn)行語法分析的。因為當(dāng)試圖用A去匹配輸入串時,有可能使分析過程陷入無限循環(huán),因為可能在沒有“匹配”任何輸入符號的情況下,又要求用下一層A去進(jìn)行新的匹配,即使當(dāng)某個非終結(jié)符用某個選擇匹配成功時,這種成功可能是暫時的,由于存在這種虛假現(xiàn)象,需要使用復(fù)雜的回溯技術(shù),而試探與回溯效率低、代價高,只有理論意義,在實踐中價值不大。因此,要想使用自頂向下的語法分析,必須消除文法中的左遞歸。
1) 消除直接左遞歸
采用直接改寫法:即把文法中直接左遞歸改寫為一個等價的非直接左遞歸形式。
假定關(guān)于A的全部產(chǎn)生式為:
A→Aα1|Aα2|…|Aαm|β1|β2|…|βn (αi非空,βj不以A開頭,1≤i≤m,1≤j≤n)
消除直接左遞歸后改寫為:
A→β1A | β2A| …|βnA
A→α1A|ɑ2A|…|ɑmA|ε
此方法改寫后可刪除文法中直接左遞歸,但不能消除兩步或多步推導(dǎo)形成的間接左遞歸。
2) 消除文法中所有多重間接左遞歸的方法:
當(dāng)文法中含有多重間接左遞歸時,需先將產(chǎn)生式非終結(jié)符進(jìn)行置換,將間接左遞歸轉(zhuǎn)變?yōu)橹苯幼筮f歸,再按直接改寫法來消除直接左遞歸。
輸入:不含循環(huán)推導(dǎo)和A→ε產(chǎn)生式的文法G
輸出:與G等價的不含左遞歸的文法
步驟:1.將文法的非終結(jié)符按某一順序排序,例如:P1,P2,…,Pn
2. for i:=1 to n
3. { for j:=1 to i-1
4. { 若Pj的所有產(chǎn)生式為Pj→δ1|δ2|…|δk
5. 將其替換形如Pi→Pjr的產(chǎn)生式得到Pi→δ1r|δ2r|…|δkr;}
6. 消除Pi中的一切直接左遞歸
7. 化簡上述所得文法,去除無用產(chǎn)生式
3.2 遞歸下降語法分析法中的遞歸
遞歸下降分析法,是一種確定的自頂向下語法分析方法,它根據(jù)各個產(chǎn)生式的結(jié)構(gòu),為文法的每個語法變量編寫一個處理子程序,用來識別該語法變量所代表的語法成分。由于產(chǎn)生式中的語法變量可能是遞歸調(diào)用的,所以這種實現(xiàn)方法要求子程序可以遞歸調(diào)用,另外,這種分析方法也是尋求輸入串的一個最左推導(dǎo)過程,所以稱為遞歸下降分析法。它要求文法必須滿足LL(1)文法。
采用遞歸下降分析法的文法中不能含有直接左遞歸的產(chǎn)生式,因為左遞歸會使遞歸下降語法分析器進(jìn)入一個無限循環(huán)。
遞歸下降分析法遞歸調(diào)用多,所以速度慢,占用空間較多。
4 文法中同時含有左遞歸和右遞歸的危害
如果一文法中既含有左遞歸又含有右遞歸,即有AAvA或AA 或 A Aα及A βA (v∈V*)三者之一情況,則稱此文法是二義性的。
對于編譯程序而言,二義性文法是有害的。由于語法結(jié)構(gòu)分析上的不確定性,必然會導(dǎo)致語義處理上的不確定性,最終生成的目標(biāo)代碼具有不確定性。并且對于二義性文法來說,不存在一種確切的方法進(jìn)行語法分析,此時可通過引入新的語法變量,來消除文法的二義性。
例:文法G[E]: E→id E→E+E E→E*E E→(E) 同時含有左遞歸和右遞歸,是二義性文法。
但在規(guī)定了優(yōu)先順序和結(jié)合律后可將文法改寫為:
G[E]:E → T| E+T
T → H| T*H
H →(E)| id
此時文法中只含有左遞歸而無右遞歸,改寫后的文法是個無二義性文法。
5 結(jié)束語
含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析,此時我們可以將含有左遞歸的文法轉(zhuǎn)換為改寫為一個等價的非直接左遞歸形式,將二義性文法通過規(guī)定優(yōu)先順序和結(jié)合律將文法改寫為無二義性文法。如果改寫后的文法是滿足LL(1)文法,就可以采用確定的自頂向下分析法進(jìn)行語法分析。
參考文獻(xiàn):
[1] 朱朝霞,周云才. 二義性文法的語法分析方法探討[J] 長江大學(xué)學(xué)報,2008,5(6).
[2] 蔣宗禮,姜守旭. 編譯原理[M]. 北京:高等教育出版社,2010.
[3] 張素琴, 呂映芝,等. 編譯原理[M].北京:清華大學(xué)出版社,2005.
[4] 張昱,陳意云. 編譯原理與技術(shù)[M] 北京:高等教育出版社 2010.
[5] 陳火旺, 蔣偉進(jìn),等. 編譯原理[M] 長沙:中南大學(xué)出版社,2005.
[6] 黃賢英,王柯柯. 編譯原理及實踐教程[M]. 北京:清華大學(xué)出版社,2008.