[ kruzer @ 19.11.2002. 17:40 ] @
pozdrav svima...
može li neko da mi objasni kako od izraza tipa
x+x*x da napravim drvo
Code:

       +
      / \
     x  *
        /  \
       x   x

dakle, znam dovoljno(barem mislim da znam) o tehnici programiranja potrebno za resavanje ovog problema, ali ne znam da resim logicki deo problema - kako parser uopste formira odgovarajuce drvo?! Koja pravila primenjuje...
ps: na netu sam trazio, ali nisam nasao tutorial koji bi mi na jasan nacin opisao postupak...

hvala svima koji odgovore

[Ovu poruku je menjao Gojko Vujovic dana 20.11.2002. u 11:20 GMT]
[ kruzer @ 19.11.2002. 17:43 ] @
eeeeeeditor mi malo sjebao drvo al dobro - svi znaju kako treba da izgleda
[ Alter Ego @ 20.11.2002. 04:30 ] @
Probaću da ti objasnim na primeru:

izraz je a+b*c

E=>E+E=>a+E=>a+E*E=>a+b*E=>a+b*c
gde je E aritmetički izraz.
I sada od ovoga napraviš stablo:
Code:

            E
          / | \
         /  |  \
       E  +  E
        |      / | \ 
        |     /  |  \
       a    E  *  E
              |       |
              b      c

-------------------------> a+b*c

Stablo se formira na osnovu sledećih pravila:
1. u korenu stabla je uvek startni simbol
2. u čvorovima stabla se uvek nalaze neterminali
3. u listovima stabla se uvek nalaze terminali (ovde su to a, +, b, *, c)
Listovi stabla se čitaju SA LEVA NA DESNO i predstavljaju string terminala (to jest polazni izraz)

Nadam se da ti je jasno ovo što sam napisao.

P.S. U attachmentu je rtf fajl sa istim ovim tekstom, pošto slika nije baš ispala kako treba.

[ Gojko Vujovic @ 20.11.2002. 09:22 ] @
Ja sam pokušavao da sredim ove vaše grafike, ali mi nije baš savršeno ispalo. Uglavnom, možete koristiti [ code ] ubb tagove (pogledajte stranicu Pomoć), pa forum neće "jesti" razmake. Ali onda morate stablo "nacrtati" u nekom editoru sa fiksiranom veličinom slova, pa isti kod paste-ovati ovde unutar code bloka. To zato što browser pri pisanju poruka koristi variable font width..
[ kruzer @ 20.11.2002. 17:51 ] @
da te pitam...
kako on zna u drugom koraku da je E=>E+E ?!!? jel procita ceo izraz ili sta?! ne razumem...sta recimo da ima 5 pluseva?! koji bi odabrao da bude
"prvi"?!
[ -zombie- @ 20.11.2002. 18:40 ] @
pa, otprilike da.

napravish listu operanada, po vaznosti, ali pocnes od "najmanje vaznih".

e sad, ako imash u jednom izrazu vise operanada iste vaznosti (ne mora cetiri plusa, moze plus-minu-plus-minus) njih radish sa leva na desno..

primer liste (tablice) operanada imash recimo na http://php.net/operators
(naravno ne morash sve da implementirash...)
[ kruzer @ 22.11.2002. 18:29 ] @
Da li to onda znaci da moram vise puta da prolazim kroz izraz(string)?
recimo
1. put - procita sve operatore(u izrazu) i napravi listu pocevsi od najmanje vaznih (verovatno bi trebalo da sacuva i pozicije istih?!)
2. put - pravi stablo koristeci listu operatora i izraz...

jel sam blizu resenja?
[ -zombie- @ 23.11.2002. 00:06 ] @
pa, ne bash.

ovo se radi u onoliko koraka koliko ima operacija.

recimo izraz "3+5-9*4/5+8"

u prvom koraku, imash tri operatora iste najnize tezine (dva plusa i minus).

prvo naidjesh na prvi +, i pozovesh rekurzivno funkciju koja gradi stablo sa stringom koji je levo od plusa "3" i stringom koji je desno od plusa "5-9*4/5+8".

ovaj poziv funkcije sa "3" samo pravi prost nod i izlazi.

ovaj drugi poziv nailazi na minus, i opet rekurzivno poziva za string "5" i za string "9*4/5+8".

ovaj poziv sa pet odamah zavrsava, a ovaj drugi nalazi + i poziva dva puta sa "9*4/5" i "8".

sada, * i / su iste vaznosti, pa se oni pozivaju sa desna na levo...

mrzi me da crtam stablo, ali bi trebalo da razumesh...
[ Alter Ego @ 24.11.2002. 11:13 ] @
Citat:
kako on zna u drugom koraku da je E=>E+E ?!!? jel procita ceo izraz ili sta?! ne razumem...sta recimo da ima 5 pluseva?! koji bi odabrao da bude "prvi"?!

Pa, to i jeste problem-višeznačnost gramatike. Za jedan isti izraz može da se dobije više različitih stabala! Zato se vodi računa o asocijativnosti operatora ili se koriste zagrade, a treće rešenje je da se u samu gramatiku ugrade ova pravila. Na primer, umesto jednog neterminala E (izraz), uvede se više njih: T (sabirak), F (množilac)…
Onda se višeznačna gramatika:
E->E+E|E-E|E*E|E/E…
prevodi u:
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)
F->id
itd.
Primer generisanja parsnog stabla za ovu gramatiku:
Code:

a+b*c
          E
               /  |  \
              E  +  T
              |      / | \
              T     T *  T
              |     |      |
              F     F     c
              |     | 
              a b

Implementacija ovoga je već komplikovanija i postoji veći broj pristupa i odgovarajućih algoritama. Jedan od najprostijih algoritama se bazira na rekurziji.
[ kruzer @ 24.11.2002. 14:48 ] @
znam, to se zove rekurzivni spust(top - down parsing)...
ali nisam uspeo da ga implementiram... moze li neko da mi pomogne?
evo ovo mi nije jasno:
1. kako bi trebalo da izgleda prototip funkcije(u Cu ili pascalu)
2. da li ta rekurzivna funcija procita samo jedanput string(izraz) ili dvaput ili vise puta(ovo mi i dalje nije jasno)
3. link za neki pocetnicki tutorial ili knjiga.
[ Alter Ego @ 24.11.2002. 15:49 ] @
Jedino što mi pada na pamet da ti preporučim je skripta iz koje sam spremao ispit. Zove se "Programski jezici i prevodioci-folije sa predavanja", dr. Marko Vušković. Od ovoga što tebe zanima, tamo su date teorijske osnove i dosta algoritama (paskal-olika sintaksa).
[ Alter Ego @ 24.11.2002. 18:12 ] @
Ne bi bilo loše da kažeš šta ti konkretno treba. Ovako ne mogu puno da ti pomognem. Ako ti treba samo izračunavanje izraza, to nije neki problem. Tu se postavlja pitanje u kojoj notaciji je izraz. Ako je u infiksnoj (prirodnoj) notaciji, problem je to što MORA više puta da se prođe kroz izraz. To se izbegava tako što se koristi neka druga notacija (postfiks ili prefiks). Algoritam za ove notacije je vrlo jednostavan. Možeš da napraviš da program prihvata izraz u infiks notaciji i da zatim interno prevodi u prefiks. Taj pristup se uostalom primenjuje kod većine prevodilaca.
Ako želiš, mogu da ti dam ove algoritme, pa ti probaj da ih implementiraš. Ako ne budeš uspeo, pošalji ono što si uradio pa ćemo nešto da iskombinujemo
[ kruzer @ 24.11.2002. 23:34 ] @
Hoću da namestim program koji izračunava upisani izraz... znači uneseš:
50*4-8/8
i on ti izbaci 199.

e sad hteo sam da uradim sa stablom, ali mi ne uspeva, pa sam odlučio da odradim sa stekom....
ako ikada ovo odradim(sa stekom) postovaću ovde da se drugi ne bi mučili ko ja...
zato se nadam da će ako neko ima svoju verziju rešenja ovog problema(stablo, ili šta god), postovati takođe...

alter ego jaaaaavi se... :)
[ Alter Ego @ 25.11.2002. 05:44 ] @
Što odmah ne kažeš. Može sa stekom da se uradi. Kao što rekoh, daću ti algoritam, a za implementaciju ćeš morati da se pomučiš. Kad negde zapne, pogledaćemo zajedno šta je u pitanju.
Dakle evo algoritma za računanje izraza u posfix obliku:

Code:

EVAL-EXP(postfix)
INIT_STACK(S, n)
while(not_end_of postfix) do
   x = INPUT(postfix)
   if(x = operand) then
      PUSH(S, x)
   else if (x = un_op) then
             oprnd = POP(S)
             rez = x oprnd
             PUSH(S, rez)
          else if (x = bin_op) then
                   oprnd2 = POP(S)
         oprnd1 = POP(S)
                   rez = oprnd1xoprnd2
         PUSH(S, rez)
          end if
end_while
rez = POP(S)
if(STACK_EMPTY(S)) then
   return rez
else 
   ERROR(Nepravilan izraz)
end_if

S je stek
posfix je argument procedure i predstavlja ulazni izraz
Dovoljan je jedan prolaz kroz izraz.
Algoritam prvo stavlja sve operande na stek (pošto u ovoj notaciji prvo idu operandi), a zatim kada naiđe na operatore, ispituje da li je unarni ili binarni operator. Uzima jedan ili dva operanda sa steka, u zavisnosti da li je unarni ili binarni operator, i vraća rezultat na stek.

Za početak probaj ovo da implementiraš, a posle ćemo preći na drugi (teži) deo problema.
[ tOwk @ 26.11.2002. 13:00 ] @
Približna specifikacija:
Code:
cifra ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
broj  ::= cifra+
izraz ::= broj
izraz ::= izraz "+" izraz |
      izraz "-" izraz |
      izraz "/" izraz |
      izraz "*" izraz |
      "(" izraz ")"


1. Izvršiš ,,tokenizaciju'' izraza "50*4-8/8" i dobiješ:
Code:
50[iz] *[op] 4[iz] -[op] 8[iz] /[op] 8[iz]


Ovde ako si imao zagrade, od toga ćeš praviti jedan izraz.

2. Nađeš sve *[op] i /[op] (prioritetne operacije), i sa njima susednim tokenima kategorije [iz] napraviš stabla, gde rekurzivno obrađuješ svaki izraz ([iz])

3. Isto za ostale operacije (+[op] i -[op])


Neoptimizovan ,,pseudo-srpski'' kod:
Code:

ListaTokena=tokenize("50*4-8/8")

praviStablo(ListaTokena):
   za svako i, ListaTokena(i)==*[op] ili ListaTokena(i)==/[op]:
    Prethodnik = ListaTokena(i-1)
    Sledbenik  = ListaTokena(i+1)
    Izraz = praviStablo(Prethodnik), ListaTokena(i), praviStablo(Sledbenik)
    Zameni(ListaTokena(i-1,i,i+1) sa Izraz)    # Izbaci prethodnika i sledbenika, a na mesto i stavi Izraz
   za operacije +[op] i -[op], radi isto kao gore  # razdvojeno zbog prioriteta

   praviStablo(ListaTokena) # dok god ListaTokena ne postane jedan Izraz,
                            # ponavljaj i ponavljaj


Rekurzija je gore potrebna samo za unete složene izraze (one u zagradama); ako ne dozvoliš zagrade, moglo bi i bez rekurzije.

Primeri kako radi algoritam (po jedna iteracija u jednom redu) za dva izraza:
Code:

10/5/6*7 
-> 10[iz] /[op] 5[iz] /[op] 6[iz] *[op] 7[iz]
-> (10/5)[iz] /[op] 6[iz] *[op] 7[iz]
-> ((10/5)/6)[iz] *[op] 7[iz]
-> (((10/5)/6)*7)[iz]

50*4-8/8 
-> 50[iz] *[op] 4[iz] -[op] 8[iz] /[op] 8[iz]
-> (50*4)[iz] -[op] (8/8)[iz]
-> ((50*4)-(8/8))[iz]


Što se praktičnih stvari tiče, ima tu još poneka začkoljica (npr. provera da li su Prethodnik i Sledbenik zaista kategorije [iz]; ispunjavanje uslova da je u ListaTokena moguće smestiti i stablo kakvo je vraćeno u Izraz, popravka vrednosti i, itd.), ali neću valjda sve da ja ispišem u ovom lako razumljivom pseudo-jeziku.

Naravno, drugi način ti je da izvršiš ,,normalizaciju'' izraza: umetneš zagrade tamo gde su neophodne, a onda je veoma lako napraviti stablo. Postupak je sličan kao i gore, samo ne praviš stablo odmah, već umećeš zagrade.

Tako za izraz "50*4-8/8" potražiš sve * i /, prve susedne izraze uokviriš zagradama, i dobiješ "(50*4)-(8/8)". Ponoviš isto za + i -, i eto ti ga "((50*4)-(8/8))". A koliko je dalje trivijalno, valjda ne treba ni da pričam.

Toliko
[ kruzer @ 11.12.2002. 18:14 ] @
Citat:
Alter Ego:
Jedino što mi pada na pamet da ti preporučim je skripta iz koje sam spremao ispit. Zove se "Programski jezici i prevodioci-folije sa predavanja", dr. Marko Vušković. Od ovoga što tebe zanima, tamo su date teorijske osnove i dosta algoritama (paskal-olika sintaksa).


Jel mozes ovo da okacis negde ako je u el. formi?

btw: Hvala svima, puno ste mi pomogli i uspesno sam odradio seminarski iz gorenavedenog ispita...
Sada mi je ostala jos teorija, pa mi trebaju linkovi ka teoriji o kompajlerima ili makar nazivi knjiga koje postoje u Narodnoj Biblioteci u Bgu a ticu se ove oblasti(nisam valjda jedini koji ide tamo)...

pozdrav.
[ Dejan @ 13.12.2002. 07:46 ] @
Evo ti skripta iz konstrukcije kompajlera na PMF-u u Novom Sadu
http://perun.im.ns.ac.yu/ivanovic/cc/cc.pdf
[ Dejan @ 13.12.2002. 07:54 ] @
Na adresi
http://lampwww.epfl.ch/~michelou/links/compiler/compiler.pdf
imas jedan tutorijal koji je prilicno dobar.

[ na zalost, forum ne moze da prikaze adresu kako treba, prvi deo je lampwww.epfl.ch ]
[ tOwk @ 13.12.2002. 20:30 ] @
Jedna knjiga od P. D. Terry-a je kompletna dostupna sa net-a.

Probaj gugl sa "terry compilers" i eto zanimljivih rezultata.
[ tOwk @ 14.12.2002. 00:38 ] @
A svakako i
ftp://ftp.cs.vu.nl/pub/dick/PTAPG/PTAPG.txt

Parsing Techniques - A Practical Guide

U istom direktorijumu se nalazi i knjiga u gzipovanom PostScript zapisu

I ovo bi trebalo da bude dosta ,,praktičan vodič'' -- znači ne baš rigorozan kako bi možda bilo traženo ponegde
[ dRock9 @ 14.12.2002. 16:23 ] @
Iskreno, najbolja knjiga koju sam video o kompajlerima je
Compilers - Principles, Tehnics & Tools

Knjiga je dosta stara, ali je odlicna. Jedini problem, koliko znam, je da ne postoji verzija na srpskom i tesko se nalazi kod nas (mozda neka bolja biblioteka, ili ako imas nekog u americi mozes da je narucis sa amazon-a).

poz
[ Goran Rakić @ 14.12.2002. 16:38 ] @
Ili uzmeš VIsa-u Virtuon i nomralno poručiš knjigu sa amazon.co.uk, kao svuda u svetu
[ tOwk @ 15.12.2002. 01:38 ] @
Citat:
...kao svuda u svetu


Da, kao svuda... U Mongoliji, Pakistanu, Iraku, Obali slonovače, Etiopiji, Argentini i brojnim drugim državama... Zaista, onih 30 država u kojima je to ,,normalno'' je zaista svuda... A ipak ne verujem da smo mi u tih 30...

Stoga, ili državne biblioteke, ili besplatno ,,svlačenje''...

A ako već ne veruješ da postoji dovoljno besplatne literature, uzmi izvorni kod za bison, yacc i eto ti za čitanje!!!

Naravno, odrasli smo ipak uz papirna izdanja, a zasad je, ukoliko ne možeš da štampaš ponešto, najbolje da posetiš biblioteku. I Univerzitetska biblioteka u Beogradu bi mogla imati ponešto.
[ dRock9 @ 15.12.2002. 13:14 ] @
Posto zbog ogranicenja velicine attachment-a uz post, ne mogu da posaljem tutorial, evo adrese sa koje moze da se skine:
http://custom.lab.unb.br/pub/plan/c/iecc/file/crenshaw-txt.zip

Dokument je napisao Jack Crenshaw, zove se Let's build a compiler.

Ne preterano opsirno, ali fino za pocetak - naravno in English :)

tOwk: 'De si Danilo, nema te 1024 godine.

Pozdrav svima !