Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

sintaksna analiza-najprostija

[es] :: Art of Programming :: sintaksna analiza-najprostija

Strane: 1 2

[ Pregleda: 6455 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon sintaksna analiza-najprostija19.11.2002. u 17:40 - pre 233 meseci
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]
 
Odgovor na temu

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija19.11.2002. u 17:43 - pre 233 meseci
eeeeeeditor mi malo sjebao drvo al dobro - svi znaju kako treba da izgleda
 
Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com


Profil

icon Re: sintaksna analiza-najprostija20.11.2002. u 04:30 - pre 233 meseci
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.

Prikačeni fajlovi
 
Odgovor na temu

Gojko Vujovic
Amsterdam, NL

Administrator
Član broj: 1
Poruke: 13651



+163 Profil

icon Re: sintaksna analiza-najprostija20.11.2002. u 09:22 - pre 233 meseci
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..
 
Odgovor na temu

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija20.11.2002. u 17:51 - pre 233 meseci
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"?!
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost


+4 Profil

icon Re: sintaksna analiza-najprostija20.11.2002. u 18:40 - pre 233 meseci
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...)
 
Odgovor na temu

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija22.11.2002. u 18:29 - pre 233 meseci
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?
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.dial.InfoSky.Net

Sajt: localhost


+4 Profil

icon Re: sintaksna analiza-najprostija23.11.2002. u 00:06 - pre 233 meseci
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...
 
Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com


Profil

icon Re: sintaksna analiza-najprostija24.11.2002. u 11:13 - pre 233 meseci
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.
 
Odgovor na temu

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija24.11.2002. u 14:48 - pre 233 meseci
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.
 
Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com


Profil

icon Re: sintaksna analiza-najprostija24.11.2002. u 15:49 - pre 233 meseci
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).
 
Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com


Profil

icon Re: sintaksna analiza-najprostija24.11.2002. u 18:12 - pre 233 meseci
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
 
Odgovor na temu

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija24.11.2002. u 23:34 - pre 233 meseci
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... :)
 
Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com


Profil

icon Re: sintaksna analiza-najprostija25.11.2002. u 05:44 - pre 233 meseci
Š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.
 
Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beotel.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..


+2 Profil

icon Re: sintaksna analiza-najprostija26.11.2002. u 13:00 - pre 233 meseci
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

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

kruzer

Član broj: 919
Poruke: 46
*.panet.co.yu



Profil

icon Re: sintaksna analiza-najprostija11.12.2002. u 18:14 - pre 232 meseci
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.
 
Odgovor na temu

Dejan

Član broj: 989
Poruke: 6
*.neobee.net



Profil

icon Re: sintaksna analiza-najprostija13.12.2002. u 07:46 - pre 232 meseci
Evo ti skripta iz konstrukcije kompajlera na PMF-u u Novom Sadu
http://perun.im.ns.ac.yu/ivanovic/cc/cc.pdf
 
Odgovor na temu

Dejan

Član broj: 989
Poruke: 6
*.neobee.net



Profil

icon Re: sintaksna analiza-najprostija13.12.2002. u 07:54 - pre 232 meseci
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 ]
 
Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.matf.bg.ac.yu

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..


+2 Profil

icon Re: sintaksna analiza-najprostija13.12.2002. u 20:30 - pre 232 meseci
Jedna knjiga od P. D. Terry-a je kompletna dostupna sa net-a.

Probaj gugl sa "terry compilers" i eto zanimljivih rezultata.
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.
 
Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.matf.bg.ac.yu

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..


+2 Profil

icon Re: sintaksna analiza-najprostija14.12.2002. u 00:38 - pre 232 meseci
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
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.
 
Odgovor na temu

[es] :: Art of Programming :: sintaksna analiza-najprostija

Strane: 1 2

[ Pregleda: 6455 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.