遞歸對(duì)自頂向下語法分析的影響

摘要：在編譯程序的語法分析中，含有左遞歸的文法，無法采用自頂向下的方法來進(jìn)行語法分析，該文從遞歸的角度出發(fā)，討論遞歸對(duì)自頂向下語法分析的影響。

關(guān)鍵詞：編譯器 ；語法分析；遞歸；左遞歸；右遞歸

中圖分類號(hào)：TP314.51 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）04-0231-02

語法分析是編譯程序的核心部分，語法分析方法有多種，每一種語法分析方法只能處理某一種形式的文法，為了適應(yīng)所選擇的語法分析方法，常常需要對(duì)原始文法進(jìn)行改造。比如含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析，本文從遞歸的角度出發(fā)，討論遞歸對(duì)自頂向下語法分析的影響。

1 遞歸的定義

遞歸作為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用，程序調(diào)用自身的編程技巧稱為遞歸，遞歸可把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原始問題相似的規(guī)模較小的問題來求解，只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的主要優(yōu)勢(shì)在于用有限的語句來定義對(duì)象的無限集合。其缺點(diǎn)是遞歸算法相對(duì)于非遞歸算法效率低，在遞歸調(diào)用的過程中系統(tǒng)需要為每一層的返回點(diǎn)、局部變量等開辟棧來存儲(chǔ)，如果遞歸次數(shù)過多容易造成棧溢出。

2 文法中的遞歸

若文法中存在一個(gè)（或多個(gè)）非終結(jié)符號(hào)，它可以推導(dǎo)出含有其自身的符號(hào)串，則稱該非終結(jié)符號(hào)是遞歸的。一個(gè)文法中如果含有遞歸的非終結(jié)符號(hào)，則此該文法稱為遞歸文法。

文法中遞歸的分類：

假設(shè)A是文法G的某個(gè)語法變量，如果存在推導(dǎo)AαAβ，則稱文法是遞歸的；

1） 當(dāng)α=ε時(shí)，稱之為左遞歸；當(dāng)β=ε時(shí)，稱之為右遞歸；

2） 如果AαAβ需要兩步以上推導(dǎo)，則稱文法G是間接遞歸；并且當(dāng)α=ε時(shí)，稱之為間接左遞歸；當(dāng)β=ε時(shí)，稱之為間接右遞歸；

3） 如果文法G中存在形如A→αAβ的產(chǎn)生式，則稱文法G是直接遞歸；當(dāng)α=ε時(shí)，稱之為直接左遞歸，當(dāng)β=ε時(shí)，稱之為直接右遞歸。

3 遞歸對(duì)自頂向下語法分析的影響

3.1 消除左遞歸引起的無窮推導(dǎo)問題

使用自頂向下語法分析法進(jìn)行語法分析時(shí)，假設(shè)文法中存在非終結(jié)符A，并且有AAa左遞歸，此文法是不能使用自頂向下的方法進(jìn)行語法分析的。因?yàn)楫?dāng)試圖用A去匹配輸入串時(shí)，有可能使分析過程陷入無限循環(huán)，因?yàn)榭赡茉跊]有“匹配”任何輸入符號(hào)的情況下，又要求用下一層A去進(jìn)行新的匹配，即使當(dāng)某個(gè)非終結(jié)符用某個(gè)選擇匹配成功時(shí)，這種成功可能是暫時(shí)的，由于存在這種虛假現(xiàn)象，需要使用復(fù)雜的回溯技術(shù)，而試探與回溯效率低、代價(jià)高，只有理論意義，在實(shí)踐中價(jià)值不大。因此，要想使用自頂向下的語法分析，必須消除文法中的左遞歸。

1） 消除直接左遞歸

采用直接改寫法：即把文法中直接左遞歸改寫為一個(gè)等價(jià)的非直接左遞歸形式。

假定關(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)文法中含有多重間接左遞歸時(shí)，需先將產(chǎn)生式非終結(jié)符進(jìn)行置換，將間接左遞歸轉(zhuǎn)變?yōu)橹苯幼筮f歸，再按直接改寫法來消除直接左遞歸。

輸入：不含循環(huán)推導(dǎo)和A→ε產(chǎn)生式的文法G

輸出：與G等價(jià)的不含左遞歸的文法

步驟：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. 化簡(jiǎn)上述所得文法，去除無用產(chǎn)生式

3.2 遞歸下降語法分析法中的遞歸

遞歸下降分析法，是一種確定的自頂向下語法分析方法，它根據(jù)各個(gè)產(chǎn)生式的結(jié)構(gòu)，為文法的每個(gè)語法變量編寫一個(gè)處理子程序，用來識(shí)別該語法變量所代表的語法成分。由于產(chǎn)生式中的語法變量可能是遞歸調(diào)用的，所以這種實(shí)現(xiàn)方法要求子程序可以遞歸調(diào)用，另外，這種分析方法也是尋求輸入串的一個(gè)最左推導(dǎo)過程，所以稱為遞歸下降分析法。它要求文法必須滿足LL（1）文法。

采用遞歸下降分析法的文法中不能含有直接左遞歸的產(chǎn)生式，因?yàn)樽筮f歸會(huì)使遞歸下降語法分析器進(jìn)入一個(gè)無限循環(huán)。

遞歸下降分析法遞歸調(diào)用多，所以速度慢，占用空間較多。

4 文法中同時(shí)含有左遞歸和右遞歸的危害

如果一文法中既含有左遞歸又含有右遞歸，即有AAvA或AA 或 A Aα及A βA （v∈V*）三者之一情況，則稱此文法是二義性的。

對(duì)于編譯程序而言，二義性文法是有害的。由于語法結(jié)構(gòu)分析上的不確定性，必然會(huì)導(dǎo)致語義處理上的不確定性，最終生成的目標(biāo)代碼具有不確定性。并且對(duì)于二義性文法來說，不存在一種確切的方法進(jìn)行語法分析，此時(shí)可通過引入新的語法變量，來消除文法的二義性。

例：文法G[E]： E→id E→E+E E→E*E E→（E） 同時(shí)含有左遞歸和右遞歸，是二義性文法。

但在規(guī)定了優(yōu)先順序和結(jié)合律后可將文法改寫為：

G[E]：E → T| E+T

T → H| T*H

H →（E）| id

此時(shí)文法中只含有左遞歸而無右遞歸，改寫后的文法是個(gè)無二義性文法。

5 結(jié)束語

含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進(jìn)行語法分析，此時(shí)我們可以將含有左遞歸的文法轉(zhuǎn)換為改寫為一個(gè)等價(jià)的非直接左遞歸形式，將二義性文法通過規(guī)定優(yōu)先順序和結(jié)合律將文法改寫為無二義性文法。如果改寫后的文法是滿足LL（1）文法，就可以采用確定的自頂向下分析法進(jìn)行語法分析。

參考文獻(xiàn)：

[1] 朱朝霞，周云才. 二義性文法的語法分析方法探討[J] 長(zhǎng)江大學(xué)學(xué)報(bào)，2008，5（6）.

[2] 蔣宗禮，姜守旭. 編譯原理[M]. 北京：高等教育出版社，2010.

[3] 張素琴， 呂映芝，等. 編譯原理[M].北京：清華大學(xué)出版社，2005.

[4] 張昱，陳意云. 編譯原理與技術(shù)[M] 北京：高等教育出版社 2010.

[5] 陳火旺， 蔣偉進(jìn)，等. 編譯原理[M] 長(zhǎng)沙：中南大學(xué)出版社，2005.

[6] 黃賢英，王柯柯. 編譯原理及實(shí)踐教程[M]. 北京：清華大學(xué)出版社，2008.