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

1 Definicija
- 1.1 Neposredna lijeva rekurzija
- 1.2 Posredna lijeva rekurzija
2 Razrješavanje lijeve rekurzije
- 2.1 Razrješavanje neposredne lijeve rekurzije
- 2.2 Razrješavanje posredne lijeve rekurzije
3 Klopke
4 Vanjske poveznice

[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 $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 $α 1,α 2,...,α 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

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

}

[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

Kategorija: Formalni jezici

See also ebooksgratis.com: no banners, no cookies, totally FREE.