Can you summarize the following document?
        
  "一個文法是左遞迴的,若我們可以找出其中存在某非終結符號A,最終會推匯出來的句型(sentential form)裡面包含以自己為最左符號(left-symbol)的句型"

  直接左遞迴(Immediate left recursion)以下面的句型規則出現: 這裡formula_2跟formula_3代表不同的非終結符號跟終結符號組成的序列,並且formula_3不一定要包含formula_5。舉例來說,以下規則 就是一個直接左遞迴的例子。 這規則的"遞迴下降分析器"(recursive descent parser)可能會像這樣:  然後這個遞迴下降分析器在嘗試去解析包含此規則的文法時,會陷入一個無窮的遞迴。

  間接左遞迴(indirect left recursion)最簡單的形式如下: 這規則可能產生 formula_9 這種生成。  簡單的說,間接左遞迴就是,並非在一條規則內完成左遞迴,而是在許多條規則之後,於產生的句子最左邊出現了一開始的非終結符號。  更一般化的說法,對非終結符號formula_10,間接左遞迴被定義為以下的型態: 這裡的formula_15都是一堆終端與非終結符號的序列。

  一個包含左遞迴的形式文法不能以簡易的 遞迴下降分析器進行語法分析,除非將文法轉變為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的規則改成以下規則:  然後對新創造出來非終端符號的規則  這個新創造出來的符號常被稱為"尾巴"(tail),或者"rest"(剩餘)  舉例,考慮以下規則  我們可以改寫為  然後最後一個規則可以縮短改寫為  來避免掉左遞迴的出現

  如果文法內不存在 formula_26(代表空字串)的生成 (不存在formula_27這樣的規則),而且不是迴圈(cyclic)的文法(對所有非終端符號A,不存在像是formula_28這種形式的規則),以下這個一般化的演算法可以用來去除文法的間接左遞迴:  將所有非終端符號以某個固定的順序formula_29排列

  上面的轉換使用右遞迴的文法來避免掉左遞迴的出現;但是這樣會改變規則的結合律。左遞迴會創造出向左的結合律;但是右遞迴則會創造出向右的結合律。  範例 :  一開始我們拿到以下文法:  在我們使用上面的轉換方式來移除掉左遞迴之後,我們取得了以下文法:  我們將字串 'a + a + a'用一個LALR分析器(這種分析器可以處理左遞迴的文法)使用原先的文法來分析,會得到下面的分析樹(parse tree): 整個分析樹是往左邊長,代表在這裡的規則,'+'這個符號是左結合(left associative)的,或者說這規則代表(a + a) + a。  但是我們改變了文法之後,那這個分析樹會變成:  我們可以看出這棵樹現在是往右邊成長,意思上代表了a + ( a + a)。我們將'+'的結合律改變了, 變成是右結合的規則。 在處理加法的文法時這不是什麼問題,但是如果我們現在處理的是減法,這就會變成是很嚴重的問題。  問題的關鍵在於有很多常用的算術規則要求左結合的規則。我們有幾種解決辦法: (a) 將規則重新改為左遞迴,(b) 使用更多的非終端符號來改寫規則,以強迫文法合乎正確的結合(c) 如果使用YACC 或者Bison,他們有所謂"算符宣告"(operator declarations), %left, %right and %nonassoc,這一些算符可以告訴語法分析器產生程式(parser generator)應該遵從哪一種結合。
在電腦科學裡面,左遞迴是一種遞迴的特殊狀況。