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
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: 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:
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.
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
Gdje je:
A lijevo rekurzivan nezavršni znak niz nezavršnih i završnih znakova različit od praznog niza () niz završnih i nezavršnih znakova ne sadrži A na krajnje lijevom mjestu.
Zamijeni A-produkciju produkcijom:
I stvori novi nezavršni znak
Ovaj novostvoreni znak se često zove "rep" ili "ostatak". Razrješavanje posredne lijeve rekurzije 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 , ... .
for i = 1 to n { for j = 1 to i – 1 { neka su trenutne produkcije
zamijeni svaku produkciju sa
razriješi neposrednu lijevu rekurziju za
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:
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: 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 http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf http://www.wvutech.edu/mclark/Systems%20Programming/Removing%20Left%20Recursion.pdf Practical Considerations for LALR(1) Grammars
Kategorija:Formalni jezici Kategorija:Kontrola toka