Prije nego se prijede na opis Pascala i programiranja, u ovom se dijelu uvode osnovni pojmovi o kompjuterima, jezicima za programiranje, algoritmima, rekurzijama, prevoditeljima i programiranju.
Izucavanje Pascala i programiranja zahtijeva strog, formalan pristup. Takoder podrazumijeva solidno predznanje iz matematike, posebno matematicke logike i teorije skupova. Zbog toga ovo poglavlje sadrži kratak pregled teorije skupova i matematicke logike.
Skup intuitivno shvacamo kao kolekciju elemenata (ili clanova) koji posjeduju izvjesna svojstva. Na primjer, skup dana u tjednu sacinjavaju sljedeci elementi: ponedjeljak, utorak, srijeda, cetvrtak, petak, subota, nedjelja.
Ako je a element skupa S, piše se a ? S i cita "a je element
skupa S", a ako nije, piše se a ? S i cita "a nije element skupa
S". Na primjer, petak ? S, svibanj ? S, gdje je S skup dana u
tjednu.
Elementi skupa mogu biti atomi, koji predstavljaju sami sebe, ili
neki drugi skupovi. Prikazuje se samo jedno pojavljivanje nekog
elementa u skupu. Redoslijed pisanja elemenata skupa nije bitan.
Primjeri:
{a, b, c} = {a, c, b} = {b, a, c} = {b, c, a} = {c, a, b} =
{c, b, a}
{a, a} = {a}
{a, {b}} ? {a, b}
{a} ? {{a}}
Definira se i prazan skup, skup koji ne sadrži nijedan element. Oznacuje se sa Ř.
Do pojma podskupa dolazi se promatranjem dijela nekog skupa. Kaže se da je B podskup skupa A ako je svaki element x iz B ujedno i element skupa A. U tom slucaju piše se
B ? ANa primjer, skup
P = {ponedjeljak, srijeda, petak}
podskup je skupa S svih dana tjedna, tj. P ?S. Piše se B ? A i kaže da je B pravi podskup skupa A ako u A postoji najmanje jedan element koji nije u B. Ako se želi istaknuti da B, u krajnjem slucaju, može biti cijeli A, piše se B ? A.
Skup S smatra se zadanim ako je nedvosmisleno receno, objašnjeno ili specificirano, što su elementi tog skupa. Zadati skup S znaci dati ogranicenje, propis ili svojstvo kojim su u potpunosti odredeni svi elementi skupa. U nekim se slucajevima elementi skupa jednostavno navedu izmedu viticastih zagrada. Na primjer
S = { a1 ..., an}
Cesto je nemoguce nabrojiti sve elemente skupa koji se mogu zadati nekim propisom, kao na primjer kada se govori o skupu svih parnih brojeva. Premda je taj skup odreden, nije moguce navesti sve njegove elemente, pa se piše
S = {2, 4, 6, 8, 10, 12, ...}Tockice naznacuju sve ostale elemente iz S koji se eventualno ne mogu navesti. U takvim je slucajevima prikladno skup zadati na sljedeci nacin:
S = {x | P(x)}
što se cita: "Skup S sadrži one elemente x za koje je ispunjeno svojstvo (ili predikat) P(x)". Na primjer, ako je N skup prirodnih brojeva, može se napisati
S = {x | "x je paran"} ili S = {x | x = 2n,
n?N}
Postoji nekoliko operacija sa skupovima koje se mogu koristiti pri izgradivanju novih skupova. Neka su A i B skupovi. Unija od A i B, napisana kao A ? B, je skup koji sadrži sve elemente skupa A zajedno sa svim elementima skupa B:
A ? B = {x | x?A ili x?B}
Presjek skupova A i B, A ? B, skup je elemenata sadržanih i u A i u B:
A n B = {x | x?A i x?B}
Razlika skupova A i B, A \ B, skup je elemenata koji pripadaju skupu A, a nisu u B:
A \B = {x | x?A i x?B}
Direktni ili Kartezijev produkt dvaju skupova A i B je skup:
A x B = {(a, b) | a?A, b?B}
Element tako nastalog skupa, (a, b), naziva se uredeni par. Na primjer, ako je A = {a, b}, B = {0, 1}, Kartezijev produkt A x B jest skup
{(a, 0), (a, 1), (b, 0), (b, 1)}
Prva komponenta bilo kojeg para mora biti iz A, druga iz B. Zbog toga (0, a) nije element skupa A x B.
Relacija je bilo koji podskup Kartezijevog produkta skupova. Na primjer, ako je N = {1, 2}, M = {0, 1, 2, 3, 4, 5}, relacija R, R?NxM, može biti
R = {(1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2)}
Primijetiti da relacija R u ovom primjeru oznacuje svojstvo parova (x, y), x?N, y?M, da im je zbroj manji ili jednak 4. Isto svojstvo može se napisati kao xRy što se cita "x je u relaciji R sa y" ili "izmedu x i y postoji relacija R".
Funkcija (preslikavanje, transformacija) f iz skupa A u skup B jest relacija iz A u B takva da, ako su (a, b) i (a, c) u f, vrijedi b = c.
Ako je (a, b) u f cesto se piše b = f(a). Kaže se da je f(a) definirano ako postoji b u B tako da je (a, b) u f. Ako je f(a) definirano za sve a iz A, kaže se da je f totalno preslikavanje sa A u B. Ako to nije ispunjeno, f je parcijalno preslikavanje iz A u B. U oba slucaja piše se
f: A ? B
i kaže da je A domena, a B kodomena funkcije f.
Dobro poznavanje elemenata matematicke logike osnovni je uvjet shvacanja problema programiranja. Ovo podpoglavlje predstavlja kratak repetitorij matematicke logike, s težištem na dijelovima neophodnim za razumijevanje logickih izraza u Pascalu, te primjena u programiranju.
Algebra sudova osnova je drugih dijelova matematicke logike, prijeko potrebna za njihovo razumijevanje. Izgraduje se na isti nacin kao i mnogobrojne matematicke teorije. Za osnovne pojmove uzima se neka klasa objekata, takoder i neka svojstva, odnosi i operacije nad tim objektima. Ti se osnovni pojmovi smatraju polaznim, i za njih nije potrebno dati nikakvu definiciju.
Osnovni pojmovi najcešce se objašnjavaju primjerima. Osnovni objekt kojeg proucava algebra sudova je elementarni sud. Na primjer, elementarni sudovi su:
"Broj 100 djeljiv je s 4"
"Danas je lijepo vrijeme"
"Štef nema djevojku"
"Mjesec je veci od Zemlje"
"17 je prost broj"
Svi elementarni sudovi moraju imati jedno i samo jedno
svojstvo:
"biti istinit" ili "biti lažan"
Na primjer, sud "7 je vece od 5" je istinit, a sud "8 je prost broj" nije istinit. U daljnjem tekstu elementarne sudove oznacivat cemo malim slovima a, b, c, itd.
Za primjene u programiranju posebno su važni elementarni sudovi nazvani relacijski izrazi. Opcenito relacijski izraz sadrži dva izraza istog tipa (na primjer, dva aritmeticka izraza) izmedu kojih je napisana jedna od relacija:
= jednako
? razlicito
< manje
= manje ili jednako
> vece
= vece ili jednako
Na primjer, relacijski izraz (elementarni sud) "9 > 5" citat cemo "9 je vece od 5".
Od elementarnih sudova moguce je, uz pomoc nekoliko logickih operacija, graditi složene sudove. Jasno je da ce i složeni sud biti istinit ili lažan. U daljnjem tekstu govorit ce se o njegovoj "vrijednosti istinitosti", koja ce biti oznacena sa "T" za istinito, i sa "F" za lažno.
Vrijednost istinitosti složenog suda ovisi o istinitosti sudova od kojih je složeni sud izgraden.
Postoji nekoliko unarnih i binarnih logickih operacija (logickih veznika ili konektiva). Ovdje su opisane samo one osnovne, negacija, kao unarna logicka operacija, te binarne logicke operacije:
• konjunkcija
• disjunkcija
• implikacija
Negacija je unarna logicka operacija i ujedno najjednostavnija
operacija algebre sudova. U govornom jeziku odgovara joj približno
rijec "ne". Ako negaciju oznacimo sa "?", njezino djelovanje na sud
"a" dano je u sljedecoj tablici:
a ¬a
F T
T F
Ako je "a" neki sud, na primjer "5 je djelitelj od 7", ¬a novi je sud "5 nije djelitelj od 7". Sud ¬a cita se "ne a" ili "non a".
Ako su "a" i "b" sudovi, onda je a?b novi složeni sud ili konjunkcija sudova "a" i "b". Znak "?" cita se "i" ili "et". Djelovanje operacije konjunkcije definirano je sljedecom tablicom:
a b a?b
F F F
F T F
T F F
T T T
Operacija konjunkcije po smislu približno odgovara vezniku "i". Na primjer, elementarni sudovi "6 je djeljivo sa 3", "10 je vece od 5" istiniti su, pa je istinita i njihova konjunkcija "6 je djeljivo sa 3 i 10 je vece od 5". Medutim, elementarni sudovi "3 je djeljivo sa 7" i "3 je vece od 7" lažni su, pa je lažan i složeni sud "3 je djeljivo sa 7 i 3 je vece od 7".
Operacija disjunkcije najcešce se oznacuje sa "?" i cita "ili". Treba napomenuti da veznik "ili" u mnogim jezicima ima dva razlicita znacenja. U jednom slucaju radi se o tzv. "iskljucnom", u drugom o "neiskljucnom" vezniku "ili". Razlika medu njima pokazana je u sljedecem primjeru: Ako su "a" i "b" dva lažna suda, lažan je i složeni sud a?b. Ako je "a" istinito, a "b" lažno, ili "a" lažno, a "b" istinito, istinit je i složeni sud a?b. Što je, medutim, s vrijednošcu istinitosti suda a?b ako su i "a" i "b" istiniti? U prvom slucaju, ako se složena izjava smatra istinitom, govori se u neiskljucnoj, u drugom o iskljucnoj disjunkciji.
U matematickoj logici operacija disjunkcije odgovara neiskljucnom vezniku "ili". Iz prethodnih razmatranja slijedi definicija: disjunkcija sudova "a" i "b", napisana kao a?b, složen je sud koji je lažan onda i samo onda ako su i "a" i "b" lažni. Iz te definicije slijedi tablica:
a b a?b
F F F
F T T
T F T
T T T
Implikacija se obicno oznacuje sa "?" i definira na sljedeci nacin: ako su "a" i "b" dva suda, a?b (cita se "a implicira b") složeni je sud koji je istinit uvijek osim ako je "a" istinito, a "b" lažno. Tablica istinitosti implikacije dana je sa:
a b a?b
F F T
F T T
T F F
T T T
Operacija implikacije odgovara, u odredenom smislu, veznicima "ako..., onda...". Sud "ako je a, onda je b" može se shvatiti kao ¬a?b. U vecini slucajeva pogodnije je sud a?b zamijeniti sudom ¬(a?¬b). Takvo znacenje implikacije istice cinjenicu da pri istinitosti a?b ne može nastupiti slucaj da je "a" istinito, a "b" lažno. To odgovara važnom svojstvu implikacije da istina ne može implicirati neistinu. Na kraju treba napomenuti da se sud a?b ne podudara uvijek po smislu sa sudom "ako je a, onda je b". Otuda, da bi se izbjegli eventualni nesporazumi, složeni sud a?b bolje citati "a implicira b".
Uporabom navedenih logickih operacija i uvodenjem zagrada mogu se, kao i u algebri, graditi razni složeni sudovi ili logicki izrazi. Na primjer:
(a?b)?c (a?b)?(c?d) ¬a?(b?c)
Logicke varijable koje se pojavljuju u izrazima mogu biti elementarni sudovi, na primjer "x<6", ili nosioci logickih vrijednosti dobivenih kao rezultat prethodnog izracunavanja (nekog logickog izraza). Takoder se može pojaviti logicka konstanta "F", cija je vrijednost istinitosti uvijek jednaka "laž", i logicka konstanta "T" cija je vrijednost istinitosti uvijek jednaka "istina".
Logicki izrazi koji sadrže samo operacije negacije, konjunkcije i disjunkcije, te zagrade, nazivaju se Booleove formule. Za Booleove formule vrijede sljedeci zakoni:
1) Zakon komutacije:
(x?y) = (y?x)
(x?y) = (y?x)
2) Zakon asocijacije:
(x ? (y?z)) = ((x?y) ? z)
(x ? (y?z)) = ((x?y) ? z)
3) Zakon idempotentnosti:
(x?x)=x
(x?x)=x
4) Zakon distribucije:
(x ? (y?z)) = ((x?y) ? (x?z)) (x ? (y?z)) ? ((x?y) ? (x?z))
5) De Morganov zakon:
¬(x?y) = (¬x ? ¬y)
¬(x?y) = (¬x ? ¬y)
6) Zakon dvostruke negacije:
¬¬x = x
Posebno je cesta uporaba de Morganovog zakona u programiranju.
Kompjuter je stroj složene tehnicke strukture, s brojem komponenata ovisnim o njegovoj namjeni. Osnovne komponente od kojih se sastoji svaki suvremeni kompjuter, što je pojednostavljeno prikazano na sljedecoj slici, jesu:
Centralni procesor izvršava upravljacke zadatke i operacije s podacima. Sastoji se od:
• upravljacke jedinice
• aritmeticko-logicke jedinice
Upravljacka ili kontrolna jedinica nadgleda i uskladuje funkcioniranje svih komponenti i kompjutera kao cjeline. Pri izvršenju instrukcija programa ona ukljucuje u rad ostale jedinice i uredaje, u skladu s izraženim zahtjevima.
Aritmeticko-logicka jedinica izvršava osnovne
aritmeticke i logicke operacije s podacima: zbrajanje, oduzimanje,
množenje, dijeljenje i usporedbu vrijednosti. Složenije operacije
izražene u programu izvršavaju se prethodnim razlaganjem u fazi
prevodenja programa na skup osnovnih aritmetickih i logickih
operacija.
Centralni procesor sadrži još i nekoliko memorijskih registara
neophodnih za smještaj podataka s kojima procesor trenutno
operira.
U memoriju se pohranjuju podaci, instrukcije i tekstovi programa za tekucu ili buducu uporabu. Kompjuteri imaju dvije vrste memorija: radnu i sekundarnu.
Radna (glavna ili primarna) memorija dio je centralnog dijela kompjutera i služi za pohranjivanje programskih instrukcija i podataka za tekucu uporabu.
Glede tehnicke izvedbe radna se memorija sastoji od velikog broja celija - bistabilnih elektronickih sklopova, cija je karakteristika da mogu biti u jednom od dva moguca stanja ( +/- ili ima/nema, na primjer), koja oznacavamo brojevima 0 i 1. Prema tome, svaka celija predstavlja binarnu znamenku koju nazivamo bit (od rijeci binary digit - binarna znamenka).
Bitovi se, radi predocavanja ostalih znamenki, slova i drugih znakova, grupiraju u bajtove (byte - bajt). Jedan bajt sastoji se najcešce od 8 bitova, koji u kombinacijama nula i jedinica mogu predstaviti 28 (256) znakova.
Bajtovima se obicno izražava kapacitet memorije i to kao
potencija broja 2. Naprimjer M = 214 bajtova, ili u obliku M = N x
2l0. Jedinica mjere memorijskog kapaciteta 1 KB (1 kilobajt),
jednaka je upravo 210, odnosno 1024 bajtova.
Bitna karakteristika radne memorije jest velika brzina pristupa svakoj adresi i velika brzina pisanja i citanja podataka i instrukcija. Osim toga, svi podaci s kojima program radi pohranjeni su u radnoj memoriji i gube se nepovratno okoncanjem programa (kao i sam izvršni program).
Želimo li sacuvati podatke i programe za neku buducu upotrebu, možemo ih pohraniti u sekundarnoj (vanjskoj, perifernoj ili pomocnoj) memoriji. Sekundarnu memoriju sacinjavaju magnetski mediji: diskovi, diskete, magnetske vrpce, kasete, itd. Bitne karakteristike tih memorija su veliki kapacitet, desetine tisuca do nekoliko milijuna puta veci od kapaciteta primarne memorije, i trajno pamcenje pohranjenih podataka.
Ulazni i izlazni uredaji (neki od njih mogu biti i jedno i drugo) omogucuju komuniciranje s kompjuterom: unošenje, citanje, upisivanje, ispisivanje i prikaz podataka i programa. Drugim rijecima, oni omogucuju prijenos i razmjenu podataka i programa izmedu vanjske okoline i kompjutera. Ovdje se pod pojmom "ulaz" podrazumijeva unošenje ili citanje podataka s ulaznog uredaja u primarnu ili sekundarnu memoriju, a "izlaz" znaci iznošenje - ispis rezultata obrade iz memorije na izlazni uredaj i prikaz tih rezultata na nekom izlaznom mediju (ekran, papir itd).
Hardverski dio kompjutera može izvršiti ulazne, racunske i izlazne operacije, ali koje i kojim redoslijedom odreduje se softverskim dijelom. Na kompjuteru razlikujemo dvije vrste softvera:
Sistemski softver je skup programa za upravljanje i kontrolu rada uredaja, za opsluživanje korisnika i izvršenje njihovih programa. U gruboj podjeli sacinjavaju ga programi operacijskog sustava, uslužni programi i prevoditelji.
Bitna komponenta sistemskog softvera je operacijski sustav. To je skup programskih modula pomocu kojih se, jednostavno receno: nadziru hardverski resursi (procesor, primarna i sekundarna memorija i ulazno-izlazni uredaji), rješavaju konflikti u zahtjevima za hardverskim resursima izraženi korisnickim programima, optimizira i usaglašava rad hardverskih uredaja u skladu s korisnickim zahtjevima i upravlja komuniciranjem korisnika s kompjuterom i hardverskim uredajima pri izvršenju korisnickih programa.
Operacijski se sustav, dakle, ponaša kao posrednik izmedu korisnickih programa i hardvera. Od mnogih operacijskih sustava danas su u široj upotrebi UNIX, MS-DOS i XENIX.
Uslužni programi omogucuju sortiranje podataka, prenos podataka i programa s jednog medija na drugi, upisivanje podataka i programa, vodenje statistike i evidencije o radu kompjutera i sl. Osnovne karakteristike su im otvorenost (moguce je proširenje novim programima), relativna neovisnost o operativnom sustavu i smještaj na sekundarnoj memoriji.
Prevoditelji su programi koji "razumiju" jezike za programiranje i korisnicke programe, napisane u tim jezicima, prevode u programe strojnog ili nekog drugog jezika za programiranje.
Sistemski softver na suvremenim kompjuterima obuhvaca i sustave za upravljanje bazama podataka, koji omogucuju definiranje složenih struktura podataka i upravljanje pristupom podacima ovisno o potrebama korisnika.
Aplikacijski softver je skup programa kojima korisnici izražavaju zahtjeve za informacijama ili podacima ili rješavaju razlicite vrste problema. Neke od tih programa napisali su sami korisnici, drugi postoje kao gotovi programski paketi. Spomenimo samo neke vrste aplikacijskih programskih paketa:
Kompjuter može uraditi samo ono za što je netko dao instrukcije
(program)
- niz logickih i aritmetickih operacija napisanih u jeziku
kompjutera.
Kompjuter takve instrukcije izvršava brzo i gotovo nepogrešivo,
upravo onako kako su zadane.
Kompjuter može izvršiti samo mali broj veoma jednostavnih operacija. Na primjer, oduzimanje, množenje i dijeljenje svodi na operacije zbrajanja i pomicanja znamenki. Kompjuter "razumije" i može izvršiti samo instrukcije strojnog jezika. Razvojem kompjutera usavršavali su se i jezici za komuniciranje s njima (programirni jezici), pa razlikujemo cetiri generacije:
l) Prva generacija - strojni jezici
2) Druga generacija - simbolicki (asemblerski) jezici
3) Treca generacija - jezici za programiranje visoke razine
4) Cetvrta generacija - jezici cetvrte generacije
Generacije jezika za programiranje ne treba poistovjecivati s generacijama kompjutera. Na primjer, danas su u upotrebi kompjuteri cetvrte generacije na kojima nalazimo sve cetiri generacije jezika za programiranje. Osim dane podjele jezika za programiranje postoji još i druge. Prema jednoj od njih, na primjer, svi jezici za programiranje dijele se na:
Pisanje programa za prve kompjutere bilo je iskljucivo u strojnom jeziku. To je bilo dosta mukotrpno jer je strojni jezik niz nula i jedinica, odredene konacne duljine. Trebalo je pamtiti što koji od tih nizova znaci (na primjer, da niz 00111 znaci "zbroj"). Pisanje programa u strojnom jeziku ne samo da je bilo otežano nerazumljivim kodovima pojedinih instrukcija, vec nije postojao ni jedinstveni strojni jezik, pa onaj koji je poznavao jezik jednog stroja nije mogao tim jezikom programirati na drugom.
Prvi korak prema tzv. "jezicima više razine" bilo je uvodenje simbolickog (asemblerskog ili mnemonickog) jezika. U tom jeziku programer koristi mnemonicka imena i za operacije i za operande. Tako, na primjer, u nekom simbolickom jeziku može se napisati:
ADD X, Y
umjesto, na primjer, 0110 001110 010101 u nekom strojnom jeziku.
Program u simbolickom jeziku lakši je za pisanje i razumijevanje
od
programa pisanog u strojnom jeziku. Prije svega, numericki kodovi
za
operacije i adrese zamijenjeni su prihvatljivim simbolickim
kodovima koji vec svojim imenom podsjecaju korisnika na svoju
namjenu.
Uvodenjem asemblerskih jezika znatno je olakšano pisanje i razumijevanje programa, ali još uvijek je bilo odredenih teškoca jer je programer morao detaljno znati kako odredeni kompjuter izvršava operacije. Takoder je morao racunanjem napamet prevoditi kompleksne operacije i strukture podataka u niz operacija niske razine koje upotrebljavaju samo primitivne tipove podataka strojnoga jezika te voditi racuna kako i gdje su podaci postavljeni u radnoj memoriji kompjutera.
Da bi se nadišli takvi i slicni problemi, razvijeni su jezici visoke razine, koji programeru omogucuju da piše algoritme u prirodnijoj notaciji u kojoj se ne treba baviti mnogim detaljima vezanim za specificni kompjuter. Na primjer, daleko je ugodnije pisati A=B + C nego niz asemblerskih instrukcija.
Danas je u široj uporabi dvadesetak jezika visoke razine. To su:
Ada, ALGOL 60 i 68, APL, BASIC, C, COBOL, FORTRAN, ICON, LISP,
Modula-2, Pascal, PL/1, PROLOG, SNOBOL, itd. Oni se razlikuju po
svom stupnju bliskosti matematickom jeziku ili prirodnim jezicima,
s jedne strane, i strojnom jeziku, s druge strane. Takoder se
razlikuju po vrsti problema cijem rješavanju su najbolje
prilagodeni. Suvremeni jezici za programiranje visoke razine
slicnih su osnovnih mogucnosti; ipak razlikujemo nekoliko skupina
jezika, ovisno o vrsti problema za cije su rješavanje
prilagodeni:
• za ucenje programiranja (LOGO, BASIC, Pascal)
• za rješavanje znanstvenih problema - algoritamski algebarski
jezici (ALGOL, APL, BASIC, FORTRAN, Pascal)
• za obradu podataka (COBOL, PL/1)
• za sistemske programe (Ada, C, Modula-2)
• za sisteme umjetne inteligencije (LISP, PROLOG)
• za obradu teksta (ICON, SNOBOL, TEX), itd.
Jezici za programiranje visoke razine podvrgnuti su standardima s propisanom sintaksom i semantikom, cime je u velikoj mjeri postignuta neovisnost o karakteristikama kompjutera i operacijskog sistema na kome su instalirani.
Bez obzira što je svaka nova generacija jezika bila bliža korisniku, još uvijek je programiranje u tim jezicima posebna disciplina. Tek s pojavom jezika cetvrte generacije stvorena je alternativa profesionalnom programiranju. Karakteristika je tih jezika da su potpuno prilagodeni krajnjim korisnicima - neprogramerima u principu, a primjenjuju ih veoma uspješno i informaticari (programeri i analiticari sistema) radi ubrzanja procesa programiranja.
Proceduralni jezik specificira kako ce nešto biti izvršeno, a neproceduralni što ce biti izvršeno, ne ulazeci u detalje kako.
Strojni jezik je proceduralan. Za druge se jezike može govoriti o postotku proceduralnosti ili neproceduralnosti. Jezici cetvrte generacije su neproceduralni, ili su to u vecem postotku.
Suvremeni jezici trece i cetvrte generacije kombinacija su proceduralnih i neproceduralnih komponenti. To je, opcenito, poželjno jer se neproceduralnim komponentama ubrzava programiranje i pojednostavljuje uporaba jezika, dok se proceduralnim komponentama proširuje obujam primjena jezika u rješavanju problema.
Jezici za programiranje daleko su jednostavniji od prirodnih (npr. hrvatskoga, engleskoga, francuskoga, talijanskoga, itd). Osim toga, "recenice" jezika za programiranje mogu se opisati strogim pravilima, bez izuzetaka i s jedinstvenim znacenjem. Na žalost, u mnogim knjigama o jezicima za programiranje i školama programiranja jezik se nastoji prikazati iskljucivo primjerima, a onome tko ga uci preostaje da sam zakljuci i izvede opca pravila za pisanje naredbi. S druge strane, još uvijek ne postoji "recept" koji bi upucivao na prave puteve definiranja i ucenja jezika za programiranje. Medutim, iskustvo pokazuje da se najveci ucinci postižu ako se pri ucenju jezika istaknu tri stvari: leksicka struktura, sintakticka struktura i semantika jezika.
Definirati leksicku strukturu nekog jezika znaci definirati alfabet i rjecnik. Alfabet je skup svih znakova koji se koriste u pisanju. To su slova, znamenke, operacije, te drugi znakovi.
Rjecnik je skup rijeci (simbola) definiranih nad alfabetom. Rijec (ili simbol) je niz znakova iz alfabeta koji se može promatrati kao jedinstvena, nedjeljiva cjelina. Na primjer, neka je dan niz A-B*C. Sastoji se od pet znakova koji mogu biti grupirani na nekoliko nacina. Može se smatrati da niz A-B cini jednu rijec (u jeziku COBOL to bi bilo ime varijable). Ili se A-B može promatrati kao varijabla A minus varijabla B (kao što je u FORTRAN-u i nekim drugim jezicima). Što je od ovog korektno, ovisi o definiciji leksicke strukture jezika. Njome ce biti propisano koje rijeci treba tretirati kao imena, a koje kao operatore.
Radi boljega sagledavanja leksicke strukture nekoga jezika uobicajeno je rjecnik podijeliti u klase rijeci (simbola) koje imaju zajednicka svojstva: brojeve, imena, rezervirane rijeci, imena funkcija, ostale (specijalne) simbole itd.
Sintakticka (ili sintaksna) struktura jezika utvrduje grupiranje leksickih konstrukata u šire strukture, nazvane sintakticke kategorije. Pravila koja odreduju da li niz simbola pripada jeziku ili ne nazivaju se sintaksa jezika.
Danas je u uporabi nekoliko notacija ili nacina prikazivanja
prvobitno definirane Backus-Naurove forme (BNF). Upravo od pojave
Pascala popularni su sintakticki dijagrami. Ukratko, sintakticki
dijagrami sadrže sljedece simbole:
(SLIKA) Simbol jezika. Ono što je upisano unutar ovog simbola dio
je je naredbe jezika opisane dijagramom, odnosno definira samo
sebe. Na primjer: (SLIKA)
(SLIKA) Opcenito ime ili konstrukt koji je vec definiran ili ce
biti definiran naknadno. Ono što je upisano u pravokutniku nije
element jezika, vec služi za opis strukture naredbe jezika. Drugim
rijecima, to je sintakticka kategorija. Na primjer: (SLIKA)
(SLIKA) Pokazuje moguci tok kretanja kroz dijagram (usmjeren
strelicom).
Ako u tekstu upucujemo na sintakticku kategoriju (ono što je
upisano u pravokutniku), pisat cemo je izmedu znakova "<" i
">". Na primjer:
<naredba> <ime><broj> <aritmeticki izraz>
Notacija sintaktickih dijagrama primijenjena u opisu sintakse Pascala može biti pojednostavljena:
• sintakticke kategorije bit ce pisane malim slovima
• simboli jezika bit ce pisani velikim slovima ili nizovima znakova
razlicitim od malih slova
Sada se postavlja pitanje: Kako "citati" sintakticke dijagrame?
Odgovor je jednostavan: treba krenuti slijeva i prolazeci kroz
dijagram definiranim putovima (pazeci na njihovo usmjerenje) doci
do izlaza. Izlaz je , ??, odnosno strelica iza koje nema više
nijednog simbola. Pri tome treba zapisivati sadržaj simbola
dijagrama: simbole jezika izravno prepisivati, a one koji su unutar
pravokutnika napisati izmedu znakova "<" i ">", potom ih
zamijeniti njihovom definicijom (njihovim dijagramom). Postupak
treba ponavljati sve dok se ne dobije niz koji je sacinjen samo od
simbola iz jezika (rjecnika). Na primjer, definirajmo primjenom
sintaktickih dijagrama pravilo pisanja prirodnih brojeva:
prirodni broj : (SLIKA)
nenula: (SLIKA)
brojka (SLIKA)
Pravilo pisanja prirodnih brojeva sadrži dva simbola koji nisu u
jeziku. Sve tri definicije u potpunosti opisuju tvorbu prirodnih
brojeva. Na primjer, krenuvši od definicije prirodnog broja prvo
nailazimo na <nenula>. Poslije toga može se završiti ili
krenuti putem preko <brojka>. Pretpostavimo da smo završili.
Medutim, <nenula> nije element jezika, pa ga moramo
zamijeniti njegovom definicijom. Ako pogledamo definiciju
sintakticke kategorije <nenula>, zakljucit cemo da moramo
izabrati jednu brojku od 1 do 9. Na primjer, izaberimo brojku 8.
Dakle, umjesto <nenula> možemo napisati 8. To je ujedno i
prirodan broj. Evo još jednog primjera primjene danih pravila:
<nenula> <brojka> <brojka>
9 <brojka> <brojka>
9 0 <brojka>
9 0 <nenula>
9 0 1
Uocimo da dijagram kojim je definiran <prirodni broj> sadrži
petlju koja osigurava da generiramo potpuni (beskonacni) skup
zapisa beskonacnog skupa prirodnih brojeva. Takoder primijetimo da
je bilo neophodno uvesti strukturu <nenula> koja je osigurala
da prirodni broj ne smije biti 0, niti smije poceti nulom.
Vec iz ovog jednostavnog primjera mogu se uociti prednosti primjene sintaktickih dijagrama u definiranju i ucenju jezika. Navedimo samo najbitnije:
1) Kompaktnim konacnim pravilom - sintaktickim dijagramom -
moguce je opisati veliki skup kombinacija u generiranju dane
naredbe.
2) Pravila predocena dijagramima brže se pamte i uce, jer vecina
ljudi bolje pamti vizualno.
3) Promatranjem svih naredbi jezika moguce je uociti dijelove koji
su jednaki. Uvodenjem posebnih imena za takve dijelove znatno se
pojednostavljuje ucenje jezika.
Medutim, sintakticki dijagrami nece uvijek biti dovoljni za potpuni opis svih naredbi. Jer, pojedine dodatne (kontekstne) uvjete koji moraju biti ispunjeni prilikom pisanja nekih naredbi nije moguce opisati dijagramom. Na primjer, u Pascalu izraz A+B napisan je korektno ako su A i B varijable ili konstante istog primitivnog tipa, nizovnog ili skupovnog tipa. Osim toga, postojat ce situacije gdje je moguc opis sintaktickim dijagramom, ali bi bio prekompliciran. I u jednom i u drugom slucaju davat cemo dodatna pravila rijecima. Na primjer, ako želimo definirati pravilo za tvorbu prirodnih brojeva od 1 do 999999, onda cemo uz dano pravilo reci da ono vrijedi uz uvjet da se <brojka> smije upotrijebiti do 6 puta ili cemo u sintaktickom dijagramu oznaciti maksimalni broj prolazaka odredenim putem.
Osim sintaktickih dijagrama cesta je uporaba još jedne notacije
koju cemo pretežito rabiti u našem opisu sintakse Pascala.
Sintakticke kategorije i rijeci jezika pišu se jednako kao i u
pojednostavljenom sintaktickom dijagramu. Znacenje preostalih
pravila prikažimo sintaktickim dijagramom:
1) ? ? ? ? ? ? ?
2) ? ? ? (SLIKA)
3) [ ? ] (SLIKA)
4) { ? } (SLIKA)
Na primjer, pravilo pisanja prirodnih brojeva u ovoj notaciji
prikazano je sa:
prirodni__broj: nenula { brojka }
nenula: 1|2|3|4|5|6|7|8|9
brojka: nenula | 0
Vec smo nekoliko puta upotrebili termin "jezik za programiranje" a da nismo definirali što to znaci. Jezik za programiranje može se definirati kao notacijska tehnika (pismo) kojom se na kompaktan, nedvosmislen i konacan nacin specificira niz operacija koje ce biti izvršene nad nekim objektima - podacima. Odredeni niz tih operacija napisan u nekom jeziku naziva se program.
Opcenito se i operacije i podaci u vecini jezika za
programiranje mogu grupirati hijerarhijski, kao što je prikazano na
sljedecoj slici:
program
?
potprogram
?
naredbe
?
izrazi
?
___________?___________
? ? ?
podaci operacije funkcije
Hijerarhija elemenata programa
Korištenjem ovakve hijerarhijske strukture znatno se olakšava i
ucenje jezika. Naime, premda smo rekli da su jezici za
programiranje daleko jednostavniji od prirodnih, bilo bi ih teško
uciti bez neke sistematizacije. Sagledavajuci dijelove jezika
postupno, kroz hijerarhijsku strukturu i grupe naredbi, jezik se
može nauciti daleko brže i potpunije.
U daljnjem detaljnijem opisu elemenata programa podimo redom od onih koji su na najnižoj razini prema vrhu.
Podaci su na razini strojnog jezika predoceni znakova binarnog alfabeta. U jezicima za programiranje visoke razine podaci ne pripadaju samo jednom skupu vrijednosti, niti su nad razlicitim skupovima dozvoljene sve operacije. Zato se u tim jezicima uvodi pojam tipa podataka.
Tip podataka je skup vrijednosti koje imaju izvjesne zajednicke osobine. Najznacajnija od njih je skup operacija koje su definirane nad vrijednostima tog tipa.
U programiranju opcenito, a posebno u jezicima za programiranje visoke razine, pojam tipa od posebne je važnosti. Tipom se odreduje iz kojega se skupa vrijednosti varijablama u programu mogu dodjeljivati vrijednosti, i koje su operacije dopuštene.
U vecini jezika za programiranje, kao što je to na primjer u Pascalu, zahtijeva se eksplicitno deklariranje varijabli po tipu prije njihove prve upotrebe u programu.
Jedan od osnovnih razloga za uvodenje tipova bio je omogucivanje kontrole korektnosti upotrebe vrijednosti razlicitog tipa i operacija s njima u izrazima programa. Jednako važan razlog u implementaciji jezika jest što razliciti tipovi vrijednosti zahtijevaju razlicit broj celija za memoriranje i razlicit prikaz u memoriji. U vecini jezika za programiranje susrecu se sljedeci standardni tipovi podataka:
• brojcani (cjelobrojni i realni)
• logicki
• znakovni
Ova cetiri tipa podataka nazzivaju se još i primitivni tipovi, zato što u jezicima za programiranje visoke razine predstavljaju nedjeljive cjeline i imaju izravan prikaz u memoriji
Cjelobrojni tip (integer) podskup je skupa cijelih brojeva,
odnosno skup cjelobrojnih vrijednosti iz intervala
-2n-l, 2n-l-1,
gdje je n duljina memorijske celije (u bitovima) za pamcenje
cjelobrojnih vrijednosti, ukljucujuci predznak. Koji je to tocno
podskup, ovisi o realizaciji jezika za programiranje i verzije
kompjutera. Nad ovim tipom, u vecini jezika za programiranje,
definirane su standardne operacije cjelobrojne aritmetike:
zbrajanje, oduzimanje, množenje, cjelobrojno dijeljenje i
potenciranje. Pri izvršavanju tih operacija vrijede svi zakoni
aritmetike pod uvjetom da nije došlo do prekoracenja najmanje i
najvece moguce vrijednosti cijelog broja (što je odredeno duljinom
pridružene memorijske celije).
Realni tip (real) je podskup realnih brojeva, odnosno skup
brojeva oblika
± O.m x 2± e
gdje je m mantisa, a e eksponent. Mantisa je binarni broj duljine
n, a eksponent binarni broj duljine k. Preciznost zapisa realnog
broja ovisna je o n i k. U nekim jezicima postoji samo jedan prikaz
realnih brojeva. Tako je bilo i sa standardnom verzijom Pascala.
Vidjet cemo da Turbo Pascal ima nekoliko prikaza realnih brojeva.
Nad realnim tipom definirane su standardne operacije realne
aritmetike (zbrajanje, oduzimanje, množenje, dijeljenje i
potenciranje). Zbog ogranicene i konacne duljine memorijskih celija
za pamcenje realnih vrijednosti u memoriji kompjutera, prakticki je
nemoguce prikazati i u memoriji upamtiti proizvoljnu realnu
vrijednost, vec samo podskup realnih vrijednosti. Drugim rijecima,
realni tip na kompjuteru je konacan skup realnih vrijednosti. Zbog
toga se racunske operacije ne obavljaju s tocnim vec s približnim
vrijednostima. Posljedica je toga da su rezultati operacija
aproksimacija tocnih rezultata.
Skup vrijednosti logickoga tipa (logical) sastoji se od dvije logicke konstante: true (istina) i false (neistina, laž). U vecini jezika za programiranje, u kojima je uveden logicki tip podataka, definirane su Booleove operacije - negacija, konjunkcija i disjunkcija, a u nekim jezicima i implikacija i još neke druge operacije.
Skup vrijednosti znakovnoga tipa (character, odnosno char) odreden je alfabetom jezika za programiranje (skupom svih znakova dopuštenih u jeziku za programiranje). Nad znakovnim tipom najcešce je definirana samo operacija nastavljanja, ali rezultat te operacije nije znak vec niz znakova.
Na apstraktnoj razini svaki jezik za programiranje koristi objekte: cjelobrojne, realne, logicke, itd. Kao što je vec opisano u prethodnom poglavlju, memorija kompjutera sastoji od celija koje mogu pamtiti vrijednost bilo kojega tipa. Celije su razlicite duljine, od jednog bajta do nekoliko memorijskih rijeci, ovisno o tipu podataka. Svaka celija ima ime koje je obicno varijabla jezika za programiranje. Ime je rijec koja se tvori prema pravilima leksicke strukture jezika. U vecini jezika ime je najmanje jedno slovo ili slovo kojega slijedi niz sastavljen od znamenki i slova.
Opcenito, podaci bilo kojega tipa mogu biti:
• varijable
• konstante
Varijabla u matematici ne predstavlja nijednu posebnu vrijednost.
Tako je, na primjer, u tvrdnji da za svaki prirodni broj n
vrijedi:
n2 > 0
U jezicima za programiranje pojam "varijable" koristi se za nešto
što postoji s vremenom i koje u svakom trenutku ima izvjesnu
vrijednost. Varijabla je odredena svojim imenom i tipom. Tip
varijable odreduje iz kojeg ce se skupa vrijednosti dodjeljivati
(pridruživati) varijabli. U nekim jezicima tip varijable može biti
definiran pocetnim slovom, u drugima odredenim sufiksom, a u nekima
tek eksplicitnom deklaracijom tipa.
Konstante imaju odredene vrijednosti koje se ne mijenjaju tokom
izvršavanja programa. Zadaju se eksplicitno, pišuci konkretnu
vrijednost iz skupa svih vrijednosti nekog tipa ili im se
pridružuje simbolicko ime. Na primjer, -123 je cjelobrojna
konstanta, a 0.505 realna. Važno je primijetiti da u jezicima za
programiranje konstante nisu vrijednosti. Bolje ih je zamisliti kao
posebnu vrstu varijabli koje svoje vrijednosti steknu prije nego
što se program pocne odvijati i nikad ih ne mijenjaju.
Vrijednosti bez komponenti, koje predstavljaju same sebe i dalje
se ne dijele, nazivaju se primitivni tipovi. Nosioci primitivnih
tipova su konstante ili varijable koje se mogu nazvati "primitivne"
varijable.
Polazeci od primitivnih tipova moguce je definirati strukturirane
tipove - skupove vrijednosti cija struktura ima odredeni smisao.
Nosioci strukturiranih podataka bit ce strukturirane varijable. One
se mogu koristiti tako da se odnose na strukturiranu vrijednost u
cjelini ili na pojedine komponente. Da bi se definirao
strukturirani tip, neophodno je definirati metodu strukturiranja i
tipove komponenti. U vecini jezika za programiranje susrecu se
sljedeci strukturirani tipovi podataka:
• polje
• niz
• slog
• datoteka
Pascal ima, pored navedenih, i skup kao strukturirani tip
podataka.
Polje (array) je kolekcija elemenata istog tipa (na primjer realnog
ili znakovnog) objedinjenih u k-dimenzionalnoj strukturi. Elementi
polja imaju isto ime ali k razlicitih indeksa:
A (i1, i2, ..., ik)
Ovdje je A ime polja, a i1, ..., ik su indeksi elemenata polja.
Broj k (k?l) je dimenzija polja. Na primjer, jednodimenzionalno
polje B(n) od n elemenata može se prikazati kao uredena
n-torka:
{ B(l), B(2), ..., B(n) },
a dvodimenzionalno polje C(m,n), od m x n elemenata, kao uredena
tablica:
C(1, 1) C(l,2) C(l,3) ... C(l,n)
C(2,l) C(2,2) C(2,3) ... C(2,n)
... ... ... ... ...
C(m,l) C(m,2) C(m,3) ... C(m,n)
Jednodimenzionalno polje naziva se vektor, dvodimenzionalno
matrica. Polje B iz prethodnoga primjera je vektor, a polje C
matrica. Svi poznati jezici za programiranje imaju strukturu polja,
ali rijetki su oni u kojima su definirane i operacije s poljima.
Sintakse polja, a djelomicno i semantike, razlikuju se od jezika do
jezika.
Niz (string) je kolekcija znakova koja se na razini jezika za
programiranje tretira kao nedjeljiva cjelina. Zbog toga se niz
znakova cesto promatra kao primitivni tip podataka, nad kojim je
najcešce definirana samo operacija nastavljanja. U nekim jezicima,
na primjer u Pascalu, niz je znakova poseban slucaj
jednodimenzionalnog polja ciji su elementi znakovi. Tako
realiziran, niz znakova predstavlja strukturu podataka znakovnog
tipa, koja omogucava definiranje operacija nad cjelinom, ali i nad
njezinim dijelovima.
Slog (record) je struktura podataka koju cini uredena kolekcija
opcenito razlicitih primitivnih ili strukturiranih tipova podataka.
Svaka komponenta sloga ima jedinstveno ime kojim se na nju upucuje.
Nad komponentama sloga dopuštene su operacije suglasno njihovom
tipu. Slog se, medutim, posebno pri ulazno-izlaznim operacijama,
cesto tretira kao kompaktna cjelina, što olakšava rad i
programiranje te ubrzava izvršenje programa.
Datoteka (file) je organizirana kolekcija zapisa, obicno pohranjena
na sekundarnoj memoriji kompjutera. Zapis je podatak primitivnog
ili strukturiranog tipa. U vecini jezika za programiranje razlikuju
se dvije vrste datoteka: one u kojima je pristup zapisima
sekvencijalan (u nizu) i datoteke s direktnim pristupom zapisima.
Na datotekama se ne cuvaju samo podaci, vec i softver potreban za
rad na kompjuteru kao i korisnicki programi.
Skup (set) je uredena kolekcija podataka istog primitivnog tipa. Na
razini jezika za programiranje promatra se kao nedjeljiva cjelina,
odnosno kao skup u matematickom smislu, pa su nad njim definirane
skupovne operacije (unija, presjek i razlika).
Izrazi nisu naredbe vec sintakticke strukture koje, opcenito,
sadrže operande (varijable, konstante i funkcije) i operacije.
Prema tipu vrijednosti izraza, u vecini jezika za programiranje
razlikujemo aritmeticke, znakovne i logicke izraze.
Aritmeticki izrazi sadrže cjelobrojne i realne operande, te poznate
i o tipu ovisne aritmeticke operacije. Znakovni izrazi sadrže
nizove znakova kao operande i samo jednu operaciju - nastavljanje.
Logicki izrazi sadrže relacijske podizraze, logicke konstante i
varijable, te logicke operacije.
Elementarne akcije izracunavanja, dodjeljivanja i kontrole
redoslijeda izracunavanja specificiraju se naredbama jezika za
programiranje. Naredbe mogu imati razlicite oblike i znacenje.
Uobicajena je podjela na:
• primitivne (jednostavne)
• strukturirane (složene) naredbe
Ova podjela odraz je sintakse naredbi. Osim nje, ponekad se
naredbe, na temelju svoga znacenja, dijele na:
• naredbe za izracunavanje
• naredbe za kontrolu toka izvršavanja
• deklarativne naredbe
• ulazno/izlazne naredbe, itd.
Primitivne naredbe su one koje ne sadrže druge naredbe. To su, na
primjer, naredba za dodjeljivanje, naredba za ispisivanje, naredba
za citanje podataka, itd. U nekim jezicima program se može
promatrati kao niz primitivnih naredbi (na primjer u jezicima
SNOBOL i APL). Strukturirane naredbe (složene ili komponirane)
sadrže jednu ili više naredbi. Strukturirane naredbe su, na
primjer, naredbe WHILE i REPEAT petlje u Pascalu.
Potprogrami su takoder strukturirane naredbe koje sadrže grupu primitivnih i strukturiranih naredbi - cjeline po svojoj funkciji i operacijama koje obavljaju. Dijelimo ih na procedure i funkcijske potprograme.
Konacno, stigli smo do najviše hijerarhijske strukture elemenata programa. Program sada možemo definirati kao niz naredbi, primitivnih i složenih, kojim se opisuje postupak ulaza, izracunavanja i izlaza podataka i rezultata izracunavanja.
Kad se zna da je naredba sintakticki korektna postavlja se pitanje: što je njeno znacenje? Pravila koja daju odgovor na to pitanje nazivaju se semantikom jezika za programiranje. Semantiku jezika za programiranje daleko je teže specificirati od njegove sintakse.
Jasna razlika izmedu sintakse i semantike jezika za programiranje bila je prvi put izražena u izvještaju jezika ALGOL 60, 1963. godine. Otada postoji nekoliko pristupa u njezinoj specifikaciji. Mi cemo u našim razmatranjima pod pojmom "semantika" podrazumijevati ono što je u literaturi poznato kao "interpretativna semantika". Interpretativna semantika neke naredbe jezika za programiranje jest ucinak njezinog izvršenja na odredenom kompjuteru. Na primjer, semantika naredbe
N := 55
je dodjeljivanje vrijednosti (broja) 55 varijabli s imenom N. To možemo prikazati sa N ? 55, a citat cemo "N stjece vrijednost 55" ili "Broj 55 dodijeljen je varijabli s imenom N". Ili, semantika naredbe
Write (N)
bit ce ispis vrijednosti varijable N.
Još uvijek ne postoji pogodna notacija za opis interpretativne semantike naredbi jezika za programiranje. Najcešce se to cini rijecima.
Mi smo za opis semantike Pascala usvojili vlastitu notaciju smatrajuci da svaka naredba ima odredene ucinke na izmjene podataka u memoriji, na ispis, izbor naredbi za izvršavanje ili promjenu toka izvršavanja programa. Notacija je objašnjena na mjestima gdje je uvedena.
Programiranje je postupak specificiranja skupa naredbi u nekom jeziku za programiranje da bi se izvršila neka aktivnost, riješio odredeni problem. No, cijeli proces rješavanja problema upotrebom kompjutora obicno se sastoji od više koraka. Iskustvo je pokazalo da su oni neizbježni, ali im broj može varirati u ovisnosti o nacinu dekompozicije problema i jeziku za programiranje. Za programiranje u Pascalu navodimo sljedece korake:
1) razumijevanje problemaMožda ce citaoca koji je upoznat s nekim drugim jezicima za programiranje, npr. jezikom C, zbuniti cetvrti korak. U njemu je objedinjeno nekoliko koraka i u potpunosti istisnuta potreba za rješavanjem problema u tzv. "pseudo kodu".
Najprije treba u potpunosti razumjeti postavljeni problem. U toj fazi treba odgovoriti na nekoliko pitanja. Na primjer: što je nepoznato, što su podaci, kakvi su uvjeti, je li moguce zadovoljiti uvjete, jesu li uvjeti dovoljni, ili redundantni, ili kontradiktorni, je li vec bio viden slican problem...? Cesto cemo problem potpunije shvatiti ako nacrtamo sliku ili uvedemo notaciju.
Kad je problem shvacen u potpunosti prelazi se na pronalaženje metode za njegovo rješavanje. Cesto je put ocigledan. Može postojati cak nekoliko rješenja. Tada se "pravo" rješenje bira na temelju postavljenoga kriterija, kao na primjer da vrijeme izvršavanja bude što krace. Za neke probleme rješenje nece biti ocigledno. Tada je najbolje problem podijeliti na nekoliko potproblema i tražiti njihovo rješenje. Takav nacin rješavanja problema poznat je kao "modularizacija". Najcešca su dva pristupa: odozgo (top-down) i odozdo (bottom-up).
Pristup odozgo karakteriziran je nizom koraka koji pocinju funkcionalnim opisom citavog problema i završavaju kolekcijom funkcija, tako jednostavnih da im je rješenje dano u obliku programa ocigledno. Problem rješavamo postupno, naznacujuci njegovu strukturu i ne ulazeci u detalje, sve dok to ne bude neophodno. Paralelno s rješavanjem problema pišemo program i testiramo ga poslije svakog proširenja.
Pristup odozdo obratan je od prethodnog. Karakteriziran je nizom redukcijskih koraka koji pocinju nekim skupom osnovnih funkcija i završavaju funkcijom koja realizira željeni cilj.
Cesto se taj korak, ponekad nazvan "specificiranje", ne smatra dijelom procesa programiranja. Ali, precizno specificiranje neophodan je uvjet za uspješan program.
Algoritam je postupak ili pravilo za sustavno rješavanje odredene vrste problema. Sastoji se od opisa konacnog skupa koraka. Svaki od njih sadrži jednu ili više izjava, a svaka izjava jednu ili više operacija. Za prikaz algoritma potrebno je usvojiti odredenu notaciju - tekstualnu, graficku, skupom formula, kombiniranu ili neku drugu. No, radi implementacije algoritma na kompjutoru, potrebno je opisati ga u nekom, za tu svrhu odabranom, jeziku za programiranje. Upravo je Pascal kao stvoren za to!
Oblikovanje algoritma zahtijeva poznavanje nekoliko algoritamskih konstrukata. Tri su osnovna konstrukta, cijom se kompozicijom može oblikovati algoritam kao rješenje zadanog problema: slijed (sekvenca), grananje (selekcija) i ponavljanje (iteracija).
Slijed, odnosno sekvenca, jest skup jednog ili više koraka algoritma koji se odvijaju sekvencijalno - redno, u nizu - jedan za drugim. Broj je koraka proizvoljan. Svaki korak može biti skup od jedne ili više izjava, a može predstavljati i cijeli algoritamski konstrukt - sekvencu, selekciju ili iteraciju. Shematski, sekvenca se može prikazati kao
-----? korakl -----? . .. -----? korakN
Na primjer, algoritam
1) Unesi N vrijednosti i zbroji ih
2) Izracunaj prosjecnu vrijednost,
3) Ispiši zbroj i prosjecnu vrijednost.
jest sekvenca triju koraka, koji se odvijaju jedan za drugim, a
svaki može biti algoritamski konstrukt.
Cesto je u algoritmima potrebno odluciti koju od dviju ili više sekvenci treba izvršiti s obzirom na postavljeni uvjet. Jednostavniji oblik grananja (selekcije) jest izbor jedne od dviju sekvenci, ovisno o tome je li postavljeni uvjet istinit, kad bi se izvela prva sekvenca, ili neistinit, kad bi se izvela druga. To je poznati IF-THEN-ELSE konstrukt u vecini jezika za programiranje visoke razine, a shematski se može prikazati kao
Ponavljanje, odnosno iteracija, jest sekvenca koraka algoritma koja se odvija izvjestan broj puta, sve dok je postavljeni uvjet ispunjen (okoncava se kad uvjet više nije ispunjen - kad postane neistinit), ili sve dok je odredeni uvjet neispunjen (okoncava se kad je uvjet ispunjen - postao je istinit). Prvi od iterativnih konstrukata poznat je pod imenom DO-WHILE, drugi kao DO-UNTIL (ili REPEAT-UNTIL). Prikažimo ta dva nacina iteracije shematski:
WHILE I<N DO BEGIN
I := I+1;
ReadLn (A);
Sr := Sr+A
END
Na kraju, napišimo u Pascalu kompletan algoritam iz prethodnih
primjera koristeci osnovne konstrukte:
I := 0; Sr := 0; Readln (N);
WHILE I<N DO BEGIN
I := I+1;
Readln (A);
Sr := Sr+A
END;
IF N>0 THEN
Writeln (Sr :20:4, Sr/N :20:4)
ELSE
Writeln ('N <= 0!')
Rekurzija je, opcenito, svojstvo objekta da se definira i pomocu samoga sebe (ili, da sudjeluje u definiciji samog sebe).
U matematici, rekurzija je takav algoritam, odnosno notacija ili pravilo opisa objekta, u cijim se definicijama kao parametar ili argument pojavljuju (i) sami objekti. Tako, na primjer, funkcija faktorijela nenegativnog cijelog broja definirana je rekurzivno sljedecim pravilom:
0! = 1F(0) = 1, F(l) = 1, F(n) = F(n-l) + F(n-2), n=2Iskustvo pokazuje da se najbolji ucinak u rješavanju nekog problema postiže kad izabrana metoda rješavanja i program prate strukturu problema. Na primjer, ako se za rješenje nekoga problema primijeni strategija razvoja odozgo, i program treba biti tako napisan. To znaci da se najprije u glavnom programu definira temeljna struktura rješavanja s nizom poziva podprograma koji, dalje, predstavljaju rješenje problema na sljedecoj (nižoj) razini. Istodobno se uvode potrebni tipovi podataka, konstante i varijable.
Evolucija jezika za programiranje, od asemblerskih jezika do jezika visoke razine, uvela je potrebu za posebnim programima - prevoditeljima. Kako kompjutor neposredno izvršava instrukcije u svom strojnom jeziku, neophodno je prevesti programe u taj jezik.
Prevoditelj je, dakle, program koji instrukcije korisnika
prevodi iz izvornog jezika u program izražen ciljnim jezikom. Ako
izvorni jezik pripada klasi jezika visoke razine, kao što je to
Pascal, a ciljni je asemblerski ili strojni, prevoditelj se naziva
kompilator.
Izvršavanje programa pisanog u jeziku visoke razine u osnovi je
dvodijelni je proces. Izvorni program najprije se kompilira, tj.
prevede u ciljni program, potonji se zatim smjesti u memoriju i
izvršava. Buduci da postoji nekoliko vrsta izvornih i ciljnih
jezika, razlikuje se nekoliko vrsta prevoditelja.
Asembler je prevoditelj koji prevodi program pisan u asemblerskom
jeziku u strojni jezik.
Neki prevodioci transformiraju program pisan u izvornom jeziku u
pojednostavljeni jezik, nazvan "medukod", koji se može direktno
izvršiti koristeci program zvan interpretator.
Termin pretprocesor katkad se upotrebljava za prevodioce koji
prihvacaju programe pisane u jednom jeziku visoke razine i prevode
ga u ekvivalentan program u drugom jeziku visoke razine.
Uobicajeno je da se prevoditelj jezika trece i cetvrte
generacije realizira kao kompilator. Zbog toga cemo reci nešto više
o kompilatorima. Kompilator prihvaca na ulazu izvorni program i
proizvodi semanticki ekvivalentan niz strojnih instrukcija. Takav
proces previše je kompleksan, i s logickog i s implementacijskog
aspekta, da bi se mogao razmatrati u jednom koraku. Zbog toga je
mnogo prikladnije podijeliti ga na niz procesa, nazvanih "faze", i
promatrati ih odvojeno, kao što je prikazano na crtežu.
(SLIKA)
Leksicka analiza jest prva faza kompilacije. Njen je zadatak
citanje izvornog programa, znak po znak, i grupiranje nizova
znakova u šire leksicke strukture - rijeci (simbole). Na primjer,
ako je na ulazu niz znakova
IF(A<K)AND(B<K) THEN MAX:=K
onda se u leksickoj analizi Pascala ovaj niz znakova grupira u niz
simbola
IF ( A < K ) AND ( B < K ) THEN MAX := K
Sintakticka analiza jest druga faza kompilacije. To je proces
utvrdivanja može li dani niz simbola (izlaz iz leksicke analize)
tvoriti dio programa napisanog u izvornom jeziku. Ako može, simboli
ce na izlazu iz sintakticke analize biti grupirani u šire,
sintakticke strukture. Cesto ce to biti predstavljeno u obliku
stabla.
Generator medukoda koristi strukturu dobivenu na izlazu sintakticke
analize da bi kreirao niz primitivnih instrukcija, u nekom
medujeziku - apstraktnom jeziku slicnom asemblerskom.
Optimiziranje koda jest faza u kojoj se medukod "popravlja". Time
se dobiva konacni ciljni kod koji radi brže i zauzima manje
memorijskog prostora.
U završnoj fazi, generiranju koda, proizvodi se ciljni kod uz
odredivanje memorijskih lokacija za podatke, odvajanje koda za
pristup svakom podatku i biranje registara u kojima ce biti
obavljena pojedina izracunavanja.
Tablica simbola dio je kompilatora u kojem se vode imena
upotrijebljena u programu, sa svim potrebnim dodatnim
informacijama. Dostupna je svim fazama kompilacije.
U bilo kojoj fazi kompilacije može se otkriti pogreška. Sve
pogreške pamte se na jednom mjestu i dojavljuju nakon završene
kompilacije (na primjer, tako radi prevoditelj FORTRAN-a) ili se
otkrivanjem prve pogreške prekida daljnja kompilacija i dojavljuje
pogreška (Turbo Pascal). Otkrivanjem prve pogreške prekida se
daljnje generiranje medukoda. Sa stanovišta programera potrebno je
razlikovati leksicke i sintakticke pogreške.
Leksicke pogreške nastaju kršenjem leksickih pravila. Na primjer,
pisanjem znaka koji ne pripada alfabetu jezika. Sintakticke
pogreške nastaju kršenjem sintaktickih pravila jezika.
Opcenito je poznato, i to se najcešce navodi kao "aksiom", da i
najtrivijalniji programi napisani u prvoj verziji sadrže greške -
"bugove". Zato se cesto kaže da program koji "prode" u prvom
izvršavanju sigurno nije dobar!
Pogreške u programu mogu se klasificirati na nekoliko nacina.
Najcešce ih dijelimo na leksicke, sintakticke i logicke.
Leksicke i sintakticke pogreške ne predstavljaju poseban problem.
Otkriva ih kompilator. Najteže je otkriti logicke pogreške jer,
nažalost, ne postoje metode koje sa sigurnošcu otkrivaju logicke
pogreške.
Popularna metoda za otkrivanje logickih pogrešaka jest testiranje.
Temelj testiranja programa jest zakljucivanje. Netko, na temelju
ocekujucih rezultata pojedinih slucajeva testiranja, zakljucuje da
je program "dobar" i da ce uvijek davati korektne rezultate za bilo
koje druge, neprovjerene ulazne podatke.
Pisanje programa ima smisla ako ce program biti izvršavan više
od jedanput. Ponekad ce proci više vremena izmedu dvaju izvršenja.
Ako program nije dovoljno dokumentiran, to ce prouzrociti probleme,
cak i za autora programa! Sigurno ce zaboraviti mnogo toga i cuditi
se što pojedini dijelovi rade. Ponekad ce program citati netko
drugi, pa ce posebni problemi nastupiti ako program nije
dokumentiran.
Postoji mišljenje da program treba dokumentirati nekim dodatnim
opisima, na primjer "dijagramom toka". Još je uvijek to prilicno
popularna metoda, pa ce vjerojatno neki citaoci biti iznenadeni što
je mi u našoj školi necemo rabiti. Za to imamo barem sedam
razloga:
1) Dijagramom toka nije predocena struktura programa.
2) Potrebno je prevodenje iz "jezika" dijagrama toka u jezik za
programiranje, pri cemu mogu biti nacinjene pogreške.
3) Dijagrami toka nastali su u ranijoj fazi razvoja jezika za
programiranje, kad jezik za programiranje nije mogao istodobno
poslužiti i kao "pseudo" jezik za pisanje algoritama, jer nije
sadržavao konstrukte kao što su IF-THEN-ELSE, WHILE petlja, niti
potprograme.
4) U fazi razvoja dijagrama toka ne postoji provjera (testiranje)
je li postavljena logika korektna.
5) Dijagram toka podrazumijeva detaljizaciju rješenja problema, što
poslije prevodenja u programski jezik i pojavom logickih pogrešaka
otežava njihovo lociranje, te nalaže vracanje u "jezik" dijagrama
toka, nalaženje pogreške u dijagramu, ispravljanje dijagrama toka i
ponovno prevodenje u programski jezik.
6) Potreba da se uz program stalno posjeduje dijagram toka, bilo za
onoga tko je program razvijao ili onoga tko ce program kasnije
pregledavati.
7) Konacno, dijagrami toka imali su donekle opravdanje dok je
razvoj algoritma bio odvojen od pisanja programa, kad je trebalo
cekati nekoliko dana da se dobiju rezultati programa.
Praksa pokazuje da se najveci ucinci postižu ako je program sam
sebi dokumentacija. Nikakvi dodatni opisi ne mogu popraviti loše
napisan program! Zbog toga treba paralelno s razvojem programa u
njega ugraditi i dokumentaciju. U tome nam najviše može pomoci
uporaba komentara, jer radi toga i postoje!
I "lijepo pisanje" znatno pridonosi povecanju citljivosti programa
i time skracuje vrijeme lociranja i otklanjanja pogrešaka. Obratite
pozornost na programe u ovoj knjizi. Željeli smo iz vlastita
višegodišnjeg iskustva pokazati kako bi trebali izgledati programi
u kojima ce struktura doci do što veceg izražaja. Na primjer,
obratite pozornost kako pišemo niz naredbi (BEGIN ... END) u
selekciji i iteraciji. Dakako, na vama je da to prihvatite ili ne,
ali prije toga provjerite jesmo li u pravu!