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  
}

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 Архивирано на сајту Wayback Machine (28. август 2017), 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