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.”^[1]

Neposredna leva rekurzija

Neposredna leva rekuzija se javlja u pravilima oblika

${\displaystyle A\rightarrow A\alpha \,|\,\beta }$

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

Primer : Pravilo

${\displaystyle 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:

${\displaystyle A\rightarrow B\alpha \,|\,C}$

${\displaystyle B\rightarrow A\beta \,|\,D}$

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

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

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

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

${\displaystyle ...}$

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

Gde su ${\displaystyle \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"^[2], koji je napisao Robert C. Moore.

Za svako pravilo oblika

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

Gde važi:

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

Zamenimo A-pravilo pravilom:

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

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

${\displaystyle 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 ${\displaystyle A\rightarrow ...|\epsilon |...}$) i bez jednostukih pravila (ni za jedan neterminal A ne postoji izvođenje oblika ${\displaystyle 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 ${\displaystyle A_{1}}$, ... ${\displaystyle A_{n}}$.

for i = 1 to n {

for j = 1 to i – 1 {

• ako su ${\displaystyle A_{j}}$ pravila

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

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

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

}

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

}

Primer

Posmatrajmo gramatiku aritmetičkih izraza:

${\displaystyle Expr\rightarrow Expr\,+\,Term\,|\,Term}$

${\displaystyle Term\rightarrow Term\,*\,Factor\,|\,Factor}$

${\displaystyle 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:

${\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)\,|\,Broj}$

Pogledajte još

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

Beleške