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

Sadržaj

[uredi] Definicija

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.

[uredi] Neposredna lijeva rekurzija

Neposredna lijeva rekurzija se događa u produkcijama oblika

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

Gdje su α i β nizovi završnih i nezavršnih znakova, i β 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.

[uredi] Posredna lijeva rekurzija

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 A0,A1,...,An, 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 α12,...,αn nizovi završnih i nezavršnih znakova.

[uredi] Razrješavanje lijeve rekurzije

[uredi] Razrješavanje neposredne lijeve rekurzije

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
  • α niz nezavršnih i završnih znakova različit od praznog niza (\alpha \ne \epsilon)
  • β 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".

[uredi] Razrješavanje posredne lijeve rekurzije

Ako gramatika nema ε-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 A1, ... An.

for i = 1 to n {
for j = 1 to i – 1 {
  • neka su trenutne Aj 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 Ai
}
}

[uredi] Klopke

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   ε
                                                 |
                                                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.

[uredi] Vanjske poveznice

Drugi jezici