查看“︁左遞歸”︁的源代码

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

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

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

== 定義 ==
"一個文法是左遞歸的，若我們可以找出其中存在某非终结符號A，最終會推導出來的句型(sentential form)裡面包含以自己為最左符號(left-symbol)的句型"<ref>[http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion'  Notes on Formal Language Theory and Parsing] {{Wayback|url=http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion' |date=20170828232456 }}, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.[[JPR02]]</ref>

=== 直接左遞歸 ===
直接左遞歸（Immediate left recursion）以下面的句型規則出現：
:<math>A \to A\alpha \mid \beta</math>
這裡<math>\alpha</math>跟<math>\beta</math>代表不同的非终结符號跟终结符號組成的序列，並且<math>\beta</math>不一定要包含<math>A</math>。舉例來說，以下規則
:<math>\mathit{Expr} \to \mathit{Expr} + \mathit{Term}</math>
就是一個直接左遞歸的例子。 這規則的''[[遞歸下降分析器]]''(recursive descent parser)可能會像這樣：
<syntaxhighlight lang="text">
function Expr()
{  
    Expr();  match('+');  Term();
}
</syntaxhighlight>
然後這個遞歸下降分析器在嘗試去解析包含此規則的文法時，會陷入一個無窮的遞歸。

=== 間接左遞歸 ===
間接左遞歸(indirect left recursion)最簡單的形式如下：
:<math>A \to B\alpha \mid C</math>
:<math>B \to A\beta \mid D,</math>
這規則可能產生 <math>A \Rightarrow B\alpha \Rightarrow A\beta\alpha \Rightarrow \ldots </math> 這種生成。

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

更一般化的說法，對非终结符號<math>A_0, A_1, \ldots, A_n</math>，間接左遞歸被定義為以下的型態：
:<math>A_0 \to A_1\alpha_1 \mid \ldots</math>
:<math>A_1 \to A_2\alpha_2 \mid \ldots</math>
:<math>\cdots</math>
:<math>A_n \to A_0\alpha_{n+1} \mid \ldots</math>
這裡的<math>\alpha_1, \alpha_2, \ldots, \alpha_n</math>都是一堆終端與非终结符號的序列。

== 在由上而下語法分析(top-down parsing)裡容納左遞歸 ==
一個包含左遞歸的[[形式文法]]不能以簡易的 [[遞歸下降分析器]]進行[[語法分析器|語法分析]]，除非將文法轉變為[[Weak equivalence|weakly equivalent]] 的右遞歸形式 (相對的，在[[LALR]]分析器裡面則比較偏好左遞歸，因為比起右遞歸來說會使用比較少的[[堆疊]])；然而，比較複雜的由上而下(top-down)語法分析器裡面可以藉由使用縮減(by use of curtailment)來實做一般的[[上下文無關文法]]。 在2006年, Frost 和 Hafiz 提出一個演算法，可以容納包含直接左遞歸生成規則的 {{tsl|en|ambiguous grammer|模糊文法}}(ambiguous grammers)。<ref name="FrostHafiz2006">{{cite journal|last=Frost|first=R.|coauthors=R. Hafiz|date=2006|title=A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.|journal=ACM SIGPLAN Notices|volume=41|issue=5|pages=46–54|url=http://portal.acm.org/citation.cfm?id=1149988|doi=10.1145/1149982.1149988|access-date=2010-10-11|archive-date=2020-06-28|archive-url=https://web.archive.org/web/20200628080400/https://dl.acm.org/doi/10.1145/1149982.1149988|dead-url=no}}</ref> 在2007年，Frost，Hafiz和Callaghan 將此演算法延伸為一個完整的，可以適用並在[[多項式時間]]內處理直接或間接左遞歸，而且可以為高度模糊文法接近指數數目的分析樹，產生小一些多項式空間的表示法。<ref name="FrostHafizCallaghan2007">{{cite journal|last=Frost|first=R.|coauthors=R. Hafiz and P. Callaghan|date=June 2007|title=Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars.|journal=10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE|location=Prague|pages=109–120|url=http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf|access-date=2010-10-11|archive-date=2011-05-27|archive-url=https://web.archive.org/web/20110527032954/http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf|dead-url=yes}}</ref>這些人後來在[[Haskell]]程式語言裡面以這個演算法實做了一個的分析器組合(parser combinator)的集合。<ref name="FrostHafizCallaghan2008">{{cite journal|last=Frost|first=R.|coauthors=R. Hafiz and P. Callaghan|date=January 2008|title=Parser Combinators for Ambiguous Left-Recursive Grammars.|journal=10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN|volume=4902|issue=2008|pages=167–181|url=http://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf|doi=10.1007/978-3-540-77442-6_12|access-date=2010-10-11|archive-date=2008-12-21|archive-url=https://web.archive.org/web/20081221131212/http://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf|dead-url=no}}</ref>

== 移除左遞歸 ==
=== 移除直接左遞歸 ===
一個一般化後移除直接左遞歸的演算法如下所述。 這個方法已經有過許多的改進，包括Robert C. Moore所撰寫，名為"Removing Left Recursion from Context-Free Grammars"的改進。<ref name="Moore2000">{{cite journal|last=Moore|first=Robert C.|title=Removing Left Recursion from Context-Free Grammars|journal=6th Applied Natural Language Processing Conference|date=May 2000|pages=249–255|url=http://acl.ldc.upenn.edu/A/A00/A00-2033.pdf|deadurl=yes|archiveurl=https://web.archive.org/web/20060916125856/http://acl.ldc.upenn.edu/A/A00/A00-2033.pdf|archivedate=2006-09-16}}</ref>

對於每個規則如下

:<math>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </math>

(注意這裡：

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

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

:<math>A \rightarrow \beta_1A^\prime\, |\, \ldots\,  |\,  \beta_mA^\prime</math>

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

:<math>A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\,  |\,  \ldots\, |\, \alpha_nA^\prime</math>

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

舉例，考慮以下規則

:<math>Expr \rightarrow Expr\,+\,Expr\,|\,Int\,|\,String</math>

我們可以改寫為

:<math>Expr \rightarrow Int\,ExprRest\,|\,String\,ExprRest</math>

:<math>ExprRest \rightarrow \epsilon\,|\,+\,Expr\,ExprRest</math>

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

:<math>ExprRest \rightarrow \epsilon\,|\,+\,Expr</math>

來避免掉左遞歸的出現

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

將所有非終端符號以某個固定的順序<math>A_1, \ldots A_n</math>排列

: 從 i = 1 到 n {
::從 j = 1 到 i – 1 {
:::* 設<math>A_j</math>的生成規則為
:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>
:::* 將所有規則 <math>A_i \rightarrow A_j \gamma</math>換成
:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</math>
:::*移除<math>A_i</math>規則中的直接左遞歸
::}
:}

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

範例 :

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

:<math>Expr \rightarrow Expr\,+\,Term\,|\,Term</math>

:<math>Term \rightarrow Term\,*\,Factor\,|\,Factor</math>

:<math>Factor \rightarrow (Expr)\,|\,Int</math>

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

:<math>Expr \rightarrow Term\ Expr'</math>

:<math>Expr' \rightarrow {} + Term\ Expr'\,|\,\epsilon</math>

:<math>Term \rightarrow Factor\ Term'</math>

:<math>Term' \rightarrow {} * Factor\ Term'\,|\,\epsilon</math>

:<math>Factor \rightarrow (Expr)\,|\,Int</math>

我們將字串 '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   <math>\epsilon</math>
                                                  |
                                                 Int

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

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

== 相關條目 ==
* [[尾部遞歸]]

== 參考資料 ==
<references />

== 外部連結 ==
* [http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf CMU lecture on left-recursion] {{Wayback|url=http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf |date=20160303213847 }}
* [http://lambda.uta.edu/cse5317/notes/node21.html Practical Considerations for LALR(1) Grammars] {{Wayback|url=http://lambda.uta.edu/cse5317/notes/node21.html |date=20201201013243 }}
* [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] {{Wayback|url=http://www.cs.uwindsor.ca/~hafiz/proHome.html |date=20130404013000 }} - eXecutable SpecificAtIons of GrAmmars

[[Category:控制流程]]
[[Category:形式語言]]
[[Category:分析演算法]]
[[Category:递归]]