Lijeva rekurzija

Izvor: Wikipedija

U računarstvu, lijeva rekurzija je poseban slučaj rekurzije

Formalna gramatika koja sadrži lijevu rekurziju ne može biti parsirana tehnikom rekurzivnog spusta. Umjesto toga, lijeva je rekurzija pogodniji odabir za LALR parsere s obzirom na to da rezultira u manjoj potrošnji stogovnog prostora od desne rekurzije.

Definicija[uredi | uredi kôd]

Gramatika je lijevo rekurzivna ako možemo pronaći nezavršni znak A koji će s vremenom biti korišten u postupku generiranja rečeničnog oblika sa sobom sadržanim na krajnje lijevom mjestu desne strane produkcije.

Neposredna lijeva rekurzija[uredi | uredi kôd]

Neposredna lijeva rekurzija se događa u produkcijama oblika

Gdje su i nizovi završnih i nezavršnih znakova, i ne sadrži A na krajnje lijevom mjestu.

Primjer: Produkcija

je neposredno lijevo rekurzivna. Parser koji koristi tehniku rekurzivnog spusta bi za ovu produkciju izgradio potprogram sljedećeg oblika:

function Expr() {
Expr();
match('+');
Term();
}

te bi, kao što je očito, ušao u beskonačnu rekurziju.

Posredna lijeva rekurzija[uredi | uredi kôd]

U najjednostavnijem obliku, posredna lijeva rekurzija se može definirati kao:

Pri čemu je moguć slijed generiranja međuniza

Općenitije, za nezavršne znakove , posredna lijeva rekurzija se može definirati u obliku:

Gdje su nizovi završnih i nezavršnih znakova.

Razrješavanje lijeve rekurzije[uredi | uredi kôd]

Razrješavanje neposredne lijeve rekurzije[uredi | uredi kôd]

Slijedi općeniti algoritam za razrješavanje neposredne lijeve rekurzije. Ovaj je algoritam s vremenom poboljšan na nekoliko načina, jedan od kojih je opisan u ovom papiru.

Za svaku produkciju oblika

Gdje je:

  • A lijevo rekurzivan nezavršni znak
  • niz nezavršnih i završnih znakova različit od praznog niza ()
  • niz završnih i nezavršnih znakova ne sadrži A na krajnje lijevom mjestu.

Zamijeni A-produkciju produkcijom:

I stvori novi nezavršni znak

Ovaj novostvoreni znak se često zove "rep" ili "ostatak".

Razrješavanje posredne lijeve rekurzije[uredi | uredi kôd]

Ako gramatika nema -produkcija (zj. nijedna produkcija nije oblika ) i nije ciklička (tj. nema produkcija oblika za bilo koji nezavršni znak A), sljedeći općeniti algoritam može biti primijenjen za razrješavanje posredne lijeve rekurzije:

Preuredi nezavršne znakove u neki (bilo koji) fiksni poredak , ... .

for i = 1 to n {
for j = 1 to i – 1 {
  • neka su trenutne produkcije
  • zamijeni svaku produkciju sa
  • razriješi neposrednu lijevu rekurziju za
}
}

Klopke[uredi | uredi kôd]

Gornje transformacije razrješavaju lijevu rekurziju stvaranjem desno rekurzivne gramatike, što će uzrokovati promjenu asocijativnosti produkcija. Lijeva rekurzija uzrokuje lijevu asocijativnost, desna rekurzija uzrokuje desnu asocijativnost. Na primjer: Započinjemo s gramatikom:

Nakon primjene standardnih transformacija za razrješavanje lijeve rekurzije, dobiva se sljedeća gramatika:

Parsiranje niza znakova 'a + a + a' prvom gramatikom u LALR parseru (koji može prepoznati lijevo rekurzivne gramatike) bi rezultiralo sljedećim stablom parsiranja:

                           Expr
                         /      \
                       Expr  + Term
                     /  |  \        \
                   Expr + Term    Factor
                    |       |        |
                  Term    Factor    Int
                    |        |
                  Factor    Int
                    |
                   Int  

Ovo stablo parsiranja raste na lijevu stranu, što pokazuje da je operator '+' lijevo asocijativan, predstavljajući grupiranje operanada u obliku (a + a) + a.

Ali promjenom gramatike se mijenja i stablo parsiranja:

                            Expr ---
                           /        \
                         Term      Expr' --
                           |      /  |     \ 
                       Factor    +  Term   Expr' ------
                           |         |      |  \       \
                          Int      Factor   +  Term   Expr'
                                                 |      |
                                               Factor   
                                                 |
                                                Int

Sad stablo raste na desnu stranu, predstavljajući grupiranje operanada u obliku a + (a + a). Promijenjena je asocijativnost operatora '+', koji se sad desno asocijativan. Iako ovo nije problem za asocijativnost zbrajanja sa zabrajanjem, izraz bi poprimio znatno drugačiju vrijednost ako bi se radilo o oduzimanju.

Problem je u tome što normalna aritmetika zahtijeva lijevu asocijativnost. Postoji nekoliko rješenja:

  • prepisivanje gramatike sa svim produkcijama u lijevo rekurzivnom obliku
  • prepisivanje gramatike dodavanjem nezavršnih znakova koji bi prisilile ispravne prednosti/asocijativnosti operatora
  • ako se koriste YACC ili Bison, postoje operatorske deklaracije %left, %right i %nonassoc koje govore generatoru parsera koju asocijativnost da nametne.

Vanjske poveznice[uredi | uredi kôd]