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

 

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

Primer : Pravilo

 

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:

 

 

Iz kojih bi se moglo dobiti izvođenje:  

Uopšteno govoreći, za neterminale  , posredna leva rekurzija može se definisati postojanjem forme:

 

 

 

 

Gde su   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

 

Gde važi:

  • Neterminal A poseduje levu rekurziju
  •   je neprazna rečenična forma ( )
  •   je rečenična forma koja ne počinje simbolom A.

Zamenimo A-pravilo pravilom:

 

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

 

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

Eliminacija posredne leve rekurzijeУреди

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

Prethodno među neterminalima uspostavimo neki (bilo kakav) poredak  , ...  .

for i = 1 to n {
for j = 1 to i – 1 {
  • ako su   pravila
 
  • svako pravilo oblika   zamenimo sa
 
}
  • eliminišemo neposrednu levu rekurziju za  
}

PrimerУреди

Posmatrajmo gramatiku aritmetičkih izraza:

 
 
 

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:

 
 
 
 
 

Pogledajte jošУреди

BeleškeУреди

  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. ^ Removing Left Recursion from Context-Free Grammars, Robert C. Moore, Microsoft Research, Redmond, WA, USA