PP teorija Flashcards
- Objasniti namenu programskih prevodioca?
Uvek kada softversku aplikaciju razvijamo nekim višim programskim jezikom, a to je danas standardni pristup, treba nam softver koji će taj program da prevede u mašinski jezik, zato što svi računari, ma koliko složeni bili, obrađuju instrukcije predstavljene u mašinskom (binarnom) obliku. Ukoliko je programski jezik koji koristimo na višem nivou, zadatak tog softvera je složeniji. Programski prevodioci su softverske komponente koje generalno prevode programe pisane u jednom programskom jeziku u odgovarajuće programe pisane drugim programskim jezikom, Slika 1.1
1. Slika 1.1 Programski prevodilac
Obično je jezik sa kog se prevodi višeg nivoa od jezika na koji se vrši prevođenje, mada u opštem slučaju možemo da prevodimo sa jednog jezika višeg nivoa na drugi jezik višeg nivoa, ali i da se kod niskog nivoa prevodi u kod višeg nivoa ( npr. krosasembleri).
SLIKA
- Sta je to assembler?
Mašinski jezik je programski jezik najnižeg nivoa i podrazumeva da se program sastoji od naredbi i podataka napisanih u biarnom obliku (preko nizova jedinica i nula) uz korišćenje apsolutnih adresa podataka. Na ovom nivou programski prevodilac nije potreban, naredbe se upisuju direktno u operativnu memoriju i izvršavaju.
Drugu generaciju jezika čine asemblerski jezici kod kojih se jedna mašinska naredba predstavlja simbolički uz korišćenje simboličkih adresa naredbi i podataka. Ovi jezici su višeg nivoa od mašinskih ali su i dalje mašinski zavisni. Naime, asemblerski jezik se projektuje zajedno sa procesorom računara i struktura procesora bitno utiče na strukturu asemblerskog jezika i obrnuto. Za prevođenje zapisa sa nivoa asemblerskog jezika na mašinski nivo potreban je programski prevodilac koji se u ovom slučaju naziva Asembler (assembler), Error! Reference source not found., pa odatle i naziv ovih jezika.
SLIKA
- Cemu sluze makroprocesori?
Makroasemblerski jezici su nešto višeg nivoa od asemblerskih jezika i omogućavaju skraćeno zapisivanje programa tako što se grupa asemblerskih naredbi predstavi jednom makro naredbom. Kod programa napisanih na ovom nivou najpre se koristi makroprocesor čiji je zadatak da pozive makro naredbi zameni odgovarajućim sekvencama asemblerskih naredbi. Nakon toga se, pomoću odgovarajćeg asemblera, dobijeni asemblerski kod prevodi u mašinski, Slika 3.1.
Slika 3.1 Makroprocesor
Kako je asemblerski jezik niskog nivoa, a posebno zbog činjenice da je svakoj asemblerskoj naredbi odgovara jedna mašinska naredba, razvoj asemblera nije komplikovan zadatak. Slično je i sa makroproceosorom, čiji je zadatak prvenstveno da pokupi i zapamti definicije makro naredbi i da zameni pozive makronaredbi odgovarajućim sekvencama asemblerskih naredbi.
- Objasniti razliku izmedju kompilatora i interpretatora?
Kada se za razvoj programa koriste viši programski jezici onda je proces prevođenja na mašinski nivo je nešto složeniji. U te svrhe se kao programski prevodioci koriste kompilatori i interpretatori, Error! Reference source not found.. Osnovna razlika između kompilatora i interpretatora je u tome što kompilator najpre vrši analizu programa na osnovu koje generiše izvršni fajl celog programa. Interpretatori koriste drugu strategiju. Oni prevode naredbu po naredbu programa i čim formiraju celinu koja može da se izvršava, izvršavaju je.
- Navesti osnovne osobine kompilatora?
Kompilator započinje analizu programa fazom leksičke analize. U ovoj fazi identifikuju se leksičke celine i nastoji se da se uprosti zapis programa kako bi se pripremio za sintaksnu analizu. Na primer, za proces sintaksne analize nije važno da li je neka promenljiva u programu nazvana A ili B već je važno da se na određenom mestu javlja poromenljiva. Zbog toga se sve leksičke celine zamenjuju odgovarajućim simbolima a sve dodatne informacije o njima pamte u posebnoj strukturi koja se naziva Tablica simbola (Symbol Table).
Nakon leksičke analize sledi faza sintaksne analize. Zadatak ove faze je da se utvrdi da li je program tačno napisan u skladu sa pravilima kojima je definisan programski jezik koji je korišćen. Danas se koriste formalni opisi programskih jezika preko odrđenih meta jezika. U suštini zadatak sintaksnog analizatora je da rasčlani složene naredbe jezika na elementarne. Kao rezultat sintaksne analize dobija se sintaksno stablo koje pokazuje koja pravila i kojim redosledom treba primeniti da bi se generisala određena naredba jezika, odnosno od kojih se elementarnih naredbi sastoji svaka složena naredba.
Na osnovu sintasnog stabla genriše se međukod programa. Međukod je reprezentacija programa koja je mašinski nezavisna ali se jednostavno preslikava u mašinski ili asemblerski kod za određenu mašinu.
Kod koji kompilator genriše u prvom prolazu obično sadrži puno redundatnosti pa se zato mora vršiti optimizacija koda. Ova optimizacija može da bude mašinski nazavisna, kada se vrši na nivou međukoda ali i mašinski zavisna, kada se vrši na nivou generisanog koda.
Savremeni kompilatori pored sintaksne vrše i semantičku analizu koja se često integriše sa sintaksnom analizom ili se izvršava kao nezavisna faza. Zadatak semantičke analize je da utvrdi da li su u pisanju programa ispoštovana dodatna, semantička pravila koja se ne mogu formalno definisati kroz formalni opis jezika. Takva pravila su recimo pravila vezana za koncept jakih tipova podataka ili pravila o tome kojim stvarnim parametrima mogu da se zamenjuju stvarni parametri i sl. Ova dodatna pravila se obično definišu kao procedure koje se izvršavaju prilikom primene određenog sintaksnog pravila.
- Objasniti sta je to medjukod?
Na osnovu sintasnog stabla genriše se međukod programa. Međukod je reprezentacija programa koja je mašinski nezavisna ali se jednostavno preslikava u mašinski ili asemblerski kod za određenu mašinu. Koncept korišćenja međukoda kod kompilatora ima niz prednosti. Kako je međukod mašinski nezavisan, jednostavno se može preslikati u bilo koji drugi mašinski jezik. To znači da se na osnovu jednom generisanog međukoda može generisati mašinski kod za različite mašine i ostvariti prenosivost koda.
- Nacrtati potpunu semu strukture kompilatora?
IMa slika 3. stranica u skripti
- Definisati pojam azbuke.
Prilikom opisa jezika polazi se od azbuke kao osnovnog pojma. Neka je V konačan neprazan skup
elemenata. Elemente skupa V nazivamo simbolima, slovima, a sam skup apstraktnom azbukom ili
samo azbukom.
Primer 8.1 Primeri azbuka
V={0,1} Azbuci V pripadaju samo cifre 0 i 1;
V={a,b,c} Azbuci pripadaju samo slova a,b i c
Za opis programskih jezika se koriste nešto složenije azbuke.
Na primer jednu takvu azbuku mogu da čine sledeći simboli:
- Velika i mala slova abecede: A,a,B,b,C,c …
- Specijalni znaci: +, -,*, :=, …
- Reči kao što su: begin, end, if, then, …
Napomena: U ovom slučaju se svaka reč tretira kao jedan simbol.
- Dati formalnu definiciju pojma reči.
Reč u kontekstu formalnih jezka se definiše kao konačan niz simbola azbuke V. Niz koji ne sadrži
nijedan simbol naziva se prazna reč i označava sa .
Primer 2.2 Reči
Neka je V={a,b,c}. Sledeći nizovi su reči azbuke V: , a, b, c, aa, bb, cc, ab, ac,
abc, aabc
Reči su uređeni nizovi tako da se reč ab razlikuje od reči ba.
- Navesti osnovne delove reči.
Razlikujemo i sledeće pojmove:
Prefiks reči x je niz koji se dobija izbacivanjem nijednog ili više krajnjih simbola reči x.
Sufiks reći x je niz koji se dobija izbacivanjem nula ili više početnih simbola reči x.
Podniz reči x je reč koja se dobija kada se izbaci neki prefiks i neki sufiks reči x. Svaki prefiks i svaki
sufiks reči x su podnizovi reči x, dok svaki podniz reči x ne mora da bude ni sufiks ni prefiks reči x.
Za svaku reč x i x i su njeni prefiksi, sufiksi i podnizovi.
Primer 2.7 Delovi reči
Neka je data reč banana.
Reči b, ba, ban, bana, banan i banana su njeni prefiksi,
b, ba, ban, bana, banan su pravi prefiksi.
Reči a, na, ana, nana, anana i banana su njeni sufiksi
a, na, ana, nana, anana su pravi sufiksi.
aba, ana, anan su podnizovi reči banana.
baaa i bnna su podsekvenca reči babana.
- Navesti osnovne operacije koje se mogu izvršavati nad rečima.
Proizvod reči
Ako su x i y dve reči azbuke V, proizvod ili spajanje reči je operacija kojom se stvara nova reč tako što se
na jednu reč nadovezuje druga reč.
Primer 2.4 Proizvod reči
Neka je: x = aA i y = ab. Proizvodom ovih reči nastaje reč z = xy = aAab
Takođe važi da je: x = x = x. Prazna reč je neutralni element za operaciju proizvoda (nadovezivanja)
reči.
Eksponent reči
Višestruki proizvod iste reči se definiše kao eksponent reči.
Primer 2.5 Eksponent reči
xx = x2
xxx = x3.
x1=x
x0= .
Transponovana reč
Transponovana reč reči x u oznaci xT definiše se na sledeći način:
1. T =
2. (xa)T = axT
Rezultat operacije transponovanja reči je reč u kojoj su slova ispisana u obrnutom redosledu u odnosu na
originalnu reč.
Primer 2.6.Transponovana reč
Neka je data reč x=baba. Tada je xT=abab
Ako je x=radar tada je xT=radar. Ovakve reči nazivamo palindromima.
- Dati formalnu definiciju pojam jezika.
Neka je data azbuka V. Skup svih reči nad azbukom V se označava sa V. Napomenimo da je skup
V uvek beskonačan, bez obzira na to kako je definisana azbuka V. Čak i u slučaju kada azbuka V
sadrži samo jedan simbol V={a}, skup V={ , a, aa, aaa, aaaa, …}.
Formalni jezik nad azbukom V je bilo koji podskup skupa V . Bilo koji podskup bilo da je konačan ili
beskonačan predstavlja jezik. Kako je V* uvek beskonačan skup broj njegovih podskupova je takođe
beskonačan.
- Navesti osnovne operacije nad jezicima.
Ako je L formalni jezik onda se može definisati i njegov reverzni jezik u oznaci LR, kao skup svih
reverznih reči jezika L.
LR ={xT | xL}
Ako su L i M formalni jezici, onda je LM, unija ova dva jezika i obuhvata sve reči koje pripadaju
ili jeziku L ili jeziku M.
L M={x | x L x M}
Ako su L i M formalni jezici, onda je L M, proizvod ova dva jezika i obuhvata sve reči nastaju
operacijom nadovezivanja reči jezika M na reči jezika L.
L M={xy | x L y M}
Potpuno zatvaranje jezika L, koje se označava sa L*, je skup svih reči koje nastaju kao proizvodi reči
jezika L uključujući i .
0
*
i
L Li
Pozitivno zatvaranje jezika L, za koje se koristi oznaka L+ se definiše kao:
i 1
i L L
- Šta su to formalne gramatike i kako se definišu?
Noam Chomsky je još u svojim ranim radovima dao sledeću definiciju formalnih gramatika: Svaka
formalna gramatika G se može definisati kao skup G=(Vt, Vn, S, P) gde je Vt skup terminalnih
sibola, Vn skup neterminalnih simbola, S startni simbol i P skup smena definisan na sledeći način:
* * *
pri čemu je V = Vt Vn i važi Vt Vn =
Uočimo da je uslov da reč na levoj strani pravila mora da sadrži bar jedan neterminalni simbol.
Formalni jezik L definisan gramatikom G je skup reči koje se sastoje od terminalnih simbola a
dobijaju se tako što se na starni simbol primene pravila gramatike:
POGLEDAJ PDF BOLJE
- Šta su to neredukovane gramatike. Dati primer.
Gramatika mora da bude redukovana. Redukovana gramatika je gramatika koja ne sadrzi beskorisna
pravila. Beskorisna pravila su ona koje sadrže simbole koji ne mogu da budu izvedeni iz startnog
simbola gramatike, ili smene koje sadrže “beskonačne” simbole.
Primer 2.13 Neredukovana gramatika
Gramatika G=( {W,X,Y,Z}, {a}, W, P} gde je:
P: 1. W aW
2. W Z
3. W X
4. Z aZ
5. X a
6. Y aa
je primer neredukovane gramatike iz sledećih razloga:
1. Pravilo 2. je neupotrebljivo pravilo jer je Z beskonačan simbol, nikada se ne ukida.
2. Pravilo 4. je neupotrebljivo iz istog razloga.
3. Pravilo 6. je neupotrebljivo zato što ne postoji izvođenje W Y. Nikada se ne generiše
neterminal Y.
- Sta su to nejednoznačne gramatike. Dati primer.
Gramatika ne mora da bude jednoznačna. Kod nejednoznačnih gramatika za jedan ulazni niz je
moguce kreirati veći broj sintaksnih stabala.
Primer 2.14 Nejednoznačna gramatika
G=( {Izraz}, {const,+,*}, Izraz, P)
P: Izraz Izraz + Izraz
Izraz Izraz * Izraz
Izraz const
- Navesti osnovne tipove gramatika po Čomskom.
Još u svojim ranim radovima Chomsky je formalne je identifikovao četri tipa formalnih gramatika i jezika.
Gramatike koje zadovoljavaju gore date opšte uslove je nazvao gramatikama tipa nula. praktično svaka
formalna gramatika je gramatika tipa nula. ostali tipovi gramatika imaju strože definisane uslove koje
treba da zadovolje pravila. To znači da se tim tipovaima gramtika može definisati uži skup jezika ali se
zato može jednostavnije vršiti analiza i prepoznavanje takvih jezika.
Gramatike tipa jedan ili Konteksne gramatike
Gramatike tipa jedan su formalne gramatike koje pored opštih uslova koji zadovoljavaju gramatike tipa
nula imaju pravila x y koja zadovoljavaju sledeći uslov:
| x | | y |
To znači da se reči sa leve strane smena mogu preslikavati samo u reči koje su jednake ili veće dužine.
Drugim rečima, nisu dozvoljena pravila oblika:
x
Gramatike tipa jedan kao i gramatike tipa nula se obično nazivaju i konteksnim gramatikama. To je zbog
toga što se neterminal koji je obavezan na levoj strani smene kod ovih gramatika nalazi u nekom
kontekstu i čitav taj kontekst se preslikava u novu reč.
Gramatike tipa dva ili Beskontekne gramtike
Gramatike tipa dva su gramatike kod kojih su pravila definisana tako da se na levoj strani nalazi samo
neterminal. Neterminali se preslikavaju u reči. Kako se neterminali prilikom izviđenja posmatraju
izolovano od konteksta u kome se nalaze ove gramatike se nazivaju beskonteksnim gramatikama. Znači
smene kod ovih gramatika su oblika:
A y, gde je AVn i y Vt*
Za opis programskih jezika se obično koriste beskonteksne gramatike.
Gramatike tipa tri su formalne gramatike koje zadovoljavaju opšte uslove ali su orgraničene na smene
oblika:
A a B ili , A a gde je AVn i a Vt
Naziv regularne gramatike dolazi odatle što su ove gramatikama tipa tri generišu regularni izrazi koji se
efikasno mogu prepoznavati konačnim automatima. Regularne gramatike imaju široku primenu u mnogim
oblastima u kojima treba vriti prepoznavanje nizova. U kontekstu programskih prevodilaca koriste se za opis leksičkih elemenata jezika (identifikatora, konstanti, literala i sl.) koje prepoznaje leksički analizator, o čemu će biti reči kasnije.
- Šta su to konteksne, a šta beskonteksne gramatike?
Gramatike tipa jedan kao i gramatike tipa nula se obično nazivaju i konteksnim gramatikama. To je zbog toga što se neterminal koji je obavezan na levoj strani smene kod ovih gramatika nalazi u nekom kontekstu i čitav taj kontekst se preslikava u novu reč.
Gramatike tipa dva beskontekstne
Neterminali se preslikavaju u reči. Kako se neterminali prilikom izviđenja posmatraju izolovano od konteksta u kome se nalaze ove gramatike se nazivaju beskonteksnim gramatikama.
- Šta su to normalne forme gramatika?
Pod normalnim formama gramatika podrazumevamo standardni način zadavanja gramatika određenog tipa. To znači da se smene jedne gramatike mogu prikazati na neki drugi način a da se pri tome ne promeni jezik koji definišu. Tako dolazimo i do pojma ekvivalentnih gramatika.. Dve gramatike su ekvivalentne ako definišu isti jezik.
Naime nekada je potrebno smene gramatike predstaviti na baš određeni način da bi se mogao primeniti neki određeni postupak analize. U te svrhe su i definisane azličite normalne forme za određene tipove gramatika. Pomenućemo samo neke.
- Šta su to automati. Objasniti kako teče proces prepoznavanja reči automatom.
Problem prepoznavanja jezika, odnosno utvrđivanja da li zadata reč pripada jeziku opisanim određenom gramatikom, rešava se automatima kao uređajima za prepoznavanje jezika.
Generalno gledano svi automati se mogu predstaviti šemom datom na Slika 20.1, Niz simbola (reč) koji se prepoznaje zapisan je na ulaznoj traci. Po ulaznoj traci se kreće ulazna glava koja u jednom trenutku čita jedan simbol sa trake, Ova glava se u opštem slučaju može kretati i napred i nazad.
Slika 20.1 Šema automata kao uređaja za prepoznavanje jezika
Funkcionalni deo automata je njegov najznačajniji deo. Može da se nađe u nizu različitih stanja u
zavisnosti od toga kako je opisan jezik koji se prepoznaje. Funkcionalni organ beleži predistoriju
prepoznavanja i za to koristi memoriju koja je u ovom opštem modelu predstavljena kao beskonačna
memorija. Automat sa beskonačnom memorijom nije praktično izvodljiv tako da se realni automati
razlikuju od ovog modela po tome što koriste neki određeni tip memorije.
Proces prepoznavanja reči koja je upisana na ulaznu traku kreće tako što se ulazna glava pozicionira na
startni simpol (#), a funkcionalni organ se nalazi u svom početnom stanju. U svakom koraku
prepoznavanja, u zavisnosti od toga gde je pozicionirana ulazna glava (koji simbol čita) i stanja
funkcionalnog organa, kao i simbola u radnoj memoriji koji čita radna glava događaju se sledeće promene
u automatu:
* menja se stanje funkcionalnog organa
* u radnu memoriju se upisuje jedan ili više simbola
* radna glava se pomera napred, nazad ili ostaje na poziciji na kojoj se i nalazi.
Proces prepoznavanja reči je uspešno završen u trenutku kada se ulazna glava pozicionira na krajnji
granični simbol (desni #) i funkcionalni organ se nadje u jednom od svojih završnih stanja.
U opštem slučaju automati se mogu podeliti na četri klase:
* 2N Dvosmerni nedeterministički
* 1N Jednosmerni nedeterministički
* 2D Dvosmerni deterministički
* 1D Jednosmerni deterministički
Podela na jednosmerne i dvosmerne izvršena je na osnovu mogučnosti pomeranja ulazne glave. Ako se
ulazna glava kreče samo napred onda su to jednosmerni automati, a u slučaju kada je dozvoljeno i
vraćanje glave unatrag onda su to dvosmerni automati. Podela na determinističke i nedeterminističke
izvršena je u odnosu na preskikavanje stanja funkcionalnog organa koje se vrši u toku prepoznavanja .
Ukoliko je stanje u koje prelazi automat za određeni ulazni simbol i određeno zatečeno stanje,
jednoznačno definisana onda je to deterministički automat. Ukoliko je ovo preslikavanje višeznačno
onda je to nedeterministički automat.
- Kako je definisana Tjuringova mašina?
Error! Reference source not found. prikazuje šemu Tjuringove mašine kao osnovnog automata za
prepoznavanje jezika. Za razliku od opšteg modela automata Tjuringova mašina ima radnu memoriju
u vidu beskonačne trake.
# a # 1 a2 an ai
Funkcionalni
organ
Ulazna glava
Ulazna traka
A1 A2 An Ai
Radna memorija
2N Tjuringova mašina se može opisati sledećom entorkom: Tm=(Q, V, S, P, q0, b, F) gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
S – Skup simbola na radnoj traci
F – Skup završnih, krajnjih stanja (Podskup skupa Q)
q0 – Početno stanje operativnog organa
b – Oznaka za prazno slovo
P – Preslikavanje definisano sa:
odnosno ako je ulazna glava pozicionirana na simbolu a, funkcionalni organ se nalazi u stanju qi, a radna
glava iznad simbola A, automat će preći u stanje qj, na radu traku će upisti simbol B i iyvršiće pomeranje
ulazne glave i radne glave u skladu sa vrednostima d1 i d2. Pri tome važi sledeća notacija: Ako je d=0
nema pomeranja radne glave, za d=1 glava se pomera za jedno mesto u desno, a za d=-1 glava se
pomera za jedno mesto u levo (vraća se nazad).
Mašina započinje prepoznavanje tako što je ulazna glava pozicionirana na početnom graničnom simbolu,
funkcionalni organ se nalazi u početnom stanju i radna traka je prazna. Prepoznavanje reči se završava
uspešno ako se u trenutku kada se ulazna glava pozicionira na krajni granični simbol #, automat nađe u
nekom od završnih stanja (elemenata skupa F).
- Koje jezike prepoznaju automati tipa Tjuringove mašine?
Dokazano je da su sve četri klase Tjuringovih mašina, 2N, 1N, 2D, 1D su međusobno ekvivalentne i svaka
od njih prepoznaje jezike jezike tipa nula. To u suštini znači da je za prepoznavanje bilo kog jezika tipa
nula moguće definisati bilo koji tip Tjuringove mašine, odnosno ako je moguće definisati jedan tip
Tjuringove mašine onda je moguće definisati i ekvivalentne mašine ostalih tipova. Jedini problem u
svemu ovome je to što model Tjuringove mašine podrazumeva beskonačnu memoriju, što je u praksi
praktično nije izvodljivo. Zbog toga Tjuringova mašina ostaje samo teorijski model a u praksi se koriste
automati sa konačnim memorijama, što kao posledicu ima ograničenje jezika koji se mogu prepoznavati.
Može se reći da je pojam Tjuringove mašine ekvivalent pojmovima algoritam i jezici tipa nula. To znači
da se sva algoritamska preslikavanja mogu opisati jezicima tipa nula, pri čemu je moguće definisati
odgovarajuću Tjuringovu mašinu za prpoznavanje jezika.
