左遞歸

定義

"一個文法是左遞歸的，若我們可以找出其中存在某非终结符號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 [2010-10-11]. doi:10.1145/1149982.1149988. （原始内容存档于2020-06-28）.
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 [2010-10-11]. （原始内容 (PDF)存档于2011-05-27）.
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 [2010-10-11]. doi:10.1007/978-3-540-77442-6_12. （原始内容存档 (PDF)于2008-12-21）.
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）.