Лева рекурзија

Дефиниција

„Граматика је лево рекурзивна ако садржи нетерминал А, такав да се из њега може извести реченична форма која почиње тим симболом.”

Непосредна лева рекурзија

Непосредна лева рекузија се јавља у правилима облика

$A\rightarrow A\alpha \,|\,\beta$

Где су α и β реченичне форме и β не почиње симболом А.

Пример : Правило

$Expr\rightarrow Expr\,+\,Term$

садржи непосредну леву рекурзију. Анализатор рекурзивним спустом би изгледао на пример овако :

function Expr() {

Expr(); match('+'); Term();

}

и анализатор би упао у бесконачну рекурзију када би покушао да анализира граматику која садржи ово правило.

Посредна лева рекурзија

Посредна лева рекурзија у најједноставнијем облику могла би се дефинисати следећим правилима:

$A\rightarrow B\alpha \,|\,C$

$B\rightarrow A\beta \,|\,D$

Из којих би се могло добити извођење: $A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow ...$

Уопштено говорећи, за нетерминале $A_{0},A_{1},...,A_{n}$, посредна лева рекурзија може се дефинисати постојањем форме:

$A_{0}\rightarrow A_{1}\alpha _{1}\,|...$

$A_{1}\rightarrow A_{2}\alpha _{2}\,|...$

$...$

$A_{n}\rightarrow A_{0}\alpha _{(n+1)}\,|...$

Где су $\alpha _{1},\alpha _{2},...,\alpha _{n}$ реченичне форме.

Елиминација леве рекурзије

Елиминација непосредне леве рекурзије

Следи алгоритам уклањања непосредне леве рекурзије. Постигнуто је неколико унапређења овог метода, укључујући и она описана у чланку "Removing Left Recursion from Context-Free Grammars" , који је написао Robert C. Moore.

За свако правило облика

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

Где важи:

• Нетерминал А поседује леву рекурзију
• $\alpha _{i}$ је непразна реченична форма ($\alpha _{i}\neq \epsilon$)
• $\beta _{i}$ је реченична форма која не почиње симболом А.

Заменимо А-правило правилом:

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

Где је А’ нови нетерминал за који важи:

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

Новодобијени симбол се често назива „реп” или „остатак”.

Елиминација посредне леве рекурзије

Ако је граматика својствена, тј. ε-слободна (без правила облика $A\rightarrow ...|\epsilon |...$) и без једностуких правила (ни за један нетерминал А не постоји извођење облика $A\Rightarrow ...\Rightarrow A$ ), ово је општи алгоритам који се може применити за уклањње посредне леве рекурзије:

Претходно међу нетерминалима успоставимо неки (било какав) поредак $A_{1}$, ... $A_{n}$.

for i = 1 to n {

for j = 1 to i – 1 {

• ако су $A_{j}$ правила

$A_{j}\rightarrow \delta _{1}|...|\delta _{k}$

• свако правило облика $A_{i}\rightarrow A_{j}\gamma$ заменимо са

$A_{i}\rightarrow \delta _{1}\gamma |...|\delta _{k}\gamma$

}

• елиминишемо непосредну леву рекурзију за $A_{i}$

}

Пример

Посматрајмо граматику аритметичких израза:

$Expr\rightarrow Expr\,+\,Term\,|\,Term$

$Term\rightarrow Term\,*\,Factor\,|\,Factor$

$Factor\rightarrow (Expr)\,|\,Broj$

Expr и Term су лево рекурзивна. Уведимо нове помоћне симболе Expr’ и Term’. Примена наведеног поступка даје следећу граматику без лево рекурзивних правила:

$Expr\rightarrow Term\ Expr'$

$Expr'\rightarrow {}+Term\ Expr'\,|\,\epsilon$

$Term\rightarrow Factor\ Term'$

$Term'\rightarrow {}*Factor\ Term'\,|\,\epsilon$

$Factor\rightarrow (Expr)\,|\,Broj$

Погледајте још

• Елиминација е-правила
• Елиминација некорисних симбола
• Елиминација једноструких правила