[nastava:2003] - Re: prevodioci... po ko zna koji put... by "Nikola Novakovic" <houraboom@ptt.yu>

----- Original Message ----- 
From: "Bratislav Milic" <zverko@eunet.yu>
To: <nastava@titan.etf.bg.ac.yu>
Sent: Sunday, December 14, 2003 9:41 PM
Subject: [nastava] prevodioci... po ko zna koji put...


> Ovde su neke stvari koje mi nisu jasne... pa ako ima neka dobra dusa sto 
> moze da pomogne...
> 
> Pitanje:
>  Ako postoji dvosmislenost, kako rešiti taj problem bez transformacije 
> gramatike?
> 
> odgovor koji je ponudjen je da to treba uvodjenjem prvenstva ili endif 
> operacije (sto je po meni skroz pogresno - to je izvuceno iz nekog 
> primera koji je dat na predavanjima, ali to sto cemo uvesti nesto od ta 
> dva definitivno znaci da smo transformisali gramatiku)
> Ja mislim da treba pokusati drugacijom metodom parsiranja (recimo ako je 
> leva dvosmislenost, da se proba nekim bottom-up metodom obrade)

Ja sam ovo razumeo ovako:
Ako uvedemo nov neterminal (npr ENDIF ili neki drugi), definitivno smo transformisali gramatiku, znaci to nije to. 
Međutim kad se kaže uvođenje prioriteta, mislim da se cilja na sledeće i da to rešava problem:
Neka je gramatika recimo
    1. <E> -> <E> + <E>
    2. <E> -> <E> * <E>
    3. <E> -> a
Ova gramatika je dvosmislena, jer npr. za sekvencu a+a+a postoje dva stabla izvođenja.
Samim tim, u odgovarajućim ulazima SLR(1) parsera imaćemo konflikte SHIFT-REDUCE.
U zavisnosti od toga da li primenimo SHIFT ili REDUCE, izraz a+a+a tumačimo ili kao (a+a)+a ili kao a+(a+a). Još gore, kad imamo
a+a*a ne znamo da li da to tumačimo kao (a+a)*a ili a+(a*a). 
Zato usvajamo prioritete operacija:
    a) sabiranje se vrši s leva na desno, tj. a+a+a se tumači kao (a+a)+a
    b) množenje ima prioritet nad sabiranjem, tj. a+a*a tumačimo kao a+(a*a), a a*a+a kao (a*a)+a
Kad usvojimo ove prioritete, moći ćemo jednoznačno da konstruišemo SLR(1) parser za ovu dvosmislenu gramatiku, i to 
bez njene transformacije. 
Drugi primer: kako tumačiti  izraz if X then if X then S else S ? U principu, else može da se upari i sa prvim i sa drugim if i 
zato je ova gramatika dvosmislena. Problem se rešava usvajanjem konvencije da se else uparuje uvek sa najbližim if (tj. najbliže if imaće prioritet pri
uparivanju), i gramatiku možemo parsirati. Drugi način je uvođenjem ključne reči endif, ali to je već transformacija gramatike. 

> Pitanje:
> Diskutovati analizu prefiksa.

> Pitanje:
> Kako paket SymbolTablePackage možemo da realizujemo kao jedinstvenu 
> tabelu simbola, a šta treba uraditi da bi ovaj paket postao tip?

Ova dva pitanja ni meni nisu jasna, pogotovo analiza prefiksa, zašto se vrši... Ne znam

Nikola