Leva rekurzija

Definicija

„Gramatika je levo rekurzivna ako sadrži neterminal A, takav da se iz njega može izvesti rečenična forma koja počinje tim simbolom.”

Neposredna leva rekurzija

Neposredna leva rekuzija se javlja u pravilima oblika

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

Gde su α i β rečenične forme i β ne počinje simbolom A.

Primer : Pravilo

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

sadrži neposrednu levu rekurziju. Analizator rekurzivnim spustom bi izgledao na primer ovako :

function Expr() {

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

}

i analizator bi upao u beskonačnu rekurziju kada bi pokušao da analizira gramatiku koja sadrži ovo pravilo.

Posredna leva rekurzija

Posredna leva rekurzija u najjednostavnijem obliku mogla bi se definisati sledećim pravilima:

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

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

Iz kojih bi se moglo dobiti izvođenje: $A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow ...$

Uopšteno govoreći, za neterminale $A_{0},A_{1},...,A_{n}$, posredna leva rekurzija može se definisati postojanjem forme:

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

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

$...$

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

Gde su $\alpha _{1},\alpha _{2},...,\alpha _{n}$ rečenične forme.

Eliminacija leve rekurzije

Eliminacija neposredne leve rekurzije

Sledi algoritam uklanjanja neposredne leve rekurzije. Postignuto je nekoliko unapređenja ovog metoda, uključujući i ona opisana u članku "Removing Left Recursion from Context-Free Grammars" , koji je napisao Robert C. Moore.

Za svako pravilo oblika

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

Gde važi:

• Neterminal A poseduje levu rekurziju
• $\alpha _{i}$ je neprazna rečenična forma ($\alpha _{i}\neq \epsilon$)
• $\beta _{i}$ je rečenična forma koja ne počinje simbolom A.

Zamenimo A-pravilo pravilom:

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

Gde je A’ novi neterminal za koji važi:

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

Novodobijeni simbol se često naziva „rep” ili „ostatak”.

Eliminacija posredne leve rekurzije

Ako je gramatika svojstvena, tj. ε-slobodna (bez pravila oblika $A\rightarrow ...|\epsilon |...$) i bez jednostukih pravila (ni za jedan neterminal A ne postoji izvođenje oblika $A\Rightarrow ...\Rightarrow A$ ), ovo je opšti algoritam koji se može primeniti za uklanjnje posredne leve rekurzije:

Prethodno među neterminalima uspostavimo neki (bilo kakav) poredak $A_{1}$, ... $A_{n}$.

for i = 1 to n {

for j = 1 to i – 1 {

• ako su $A_{j}$ pravila

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

• svako pravilo oblika $A_{i}\rightarrow A_{j}\gamma$ zamenimo sa

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

}

• eliminišemo neposrednu levu rekurziju za $A_{i}$

}

Primer

Posmatrajmo gramatiku aritmetičkih izraza:

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

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

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

Expr i Term su levo rekurzivna. Uvedimo nove pomoćne simbole Expr’ i Term’. Primena navedenog postupka daje sledeću gramatiku bez levo rekurzivnih pravila:

$Expr\rightarrow Term\ Expr'$

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

$Term\rightarrow Factor\ Term'$

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

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

Pogledajte još

• Eliminacija e-pravila
• Eliminacija nekorisnih simbola
• Eliminacija jednostrukih pravila