Пређи на садржај

Leva rekurzija

С Википедије, слободне енциклопедије

„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:

  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