Lijeva rekurzija

Izvor: Wikipedija
Skoči na: orijentacija, traži

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 da rezultira u manjoj potrošnji stogovnog prostora od desne rekurzije.

Definicija[uredi VE | uredi]

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 VE | uredi]

Neposredna lijeva rekurzija se događa u produkcijama oblika

A \rightarrow A\alpha\,|\,\beta

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

Primjer: Produkcija

Expr \rightarrow Expr\,+\,Term

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 VE | uredi]

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

A \rightarrow B\alpha\,|\,C

B \rightarrow A\beta\,|\,D

Pri čemu je moguć slijed generiranja međuniza A \Rightarrow B\alpha \Rightarrow A\beta \Rightarrow A \Rightarrow ...

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

A_0 \rightarrow A_1\alpha_1\,|...

A_1 \rightarrow A_2\alpha_2\,|...

...

A_n \rightarrow A_0\alpha_{(n+1)}\,|...

Gdje su \alpha_1, \alpha_2, ..., \alpha_n nizovi završnih i nezavršnih znakova.

Razrješavanje lijeve rekurzije[uredi VE | uredi]

Razrješavanje neposredne lijeve rekurzije[uredi VE | uredi]

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

A \rightarrow A\alpha_1\,|\,...\,|\,A\alpha_n\,|\,\beta_1\,|\,...\,|\,\beta_m

Gdje je:

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

Zamijeni A-produkciju produkcijom:

A \rightarrow \beta_1A^\prime\, |\, ...\,  |\,  \beta_mA^\prime

I stvori novi nezavršni znak

A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\,  |\,  ...\, |\, \alpha_nA^\prime

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

Razrješavanje posredne lijeve rekurzije[uredi VE | uredi]

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

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

for i = 1 to n {
for j = 1 to i – 1 {
  • neka su trenutne A_j produkcije
A_j \rightarrow \delta_1 | ... | \delta_k
  • zamijeni svaku produkciju A_i \rightarrow A_j \gamma sa
A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma
  • razriješi neposrednu lijevu rekurziju za A_i
}
}

Klopke[uredi VE | uredi]

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 sa gramatikom:

Expr \rightarrow Expr\,+\,Term\,|\,Term

Term \rightarrow Term\,*\,Factor\,|\,Factor

Factor \rightarrow (Expr)\,|\,Int

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

Expr \rightarrow Term Expr'

Expr' \rightarrow + Term Expr'\,|\,\epsilon

Term \rightarrow Factor Term'

Term' \rightarrow * Factor Term'\,|\,\epsilon

Factor \rightarrow (Expr)\,|\,Int

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   \epsilon
                                                 |
                                                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 ukoliko 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 VE | uredi]