Lijeva rekurzija

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

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

Neposredna lijeva rekurzija se događa u produkcijama oblika

[math]\displaystyle{ A \rightarrow A\alpha\,|\,\beta }[/math]

Gdje su [math]\displaystyle{ \alpha }[/math] i [math]\displaystyle{ \beta }[/math] nizovi završnih i nezavršnih znakova, i [math]\displaystyle{ \beta }[/math] ne sadrži A na krajnje lijevom mjestu.

Primjer: Produkcija

[math]\displaystyle{ Expr \rightarrow Expr\,+\,Term }[/math]

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

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

[math]\displaystyle{ A \rightarrow B\alpha\,|\,C }[/math]

[math]\displaystyle{ B \rightarrow A\beta\,|\,D }[/math]

Pri čemu je moguć slijed generiranja međuniza [math]\displaystyle{ A \Rightarrow B\alpha \Rightarrow A\beta \Rightarrow A \Rightarrow ... }[/math]

Općenitije, za nezavršne znakove [math]\displaystyle{ A_0, A_1, ..., A_n }[/math], posredna lijeva rekurzija se može definirati u obliku:

[math]\displaystyle{ A_0 \rightarrow A_1\alpha_1\,|... }[/math]

[math]\displaystyle{ A_1 \rightarrow A_2\alpha_2\,|... }[/math]

[math]\displaystyle{ ... }[/math]

[math]\displaystyle{ A_n \rightarrow A_0\alpha_{(n+1)}\,|... }[/math]

Gdje su [math]\displaystyle{ \alpha_1, \alpha_2, ..., \alpha_n }[/math] nizovi završnih i nezavršnih znakova.

Razrješavanje lijeve rekurzije

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

[math]\displaystyle{ A \rightarrow A\alpha_1\,|\,...\,|\,A\alpha_n\,|\,\beta_1\,|\,...\,|\,\beta_m }[/math]

Gdje je:

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

Zamijeni A-produkciju produkcijom:

[math]\displaystyle{ A \rightarrow \beta_1A^\prime\, |\, ...\, |\, \beta_mA^\prime }[/math]

I stvori novi nezavršni znak

[math]\displaystyle{ A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\, |\, ...\, |\, \alpha_nA^\prime }[/math]

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

Razrješavanje posredne lijeve rekurzije

Ako gramatika nema [math]\displaystyle{ \epsilon }[/math]-produkcija (zj. nijedna produkcija nije oblika [math]\displaystyle{ A \rightarrow ... | \epsilon | ... }[/math]) i nije ciklička (tj. nema produkcija oblika [math]\displaystyle{ A \Rightarrow ... \Rightarrow A }[/math] 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 [math]\displaystyle{ A_1 }[/math], ... [math]\displaystyle{ A_n }[/math].

for i = 1 to n {

for j = 1 to i – 1 {

neka su trenutne [math]\displaystyle{ A_j }[/math] produkcije

[math]\displaystyle{ A_j \rightarrow \delta_1 | ... | \delta_k }[/math]

zamijeni svaku produkciju [math]\displaystyle{ A_i \rightarrow A_j \gamma }[/math] sa

[math]\displaystyle{ A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma }[/math]

razriješi neposrednu lijevu rekurziju za [math]\displaystyle{ A_i }[/math]

}

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:

[math]\displaystyle{ Expr \rightarrow Expr\,+\,Term\,|\,Term }[/math]

[math]\displaystyle{ Term \rightarrow Term\,*\,Factor\,|\,Factor }[/math]

[math]\displaystyle{ Factor \rightarrow (Expr)\,|\,Int }[/math]

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

[math]\displaystyle{ Expr \rightarrow Term Expr' }[/math]

[math]\displaystyle{ Expr' \rightarrow + Term Expr'\,|\,\epsilon }[/math]

[math]\displaystyle{ Term \rightarrow Factor Term' }[/math]

[math]\displaystyle{ Term' \rightarrow * Factor Term'\,|\,\epsilon }[/math]

[math]\displaystyle{ Factor \rightarrow (Expr)\,|\,Int }[/math]

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   [math]\displaystyle{ \epsilon }[/math]
                                                 |
                                                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