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 na to 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

$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

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

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
• $\alpha$ niz nezavršnih i završnih znakova različit od praznog niza ($\alpha \neq \epsilon$)
• $\beta$ niz završnih i nezavršnih znakova ne sadrži A na krajnje lijevom mjestu.

Zamijeni A-produkciju produkcijom:

$A\rightarrow \beta _{1}A^{\prime }\,|\,...\,|\,\beta _{m}A^{\prime }$

I stvori novi nezavršni znak

$A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,...\,|\,\alpha _{n}A^{\prime }$

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

Razrješavanje posredne lijeve rekurzije

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 primijenjen 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

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:

$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 TermExpr'$

$Expr'\rightarrow +TermExpr'\,|\,\epsilon$

$Term\rightarrow FactorTerm'$

$Term'\rightarrow *FactorTerm'\,|\,\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 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

• http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf  Arhivirana inačica izvorne stranice od 28. kolovoza 2017. (Wayback Machine)
• http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf  Arhivirana inačica izvorne stranice od 3. ožujka 2016. (Wayback Machine)
• http://www.wvutech.edu/mclark/Systems%20Programming/Removing%20Left%20Recursion.pdf  Arhivirana inačica izvorne stranice od 26. rujna 2007. (Wayback Machine)
• Practical Considerations for LALR(1) Grammars