遞歸對自頂向下語法分析的影響

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

關鍵詞：編譯器 ；語法分析；遞歸；左遞歸；右遞歸

中圖分類號：TP314.51 文獻標識碼：A 文章編號：1009-3044（2018）04-0231-02

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

1 遞歸的定義

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

2 文法中的遞歸

若文法中存在一個（或多個）非終結符號，它可以推導出含有其自身的符號串，則稱該非終結符號是遞歸的。一個文法中如果含有遞歸的非終結符號，則此該文法稱為遞歸文法。

文法中遞歸的分類：

假設A是文法G的某個語法變量，如果存在推導AαAβ，則稱文法是遞歸的；

1） 當α=ε時，稱之為左遞歸；當β=ε時，稱之為右遞歸；

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

3） 如果文法G中存在形如A→αAβ的產生式，則稱文法G是直接遞歸；當α=ε時，稱之為直接左遞歸，當β=ε時，稱之為直接右遞歸。

3 遞歸對自頂向下語法分析的影響

3.1 消除左遞歸引起的無窮推導問題

使用自頂向下語法分析法進行語法分析時，假設文法中存在非終結符A，并且有AAa左遞歸，此文法是不能使用自頂向下的方法進行語法分析的。因為當試圖用A去匹配輸入串時，有可能使分析過程陷入無限循環，因為可能在沒有“匹配”任何輸入符號的情況下，又要求用下一層A去進行新的匹配，即使當某個非終結符用某個選擇匹配成功時，這種成功可能是暫時的，由于存在這種虛假現象，需要使用復雜的回溯技術，而試探與回溯效率低、代價高，只有理論意義，在實踐中價值不大。因此，要想使用自頂向下的語法分析，必須消除文法中的左遞歸。

1） 消除直接左遞歸

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

假定關于A的全部產生式為：

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|ε

此方法改寫后可刪除文法中直接左遞歸，但不能消除兩步或多步推導形成的間接左遞歸。

2） 消除文法中所有多重間接左遞歸的方法：

當文法中含有多重間接左遞歸時，需先將產生式非終結符進行置換，將間接左遞歸轉變為直接左遞歸，再按直接改寫法來消除直接左遞歸。

輸入：不含循環推導和A→ε產生式的文法G

輸出：與G等價的不含左遞歸的文法

步驟：1.將文法的非終結符按某一順序排序，例如：P1，P2，…，Pn

2. for i：=1 to n

3. { for j：=1 to i-1

4. { 若Pj的所有產生式為Pj→δ1|δ2|…|δk

5. 將其替換形如Pi→Pjr的產生式得到Pi→δ1r|δ2r|…|δkr；}

6. 消除Pi中的一切直接左遞歸

7. 化簡上述所得文法，去除無用產生式

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

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

采用遞歸下降分析法的文法中不能含有直接左遞歸的產生式，因為左遞歸會使遞歸下降語法分析器進入一個無限循環。

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

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

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

對于編譯程序而言，二義性文法是有害的。由于語法結構分析上的不確定性，必然會導致語義處理上的不確定性，最終生成的目標代碼具有不確定性。并且對于二義性文法來說，不存在一種確切的方法進行語法分析，此時可通過引入新的語法變量，來消除文法的二義性。

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

但在規定了優先順序和結合律后可將文法改寫為：

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

T → H| T*H

H →（E）| id

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

5 結束語

含有左遞歸文法或二義性文法將無法采用自頂向下的方法來進行語法分析，此時我們可以將含有左遞歸的文法轉換為改寫為一個等價的非直接左遞歸形式，將二義性文法通過規定優先順序和結合律將文法改寫為無二義性文法。如果改寫后的文法是滿足LL（1）文法，就可以采用確定的自頂向下分析法進行語法分析。

參考文獻：

[1] 朱朝霞，周云才. 二義性文法的語法分析方法探討[J] 長江大學學報，2008，5（6）.

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

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

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

[5] 陳火旺， 蔣偉進，等. 編譯原理[M] 長沙：中南大學出版社，2005.

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