[ri4pp:2006] - Re: Primer sa vezbi by "Jovan Popovic" <jovan@etf.bg.ac.yu>

Eliminisanje leve rekurzije je bolje objasnjeno u fajlu "sintaksna analiza
1" - tamo imate i jedan kompletan primer.

Za ovaj primer, desne strane u smenama 2  i 3 se ubacuju umesto
neterminala <S> u prvoj smeni a drugi deo desne strane smene 1 (u ovom
slucaju terminal a) se zamenjuje novim neterminalom <S'>. Ubacuju se smene
za <S'> u kome smena pocinje drugim delom smene 1 (terminal a), a iza
njega se postavlja desna rekurzija.
Resenje da datu gramatiku je:

1. <S> -> <A>b <S'>
2. <S> -> c<D> <S'>
3. <S'> -> a<S'>

Kao sto vidite leva rekurzija je zamenjena desnom.

Dodao sam slican zadatak u fajl TopDown.zip tako da mozete pogledati
resenje ili tu ili u fajlu "Sintaksna analiza 1"

Pozdrav,
Jovan



> Molim asistenta da prodiskutuje sledece razmatranje:
> Na vezbama od 21.11.2005. (pri kraju 2. casa) bio je primer sledece
> gramatike:
> 1. <S> -> <S>a
> 2. <S> -> <A>b
> 3. <S> -> c<D>
> U prvoj smeni se javlja leva rekurzija koja moze da prouzrokuje probleme u
> parserima, pa ste rekli da se ona moze ukloniti zamenom neterminala <S> na
> desnoj strani 1. smene desnim stranama smena 2. i 3. Medjutim, moguce da
> se onda ne dobija ekvivalentna gramatika, sto se moze videti na nesto
> kracem primeru u kojem se moze primeniti ista zamena:
> 1. <S> -> <S>a
> 2. <S> -> <A>b
> 3. <A> -> a
>
> Posle uklanjanja leve rekurzije zamenom 2. smene u prvu,  dobija se
> gramatika
> <S> -> <A>ba
> <S> -> <A>b
> <A> -> a
> koja nije ekvivalentna gramatici pre zamene, jer sada <S> moze biti samo
> "aba" ili "ab" tj. uopste vise nema rekurzije.
>
> Pozdrav
> Petar
>
>
>