左遞歸

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

定義[编辑]

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

直接左遞歸[编辑]

直接左遞歸(Immediate left recursion)以下面的句型規則出現:

A \to A\alpha \mid \beta

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

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

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

function Expr()
{  
    Expr();  match('+');  Term();
}

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

間接左遞歸[编辑]

間接左遞歸(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)。[2] 在2007年,Frost,Hafiz和Callaghan 將此演算法延伸為一個完整的,可以適用並在多項式時間內處理直接或間接左遞歸,而且可以為高度模糊文法接近指數數目的分析樹,產生小一些多項式空間的表示法。[3]這些人後來在Haskell程式語言裡面以這個演算法實做了一個的分析器組合(parser combinator)的集合。[4]

移除左遞歸[编辑]

移除直接左遞歸[编辑]

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

對於每個規則如下

A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m

(注意這裡:

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

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

A \rightarrow \beta_1A^\prime\, |\, \ldots\,  |\,  \beta_mA^\prime

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

A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\,  |\,  \ldots\, |\, \alpha_nA^\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)應該遵從哪一種結合。

相關條目[编辑]

參考資料[编辑]

  1. ^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
  2. ^ Frost, R.; R. Hafiz. A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.. ACM SIGPLAN Notices. 2006, 41 (5): 46–54. doi:10.1145/1149982.1149988. 
  3. ^ Frost, R.; R. Hafiz and P. Callaghan. Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars.. 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE (Prague). June 2007: 109–120. 
  4. ^ Frost, R.; R. Hafiz and P. Callaghan. Parser Combinators for Ambiguous Left-Recursive Grammars.. 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN. January 2008, 4902 (2008): 167–181. doi:10.1007/978-3-540-77442-6_12. 
  5. ^ Moore, Robert C. Removing Left Recursion from Context-Free Grammars. 6th Applied Natural Language Processing Conference. May 2000: 249–255. 

外部連接[编辑]