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

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