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.
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 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:
te bi, kao što je očito, ušao u beskonačnu rekurziju.
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.
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:
Zamijeni A-produkciju produkcijom:
I stvori novi nezavršni znak
Ovaj novostvoreni znak se često zove "rep" ili "ostatak".
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 , ... .
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:
|