[nastava:2004] - Re:  prevodioci - 4. domaci by v.i@verat.net

> 	Verovatno si mislio na 3. zadatak.
> Slican zadatka je bio 2001/02.

Pedja,

U pravu si, mislio sam na 3. zadatak tj. onaj po modulu 3 (cetvrti po redu
od 5), i hvala ti na trudu, ali ovo sto si poslao nazalost ne resava
problem na koji sam naisao.

"Mala" razlika u odnosu na stari zadatak je sto su operatori u novom
zadatku INFIKSNI umesto prefiksni, sto onemogucuje deterministicko
top-down parsiranje jer selekcioni skupovi za smene ove gramatike ne mogu
biti disjunktni.

Ilustracija:

prefiksni operatori, (samo + i * zbog jednostavnosti)

1.        <S>  ¨ id = <E>
2.        <E>  ¨ + <E> <T>
3.        <E>  ¨ <T>
4.        <T>  ¨ * <T> <P>
5.        <T>  ¨ <P>
6.        <P>  ¨ id

ovde nema problema jer smene za <E> i <T> imaju razlicite sel skupove. A sad
ista prica, samo infiksni operatori

1.        <S>  ¨ id = <E>
2.        <E>  ¨ <E> + <T>
3.        <E>  ¨ <T>
4.        <T>  ¨ <T> * <P>
5.        <T>  ¨ <P>
6.        <P>  ¨ id

Ocigledna je direktna leva rekurzija u smenama 2 i 4 i problem sa
selekcionim skupovima. Pokusao sam i transformaciju leve rekurzije, ali
avaj... to nije resilo problem selekcionih skupova - da to moze tako, onda
bi sve gramatike bile LL(1), zar ne?


Mnoge varijacije na ovu temu postoje u zbirci, npr. bottom-up parser za
ovakvu gramatiku (koji naravno nemoze da se napravi po principu
rekurzivnog spusta) ili gramatika za prefiksne operatore koju je lako
parsirati na ovaj nacin...

I dalje sam u dilemi, mozda je trik u tome da se dodje do ovog "uvida" i
da se onda odustane od rekurzivnog spusta i predje na yacc/bison koji rade
po bottom-up sistemu?

Svejedno, kao i prosli put, komentari i ideje su dobro dosli

Pozdrav