Leva rekurzija

Из Википедије, слободне енциклопедије

Definicija[уреди]

„Gramatika je levo rekurzivna ako sadrži neterminal A, takav da se iz njega može izvesti rečenična forma koja počinje tim simbolom.” [1]

Neposredna leva rekurzija[уреди]

Neposredna leva rekuzija se javlja u pravilima oblika

A \rightarrow A\alpha\,|\,\beta

Gde su α i β rečenične forme i β ne počinje simbolom A.

Primer : Pravilo

Expr \rightarrow Expr\,+\,Term

sadrži neposrednu levu rekurziju. Analizator rekurzivnim spustom bi izgledao na primer ovako :

function Expr() {
Expr(); match('+'); Term();
}

i analizator bi upao u beskonačnu rekurziju kada bi pokušao da analizira gramatiku koja sadrži ovo pravilo.

Posredna leva rekurzija[уреди]

Posredna leva rekurzija u najjednostavnijem obliku mogla bi se definisati sledećim pravilima:

A \rightarrow B\alpha\,|\,C

B \rightarrow A\beta\,|\,D

Iz kojih bi se moglo dobiti izvođenje: A \Rightarrow B\alpha \Rightarrow A\beta\alpha \Rightarrow ...

Uopšteno govoreći, za neterminale A_0, A_1, ..., A_n, posredna leva rekurzija može se definisati postojanjem forme:

A_0 \rightarrow A_1\alpha_1\,|...

A_1 \rightarrow A_2\alpha_2\,|...

...

A_n \rightarrow A_0\alpha_{(n+1)}\,|...

Gde su \alpha_1, \alpha_2, ..., \alpha_n rečenične forme.

Eliminacija leve rekurzije[уреди]

Eliminacija neposredne leve rekurzije[уреди]

Sledi algoritam uklanjanja neposredne leve rekurzije. Postignuto je nekoliko unapređenja ovog metoda, uključujući i ona opisana u članku "Removing Left Recursion from Context-Free Grammars" [2], koji je napisao Robert C. Moore.

Za svako pravilo oblika

A \rightarrow A\alpha_1\,|\,...\,|\,A\alpha_n\,|\,\beta_1\,|\,...\,|\,\beta_m

Gde važi:

Zamenimo A-pravilo pravilom:

A \rightarrow \beta_1A^\prime\, |\, ...\,  |\,  \beta_mA^\prime

Gde je A’ novi neterminal za koji važi:

A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\,  |\,  ...\, |\, \alpha_nA^\prime

Novodobijeni simbol se često naziva „rep” ili „ostatak”.

Eliminacija posredne leve rekurzije[уреди]

Ako je gramatika svojstvena, tj. ε-slobodna (bez pravila oblika A \rightarrow ... | \epsilon | ... ) i bez jednostukih pravila (ni za jedan neterminal A ne postoji izvođenje oblika A \Rightarrow  ... \Rightarrow A ), ovo je opšti algoritam koji se može primeniti za uklanjnje posredne leve rekurzije:

Prethodno među neterminalima uspostavimo neki (bilo kakav) poredak A_1, ... A_n.

for i = 1 to n {
for j = 1 to i – 1 {
  • ako su A_j pravila
A_j \rightarrow \delta_1 | ... | \delta_k
  • svako pravilo oblika A_i \rightarrow A_j \gamma zamenimo sa
A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma
}
  • eliminišemo neposrednu levu rekurziju za A_i
}

Primer[уреди]

Posmatrajmo gramatiku aritmetičkih izraza:

Expr \rightarrow Expr\,+\,Term\,|\,Term
Term \rightarrow Term\,*\,Factor\,|\,Factor
Factor \rightarrow (Expr)\,|\,Broj

Expr i Term su levo rekurzivna. Uvedimo nove pomoćne simbole Expr’ i Term’. Primena navedenog postupka daje sledeću gramatiku bez levo rekurzivnih pravila:

Expr \rightarrow Term\ Expr'
Expr' \rightarrow {} + Term\ Expr'\,|\,\epsilon
Term \rightarrow Factor\ Term'
Term' \rightarrow {} * Factor\ Term'\,|\,\epsilon
Factor \rightarrow (Expr)\,|\,Broj

Pogledajte još[уреди]

Beleške[уреди]

  1. ^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
  2. ^ Removing Left Recursion from Context-Free Grammars, Robert C. Moore, Microsoft Research, Redmond, WA, USA