Test

Question 1

Nabroj vrste programskih prevodioca

Answer 1

Asembleri
Makroasembleri
Prevodioci jezika viseg nivoa
Hibridni prevodioci
Multijezicki prevodioci

Question 2

Sta su asembleri?

Answer 2

Asembleri su programski prevodioci koji se koriste za prevodjenje zapisa sa nivoa asemblerskog jezika na masinski nivo.
Asemblerski jezik je jako sličan mašinskom kodu tako da su asembleri imali zadatak da simboličke oznake pisane u kodu preslikaju u odgovarajuće binarno kodirane reči koje računar razume i može da izvršava.

Question 3

Sta su makroprocesori I koji su njihovi sastavni delovi?

Answer 3

Makroprocesor prepoznaje definicije makroa u kodu i vrši razvoj makroa u svakoj tački poziva makroa - prepisuje njegovo telo odnosno skup asemblerskih instrukcija i nakon toga asembler vrši dalje prevođenje.
Izvesne sekvence naredbi se često ponavljaju u programu zato se pojavljuju makroasemblerski jezici koji omogućavaju da se definišu makroi, odnosno da se skupovi asemblerskih naredbi zamene jednom instrukcijom - definiše se makro koji će se posle u programu pozivati.
Makroi su preteče potprograma u višim programskim jezicima.
Osnovni delovi su: makroprocesor I asembler.

Question 4

Navesti razliku izmedju kompilatora I interpretatora.

Answer 4

Kompilator prevodi ceo kod odjednom i formira izvršnu verziju koja može da se poziva na izvršenje proizvoljan broj puta bez ponovnog prevođenja.
Interpretator prevodi deo po deo programa i čim kreira celinu koja može da se izvrši izvršava je i taj deo prevedenog koda se briše iz memorije i prelazi se na sledeći - to je dobro za kratke programe koji se neće više puta pozivati.
Problem - ako imamo neke glomazne petlje za svaku iteraciju bi se program ponovo prevodio i potprogrami isto
Zato se sve više koriste just in time kompilatori - čim se prevede celina koja moze da se izvrši ona se izvršava, ali se prevedeni deo koda ne briše iz memorije.

Question 5

Sta podrazumevamo pod hibridnim prevodiocima?

Answer 5

Omogućavaju da se isti kod izvršava na različitim platformama - isti međukod može da se distribuira različitim mašinama i posle se različitim interpretatorima prevodi u mašinske jezike odredišnih mašina.
Danas se često umesto interpretatora (jer je spor) stavlja just in time compiler.
Vrše analizu koda kao kompilatori, generišu međukod programa i nakon toga interpretiraju taj međukod.

Question 6

Objasniti visejezicke prevodioce.

Answer 6

Nastali su da se olakša proces prevoženja.
Svaki jezik za koj se piše prevodilac se prevodi u zajednički identičan međukod. Tako da se prve faze, koje su nezavisne od odredišne mašine, ali su zavisne od izvornog jezika, pišu za svaki jezik ponaosob, a onda se takođe ponaosob vrši prevođenje međukoda za svaku odredišnu mašinu.
Za .NET je karakteristično da se u drugoj fazi umesto interpretatora koriste just in time kompajleri

Question 7

Nabroj osnovne faze u procesu prevodjenja visih programskih jezika.

Answer 7

Osnovne faze su:
Leksička analiza – leksički analizator analizira znak po znak naredbe i identifikuje leksičke celine (lekseme), pri čemu svaku leksemu zamenjuje odgovarajućim simbolom (tokenom - koj predstavlja njeno jedinstveno značenje u kodu). On izdvaja reči iz ulaznog koda i određuje njihovo značenje
Sintaksna analiza – zadatak sintaksnog analizatora je da utvrdi da li je ulazni kod napisan u skladu sa pravilima jezika. Ta pravila se definišu formalnim gramatikama. Izlaz iz sintaksnog analizatora je sintaksno stablo koje nam kaže kako je kod sagrađen i ključno je, jer se sve ostale faze oslanjaju na njega.
Semantička analiza – sintaksni analizator može da bude obogaćen dodatnim semantičkim procedurama. Proverava da li su prepoznate sintaksne celine međusobno usaglašene.
Kako mogu da ne budu usaglašene?
ako nedostaje deklaracija promenljivih
ako su operacije primenjene na nedozvoljenim tipovima podataka
ako koristimo promenljivu koja nije inicijalizovana
Generisanje međukoda – međukod programa se generiše iz apstraktnog sintaksnog stabla, svaki čvor se preslikava u naredbu, prvo se izvršavaju akcije koje su niže u stablu.
može da se izvršava u dve faze:
prvo prevođenje u međukod visokog nivoa koj je bliži sintaksnom stablu,
pa onda u međukod niskog nivoa koj je bliži asemblerskim jezicima
Pošto sintaksno stablo sadrži čvorove koji nisu bitni za dalji tok prevođenja radi se redukcija na apstraktno sintaksno stablo - izbacuju se čvorovi koji ne definišu nikakvu obradu podataka.
Optimizacija međukoda – mnogo je lakše optimizovati međukod
Generisanje koda – na osnovu međukoda generiše se ciljni kod programa. To može da bude zapis u asemblerskom jeziku ciljne mašine ili direktno mašinski jezik.

Question 8

Sta se podrazumeva pod apstraktnom (formalnom) azbukom?

Answer 8

Apstraktna (formalna) azbuka, ili samo azbuka, je svaki konačan neprazan skup simbola V.
Simbol (znak ili slovo) je osnovni (nedeljivi) element jezika.
Npr. Azbuku V čine sledeći simboli:
Mala i velika slova abecede A,a,B,b,C,c …
Specijalni znaci +, -,*, :=, …
Reči kao što su if, while, class, …
konstante
identifikatori
operatori…
Formalni jezici se definišu u 2 nivoa:
prvo se definišu leksički elementi - reči
a onda reči predstavljaju azbuku za definisanje sintakse programskog jezika

Question 9

Formalna definicija reci.

Answer 9

Reč - konačan broj redom napisanih simbola azbuke V.
Niz koji ne sadrži nijedan simbol naziva se prazna reč i označava sa ε.
Reči su uređeni nizovi tako da je ab ≠ ba
Reč se može I formalno definisati sledećim skupom pravila:
ε je reč nad azbukom V
Ako je x reč azbuke V i ako je a element azbuke V tada je i xa reč azbuke V
y je reč nad azbukom V ako i samo ako je dobijen pomoću pravila 1 i 2

Za označavanje reči koriste se obično završna mala slova abecede: u, v, w, x, y, z
| x | je dužina reči x.
| ε | = 0

x | je dužina reči x. | ξ | = 0

Question 10

Operacije nad recima.

Answer 10

Spajanje (konkatenacija) reči – proizvod - 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 recč nadovezuje druga reč.
X=aA, y=ab, z=xy=aAab ,
εx = xε = x , ε je neutralni element za operaciju množenja reči

Stepen (eksponent)
xxx…x = xn, x0 = ε , x1 = x, x2 = xx …

Delovi reči:
prefiks - Niz koji se dobija kada se izbaci nula ili više simbola na kraju reči x (može da bude i ε),
sufiks - Niz koji se dobija izbacivanjem nula ili više početnih simbola reči x (može da bude i ε),
podniz - reč koja se dobija kada se izbaci neki prefiks i/ili neki sufiks reči x (svaki prefiks i svaki sufiks reči x su podnizovi reči x, ali podniz može da bude i neki središnji deo reči, a i ε),
pravi prefiks, pravi sufiks, pravi podniz - svaki neprazan niz y koji je prefiks, sufiks ili podniz reči x, takav da je x različito od y
podsekvenca - svaki niz koji se dobija izbacivanjem nula ili više sukcesivnih simbola iz reči x

Question 11

Pojam formalnog jezika.

Answer 11

Formalnim jezikom L nad azbukom V naziva se bilo koji skup reči nad tom azbukom.
Odnosno bilo koj podskup skupa svih mogućih reči kreiranih nad datom azbukom V.
Prema ovoj definiciji formalni jezik je i prazan skup reči kao i skup { ε } koji sadrži samo reč ε i skup koj sadrži sve moguće reči sagrađene od simbola date azbuke.

Ograničenje koje će reči pripadati nekom jeziku definišemo preko formalnih gramatika.
Neka je data azbuka V. Skup svih reči nad azbukom V se označava sa V. Skup V je beskonačan.
Formalni jezik nad azbukom V je bilo koji podskup skupa V. L ⊆ V

Bilo koji podskup reci nad azbukom V, bilo da je konacan ili beskonacan, predstavlja jezik.Kako je V* uvek beskonacan skup, broj njegovih podskupova je takodje beskonacan. Drugim recima, ma koliko da je azbuka siromasna, cak I kada se sastoji samo od jednog simbola, nad njim se moze definisati beskonacan broj razlicitih formalnih jezika.

Question 12

Osnovne operacije nad jezicima.

Answer 12

Ako je L formalni jezik onda se može definisati i njegov reverzni jezik u oznaci LT, kao skup svih reverznih
(transponovanih) reči jezika L. Ovo je korisno jer neki algoritmi analiziraju kod sa kraja prema početku.
LT ={xT | x∈ L} (xa)T = axT
Ako su L i M formalni jezici, onda je L ∪ M, 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 koje 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 ε . L1 npr. su sve reči dužine 1, L su sve reči proizvolje dužine.

∞
L* = ∪Li
i=0

Pozitivno zatvaranje jezika L, za koje se koristi oznaka L+ (skup svih reči čija je dužina > 0, odnosno ne sadrži ε):
∞
L+ = ∪Li
i=1
V+ = V*\ ε

Question 13

Definicija formalne gramatike.

Answer 13

Formalna gramatika je sredstvo za opis jezika na konačan način.
Gramatika jezika opisuje kako se generišu reči koje pripadaju određenom jeziku.
Formalna gramatika je uređena četvorka koja sadrži G=(Vt, Vn, S, P) pri čemu važi

P je skup smena oblika: x->y

i važi da se u produkcionim pravilima na levoj strani uvek mora pojaviti bar jedan neterminalni simbol, a na desnoj strani je reč sastavljena iz bilo kojih simbola (neterminalnih i terminalnih).

Elementi gramatike su simboli pomoću kojih se gradi kod:
* Terminalni simboli – Osnovni simboli od kojih se satoje reči jezika. Npr. ključne reči nekog programskog jezika if, then, else su terminalni simboli. reči napisane boldiranim fontom
* Neterminalni simbol – Pomoćni (sintaksni) simboli kojima se označavaju skupovi reči. Neterminali se uvode da bi se lakše definisao jezik koji se generiše gramatikom, kao i da bi se lakše definisala hierahijska struktura jezika. reči napisane malim slovima italik ili između zagrada <>
* Startni simbol – Neterminalni simbol iz kojeg se izvode sve reči jezika koji se definiše. (simbol na levoj strani prve smene)
* Produkciono pravilo (smena) – definiše način na koji se stvaraju nizovi koji mogu da se sastoje od neterminala i terminala. U opštem slučaju pravila su oblika: x ::= y ili x -> y
na levoj strani smene je uvek jedan neterminalni simbol a na desnoj je bilo koja reč sastavljena od terminalnih i neterminalnih simbola pa i ε.

Question 14

Jezik definisan formalnom gramatikom.

Answer 14

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:
L(G) = {w S ⎯⎯→w, w ∈ V}

Question 15

Tipovi gramatika po Comskom.

Answer 15

Još u svojim ranim radovima Chomsky je formalne je identifikovao četiri 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 tipovima gramatika 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 koje 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 A∈ Vn i y∈ Vt*
Za opis programskih jezika se obično koriste beskonteksne gramatike. Za ove gramatike se koristi i naziv Bekusova normalna forma BNF i najčešće se koriste za opis sintakse programskih jezika.

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 A,B∈ Vn i a∈ Vt
Za ove gramatike se koriste još i nazivi Regularne gramatike, Gramatike sa konačnim brojem stanja i
Automatne gramatike.
Služe za opis leksičkih elemenata jezika.
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.

Question 16

Opsta definicija automata za prepoznavanje jezika.

Answer 16

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

Question 17

Tjuringova masina.

Answer 17

Za razliku od opšteg modela automata Tjuringova mašina ima radnu memoriju u vidu beskonačne trake.
Operativni organ menja stanje. * Ulazna glava se pomera. * Na radnu traku se upisuje novi simbol. * Pomera se radna glava. 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:
Q×(V∪#) ×S →{Q×(S {b})×{−1,0,+1}×{−1,0,+1}}
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 izvrš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).
TM je deterministicka ako se svaki element (q,a,X) preslikava u najvise jedan element (P, Y, d1, d2)
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.

Question 18

Linearno ograniceni automati I koje jezike prepoznaju

Answer 18

Linearno ograničeni automati su u suštini Tjuringove mašine sa konačnom trakom kao radnom
memorijom. Naime 2N Tjuringova mašina kod koje može da se odredi konstanta k takva da je dužina reči koja se upisuje na radnu traku najviše k puta veća od dužine reči koja se prepoznaje, naziva se Linearno ograničenim automatom.
Odnosno, ako se prepoznaje reč w ∈ V, gde je |w|= n, na radnu traku se upisuje reč dužine r, pri čemu je r ≤ nk

Posledica ovog ograničenja je da Linerano ograničeni automati ne prepoznaju sve jezike tipa nula. Odnosno, postoje jezici tipa nula za koje nije moguće definisati linearno ograničeni automat. Naime dokazana su sledeća tvrđenja:
Klase 2N i 1N Linearno ograničenih automata su međusobno ekvivalentne i svaka od njih prepoznaje jezike tipa jedan. Drugim rečima, za svaki jezik tipa jedan može se definisati
nedeterministički LOA koji ga prepoznaje.
Klase 2D i 1D Linearno ograničenih automatu su međusobno ekvivalentne. To znači da se za svaki 2D LOA može definisati ekvivalentan 1D LOA.
Ekvivalentnost 2N i 2D LOA do sada nije dokazana.
Svaka klasa LOA ne prepoznaje sve jezike tipa jedan.

Question 19

Magacinski automati.

Answer 19

Magacinski automat kao radnu memoriju koristi memoriju organizovanu u vidu magacina. 2N Magacinski automat je definisan entorkom Ma=(Q, V, S, P, q0, Z0, F) gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
S – Skup magacinskih simbola
F – Skup završnih, krajnjih stanja (Podskup skupa Q)

q0 – Početno stanje operativnog organa
Z0 – Početni simbol na vrhu magacina
P – Preslikavanje definisano sa:
Q ×(V∪#) × S →{Q × S* ×{−1,0,+1}}
1N magacinski automat prepoznaje jezik L ako i samo ako je L beskonteksni jezik tipa 2.

2N i 2D magacinskim automatima mogu se prepoznavati svi beskontesni i neki, ali ne svi, konteksni jezici.
Postoje beskonteksni jezici koji se ne mogu prepoznati 1D magacinskim automatima.
Magacinski automati se koriste u sintaksnoj analizi programskih jezika

Question 20

Konacni automati.

Answer 20

Konačni automati su uređaji za prepoznavanje regularnih jezika. Za razliku od drugih tipova nemaju radnu memoriju već se predistorija preslikavanja pamti samo preko promene stanja funkcionalnog organa
Kod dvosmernih, Na osnovu stanja operativnog organa i simbola koji čita ulazna glava, menja se stanje automata i ulazna glava pomera za jedno mesto ulevo ili udesno ili ostaje na svom mestu. Kod jednosmernih menja se samo trenutno stanje automata.

Konačan automat je opisan entorkom Ka=(Q, V, P, q0, F), gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
F – Skup završnih, krajnjih stanja (Podskup skupa Q)
q0 – Početno stanje operativnog organa
P – Preslikavanje pravilima oblika: Q × {V ∪ #} → Q
Za ulazni niz w∈ V*, kažemo da je prepoznat automatom ako automat prevodi iz početnog u neko od
njegovih krajnjih stanja, odnosno ako je P(q0, w) ∈ F.
Za predstavljanje automata se koriste grafovi, pri čemu čvorovi grafa odgovaraju stanjima automata, a potezi preslikavanjima. Na Slici 3.5 je predstavljen graf koji odgovara automatu iz primera. Početno stanje automata je označeno strelicom, a krajnje stanje sa dva koncentrična kruga.
Kako se preslikavanje P(qi,a)=qj može tumačiti da se stanje qi automata za ulazno slovo a preslikava u stanje qj, svako takvo preslikavanje se na grafu predstavlja odlaznim potegom od stanja qi do stanja qj na kome je oznaka a.

Question 21

Razlika izmedju deterministickih I nedeterministickih konacnih automata.

Answer 21

Podela na determinističke i nedeterminističke izvršena je u odnosu na preslikavanje stanja funkcionalnog organa koje se vrši u toku prepoznavanja .
Deterministicki – pod dejstvom istog ulaznog simbola prelazi u jedno stanje.
Nederministicki – pod dejstvom istog ulaznog simbola prelazi u vise stanja.
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.

Question 22

Pojam regularnog izraza I nekoliko primera

Answer 22

Jezici tipa tri koji se prepoznaju konačnim automatima se nazivaju i regularnim jezicima zato što se mogu opisati regularnim izrazima.
Ovde ćemo posvetiti malo više pažnje pojmu regularni izraz. Oni se mogu posmatrati i kao meta jezici za predstavljanje formalnih jezika.
Regularni izrazi u suštini definišu skup reči jezika. Sami regularni izrazi su nizovi formirani od slova neke azbuke V i skupa specijalnih simbola. Regularni izraz obično skraceno definiše skup reči jezika definisanog nad azbukom V. Postoje posebna pravila kako se vrši tumačenje (denotacija) regularnog izraza i generisanje skupa reči jezika koji je opisan regularnim izrazom.
Regularni izrazi su veoma korisni za formalno i koncizno definisanje jezika. Kada je jezik konačan moguće je nabrojati sve reči koje sadrži, ali u slučaju beskonačnih jezika to postaje problem. Zbog toga se
regularni izrazi i koriste u različitim disciplinama kao sredstvo za opis kompleksnih jezika. Na žalost, ne

mogu se svi formalni jezici opisati regularnim izrazima. To je moguće samo u slučaju jezika tipa tri, zbog čega se oni i nazivaju regularnim. Sledeći primer ilustruje moć regularnih izraza da definišu beskonačne i kompleksne jezike.

Question 23

Pokazati kako se osnovni regularni izrazi preslikavaju u automate.

Answer 23

Za svaki regularni izraz se može definisati konačni automat koji ga prepoznaje.

Question 24

Formalna definicija regularnog izraza nad azbukom V.

Answer 24

Regularni izraz nad azbukom V definise se sledecim skupom pravila:
Prazan skup je regularni izraz
ε je regularni izraz
Ako je a ∈ V , tada je a regularni izraz
Ako su r1 i r2 regularni izrazi, onda su i (r1|r2) i (r1 ∘ r2) regularni izrazi
Ako je r regularni izraz onda je I r* takodje regularni izraz
Nema drugih regularnih izraza nad azbukom V

Question 25

Zadaci leksickog analizatora.

Answer 25

Leksičkim analizatorom se realizuje faza leksičke analize u procesu prevođenja jezika. Odnosno, u kodu se identifikuju leksičke celine koje imaju neki sintaksni smisao, transformišu se u simbole (tokene) i prosleđuju se sintaksnom analizatoru.
Pored ove osnovne uloge leksički analizator obavlja još neke zadatke:

Izbacuje iz ulaznog koda delove koji nisu značajni za sintaksnu analizu: komentare, praznine (blanko znake), tab i newline simbole.
Usklađuje listing grešaka sa ulaznim kodom. Npr. vodi računa o broju newline simbola, što se koristi kod referenciranja na greške.

Question 26

Razlika izmedju lekseme, tokena I sablona.

Answer 26

Leksema – izdvojena rec, ulazni niz koji se prepoznaje na osnovu formalnog opisa pomocu sablona I za koji se generise odredjeni token
Token – znacenje izdvojene reci, izlazni simbol koji se generise kada je prepoznat odredjeni ulazni niz znakova.
Sablon – regularni izraz, formalni opis ulaznih nizova za koje se generise odredjeni token.

Question 27

Grafovi automata za prepoznavanje osnovnih oblika regularnih izraza

Answer 27

Za svaki regularni izraz se moze definisati konacni automat koji ga prepoznaje.

Question 28

Zadatak sintaksnog analizatora I podela algoritama za sintaksnu analizu.

Answer 28

Sintaksni analizator prima niz tokena od leksičkog analizatora i proverava da li taj niz pripada jeziku koji je opisan zadatom gramatikom. Cilj sintaksnog analizatora je da generiše sintaksno stablo za ulazni niz tokena.
U odnosu na to kako obavljaju sintaksnu analizu postoje dva tipa sintaksnih analizatora:
(algoritmi)
Top-down analizatori koji vrše analizu odozgo naniže (kreće od startnog simbola i pokušava da primenom konačnog broja smena taj startni simbol preslika u kod koj se analizira)
Sleva nadesno (krajnje levo izvođenje)
Zesna nalevo (krajnje desno izvođenje)
ukoliko se dobija isto sintaksno stablo gramatika je regularna (ekvivalentna jednoznačna gramatika) ako ne gramatika je NEJEDNOZNAČNA (ispravno je sintaksno stablo zdesna nalevo)
levo asocijativni operatori * i +
desno asocijativni operatori =
prioritetniji operatori moraju da budu niže u sintaksnom stablu
Bottom-up analizatori koji vrše analizu odozdo naviše (polazi od ulaznog koda i vrši redukciju koda na startni simbol gramatike)

Question 29

Objasnite opšti top-down algoritam za sintaksnu analizu.

Answer 29

U slučaju Top-down analize polazi se od startnog simbola i nastoji se da se odrede pravila koja treba primeniti da bi se generisala reč čija se analiza vrši. To znači da se pravila otkrivaju u redosledu u kom se i primenjuju prilikom generisanja reči, odnosno odozgo naniže ako se to posmatra na sintaksnom stablu.
Kod ovog postupka analize krece se od startnog simbola I bira se prvo pravilo kojim se startni simbol preslikava u neku fazu. Posle toga u svakom koraku se nastoji da se prvi neterminalni simbol sa leve
strane zameni desnom stranom prvog raspolozivog pravila za taj neterminalni simbol. Prakticno, nastoji se da se generise analizirani niz levim izvodjenjem. Ukoliko na nekom koraku ne postoji odgovarajuca
smena, vracamo se natrag do nivoa na kome je primenjeno poslednje pravilo I trazimo alternativno pravilo koje moze da se primeni. Analiza je uspesna ako se kao rezultat ovog postupka dobije niz koji se analizira. Ako se vracanjem unazad ponovo dodje do startnog simbola gramatike I vise nema novih
alternativa za zamenu tog simbola, postupak analize je neuspesan.

Ovakav algoritam može da bude prilično neefikasan zato se prave algoritmi bez vraćanja.

Question 30

Problem leve rekurzije I kako se resava.

Answer 30

Top-down sintaksnom analizom se generiše skup smena čiji redosled primene odgovara levom izvođenju. Zbog toga ovaj postupak analize ne može da se primeni kod tzv. levo rekurzivnih gramatika. Levo rekurzivne gramatike su gramatike kod kojih postoje levo rekurzivna pravila, odnosno pravila oblika:
A → Ar, gde je A∈ Vn, a r∈ V*
Kod ovakvih pravila preslikavanjem neterminala A dobija se reč koja opet počinje istim neterminalom, i to se iz koraka u korak ponavlja, odnosno ulazi se u jednu beskonačnu petlju, tako da analizu nije moguće završiti.
Resenje:
Svaku levu rekurzivnu gramatiku moguce je transformisati u ekvivalentnu nerekurzivnu gramatiku. Ako gramatika sadrzi skup pravila za isti neterminalni simbol, medju kojima su neka levo rekurzivna, a neka ne:
A -> A α1 | A α2 |… | A αn | β1 | β2 | … | βm
Ovaj skup pravila moguce je zameniti sledecim skupom nerekurzivnih pravila A -> β1 | β2 | … | βm | β1 A’| β2 A’| … | βm A’
A’ -> α 1 | α 2 | … | α n | α 1 A’| α 2 A’| … | α n A’ Moguca je I sledeca transformacija:
A -> β1 A’| β2 A’| … | βm A’
A’ -> α 1 A’| α 2 A’| … | α n A’ |ξ

u ovakvim situacijama top-down algoritam nije primenljiv i gramatiku treba nekako transformisati - eliminacija (oslobažanje od) levo rekurzivnih smena
kada postoji rekurzivna smena u gramatici mora da postoji i jedna ne rekurzivna koja treba da prekine rekurziju
desno rekurzivna smena A’ -> α 1 A’
ξ nije pogodno za neke gramatike pa postoji alternativna eliminacija rekurzije bez njega
A -> Aα | β

A -> β A’ A -> β | β A’ da se beta javlja samo ili sa alfa (nizom alfa)
A’ -> α A’ | ξ A’ -> α | αA’

Question 31

Osnovna ideja LL (k) algoritama za sintaksnu analizu.

Answer 31

Osnovni problem kod polaznih algoritama za sintaksnu analizu je veliki broj povratnih koraka tako da je sam postupak analize dosta dug i neizvestan. Efikasni analizatori za top-down analizu koji u svakom koraku vrse neku vrstu predikcije na osnovu koje odlucuju koje ce se pravilo primeniti. Smene se
otkrivaju direktno bez povratnih petlji.
Kod ovih analizatora odluku o pravilu koje ce da se primeni se donosi i na osnovu slova u ulaznom nizu koje treba da se prepozna, na kome je trenutno ulazni pokazivac. Primenjuje se pravilo koje ce sigurno da generise bar to slovo. Ovakvi analizatori su poznati kao LL (1) analizatori (Look-Left 1), gde cifra 1 ukazuje na to da se predikcija vrsi na osnovu jednog slova u nizu.
Generalno gledano, mogu da se definisu i LL-k analizatori kod kojih se predikcija vrsi na osnovu reci duzine k, ali su LL-1 mnogo upotrebljiviji.

Ograničenje koja treba da zadovolje smene gramatike:
Ukoliko za preslikavanje jednog neterminalnog simbola postoji veći broj smena, na osnovu sledećih k ulaznih simbola koje treba dobiti jednoznačno je određeno koja će se smena primeniti.

Na početku analize se u radni magacin upisuje granični simbol (#) i startni simbol gramatike, zatim se na osnovu simbola sa vrha radnog magacina i tekućeg ulaznog simbola iz LL(1) sintaksne tabele čita akcija koja će biti izvršena.

Question 32

Formalna definicija prostih LL(1) gramatika.

Answer 32

Proste LL-1 gramatike su beskonteksne gramatike kod kojih sve smene za isti neterminalni simbol počinju različitim terminalnim simbolima:
A → a1α1 | a2α2 |…| anαn gde je ai ∈ Vt , αi ∈ V*,∧ ai ≠ a j za i ≠ j

Question 33

Leva faktorizacija.

Answer 33

Pokazali smo da se u slučaju LL-1 gramatika može vršiti prediktivna sintaksna analiza koja je mnogo efikasnija od osnovnog algoritma za sintaksnu analizu. Veoma značajno u svemu tome je da se gramatike koje ne zadovoljavaju uslov LL-1 gramatika mogu jednostavno transformisati u ovaj tip gramatika. Naime, ukoliko u gramatici postoji veći broj pravila za isti neterminalni simbol koja na desnoj strani imaju reči sa istim prefiksom, odnosno smene oblika:
A → αβ1 | αβ2 |…| αβn | γ

gde su α, β1, β2 ,, βn ,γ ∈V * i
A∈Vn ,

takva gramatika sigurno nije LL-1 gramatika. Međutim ona se transformiše u LL-1 gramatiku sledećom smenom:
A → αA’| γ
A’→ β1 | β2 | … | βn

uvedena je leva faktorizacija da se reši problem što desna strana više smena počinje istim prefiksom

Question 34

FIRST I FOLLOW funkcije

Answer 34

Ukoliko postoji smena oblika X → α, definiše se funkcija FIRST(α) koja sadrži sve terminalne simbole koji mogu da se nađu na početku reči izvedenih iz niza α, tj:
Ako jeα ∈ V +
FIRST (α ) = {a | α ⎯⎯*→ aβ , a ∈ V , β ∈ V *}

Funkcija FOLLOW se definiše za neterminalne simbola, kao skup terminalnih simbola koji mogu u toku izvođenja da se nađu iza tog neterminalnog simbola, ili:
FOLLOW ( A) = {a ∈ V | S’ ⎯⎯*→αAγ , A, S’∈ V , γ ∈ V + }
gde je a ∈ FIRST(γ ) i S’ startni simbol gramatike.
Po definiciji FOLLOW funkcija startnog simbola gramatike sadrži granični simbol #.
Za odredjivanje FOLLOW funkcije neterminalnog simbola X posmatraju se desne strane pravila u kojima se pojavljuje posmatrani simbol. Pri tome simbol X na desnoj strani smene može da se nađe u jednom od sledećih konteksta:

Z → α X xβ ∧ x∈Vt ⇒ x∈FOLLOW(X)
Z → α XYβ ∧ Y∈Vn ⇒ FIRST(Y)⊂FOLLOW(X)
Z → α X ⇒ FOLLOW(Z)⊂FOLLOW(X)

FIRST () - Skup terminalnih simbola koji mogu da se pojave na početku reči izvedenih iz date smene .
FOLLOW fja je uvedena da bismo mogli da odredimo kada treba primeniti ξ smenu
FOLLOW je skup terminalnih simbola koji u razvoju mogu da se nađu iza posmatranog neterminala
Nalazimo taj neterminalni simbol na desnoj strani smena i imamo 3 situacijeČ
iza njega se nalazi terminalni simbol
iza njega se nalazi neki neterminalni simbol
nalazi se na kraju smene

Question 35

Formalna definicija LL (1) gramatike bez ξ

Answer 35

Beskonteksna gramatika bez ε pravila je LL-1 gramatika ako su za sva pravila za isti neterminalni simbol oblika:

A →α1 | α 2 |…| αn skupovi
FIRST(α1 ), FIRST(α2 ),…, FIRST(αn )
disjunktni po parovima, odnosno:

FIRST(αi ) ∩ FIRST(αj ) = Φ,
i ≠ j.

Question 36

Formalna definicija LL (1) gramatika sa ξ pravilima.

Answer 36

Beskonteksna gramatika koja sadrzi ξ je LL-1 gramatika ako I samo ako za sva pravila oblika
A →α1 | α 2 |…| αn i A -> ξ vazi:
FIRST(αi ∘ FIRST(A)) Ո FIRST(αj ∘ FIRST(A)) = prazan skup
Za svako .. gde je simbolom ∘ oznacena operacija nadovezivanja. Ovaj uslov moze da se iskaze I na sledeci nacin:

Za sva pravila
A →α1 | α 2 |…| αn treba da vazi:

FIRST(αi) Ո FIRST(αj) = prazan skup za svako i ≠ j

Ako je αi -> ξ , tada mora da vazi i:
FIRST(αj) Ո FOLLOW(A) = prazan skup

|w| <= 1 - znači da može da bude terminalni simbol dužine 1 ili 0 - prazna reč
SAD se menja definicija FIRST funkcije Č FIRST funkcija sadrži terminalne simbole koji se nalaze na početku reči izvedenih iz posmatrane smene ili praznu reč ukoliko smena može da se preslika u praznu reč

MORA DA VAŽI
ako imamo više smena za preslikavanje neterminalnog simbolaČ
FIRST fje svih smena moraju da budu međusobno disjunktne - to važi i bez Epsilon smena
ako se neka od tih smena preslikava u prazan niz A SME SAMO 1
FIRST fja za ostale smene mora da bude disjunktna sa FOLLOW fjom za neterminal sa leve strane
ZAŠTO? zato što će se eps smena primenjivati kada se pojavi neki od simbola koji pripada FOLLOW skupu zato FOLLOW ne sme da saadrži iste simbole kao FIRST fja

Question 37

LL (1) sintaksna tabela.

Answer 37

Za sintaksnu analizu jezika definisanih LL-1 gramatikama koristi se magacinski automat I sintaksna tabela kao pomocna struktura.
U opštem slučaju Sintaksna tabela se sastoji od onoliko kolona koliko ima terminalnih simbola, a onoliko vrsta koliko ima neterminalnih i terminalnih simbola zajedno.
Polja tablice sintaksne analize se popunjavaju tako da se u polju koje odgovara neterminalu A, i terminalu a, upisuje smena koja na levoj strani ima neterminal A, a na desnoj strani reč koja počinje terminalom a, ako takva smena postoji. U preseku vrste koja je označena terminalom i kolone koja je označena istim tip terminalom upisuje se vrednost pop, dok se u preseku vrste i kolone koje su označene graničnim
simbolom # upisuje vrednost accept. Sva ostala polja su polja greške. Sintaksna tabela T(A, a), gde je A oznaka vrste, a a oznaka kolone se formalno može definisati na sledeći način:

⎧ pop
ako je A = a, a ∈ Vt ⎫

⎪ acc
Ts( A, a) =
ako je A =#∧a ∈# ⎪

⎨(aα , i) ako je A ⇒ aα i − to pravilo⎪
⎪⎩ err u svim ostalimslucajevima ⎪⎭

Question 38

LL (1) algoritam za sintaksnu analizu

Answer 38

Isto kao 29

Question 39

Opsti bottom-up algoritam za sintaksnu analizu.

Answer 39

U slučaju Bottom-Up analize primenjuje se postupak redukcije reči koja se analizira. Osnovni algoritam za analizu se sastoji u tome što se ulazni niz analizira slovo po slovo od početka prema kraju i nastoji se da se neki njegov podniz prepozna kao desna stana nekog od raspoloživih pravila gramatike. Kada se takav podniz pronađe vrši se njegova redukcija na levu stranu primenjene smene i postupak nastavlja sve dok se niz ne redukuje na startni simbol. Kao i kod osnovnog algoritma za Top-down analizu i ovde ima vraćanja unatrag i poništavanja primenjenih smena u slučaju kada dođe do greške i ne može da se ide dalje sa analizom.
Pri realizaciji ovog algoritma koristi se magacin u koji se ubacuje slovo po slovo iz ulaznog niza. Pri tome se u svakom koraku ispituje da li je moguće izvršiti redukciju niza (po nekoj smeni - da li se ono što je na vrhu magacina anlazi sa desne strane neke smene) koji je u vrhu magacina. Ako redukcija nije moguća u magacin se ubacuje novo slovo, a ako je moguća prepoznati niz sa vrha magacina se redukuje na neterminal koji je na levoj strani primenjene smene, odnosno neterminal zamenjuje redukovani niz u magacinu. Analiza je uspešno izvršena kada se dođe do graničnog simbola a u magacinu ostane samo startni simbol.

ako ne može u njemu postoji sintaksna greška