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.” -{Notes on Formal Language Theory and Parsing , James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02}-
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"}--{Removing Left Recursion from Context-Free Grammars, Robert C. Moore, Microsoft Research, Redmond, WA, USA}-, 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:
Види још Eliminacija e-pravila Eliminacija nekorisnih simbola Eliminacija jednostrukih pravila
Beleške
Категорија:Преводиоци (рачунарство) Категорија:Формални језици