左遞歸

在電腦科學裡面，**左遞歸**是一種遞歸的特殊狀況。

在上下文無關文法內裡的說法，若一個非終結符號（non-terminal）`r` 有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現 `r`，則我們說這個非終結符號 `r` 是左遞歸的。

使用類似的方式我們可以定義出某文法本身是左遞歸的。

## 定義

"一個文法是左遞歸的，若我們可以找出其中存在某非終結符號 A，最終會推導出來的句型 (sentential form) 裡面包含以自己為最左符號 (left-symbol) 的句型"

### 直接左遞歸

直接左遞歸（Immediate left recursion）以下面的句型規則出現：

　
: $A\to A\alpha \mid \beta $

這裡 $\alpha $ 跟 $\beta $ 代表不同的非終結符號跟終結符號組成的序列，並且 $\beta $ 不一定要包含 $A$ 。舉例來說，以下規則

　
: ${\mathit {Expr}}\to {\mathit {Expr}}+{\mathit {Term}}$

就是一個直接左遞歸的例子。 這規則的_遞歸下降分析器_(recursive descent parser) 可能會像這樣：

然後這個遞歸下降分析器在嘗試去解析包含此規則的文法時，會陷入一個無窮的遞歸。

### 間接左遞歸

間接左遞歸 (indirect left recursion) 最簡單的形式如下：

　
: $A\to B\alpha \mid C$

　
: $B\to A\beta \mid D,$

這規則可能產生 $A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow \ldots $ 這種生成。

簡單的說，間接左遞歸就是，並非在一條規則內完成左遞歸，而是在許多條規則之後，於產生的句子最左邊出現了一開始的非終結符號。

更一般化的說法，對非終結符號 $A_{0},A_{1},\ldots ,A_{n}$ ，間接左遞歸被定義為以下的型態：

　
: $A_{0}\to A_{1}\alpha _{1}\mid \ldots $

　
: $A_{1}\to A_{2}\alpha _{2}\mid \ldots $

　
: $\cdots $

　
: $A_{n}\to A_{0}\alpha _{n+1}\mid \ldots $

這裡的 $\alpha _{1},\alpha _{2},\ldots ,\alpha _{n}$ 都是一堆終端與非終結符號的序列。

## 在由上而下語法分析 (top-down parsing) 裡容納左遞歸

一個包含左遞歸的形式文法不能以簡易的 遞歸下降分析器進行語法分析，除非將文法轉變為 weakly equivalent 的右遞歸形式 (相對的，在 LALR 分析器裡面則比較偏好左遞歸，因為比起右遞歸來說會使用比較少的堆疊)；然而，比較複雜的由上而下 (top-down) 語法分析器裡面可以藉由使用縮減 (by use of curtailment) 來實做一般的上下文無關文法。 在 2006 年，Frost 和 Hafiz 提出一個演算法，可以容納包含直接左遞歸生成規則的 模糊文法 (ambiguous grammers)。 在 2007 年，Frost，Hafiz 和 Callaghan 將此演算法延伸為一個完整的，可以適用並在多項式時間內處理直接或間接左遞歸，而且可以為高度模糊文法接近指數數目的分析樹，產生小一些多項式空間的表示法。這些人後來在 Haskell 程式語言裡面以這個演算法實做了一個的分析器組合 (parser combinator) 的集合。

## 移除左遞歸

### 移除直接左遞歸

一個一般化後移除直接左遞歸的演算法如下所述。 這個方法已經有過許多的改進，包括 Robert C. Moore 所撰寫，名為 "Removing Left Recursion from Context-Free Grammars" 的改進。

對於每個規則如下

　
: $A\rightarrow A\alpha _{1}\,|\,\ldots \,|\,A\alpha _{n}\,|\,\beta _{1}\,|\,\ldots \,|\,\beta _{m}$

(注意這裡：

* A 是一個有左遞歸的非終端符號
* $\alpha $ 是一個終端與非終端符號的序列，而且不為空字串 ( $\alpha \neq \epsilon $ )
* $\beta $ 是一個不以 A 開頭的，以終端與非終端符號組成的序列)

將 A 的規則改成以下規則：

　
: $A\rightarrow \beta _{1}A^{\prime }\,|\,\ldots \,|\,\beta _{m}A^{\prime }$

然後對新創造出來非終端符號的規則

　
: $A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,\ldots \,|\,\alpha _{n}A^{\prime }$

這個新創造出來的符號常被稱為 "尾巴"(tail)，或者 "rest"(剩餘)

舉例，考慮以下規則

　
: $Expr\rightarrow Expr\,+\,Expr\,|\,Int\,|\,String$

我們可以改寫為

　
: $Expr\rightarrow Int\,ExprRest\,|\,String\,ExprRest$

　
: $ExprRest\rightarrow \epsilon \,|\,+\,Expr\,ExprRest$

然後最後一個規則可以縮短改寫為

　
: $ExprRest\rightarrow \epsilon \,|\,+\,Expr$

來避免掉左遞歸的出現

### 移除間接左遞歸

如果文法內不存在 $\epsilon $ (代表空字串) 的生成 (不存在 $A\rightarrow \ldots |\epsilon |\ldots $ 這樣的規則)，而且不是循環 (cyclic) 的文法 (對所有非終端符號 A，不存在像是 $A\Rightarrow \ldots \Rightarrow A$ 這種形式的規則)，以下這個一般化的演算法可以用來去除文法的間接左遞歸：

將所有非終端符號以某個固定的順序 $A_{1},\ldots A_{n}$ 排列

　
: 從 i = 1 到 n {

　
: 從 j = 1 到 i – 1 {

　
: * 設 $A_{j}$ 的生成規則為

　
: $A_{j}\rightarrow \delta _{1}|\ldots |\delta _{k}$

* 將所有規則 $A_{i}\rightarrow A_{j}\gamma $ 換成

　
: $A_{i}\rightarrow \delta _{1}\gamma |\ldots |\delta _{k}\gamma $

* 移除 $A_{i}$ 規則中的直接左遞歸

　
: }

　
: }

## 陷阱

上面的轉換使用右遞歸的文法來避免掉左遞歸的出現；但是這樣會改變規則的結合律。左遞歸會創造出向左的結合律；但是右遞歸則會創造出向右的結合律。

範例 :

一開始我們拿到以下文法：

　
: $Expr\rightarrow Expr\,+\,Term\,|\,Term$

　
: $Term\rightarrow Term\,*\,Factor\,|\,Factor$

　
: $Factor\rightarrow (Expr)\,|\,Int$

在我們使用上面的轉換方式來移除掉左遞歸之後，我們取得了以下文法：

　
: $Expr\rightarrow Term\ Expr'$

　
: $Expr'\rightarrow {}+Term\ Expr'\,|\,\epsilon $

　
: $Term\rightarrow Factor\ Term'$

　
: $Term'\rightarrow {}*Factor\ Term'\,|\,\epsilon $

　
: $Factor\rightarrow (Expr)\,|\,Int$

我們將字串 'a + a + a' 用一個 LALR 分析器 (這種分析器可以處理左遞歸的文法) 使用原先的文法來分析，會得到下面的分析樹 (parse tree)：

```
                            Expr
                         /   |   \
                       Expr   +   Term
                     /  |  \        \
                   Expr  + Term      Factor
                    |      |       |
                   Term    Factor    Int
                    |      |
                  Factor    Int
                    |
                   Int  
```

整個分析樹是往左邊長，代表在這裡的規則，'+' 這個符號是左結合 (left associative) 的，或者說這規則代表 (a + a) + a。

但是我們改變了文法之後，那這個分析樹會變成：

```
                            Expr ---
                           /        \
                         Term      Expr' --
                          |       /  |     \ 
                        Factor   +  Term   Expr' ------
                          |          |      |  \       \
                         Int       Factor   +  Term   Expr'
                                     |           |      |
                                    Int        Factor   $\epsilon $
                                                 |
                                                Int
```

我們可以看出這棵樹現在是往右邊成長，意思上代表了 a + (a + a)。我們將 '+' 的結合律改變了，變成是右結合的規則。 在處理加法的文法時這不是甚麼問題，但是如果我們現在處理的是減法，這就會變成是很嚴重的問題。

問題的關鍵在於有很多常用的算術規則要求左結合的規則。我們有幾種解決辦法： (a) 將規則重新改為左遞歸，(b) 使用更多的非終端符號來改寫規則，以強迫文法合乎正確的結合 (c) 如果使用 YACC 或者 Bison，他們有所謂_算符宣告_(operator declarations)， % left, % right and % nonassoc，這一些算符可以告訴語法分析器產生程式 (parser generator) 應該遵從哪一種結合。

## 相關條目

* 尾部遞歸

## 參考資料

## 外部連結

* CMU lecture on left-recursion （頁面存檔備份，存於網際網路檔案館）
* Practical Considerations for LALR (1) Grammars （頁面存檔備份，存於網際網路檔案館）
* X-SAIGA （頁面存檔備份，存於網際網路檔案館） - eXecutable SpecificAtIons of GrAmmars