sintaksna analiza-najprostija

pozdrav svima...
može li neko da mi objasni kako od izraza tipa
x+x*x da napravim drvo

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]

eeeeeeditor mi malo sjebao drvo al dobro - svi znaju kako treba da izgleda

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:

-------------------------> 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.

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..

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"?!

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...)

Potpis

blogče :: unescaped beta
^{» go-paste extenzija
　 » reč dana: backup
　 » bočne koalicije}

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?

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...

Potpis

blogče :: unescaped beta
^{» go-paste extenzija
　 » reč dana: backup
　 » bočne koalicije}

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:

Implementacija ovoga je već komplikovanija i postoji veći broj pristupa i odgovarajućih algoritama. Jedan od najprostijih algoritama se bazira na rekurziji.

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.

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).

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

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... :)

Š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:


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.

Približna specifikacija:


1. Izvršiš ,,tokenizaciju'' izraza "50*4-8/8" i dobiješ:


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:


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:


Š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

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

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.

Evo ti skripta iz konstrukcije kompajlera na PMF-u u Novom Sadu
http://perun.im.ns.ac.yu/ivanovic/cc/cc.pdf

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 ]

Jedna knjiga od P. D. Terry-a je kompletna dostupna sa net-a.

Probaj gugl sa "terry compilers" i eto zanimljivih rezultata.

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

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

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.