# 左遞歸

## 定義

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

### 直接左遞歸

${\displaystyle A\to A\alpha \mid \beta }$

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

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


### 間接左遞歸

${\displaystyle A\to B\alpha \mid C}$
${\displaystyle B\to A\beta \mid D,}$

${\displaystyle A_{0}\to A_{1}\alpha _{1}\mid \ldots }$
${\displaystyle A_{1}\to A_{2}\alpha _{2}\mid \ldots }$
${\displaystyle \cdots }$
${\displaystyle A_{n}\to A_{0}\alpha _{n+1}\mid \ldots }$

## 移除左遞歸

### 移除直接左遞歸

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

(注意這裡：

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

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

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

${\displaystyle Expr\rightarrow Expr\,+\,Expr\,|\,Int\,|\,String}$

${\displaystyle Expr\rightarrow Int\,ExprRest\,|\,String\,ExprRest}$
${\displaystyle ExprRest\rightarrow \epsilon \,|\,+\,Expr\,ExprRest}$

${\displaystyle ExprRest\rightarrow \epsilon \,|\,+\,Expr}$

### 移除間接左遞歸

• ${\displaystyle A_{j}}$ 的生成規則為
${\displaystyle A_{j}\rightarrow \delta _{1}|\ldots |\delta _{k}}$
• 將所有規則 ${\displaystyle A_{i}\rightarrow A_{j}\gamma }$ 換成
${\displaystyle A_{i}\rightarrow \delta _{1}\gamma |\ldots |\delta _{k}\gamma }$
• 移除${\displaystyle A_{i}}$ 規則中的直接左遞歸
}
}

## 陷阱

${\displaystyle Expr\rightarrow Expr\,+\,Term\,|\,Term}$
${\displaystyle Term\rightarrow Term\,*\,Factor\,|\,Factor}$
${\displaystyle Factor\rightarrow (Expr)\,|\,Int}$

${\displaystyle Expr\rightarrow Term\ Expr'}$
${\displaystyle Expr'\rightarrow {}+Term\ Expr'\,|\,\epsilon }$
${\displaystyle Term\rightarrow Factor\ Term'}$
${\displaystyle Term'\rightarrow {}*Factor\ Term'\,|\,\epsilon }$
${\displaystyle Factor\rightarrow (Expr)\,|\,Int}$

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


                            Expr ---
/        \
Term      Expr' --
|       /  |     \
Factor   +  Term   Expr' ------
|          |      |  \       \
Int       Factor   +  Term   Expr'
|           |      |
Int        Factor   ${\displaystyle \epsilon }$
|
Int


## 參考資料

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. (PDF). 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. (PDF). 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 (PDF). 6th Applied Natural Language Processing Conference. May 2000: 249–255. （原始内容 (PDF)存档于2006-09-16）.