[ri4pp:2006] - Primer sa vezbi by "Bojic Petar" <rapecafa@verat.net>

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