• Adresa. Funkcionalni uređaj koji virtualnu adresu (eng. Virtual address) pretvara u stvarnu adresu.
• Dijalog. Omogućuje korištenje programskog jezika u načinu dijeljenja vremena.
• višeprolazni. Generira objektni modul preko nekoliko prikaza izvornog programa.
• leđa. Isto kao relej. Vidi također: decompiler, disassembler.
• jedan prolaz. Generira objektni modul u jednom sekvencijalnom skeniranju izvornog programa.
• Optimiziranje. Izvodi optimizacije koda u generiranom objektnom modulu.
• Sintaksički orijentiran (pokrenut sintaksom). Kao ulaz prima opis sintakse i semantike jezika te tekst na opisanom jeziku, koji se prevodi u skladu s navedenim opisom.
• test. Skup makronaredbi asemblerskog jezika koji vam omogućuju postavljanje različitih postupaka otklanjanja pogrešaka u programima napisanim asemblerskim jezikom.

Svrha emitiranja- pretvarati tekst s jednog jezika na drugi, koji je razumljiv primatelju teksta. Kod programa prevoditelja adresat je tehnički uređaj (procesor) ili program tumač.

Jezik procesora (strojni kod) obično je niske razine. Postoje platforme koje se koriste kao strojni jezik visoka razina(primjerice, iAPX-432), ali oni su iznimka od pravila zbog složenosti i visoke cijene. Poziva se prevoditelj koji pretvara programe u strojni jezik koji prihvaća i izvršava izravno procesor sastavljač.

Proces kompilacije obično se sastoji od nekoliko faza: leksičke, sintaktičke i semantičke analize (engleska semantička analiza), generiranje međukoda, optimizacija i generiranje rezultirajućeg strojnog koda. Osim toga, program obično ovisi o uslugama koje pruža operativni sustav i biblioteke trećih strana (na primjer, datoteka I/O ili GUI), a izvorni kod programa mora biti povezan s tim uslugama. Povezivanje sa statičkim bibliotekama vrši povezivač ili povezivač (koji može biti samostalni program ili dio prevoditelja), dok se povezivanje s operativnim sustavom i dinamičkim bibliotekama vrši kada loader počne izvršavati program.

Prednost prevoditelja: program se prevodi jednom i nisu potrebne dodatne transformacije za svako izvođenje. Sukladno tome, prevoditelj nije potreban na ciljnom stroju za koji se program prevodi. Nedostatak: zaseban korak kompilacije usporava pisanje i otklanjanje pogrešaka i otežava pokretanje malih, jednostavnih ili jednokratnih programa.

Druga metoda implementacije je kada se program izvršava sa tumač uopće nema prijevoda. Interpretator programski simulira stroj čija petlja dohvati-izvrši radi na instrukcijama na jezicima visoke razine, a ne na strojnim instrukcijama. Takav softverska simulacija stvara virtualni stroj, koji implementira jezik. Ovaj pristup se naziva čista interpretacija. Čisto tumačenje obično se koristi za jezike s jednostavnom strukturom (na primjer, APL ili Lisp). Tumači naredbeni redak procesne naredbe u skriptama na UNIX-u ili u paketnim datotekama (.bat) na MS-DOS-u, također obično u načinu čistog tumačenja.

Prednost čistog tumača: odsutnost posrednih radnji za prevođenje pojednostavljuje implementaciju tumača i čini ga praktičnijim za korištenje, uključujući i interaktivni način. Nedostatak je taj što tumač mora biti dostupan na ciljnom stroju na kojem se program treba izvršiti.

Postoje kompromisi između kompilacije i čiste interpretacije implementacija programskog jezika, kada tumač, prije nego što izvrši program, prevodi u međujezik (na primjer, u bajt-kod ili p-kod), koji je pogodniji za interpretaciju (tj. govorimo o tumaču s ugrađenim prevoditeljem) . Ova metoda se naziva mješovita implementacija. Perl je primjer implementacije mješovitog jezika. Ovaj pristup kombinira prednosti kompilatora i interpretera ( velika brzina izvođenje i upotrebljivost) i nedostatke (prijevod i pohranjivanje programa na međujeziku zahtijeva dodatne resurse; mora se osigurati tumač za izvođenje programa na ciljnom stroju). Također, kao i u slučaju prevoditelja, mješovita implementacija zahtijeva da izvorni kod ne sadrži pogreške (leksičke, sintaktičke i semantičke) prije izvođenja.

Emitiranje I tumačenje - različite procese: prijevod se bavi prevođenjem programa s jednog jezika na drugi, a tumačenje je zaduženo za izvođenje programa. Međutim, budući da je svrha prevođenja obično pripremiti program za usmeno prevođenje, ti se procesi obično razmatraju zajedno. Na primjer, programski jezici često se karakteriziraju kao "kompilirani" ili "interpretirani", ovisno o tome dominira li u upotrebi jezika kompilacija ili interpretacija. Štoviše, gotovo svi programski jezici niske razine i treće generacije, kao što su asembler, C ili Modula-2, se prevode, a jezici više razine, kao što su Python ili SQL, se interpretiraju.

S druge strane, postoji međusobno prožimanje procesa prevođenja i tumačenja: tumači mogu kompilirati (uključujući dinamičku kompilaciju), a prevoditelji mogu zahtijevati interpretaciju za konstrukcije metaprogramiranja (na primjer, za makronaredbe u asemblerskom jeziku, uvjetnu kompilaciju u C-u ili za predloške u C++).

Štoviše, isti programski jezik može se i prevoditi i tumačiti, au oba slučaja moraju postojati zajedničke faze analize i prepoznavanja konstrukata i direktiva izvornog jezika. Ovo se odnosi i na softverske i na hardverske implementacije - na primjer, procesori obitelji x86, prije izvršavanja instrukcija strojnog jezika, dekodiraju ih, ističući polja operanda (registri, memorijske adrese, neposredne vrijednosti), dubinu bita itd., u operativnim kodovima i u Pentium procesori s arhitekturom NetBurst, strojni kod se općenito prevodi u niz mikrooperacija prije pohranjivanja u internu predmemoriju.

ODJELJAK 7. Prijevod, kompilacija i tumačenje

Program je slijed instrukcija dizajniranih da ih računalo izvrši. Trenutno su programi napisani u obliku teksta koji se upisuje u datoteke. Ovaj tekst rezultat je aktivnosti programera i, unatoč specifičnostima formalnog jezika, ostaje program za programera.

Proces izrade programa uključuje nekoliko faza. Nakon faze razvoja projekta programa slijedi faza programiranja. U ovoj fazi program je napisan. Programeri lakše percipiraju ovaj tekst nego binarni kod, budući da razne mnemoničke kratice i imena sadrže dodatne informacije.

Obrađuje se izvorna datoteka programa (koja se naziva i izvorni modul). prevoditelj , koji prevodi program iz programskog jezika u strojno razumljiv niz kodova.

Prevoditelj - program ili tehnička sredstva, nastupajući emitiranje programa. Strojni program koji prevodi s jednog jezika na drugi i, posebno, s jednog programskog jezika na drugi. Program za obradu dizajniran za pretvaranje izvornog programa u objektni modul.

Prevoditelj obično također provodi dijagnostiku grešaka, generira rječnike identifikatora, ispisuje tekstove programa itd.

Emitiranje programa - transformacija programa predstavljenog na jednom od programskih jezika u program na drugom jeziku i, u određenom smislu, ekvivalentan prvom.

Poziva se jezik na kojem je predstavljen ulazni program izvorni jezik, i sam program izvorni kod. Poziva se izlazni jezik ciljani jezik ili objektni kod.

Vrste prevoditelja

Prevoditelji se dijele na:

· Adresa. Funkcionalni uređaj koji pretvara virtualnu adresu virtualna adresa) na pravu adresu (eng. memorijska adresa).

· Dijalog. Omogućuje korištenje programskog jezika u načinu dijeljenja vremena.

· višeprolazni. Generira objektni modul preko nekoliko prikaza izvornog programa.

· leđa. Isto kao relej. Vidi također: decompiler, disassembler.

· jedan prolaz. Generira objektni modul u jednom sekvencijalnom skeniranju izvornog programa.

· Optimiziranje. Izvodi optimizacije koda u generiranom objektnom modulu.

· Sintaktički orijentiran (sintaktički vođen). Kao ulaz prima opis sintakse i semantike jezika te tekst na opisanom jeziku, koji se prevodi u skladu s navedenim opisom.

· test. Skup makronaredbi asemblerskog jezika koji vam omogućuju postavljanje različitih postupaka otklanjanja pogrešaka u programima napisanim asemblerskim jezikom.

Prevoditelji su implementirani u obrazac sastavljači ili tumači . U smislu obavljanja posla, kompilator i interpreter su vrlo različiti.

Sastavljač(Engleski) sastavljač- compiler, collector) - prevoditelj koji obavlja transformaciju programa prevedenog u izvorni jezik, objektnom modulu. Program koji prevodi tekst jezičnog programa visoke razine u svoj ekvivalentni program strojnog jezika.

· Program dizajniran za prevođenje jezika visoke razine u apsolutni kod ili, ponekad, u asemblerski jezik. Ulazna informacija za prevodilac (izvorni kod) je opis algoritma ili programa u jeziku specifičnom za domenu, a izlaz prevoditelja je ekvivalentan opis algoritma u strojno orijentiranom jeziku (objektni kod).

Kompilacija- prijevod programa napisanog na izvornom jeziku u objektni modul. Implementirao kompilator.

Prevedi - prevesti strojni program s problemski orijentiranog jezika na strojno orijentirani jezik.

Kompajler čita cijeli program u cijelosti, prevodi ga i stvara potpunu verziju programa na strojnom jeziku, koji se zatim izvršava.

Tumač(Engleski) tumač- tumač, tumač) prevodi i izvršava program redak po redak. Interpretator uzima sljedeću jezičnu naredbu iz programskog teksta, analizira njenu strukturu i zatim je odmah izvršava (obično se, nakon analize, naredba prevodi u neku međureprezentaciju ili čak strojni kod za učinkovitije daljnje izvođenje). Tek nakon uspješnog izvršenja trenutne naredbe, tumač će prijeći na sljedeću. Štoviše, ako se ista naredba izvrši više puta u programu, interpretator će je izvršiti kao da se s njom susreo prvi put. Kao rezultat toga, programi koji zahtijevaju veliku količinu računanja radit će sporo. Osim toga, da biste pokrenuli program na drugom računalu, ondje također mora postojati tumač - uostalom, bez njega je tekst samo skup znakova.

Na drugi način možemo reći da tumač modelira neki računalni virtualni stroj za koji osnovne upute nisu elementarne naredbe procesora, već operatori programskog jezika.

Razlike između kompilacije i interpretacije.

1. Nakon što je program preveden, ni izvorni program ni prevodilac više nisu potrebni. U isto vrijeme, program koji tumač obrađuje mora ponovno prijenos u strojni jezik svaki put kada se program pokrene.

2. Prevedeni programi rade brže, ali interpretirane programe lakše je popraviti i promijeniti.

3. Svaki specifični jezik usmjeren je ili na kompilaciju ili na interpretaciju, ovisno o svrsi za koju je stvoren. Na primjer, Pascal obično se koristi za rješavanje prilično složenih problema u kojima je važna brzina programa. Stoga se ovaj jezik obično implementira korištenjem sastavljač.

Na drugoj strani, OSNOVNI, TEMELJNI je stvoren kao jezik za programere početnike, za koje izvođenje programa red po red ima neosporne prednosti.

Gotovo svi programski jezici niske razine i treće generacije, poput asemblera, C ili Modula-2, se kompiliraju, dok se jezici više razine, poput Pythona ili SQL-a, interpretiraju.

Ponekad za jedan jezik postoji i sastavljač, i tumač. U ovom slučaju, možete koristiti tumač za razvoj i testiranje programa, a zatim kompajlirati otklonjeni program kako biste ubrzali njegovo izvođenje. Postoji međusobno prožimanje procesa prevođenja i tumačenja: tumači mogu biti kompilatori (uključujući one s dinamičkom kompilacijom), a prevoditelji mogu zahtijevati interpretaciju za konstrukcije metaprogramiranja (na primjer, makronaredbe u asemblerskom jeziku, uvjetna kompilacija u C ili predlošci u C++).

4. Prevođenje i tumačenje su različiti procesi: prevođenje se bavi prevođenjem programa s jednog jezika na drugi, a tumačenje je odgovorno za izvođenje programa. Međutim, budući da je svrha prevođenja obično pripremiti program za usmeno prevođenje, ti se procesi obično razmatraju zajedno.

Zaključak: Nedostatak prevoditelja je zahtjevnost prevođenja programskih jezika koji su orijentirani na podatke i složene strukture, često nepoznati unaprijed ili se dinamički mijenjaju tijekom rada programa. Zatim morate umetnuti puno dodatnih provjera u strojni kod, analizirati dostupnost resursa operativnog sustava, dinamički ih uhvatiti i otpustiti, formirati i obraditi u memoriji računala. složeni objekti, što je prilično teško implementirati na razini tvrdo kodiranih strojnih instrukcija, i gotovo nemoguće za zadatak.

Uz pomoć tumača, naprotiv, dopušteno je zaustaviti program u bilo kojem trenutku, ispitati sadržaj memorije, organizirati dijalog s korisnikom, izvršiti proizvoljno složene transformacije i istovremeno stalno pratiti stanje okruženje softvera i hardvera, čime se postiže visoka pouzdanost. Prilikom izvršavanja svake naredbe, tumač provjerava mnoge karakteristike operacijskog sustava i, ako je potrebno, informira programera što je moguće detaljnije o problemima koji se pojavljuju. Osim toga, prevoditelj je vrlo prikladan za korištenje kao alat za učenje programiranja, jer vam omogućuje razumijevanje principa rada bilo koje pojedinačne izjave u jeziku.

Proces kompilacije podijeljen je u nekoliko faza:

1. Pretprocesor. Izvorni program obrađuje se zamjenom postojećih makronaredbi i datoteka zaglavlja.

2. Leksička i sintaktička analiza. Program se pretvara u niz tokena, a zatim u interni prikaz stabla.

3. Globalna optimizacija. Unutarnji prikaz programa stalno se transformira kako bi se smanjila veličina i vrijeme izvođenja programa.

4. Generiranje koda. Interni prikaz se pretvara u blokove instrukcija procesora, koji se pretvaraju u asemblerski tekst ili objektni kod.

5. Skupština. Ako se generira asemblerski tekst, asemblera se da bi se dobio objektni kod.

6. Skupština. Asembler kombinira više objektnih datoteka u izvršnu datoteku ili biblioteku.

U fazi leksička analiza (LA) ulazni program, koji je tok znakova, podijeljen je na lekseme - riječi u skladu s definicijama jezika. Glavni formalizam koji leži u osnovi implementacije leksičkih analizatora su konačni automati i regularni izrazi. Leksički analizator može raditi u dva glavna načina: ili kao podrutina koju poziva parser nakon sljedećeg tokena ili kao puni prolaz, što rezultira datotekom tokena. U procesu izdvajanja tokena, LA može neovisno graditi tablice imena i konstanti i dati vrijednosti za svaki token sljedeći put kada mu se pristupi. U ovom slučaju, tablica imena se gradi u sljedećim fazama (na primjer, tijekom parsiranja).

U fazi LA otkrivaju se neke (najjednostavnije) pogreške (nevažeći znakovi, neispravno bilježenje brojeva, identifikatori itd.).

Razmotrimo detaljnije fazu leksičke analize.

Glavni zadatak leksičke analize - razbiti unos teksta, koji se sastoji od niza pojedinačnih znakova, u niz riječi, odnosno leksema, tj. izolirajte ove riječi iz kontinuiranog niza znakova. S ove točke gledišta svi znakovi ulaznog niza dijele se na znakove koji pripadaju nekim leksemima i znakove koji razdvajaju lekseme (separatore). U nekim slučajevima možda neće biti razdjelnika između tokena. S druge strane, u nekim jezicima tokeni mogu sadržavati beznačajne znakove (na primjer, razmak u Fortranu). U C-u, vrijednost razdvajanja znakova za razdvajanje može se blokirati ("\" na kraju retka unutar "...").

Obično su svi leksemi podijeljeni u klase. Primjeri takvih klasa su brojevi (cijeli, oktalni, heksadecimalni, realni, itd.), identifikatori, nizovi. Ključne riječi i interpunkcijski simboli (ponekad zvani simboli za razdvajanje) označeni su zasebno. Tipično, ključne riječi su neki konačni podskup identifikatora. U nekim jezicima (na primjer, PL/1) značenje leksema može ovisiti o njegovom kontekstu i nemoguće je provesti leksičku analizu odvojeno od sintaktičke.

Sa stajališta daljnjih faza analize, leksički analizator proizvodi dvije vrste informacija: za sintaktički analizator, koji radi nakon leksičkog analizatora, bitne su informacije o slijedu klasa tokena, graničnika i ključnih riječi, a za analiza konteksta, radeći nakon sintaktičke, važni su podaci o specifičnim značenjima pojedinih leksema (identifikatori, brojevi itd.).

Dakle, opća shema leksičkog analizatora je sljedeća. Prvo se dodjeljuje jedan token (možda korištenjem znakova za razdvajanje). Ključne riječi se prepoznaju eksplicitnim odabirom izravno iz teksta ili se prvo dodjeljuje identifikator, a zatim se provjerava pripada li skupu ključnih riječi.

Ako je odabrani leksem graničnik, tada se on (točnije, neka njegova obilježja) ispisuje kao rezultat leksičke analize. Ako je odabrani leksem ključna riječ, vraća se atribut odgovarajuće ključne riječi. Ako je odabrani leksem identifikator, vraća se atribut identifikatora, a sam identifikator pohranjuje se zasebno. Konačno, ako odabrani token pripada bilo kojoj drugoj klasi tokena (na primjer, token je broj, niz itd.), tada se vraća atribut odgovarajuće klase, a vrijednost tokena se pohranjuje odvojeno.

Leksički analizator može biti neovisna faza prijevoda ili potprogram koji radi na principu "daj token". U prvom slučaju (Slika 3.1, a), izlaz analizatora je datoteka tokena, u drugom (Slika 3.1, b), token se izdaje svaki put kada se pristupi analizatoru (u ovom slučaju, kao pravilo, atribut klase tokena vraća se kao rezultat funkcije "leksičkog analizatora", a vrijednost tokena se prosljeđuje kroz globalnu varijablu). Što se tiče obrade vrijednosti tokena, parser može jednostavno vratiti vrijednost svakog tokena, u kojem slučaju se konstrukcija tablica objekata (identifikatora, nizova, brojeva itd.) odgađa za kasnije faze, ili može sam izgraditi tablice objekata . U tom se slučaju kao vrijednost leksema daje pokazivač na unos u odgovarajuću tablicu.

Riža. 3.1:

Rad leksičkog analizatora zadaje neki konačni automat. Međutim, izravan opis državni stroj nezgodno s praktičnog gledišta. Stoga se za određivanje leksičkog analizatora u pravilu koristi ili regularni izraz ili desnolinearna gramatika. Sva tri formalizma (konačni automati, regularni izrazi i desnolinearne gramatike) imaju istu izražajnu snagu. Konkretno, prema regularni izraz ili desno-linearne gramatike, može se konstruirati stroj stanja koji prepoznaje isti jezik.

Glavni zadatak raščlanjivanja - analiza strukture programa. U pravilu se struktura shvaća kao stablo koje odgovara raščlanjivanju u gramatici jezika bez konteksta. Trenutno se najčešće koriste ili LL(1) analiza (i njena varijanta rekurzivnog spuštanja) ili LR(1) analiza i njene varijante (LR(0), SLR(1), LALR(1) i druge). Rekurzivno spuštanje se češće koristi pri ručnom programiranju parsera, LR(1) - kada se koriste sustavi automatizacije za izgradnju parsera.

Rezultat parsiranja je stablo sintakse s vezama na tablicu imena. Proces raščlambe također otkriva pogreške povezane sa strukturom programa.

U fazi kontekstualne analize otkrivaju se ovisnosti između dijelova programa koje se ne mogu opisati sintaksom bez konteksta. To su uglavnom odnosi "opis-uporaba", posebice analiza tipova objekata, analiza opsega, podudaranje parametara, oznake i drugo. U procesu kontekstualne analize gradi se tablica simbola, koja se može smatrati tablicom imena, dopunjena informacijama o opisima (svojstvima) objekata.

Glavni formalizam koji se koristi u kontekstualnoj analizi je gramatike atributa. Rezultat faze analize konteksta je atribuirano programsko stablo. Informacije o objektima mogu biti ili disperzirane u samom stablu ili koncentrirane u zasebnim tablicama simbola. Proces kontekstualne analize također može detektirati pogreške povezane sa zlouporabom objekata.

Tada se program može pretvoren u internu reprezentaciju . To je učinjeno u svrhu optimizacije i/ili pogodnosti generiranja koda. Još jedan cilj pretvaranja programa u interni prikaz je želja da se ima prijenosni prevodilac. Tada samo posljednja faza (generiranje koda) ovisi o stroju. Kao interni prikaz mogu se koristiti prefiksna ili postfiksna notacija, usmjereni graf, trojke, četvorke i drugi.

Može postojati nekoliko faza optimizacije . Optimizacije obično se dijele na strojno ovisne i strojno neovisne, lokalne i globalne. Dio optimizacije ovisne o stroju izvodi se tijekom faze generiranja koda. Globalna optimizacija pokušava uzeti u obzir strukturu cjelokupnog programa, lokalno - samo njegove male fragmente. Globalna optimizacija temelji se na analizi globalnog toka koja se izvodi na programskom grafu i u biti je transformacija tog grafa. U ovom slučaju, takva svojstva programa kao što su interproceduralna analiza, intermodulna analiza, analiza područja života varijabli, itd. mogu se uzeti u obzir.

Konačno, generiranje koda- posljednja faza prijevoda. Njegov rezultat je ili asemblerski modul ili objektni (ili boot) modul. Tijekom generiranja koda, neki lokalne optimizacije, kao što je distribucija registara, izbor dugih ili kratkih skokova, uzimanje u obzir troškova naredbi pri odabiru određenog niza naredbi. Razvijene su različite metode za generiranje koda, kao što su tablice odlučivanja, podudaranje uzoraka koje uključuje dinamičko programiranje i razne sintaktičke metode.

Naravno, određene faze prevoditelja mogu biti potpuno odsutne ili kombinirane. U najjednostavnijem slučaju prevoditelja s jednim prolazom, ne postoji eksplicitna faza generiranja međureprezentacije i optimizacije, preostale faze se spajaju u jednu i ne postoji eksplicitno konstruirano stablo sintakse.

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Dobar posao na stranicu">

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Domaćin na http://www.allbest.ru

Uvod

1.1 Raščlanjivanje odozgo prema dolje

1.2 Raščlanjivanje odozdo prema gore

1.2.1 LR(k) - gramatike

1.2.1.1 LR(0) - gramatike

1.2.2 LALR(1) gramatike

2. Razvoj prevoditelja

2.1 Analiza zahtjeva

2.2 Dizajn

2.2.1 Dizajniranje leksičkog analizatora

2.2.4 Softverska implementacija parsera

2.3 Kodiranje

2.4 Ispitivanje

Zaključak

Popis korištenih izvora

Dodatak A. Popis programskog teksta prevoditelja

Dodatak B. Rezultati ispitivanja

Dodatak C. Shema programa prevoditelja

Uvod

Davno su prošli dani kada je prije pisanja programa bilo potrebno razumjeti i zapamtiti više od desetak strojnih instrukcija. Moderni programer formulira svoje zadatke u programskim jezicima visoke razine i koristi asemblerski jezik samo u iznimnim slučajevima. Kao što je poznato, algoritamski jezici postaju dostupni programeru tek nakon stvaranja prevoditelja s tih jezika.

Programski jezici se prilično razlikuju jedni od drugih u svrhu, strukturi, semantičkoj složenosti, metodama implementacije. To nameće svoje specifičnosti razvoju pojedinih prevoditelja.

Programski jezici su alati za rješavanje problema u različitim predmetnim područjima, što određuje specifičnosti njihove organizacije i razlike u namjeni. Primjeri uključuju Fortran za znanstveno računanje, C za sistemsko programiranje, Prolog za učinkovito opisivanje problema zaključivanja i Lisp za rekurzivnu obradu popisa. Ovi primjeri se mogu nastaviti. Svako od predmetnih područja ima svoje zahtjeve za organizaciju samog jezika. Stoga možemo primijetiti raznolikost oblika predstavljanja operatora i izraza, razliku u skupu osnovnih operacija, smanjenje učinkovitosti programiranja pri rješavanju problema koji nisu povezani s predmetnim područjem. Jezične razlike odražavaju se i na strukturu prevoditelja. Lisp i Prolog se najčešće izvode u interpretativnom načinu jer koriste dinamičko generiranje tipa podataka tijekom izračuna. Fortranove prevoditelje karakterizira agresivna optimizacija rezultirajućeg strojnog koda, što postaje moguće zahvaljujući relativno jednostavnoj semantici jezičnih konstrukcija - posebice zbog nepostojanja alternativnih mehanizama imenovanja varijabli putem pokazivača ili referenci. Prisutnost pokazivača u jeziku C čini specifične zahtjeve Do dinamička distribucija memorija.

Struktura jezika karakterizira hijerarhijske odnose između njegovih koncepata, koji su opisani sintaktičkim pravilima. Programski jezici mogu se međusobno jako razlikovati u organizaciji pojedinačnih koncepata i u odnosu među njima. Programski jezik PL/1 dopušta proizvoljno ugniježđivanje procedura i funkcija, dok u C-u sve funkcije moraju biti na vanjskoj razini ugniježđivanja. Jezik C++ dopušta deklaraciju varijabli u bilo kojem trenutku programa prije njegove prve uporabe, dok u Pascalu varijable moraju biti definirane u posebnom deklaracijskom području. PL/1 ide još dalje po ovom pitanju, što dopušta da se varijabla deklarira nakon što je korištena. Ili možete potpuno izostaviti opis i slijediti zadana pravila. Ovisno o odluka, prevoditelj može analizirati program u jednom ili više prolaza, što utječe na brzinu prijevoda.

Semantika programskih jezika varira u vrlo širokom rasponu. Razlikuju se ne samo u specifičnostima implementacije pojedinih operacija, već iu programskim paradigmama koje određuju temeljne razlike u metodama razvoja programa. Specifičnosti provedbe operacija mogu se odnositi i na strukturu obrađenih podataka i na pravila obrade istih vrsta podataka. Jezici kao što su PL/1 i APL podržavaju matrične i vektorske operacije. Većina jezika prvenstveno radi sa skalarima, pružajući procedure i funkcije koje su napisali programeri za rukovanje nizovima. Ali čak i kada se izvodi operacija zbrajanja dva cijela broja, jezici poput C i Pascala mogu se ponašati drugačije.

Uz tradicionalno proceduralno programiranje, koji se također naziva imperativ, postoje takve paradigme kao što su funkcionalno programiranje, logičko programiranje i objektno orijentirano programiranje. Struktura koncepata i objekata jezika snažno ovisi o odabranoj paradigmi, što također utječe na implementaciju prevoditelja.

Čak se isti jezik može implementirati na nekoliko načina. To je zbog činjenice da teorija formalnih gramatika dopušta različite metode raščlanjivanja istih rečenica. Sukladno tome, prevoditelji na različite načine mogu dobiti isti rezultat (objektni program) iz izvornog izvornog teksta.

Međutim, svi programski jezici imaju niz opće karakteristike i parametri. To zajedništvo također određuje principe organiziranja prevoditelja koji su slični za sve jezike.

Programski jezici osmišljeni su kako bi olakšali programiranje. Stoga su njihovi operatori i podatkovne strukture moćniji nego u strojnim jezicima.

Za povećanje vidljivosti programa, umjesto numeričkih kodova, simbolički ili grafički prikazi jezične konstrukcije koje su ljudima čitljivije.

Za bilo koji jezik definirano je:

- skup simbola pomoću kojih se mogu napisati ispravni programi (abeceda), osnovni elementi,

- set ispravnih programa (sintaksa),

- "značenje" svakog ispravnog programa (semantika).

Bez obzira na specifičnosti jezika, bilo koji prevoditelj može se smatrati funkcionalnim pretvaračem F koji omogućuje nedvosmisleno preslikavanje X u Y, gdje je X program na izvornom jeziku, Y je program na ciljnom jeziku. Stoga se sam proces prevođenja može formalno prikazati sasvim jednostavno i jasno: Y = F(X).

Formalno, svaki ispravan program X je niz znakova iz neke abecede A, pretvoren u odgovarajući niz Y, sastavljen od znakova iz abecede B.

Programski jezik, kao i svaki složeni sustav, definiran je kroz hijerarhiju koncepata koja definira odnos između njegovih elemenata. Ovi pojmovi su međusobno povezani u skladu sa sintaktičkim pravilima. Svaki od programa izgrađenih prema ovim pravilima ima odgovarajuću hijerarhijsku strukturu.

U tom smislu, za sve jezike i njihove programe mogu se dodatno razlikovati sljedeće zajedničke značajke: svaki jezik mora sadržavati pravila koja omogućuju generiranje programa koji odgovaraju tom jeziku ili prepoznavanje korespondencije između pisanih programa i danog jezika.

Još jedna karakteristična značajka svih jezika je njihova semantika. Određuje značenje jezičnih operacija, ispravnost operanda. Lanci koji imaju istu sintaktičku strukturu u različitim programskim jezicima mogu se razlikovati u semantici (što se, na primjer, opaža u C++, Pascal, Basic). Poznavanje semantike jezika omogućuje njegovo odvajanje od njegove sintakse i korištenje za pretvaranje u drugi jezik (za generiranje koda).

Svrha ovog kolegija je razviti prevoditelja za obuku iz zadanog jezika pojednostavljenog teksta visoke razine.

1. Metode raščlanjivanja

Razmotrite osnovne metode gramatičke analize.

1.1 Raščlanjivanje odozgo prema dolje

Prilikom raščlanjivanja od vrha prema dolje, međuzaključci se kreću duž stabla u smjeru od korijena prema lišću. U ovom slučaju, kada se lanac gleda slijeva na desno, prirodno će se dobiti lijevi zaključci. Kod determinističkog parsiranja, problem bi bio koje pravilo primijeniti za proširenje krajnjeg lijevog neterminala.

1.1.1 LL(k) - jezici i gramatike

Razmotrite izlazno stablo u procesu dobivanja lijevog izlaza lanca. Međulanac u procesu izlaza sastoji se od lanca terminala w, krajnjeg lijevog ne-terminala A, ispod tiskanog dijela x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Slika 1

Za nastavak parsiranja potrebno je zamijeniti neterminal A prema jednom od pravila oblika A:y. Ako se zahtijeva da raščlanjivanje bude determinističko (bez praćenja unatrag), ovo pravilo treba odabrati na poseban način. Kaže se da gramatika ima svojstvo LL(k) ako je, da bi se odabralo pravilo, dovoljno uzeti u obzir samo wAx i prvih k znakova nepretraženog niza u. Prvo slovo L (lijevo, lijevo) odnosi se na gledanje ulaznog niza slijeva na desno, drugo - na korišteni lijevi izlaz.

Definiramo dva skupa lanaca:

a) FIRST(x) - skup terminalnih nizova izvedenih iz x, skraćenih na k znakova.

b) FOLLOW(A) - skup terminalnih nizova skraćenih na k, koji mogu odmah slijediti A u izlaznim nizovima.

Gramatika ima svojstvo LL(k) ako iz postojanja dvaju lanaca lijevih zaključaka:

S::wAx:wzx::wu

S::wAx:wtx::wv

uvjet FIRST(u)=FIRST(v) implicira z=t.

U slučaju k=1, za odabir pravila za A dovoljno je znati samo ne-terminal A i a - prvi znak niza u:

- odaberite pravilo A:x ako je a u FIRST(x),

- pravilo A:e treba odabrati ako je a uključeno u FOLLOW(A).

LL(k)-svojstvo nameće prilično jaka ograničenja na gramatiku. Na primjer, LL(2) gramatika S: aS | a nema svojstvo LL(1), jer PRVI(aS)=PRVI(a)=a. U ovom slučaju, možete smanjiti vrijednost k korištenjem "faktorizacije" (stavljanje faktora u zagrade):

S:aA

O: S | e

Svaka LL(k)-gramatika je jedinstvena. Lijevo-rekurzivna gramatika ne pripada LL(k) ni za jedno k. Ponekad je moguće pretvoriti ne-LL(1) gramatiku u njenu ekvivalentnu LL(1) gramatiku eliminacijom lijeve rekurzije i faktorizacije. Međutim, problem postojanja ekvivalentne LL(k)-gramatike za proizvoljnu ne-LL(k)-gramatiku je neriješiv.

1.1.2 Metoda rekurzivnog spuštanja

Metoda rekurzivnog spuštanja usmjerena je na one slučajeve kada je prevodilac programiran na jednom od jezika visoke razine, kada je dopuštena uporaba rekurzivnih procedura.

Osnovna ideja rekurzivnog spuštanja je da je svaki neterminal gramatike povezan s procedurom koja prepoznaje bilo koji niz koji generira ovaj neterminal. Ove procedure pozivaju jedna drugu kada je potrebno.

Rekurzivno spuštanje može se koristiti za bilo koju LL(1) gramatiku. svaki ne-terminal gramatike odgovara proceduri koja počinje prijelazom na izračunatu oznaku i sadrži kod koji odgovara svakom pravilu za ovaj ne-terminal. Za one ulazne simbole koji pripadaju izbornom skupu ovo pravilo, izračunata grana prenosi kontrolu na kod koji odgovara ovom pravilu. Za ostale znakove unosa kontrola prelazi na rutinu za obradu grešaka.

Kod bilo kojeg pravila sadrži operacije za svaki znak uključen u desna strana pravila. Operacije su navedene redoslijedom kojim se simboli pojavljuju u pravilu. Nakon posljednje operacije kod sadrži povrat iz procedure.

Korištenje rekurzivnog spuštanja u jeziku visoke razine olakšava programiranje i otklanjanje pogrešaka.

1.2 Raščlanjivanje odozdo prema gore

Razmotrimo raščlanjivanje odozdo prema gore, u kojem se srednji zaključci kreću duž stabla prema korijenu. Ako znakove niza čitate slijeva nadesno, stablo će izgledati ovako:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Slika 2

Međuizlaz ima oblik xbu, gdje je x lanac terminala i ne-terminala iz kojeg izlazi skenirani dio lanca terminala w, bu je neskenirani dio lanca terminala, b je sljedeći znak. Za nastavak parsiranja možete ili dodati znak b skeniranom dijelu lanca (izvršiti tzv. "pomak"), ili odabrati na kraju x takav lanac z (x=yz) da jedna od gramatika pravila B:z mogu se primijeniti na z i zamijeniti x na lanac yB (izvesti takozvanu "konvoluciju"):

-S-- -S--

/ \ / \

/-x-b- \ /yB- \

/ | \ / | \

--w--b--u- --w--b--u-

Slika 3 - Nakon pomaka Slika 4 - Nakon konvolucije

Ako se konvolucija primijeni samo na posljednji likovi x, tada ćemo dobiti prave izlaze lanca. Ova analiza se naziva LR, gdje se simbol L (lijevo, lijevo) odnosi na gledanje lanca slijeva na desno, a R (desno, desno) se odnosi na rezultirajući izlaz.

Redoslijed smjena i ugovornih operacija je bitan. Stoga je za determinističko parsiranje potrebno birati između pomaka i redukcije (i različitih pravila redukcije) u svakom trenutku.

1.2.1 LR(k) - gramatike

Ako je tijekom LR parsiranja moguće donijeti determinističku odluku o pomaku/sažimanju uzimajući u obzir samo niz x i prvih k znakova neskeniranog dijela ulaznog niza u (ovi k znakovi nazivaju se predniz), gramatika je kaže se da ima LR(k)-svojstvo.

-S--

/ \

/-x-\

--w----u--

Slika 5

Razlika između LL(k)- i LR(k)-gramatika u smislu derivacijskog stabla:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Slika 6

U slučaju LL(k)-gramatika, jednoznačno se može odrediti pravilo primijenjeno na A pomoću w i prvih k simbola od vu, a u slučaju LR(k)-gramatika, pomoću w,v i prvih k simboli u. Ovaj labavi argument pokazuje da LL(k)-jezici< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - gramatike

Razmotrimo prvo najjednostavnije gramatike ove klase - LR(0). Prilikom raščlanjivanja niza u LR(0)-jeziku, uopće ne morate koristiti vodeći lanac - izbor između pomaka i kontrakcije se vrši na temelju niza x. Budući da se mijenja samo s desnog kraja tijekom parsiranja, naziva se stog. Pretpostavit ćemo da nema gramatike beskorisni likovi a simbol početka se ne pojavljuje na desnoj strani pravila - tada konvolucija do simbola početka signalizira uspješan završetak parsiranja. Pokušajmo opisati skup lanaca terminala i ne-terminala koji se pojavljuju na stogu tijekom svih LR parsiranja (drugim riječima, svi ispravni zaključci iz gramatike).

Definiramo sljedeće skupove:

L(A:v) - lijevi kontekst pravila A:v - skup stanja stoga, neposredno prije kolapsa v u A tijekom svih uspješnih LR parsiranja. Očito, svaki niz u L(A:v) završava na v. Ako se odsječe rep v svih takvih lanaca, tada dobivamo skup lanaca koji se pojavljuju lijevo od A u procesu svih uspješnih desnih zaključaka. Označimo ovaj skup L(A) - lijevi kontekst neterminala A.

Konstruirajmo gramatiku za skup L(A). Terminali i ne-terminali izvorne gramatike bit će terminali nove gramatike; ne-terminali nove gramatike bit će označeni ,... - njihove vrijednosti će biti lijevi konteksti ne-terminala izvorne gramatike. Ako je S početni simbol izvorne gramatike, tada će gramatika lijevog konteksta sadržavati pravilo : e - lijevi kontekst od S sadrži prazan niz Za svako pravilo izvorne gramatike, npr. A: B C d E

i dodajte pravila novoj gramatici:

: - L(B) uključuje L(A)

: B - L(C) uključuje L(A) B

: B C d - L(E) uključuje L(A) B C d

Rezultirajuća gramatika ima poseban oblik (takve se gramatike nazivaju lijevo-linearnim), dakle, skupovi lijevih konteksta

- su redoviti. Iz ovoga slijedi da se članstvo niza u lijevom kontekstu nekog neterminala može izračunati induktivno pomoću konačnog automata, skeniranjem niza slijeva na desno. Opišimo ovaj proces konstruktivno.

Nazovimo LR(0)-situaciju gramatičko pravilo s jednom označenom pozicijom između simbola desne strane pravila. Na primjer, za gramatiku S:A; A: aAA; A:b postoje sljedeće LR(0)-situacije: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (pozicija je označena podvlakom).

Reći ćemo da je lanac x ​​konzistentan sa situacijom A:b_c ako je x=ab i a pripada L(A). (Drugim riječima, LR zaključivanje može se nastaviti x_... = ab_...:: abc_...:: aA_...:: S_.) U ovim terminima, L(A:b) je skup nizovi koji odgovaraju situaciji A:b_, L(A)

- lanci konzistentni sa situacijom A:_b za bilo koje pravilo A:b.

Neka je V(u) skup situacija u skladu s u. Pokažimo da je funkcija V induktivna.

Ako skup V(u) uključuje situaciju A:b_cd, tada situacija A:bc_d pripada V(uc). (c - terminal ili neterminal; b, d - nizovi (mogu biti prazni) terminala i neterminala). Ne postoje druge situacije poput A:b_d, s nepraznim b u V(uc). Ostaje dodati situacije oblika C:_... u V(uc) za svaki neterminal C čiji lijevi kontekst sadrži uc. Ako situacija A:..._C... (C-neterminal) pripada skupu V(uc), tada uc pripada L(C) i V(uc) uključuje situacije oblika C:_... za sva C- gramatička pravila.

V(e) sadrži situacije S:_... (S-početni znak), kao i situacije A:_... ako se ne-terminal A pojavljuje neposredno nakon _ u situacijama koje su već uključene u V(e) .

Konačno, spremni smo za definiranje LR(0) gramatike. Neka u bude sadržaj stoga tijekom LR parsiranja, i neka V(u) bude skup LR(0) situacija koje su u skladu s u. Ako V(u) sadrži situaciju oblika A:x_ (x-slijed terminala i neterminala), tada u pripada L(A:x) i x se može saviti u A. Ako V(u) sadrži situaciju A:..._a... (a-terminal), tada je dozvoljen pomak. Govori se o sukobu shift-reduce ako su i pomak i kontrakcija dopušteni za isti niz u. Govori se o sukobu odustajanja i odustajanja ako su odustajanja dopuštena prema različitim pravilima.

Gramatika se naziva LR(0) ako nema sukoba shift-fold ili roll-down za sva stanja stoga u procesu zaključivanja LR.

1.2.1.2 LR(k) - gramatike

Samo se stanje stoga koristi u LR(0) raščlanjivanju za odabir između pomaka ili skupljanja. LR(k) raščlanjivanje također uzima u obzir k-prvih znakova nevidljivog dijela ulaznog niza (tzv. predniz). Da bi se opravdala metoda, treba pažljivo ponoviti argumente iz prethodnog odjeljka, unoseći izmjene u definicije.

Također ćemo uključiti lanac unaprijed u lijevom kontekstu pravila. Ako desna derivacija koristi derivaciju wAu: wvu, tada par wv,FIRSTk(u) pripada Lk(A:v), a par w,FIRSTk(u) pripada Lk(A). Skup lijevih konteksta, kao u slučaju LR(0), može se izračunati pomoću indukcije na lijevom lancu. Nazovimo LR(k)-situaciju par: gramatičko pravilo s označenom pozicijom i prethodni lanac duljine najviše k. Pravilo ćemo odvojiti od naprednog lanca okomitom crtom.

Reći ćemo da je lanac x ​​konzistentan sa situacijom A:b_c|t ako postoji LR-izlaz: x_yz = ab_yz:: abc_z:: aA_z:: S_, i FIRSTk(z)=t. Pravila za induktivni izračun skupa stanja Vk su sljedeća:

Vk(e) sadrži S:_a|e situacija za sva S:a pravila, gdje je S početni simbol. Za svaku situaciju A:_Ba|u iz Vk(e), svako pravilo B:b i lanac x ​​koji pripada FIRSTk(au), situacija B:_b|x mora se dodati u Vk(e).

Ako situacija A:b_cd|u ulazi u Vk(w), tada će situacija A:bc_d|u pripadati Vk(wc). Za svaku situaciju A:b_Cd|u iz Vk(wc), svako pravilo C:f i lanac x ​​koji pripada FIRSTk(du), moramo dodati situaciju C:_f|x u Vk(wc).

Koristimo konstruirane skupove LR(k)-stanja za rješavanje problema pomaka-konvolucije. Neka je u sadržaj steka, a x lanac napredovanja. Očito, A:b konvolucija se može izvesti ako Vk(u) sadrži situaciju A:b_|x. Odlučivanje je li pomak dopušten zahtijeva točnost ako gramatika sadrži e-pravila. U situaciji A:b_c|t (c nije prazno), pomak je moguć ako c počinje s terminala i x pripada FIRSTk(ct). Neslužbeno govoreći, možete gurnuti krajnji lijevi znak desne strane pravila na stog, pripremajući naknadnu konvoluciju. Ako c počinje s ne-terminala (situacija izgleda kao A:b_Cd|t), tada je guranje simbola na stog, pripremajući preklop u C, moguće samo ako C ne generira prazan niz. Na primjer, u stanju V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a pri izvođenju terminalnih lanaca iz A, u nekom koraku potrebno je primijeniti pravilo A:e na ne-terminal A koji se nalazi na lijevom kraju lanca.

Definirajmo skup EFFk(x) koji se sastoji od svih elemenata skupa FIRSTk(x) čija derivacija ne zamjenjuje neterminal na lijevom kraju od x (ako postoji) s praznim nizom. U ovim terminima, pomak je dopustiv ako skup Vk(u) sadrži situaciju A:b_c|t, c nije prazan, a x pripada EFFk(ct).

Gramatika se naziva LR(k)-gramatika ako nijedno LR(k) stanje ne sadrži dvije situacije A:b_|u i B:c_d|v takve da u pripada EFFk(dv). Takav par odgovara sukobu savijanja i savijanja ako je d prazan, i sukoba pomaka i savijanja ako d nije prazan.

U praksi se LR(k) gramatike ne koriste za k>1. Dva su razloga za to. Prvo: vrlo veliki broj LR(k) stanja. Drugo, za svaki jezik definiran LR(k) gramatikom, postoji LR(1) gramatika; štoviše, postoji LR(1)-gramatika za svaki deterministički CF-jezik.

Broj LR(1)-stanja za praktički zanimljive gramatike također vrlo velik. Takve gramatike rijetko imaju svojstvo LR(0). U praksi se češće koristi metoda između LR(0) i LR(1), poznata kao i LALR(1).

1.2.2 LALR(1) gramatike

Ove dvije metode temelje se na istoj ideji. Konstruirajmo skup kanonskih LR(0)-stanja gramatike. Ako ovaj skup ne sadrži sukobe, tada se može koristiti LR(0) parser. U protivnom, pokušat ćemo riješiti sukobe koji su se pojavili razmatranjem predniza od jednog znaka. Drugim riječima, pokušajmo izgraditi LR(1) parser sa skupom LR(0) stanja.

Metoda LALR(1) (Look Ahead) je sljedeća. Uvedimo relaciju ekvivalencije na skupu LR(1)-situacija: smatrat ćemo dvije situacije ekvivalentnima ako se razlikuju samo u prethodnim lancima. Na primjer, situacije A:Aa_Ab|e i A:Aa_Ab|a su ekvivalentne. Konstruirajmo kanonski skup LR(1)-stanja i ujedinimo stanja koja se sastoje od skupa ekvivalentnih situacija.

Ako rezultirajući skup stanja ne sadrži LR(1) sukobe, i stoga nam omogućuje konstruiranje LR(1) parsera, tada se kaže da gramatika ima svojstvo LALR(1).

2. Razvoj prevoditelja

2.1 Analiza zahtjeva

U ovom kolegiju potrebno je razviti trening prevoditelja u obliku tumača s jezika definiranog odgovarajućom formalnom gramatikom. Postoje četiri glavne faze u razvoju tumača:

Dizajniranje leksičkog analizatora;

Projektiranje stroja za časopis;

Programska implementacija parsera;

Razvoj modula tumačenja.

Razvoj će se odvijati pomoću operativnog sustava Windows XP na osobnom računalu. IBM računalo PC sa procesorom Intel Pentium IV.

Na temelju trendova razvoja softvera za implementaciju prevoditelja za obuku odabran je programski jezik C# u okruženju Visual Studio 2010.

2.2 Dizajn

2.1.1 Dizajniranje leksičkog analizatora

Leksička analiza uključuje skeniranje prevedenog (izvornog) programa i prepoznavanje leksema koji čine rečenice izvornog teksta. Tokeni uključuju, posebno, ključne riječi, operacijske znakove, identifikatore, konstante, posebne znakove itd.

Rezultat rada leksičkog analizatora (skenera) je niz tokena, a svaki token obično je predstavljen nekim kodom fiksne duljine (na primjer, cijeli broj), kao i izdavanje poruka o sintaktičkom (leksičkom ) pogreške, ako ih ima. Ako je leksem, na primjer, ključna riječ, tada njegov kod daje sve potrebne informacije. U slučaju, na primjer, identifikatora, dodatno je potreban naziv prepoznatog identifikatora, koji se obično bilježi u tablici identifikatora, organiziranoj, u pravilu, pomoću popisa. Slična tablica je potrebna za konstante.

Leksem se može opisati s dva glavna obilježja. Jedan od njih je pripadnost leksema određenoj klasi (varijable, konstante, operacije itd.) Drugi atribut definira određeni element ove klase.

Posebna vrsta tablice simbola (struktura podataka) je irelevantna za lexer ili parser. Oba trebaju samo pružiti mogućnost dobivanja indeksa koji jedinstveno identificira, na primjer, danu varijablu i vratiti vrijednost indeksa za dopunjavanje informacija o danom nazivu varijable u tablici simbola.

Pregled tablice identifikatora obavlja dvije glavne funkcije:

a) upisivanje novog imena u tablicu prilikom obrade deklaracije varijabli;

b) traženje imena koje je prethodno zabilježeno u tablici.

To omogućuje otkrivanje takvih pogrešnih situacija kao što je višestruki opis varijable i prisutnost nedeklarisane varijable.

Razvoj leksičkog analizatora djelomično se sastoji od modeliranja raznih automata za prepoznavanje identifikatora, konstanti, rezervirane riječi itd. Ako žetoni drugačiji tip početi s istim znakom ili istim nizom znakova, možda će biti potrebno kombinirati njihovo prepoznavanje.

Pokretanjem leksičkog analizatora razbijamo naš program na tokene, nakon čega svaki token prolazi provjeru duljine (token ne može imati više od 11 znakova). Nakon uspješnog prolaska ove faze, provjeravamo ispravnost lokacije tokena (ključne riječi var, begin, end, for, to, do, end_for). Zatim analiziramo varijabilne žetone - ne smiju sadržavati brojeve u svom opisu i ponavljati se. U posljednjoj fazi provjeravamo ispravnost pravopisa tokena (ključne riječi, nepoznati identifikatori). Ako barem jedna od provjera izbaci pogrešku, leksički analizator ispisuje pogrešku.

Shema programa rada leksičkog analizatora data je u Prilogu B na slici B.1.

2.2.2 Projektiranje automatskog spremnika

Definirajmo sljedeću gramatiku:

G: (Vt, Va, I, R),

gdje je Vt skup terminalnih simbola, Va skup neterminalnih simbola, I početno stanje gramatike, R skup gramatičkih pravila.

Za ovu gramatiku definiramo skupove terminalnih i neterminalnih simbola:

Sastavimo pravila za našu gramatiku G i predstavimo ih u tablici 1.

Tablica 1 - Gramatička pravila

broj pravila	Lijeva strana pravila	Desna strana pravila
		f ID = EX t EX d LE n;
Nastavak tablice 1.
broj pravila	Lijeva strana pravila	Desna strana pravila

Oznake leksema, prijevod leksema u kodove i popis gramatičkih oznaka dani su u tablicama 2, 3, 4. redom.

Tablica 2 - Zapis leksema

	Bilježenje leksema
	ključna riječ "početak" (početak opisa radnji)
	ključna riječ "end" (kraj opisa radnji)
	ključna riječ "var" (deklaracija varijabli)
	ključna riječ "čitaj" (izjava za unos podataka)
	ključna riječ "write" (izjava za izlaz podataka)
	ključna riječ "za" (naredba petlje)
	ključna riječ "za"
	ključna riječ "učiniti"
	ključna riječ "end_case" (naredba o kraju petlje)
	tip varijable "cijeli broj"
	operacija zbrajanja
	operacija oduzimanja
	operacija množenja
	znak razdjelnika ":"
	znak razdjelnika ";"
	znak razdjelnika "("
	znak za razdvajanje ")"
	znak razdjelnika ","
	Bilježenje leksema
	znak razdjelnika "="

Tablica 3 - Prijevod leksema u kodove

<цифра>
<буква>

Tablica 4 - Popis gramatičkih simbola

Oznaka	Obrazloženje
	Program
	Opis izračuna
	Opis varijabli
	Popis varijabli
	Operater
	Zadatak
	Izraz
	podizraz
	Binarne operacije
	Unarne operacije
	Popis zadataka
	Identifikator
	Konstantno

Konstruirajmo deterministički uzlazni prepoznavač.

Razmotrite sljedeće odnose kako biste izgradili deterministički rezolver odozdo prema gore:

a) Ako postoji grupni simbol B takav da je niz AB uključen u neko gramatičko pravilo i postoji simbol xPERV "(B), tada ćemo pretpostaviti da su između simbola x i A definirani odnosi x NAKON A

b) Ako u danoj gramatici postoji pravilo B-\u003e bAb A, BV a, tada je između A i x određena relacija A PRETVORI x.

Sva naša gramatika ostaje ista, to jest:

G: (Vt, Va, I, R),

a gramatička pravila D data su u tablici 5.

Tablica 5 - Gramatička pravila

broj pravila	Lijeva strana pravila	Desna strana pravila
		f ID = EX t EX d LE n;?
Nastavak tablice 5.
broj pravila	Lijeva strana pravila	Desna strana pravila

Gdje? - oznaka za kraj lanca.

Definirajmo neke slučajeve:

a) ID se sastoji od mnogo slova latinica, odnosno pretpostavljamo da je u = ( a, b, c, d, e, f,g, h, i,j,k, l,m, n, o, p,q,r,s, t, u, v, w, x, y, z)

b) CO konstanta se sastoji od brojeva, odnosno pretpostavit ćemo da je k = (0,1,2,3,4,5,6,7,8,9)

Da bi naša gramatika bila strategija mješovitog prvenstva, moraju biti ispunjeni sljedeći uvjeti:

a) Nepostojanje e-pravila

b) Postoje li pravila prema kojima x NAKON A? A PRETVORI x = ?

c) A -> bYg

a potrebno je da IN NAKON x? U PRETVORI x = ?

tj. u gramatici će se izvesti IN NAKON x ili A NAKON x, gdje je x simbol-predikat lanca b.

a) PERV "(PG) \u003d (PG?)

PRIM"(RG) = PRIM(DE) = (RG, v,:, i,;)

PRIM" (AL) = PRIM (b LE e)= (AL, b, e)

PERV" (DE) = PERV (v LV: i;) = (DE, v,:, i,;)

PERV" (LV) = PERV (ID, LV) = (LV, ID)

PERV" (OP) =(OP, ID, CO)

PERV" (EQ) = PERV(ID = EX;) = (EQ, =,;)

PERV" (EX) = (EX, SB, -)

PERV" (BO) = (B0, +,*,-)

PRVI" (SB) = PRVI((EX)SB) ? PRVI(OP) ? PRVI(VO)=(SB, (,), OP, BO);

PERV" (LE) = PERV(EQ) = (LE, (,), =,;, f, t, d, n, w, r)

PERV" (UO) = (UO,-)

PERV" (ID)= PERV" (u) = (u)

PERV" (CO) = PERV" (k) = (k)PERV" (e) =( e)

PERV" (b) =( b)

PERV" (e) =( e)

PERV" (v) =( v)

PERV" (w) =( w)

PERV" (r) =( r)

PERV" (i) =( i)

PERV" (f) =( f)

PERV" (d) = (d)

PERV" (n) =( n)

PERV" (c) =( c)

PERV" (+) =( +)

PERV" (*) =( *)

PERV" (-) =(-)

PERV" (,) =(,)

PERV" (;) =(;)

PERV" (:) =(:)

PERV" (=) = ( = )

PERV" (() =( ()

PERV" ()) =() )

PERV" (u) =(u)

PERV" (k) = (k)

b) SLJEDEĆI `(AL) = (?)?SLJEDEĆI"(PG)=(?,b,e)

DALJE ` (DE) = (?)?PRIM"(AL)= (?, b, e )

DALJE ` (LV) = (?)?PRIM"(:)= (?,:)

DALJE ` (OP) = (?)?PRIM"(SB)= (?,;,), d, t, +, -, *)

DALJE ` (EQ) = (?)?PRVI"(LE)=(?, (,),;, f, =, t, d, n,w,r )

DALJE ` (EX) = (?)?PRIM"(t)?PRIM"(d)?PRIM"(;)?PRIM"())=(?, t,d,;,))

DALJE ` (BO) = (?)?PRVI"(SB)= (?, (,), OP, BO)

DALJE ` (UO) = (?)?PRIM"(SB)= (?, (,), OP, BO)

DALJE ` (SB) = (?)?DALJE"(EX)= (?, t,d,;,), +, *, -)

DALJE ` (LE) = (?) ?PRIM"(e) ?PRIM"(n) = (?, e, n)

DALJE `(ID)=(?)? SLJEDEĆI" (OP) ? PRVI" (=) =(?,;,), d, t, +, -, *, =)

DALJE `(CO) = (?)? SLJEDEĆI" (OP)= (?,;,), d, t, +, -, *, =)

DALJE ` (b) =(?)?PRIM"(LE)= (?, u, =,;)

DALJE ` (e) =(?)?DALJE"(AL)= (?, b)

DALJE ` (v) =(?)?PRIM"(LV)= (?, u )

DALJE ` (w) =(?)?PRIM"(()= (?, ()

DALJE ` (r) =(?)?PRIM"(() = (?, ()

DALJE ` (i) =(?)?PRIM"(;)= (?,; )

DALJE ` (f) =(?)?PRIM"(ID) = (?, u)

DALJE ` (d) =(?)?PRIM"(LE)= (?, u, =,;)

DALJE ` (n) =(?)?PRIM"(i) = (?, i )

DALJE ` (+) =(?)?DALJE"(IN) = (?, +,*,-)

DALJE ` (-) =(?)?DALJE"(IN) = (?, +,*,-)

DALJE ` (*) =(?)?DALJE"(IN) = (?, +,*,-)

DALJE ` (;) =(?)?DALJE" (DE)?DALJE `(LE1)?DALJE" (EQ) = (?, b, e, l, u )

DALJE ` (:) =(?)?PRIM"(i)= (?, i )

DALJE ` (=) = (?)?PRVI"(EX) = (? (,), u, k, +, -, *)

DALJE ` (() =(?)?PRIM"(DE)= (?, v,:, i,;)

DALJE ` ()) =(?)? PERV"(;) = (?,; )

DALJE ` (,) =(?)? PERV"(LV) = (?, u)

DALJE `(u)=(?)? PERV" (ID)= ( u, ?)

DALJE `(k)=(?)? PERV (CO)= (?, k)

c) PG -> DE AL

AL NAKON DE = (b,e) NAKON DE = ((b DE), (e DE) )

e NAKON LE = ((e LE))

LE NAKON b = ((,), =,;, f, t, d, n, w, r) NAKON b = (((b), ()b), (=b), (;b), ( f b), (t b), (d b), (n b), (w b), (r b))

;NAKON i = ((; i))

i NAKON: = ( (i:) )

: NAKON LV = ( (: LV) )

LV NAKON v = ( (ID, v) )

LV POSLIJE, = ((ID,))

NAKON ID = ((,u))

LE NAKON EQ = ((,), =,;, f, t, d, n, w, r ) NAKON EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))

LE -> r (DE);

; POSLIJE) = ((;)))

) NAKON DE = (((DE))

DE NAKON (= (= ((v)), (:)), (i)), (;)), (e)))

(NAKON r = (((r))

LE -> w (DE);

; POSLIJE) = ((;)))

) ZADNJI DE = (((DE))

DE NAKON (= ((v)), (:)), (i)), (;)), (e)))

(NAKON w = (((w))

LE -> f ID = EX t EX d LE n;

; NAKON n = ((;n))

n NAKON LE = ( (n, LE))

LE NAKON d = (((,), =,;, f, t, d, n, w, r))? NAKON d = (((d), ()d), (;d), (f d), (t d), (d d), (n d), (w d), (r d))

d NAKON EX = ((d, EX))

EX POSLIJE t = (BO, -) ? NAKON t = ((BO t), (- t))

t NAKON EX = ( t EX)

EX AFTER == ((BO, -) ? AFTER == ((BO=), (-=))

NAKON ID=((=ID))

ID NAKON f = ((ID f))

EQ -> ID = EX;

; NAKON EX = ((; EX )

EX AFTER == (BO, -) ? NAKON == ((BO=), (-=))

NAKON u = ( (=u))

SB NAKON UO = ( (,), OP, BO ) NAKON UO = (((UO), (OP UO), (BO UO) )

) NAKON EX = ( ()EX) )

EX AFTER (= (BO, -) ? AFTER (= ((BO (), (- ())

SB->SB BO SB

SB NAKON BO = ((,), OP, BO) NAKON BO = (((BO), ()BO), (OP BO), (BO BO))

BO NAKON SB = (+,*,-) NAKON SB = ((+SB), (*SB), (-SB))

ID NAKON u = ((u, u))

G) PG ->DE AL

AL ROLL PG = AL ROLL NEXT" (PG) = ((AL ?))

e KOTRI AL = e KORITI SLJEDEĆI"(AL)= ((eb), (e?))

=; FOLD NEXT"(DE) = ((;b), (;?))

LV PROTOK LV = LV PROTOK SLJEDEĆI" (LV) = ((LV:), (LV?))

ID ROLL LV = ID ROLL NEXT" (LV) = ((ID:), (ID ?))

; PRETVORI LE=; FOLD NEXT" (LE) = ((; e), (;?), (;n))

LE -> f ID = EX t EX d LE n;

; PRETVORI LE=; FOLD NEXT" (LE) = ((; e), (;?), (;n))

EQ ROLL LE = EQ ROLL NEXT" (LE) = ((EQ e), (EQ?), (EQ n))

EQ -> ID = EX;

; PRETVORI EQ=; FOLD NEXT" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))

SB ROLL EX = SB ROLL NEXT" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) SB ROLL = SB SLJEDEĆI ROLL" (SB) = (() t), ()?), () d), ())), ();))

OP ROLL SB = OP ROLL NEXT" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))

SB->SB BO SB

SB ROLL SB = SB ROLL NEXT" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

ROLL UO = - ROLL NEXT" (UO) = ( (-?), (--))

BACI BO = + BACI SLJEDEĆI" (BO) = ((++), (+?), (+*), (+-))

* ROLL BO = * ROLL NEXT" (BO) = ((*+), (*?), (**), (*-))

ROLL BO = - ROLL NEXT" (BO) = ((-+), (-?), (-*), (--))

ID ROLL OP = ID ROLL NEXT" (OP) = ((ID+), (ID?), (ID*), (ID-))

CO FOLD OP = CO FOLD NEXT" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID ROLL ID = ID ROLL NEXT" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u ROLL ID = l ROLL NEXT" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))

CO ROLL CO = CO ROLL NEXT" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k ROLL CO = k ROLL NEXT" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Jedna konfliktna situacija pronađena prilikom sklapanja pravila

OP ->ID i ID -> u ID

Upisujemo ID1 -> ID, stoga prepisujemo pravilo ID1 -> u ID

Stoga ćemo izvršiti operacije konvolucije.

ID1 ROLL ID = ID1 ROLL NEXT" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Za svaki par (x, A)? x NAKON A gradimo prijelaznu funkciju koja određuje akciju prijenosa ?? (S 0, x, A) \u003d (S 0, A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (S0, b;)

? (S0, (, b) = (S0, b()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, bn)

? (S0, š, b) = (S0, š)

? (S0, r, b) = (S0, br)

? (S0,;, i) = (S0, i;)

? (S0, i,:) = (S0, i:)

? (S0,:LV) = (S0,LV:)

? (S0, ID, v) = (S0, vID)

? (S0,ID,) = (S0,ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ)= (S0, EQ()

? (S0,), EQ)= (S0, EQ))

? (S0, =, EQ)= (S0, EQ=)

? (S0,;, EQ)= (S0, EQ;)

? (S0, f, EQ)= (S0, EQf)

? (S0, t, EQ)= (S0, EQt)

? (S0, d, EQ)= (S0, EQd)

? (S0, n, EQ)= (S0, EQn)

? (S0, w, EQ)= (S0, EQw)

? (S0, r, EQ)= (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE()

? (S0,v)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0,i,)) = (S0,)i)

? (S0,:,)) = (S0, :)

? (S0,e,)) = (S0,)e)

? (S0, (, r) = (S0, r()

? (S0, (, w) = (S0, w()

? (S0,;, n) = (S0, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d()

? (S0,), d) = (S0, d))

? (S0,;, d) = (S0, d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, =BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u=)

? (S0, (, UO) = (S0, UO()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO)

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO()

? (S0,),BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB *)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Za svaki par (x, A)? A CONVULT x gradi prijelaznu funkciju koja definira djelovanje konvolucije?? * (S 0, x, bA) \u003d (S 0, B), gdje je B-> bA

? * (S 0 , AL, ?) = (S 0 , PG)

? * (S 0 , e, b) = (S 0 , AL)

? * (S 0 , n, ?) = (S 0 , AL)

? * (S 0 ,;, b) = (S 0 , DE)

? * (S 0 ,;, ?) = (S 0 , DE)

? * (S 0 ,;, e) = (S 0 , DE)

? * (S 0 , LV,:) = (S 0 , LV)

? * (S 0 , LV, ?) = (S 0 , LV)

? * (S 0 , ID, ?) = (S 0 , LV)

? * (S 0 , ID, e) = (S 0 , LV)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, n) = (S 0 , LE)

? * (S 0 , EQ, n) = (S 0 , LE)

? * (S 0 , EQ, e) = (S 0 , LE)

? * (S 0 , EQ, ?) = (S 0 , LE)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, () = (S 0 , EQ)

? * (S 0 ,;,)) = (S 0 , EQ)

? * (S 0 ,;, f) = (S 0 , EQ)

? * (S 0 ,;, =) = (S 0 , EQ)

? * (S 0 ,;, t) = (S 0 , EQ)

? * (S 0 ,;, d) = (S 0 , EQ)

? * (S 0 ,;, n) = (S 0 , EQ)

? * (S 0 ,;, w) = (S 0 , EQ)

? * (S 0 ,;, r) = (S 0 , EQ)

? * (S 0 , SB, ?) = (S 0 , EX)

? * (S 0 , SB, d) = (S 0 , EX)

? * (S 0 , SB,)) = (S 0 , EX)

? * (S 0 , SB,;) = (S 0 , EX)

? * (S 0 , SB, w) = (S 0 , EX)

? * (S 0 , SB, r) = (S 0 , EX)

? * (S 0 , SB, f) = (S 0 , EX)

? * (S 0 , SB, =) = (S 0 , EX)

? * (S 0 , SB, t) = (S 0 , EX)

? * (S 0 , SB, ?) = (S 0 , SB)

? * (S 0 , SB, () = (S 0 , SB)

? * (S 0 , SB,)) = (S 0 , SB)

? * (S 0 , SB, u) = (S 0 , SB)

? * (S 0 , SB, k) = (S 0 , SB)

? * (S 0 , SB, +) = (S 0 , SB)

? * (S 0 , SB, -) = (S 0 , SB)

? * (S 0 , SB, *) = (S 0 , SB)

? * (S 0 , SB, e) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

? * (S 0 ,), ?) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

(S 0 ,),)) = (S 0 , SB)

? * (S 0 ,),;) = (S 0 , SB)

? * (S 0 , -, ?) = (S 0 , UO)

? * (S 0 , -, -) = (S 0 , UO)

? * (S 0 , +, +) = (S 0 , BO)

? * (S 0 , +, ?) = (S 0 , BO)

? * (S 0 , +, *) = (S 0 , BO)

? * (S 0 , -, +) = (S 0 , BO)

? * (S 0 , -, ?) = (S 0 , BO)

? * (S 0 , -, *) = (S 0 , BO)

? * (S 0 , -, -)) = (S 0 , BO)

? * (S 0 , *, +) = (S 0 , BO)

? * (S 0 , *, ?) = (S 0 , BO)

? * (S 0 , *, *) = (S 0 , BO)

? * (S 0 , *, -)) = (S 0 , BO)

? * (S 0 , u, +) = (S 0 , BO)

? * (S 0 , u, ?)= (S 0 , BO)

? * (S 0 , u, *) = (S 0 , BO)

? * (S 0 , u, -)) = (S 0 , BO)

? * (S 0 , k, +) = (S 0 , BO)

? * (S 0 , k, ?) = (S 0 , BO)

? * (S 0 , k, *) = (S 0 , BO)

? * (S 0 , k, -)) = (S 0 , BO)

? * (S 0 , CO, ?) = (S 0 , OP)

? * (S 0 , CO, +) = (S 0 , OP)

? * (S 0 , CO, *) = (S 0 , OP)

? * (S 0 , CO, -) = (S 0 , OP)

? * (S 0 , CO,;) = (S 0 , OP)

? * (S 0 , CO, d) = (S 0 , OP)

? * (S 0 , CO, t) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, *) = (S 0 , OP)

? * (S 0 , ID, ?) = (S 0 , OP)

? * (S 0 , ID, () = (S 0 , OP)

? * (S 0 , ID,)) = (S 0 , OP)

? * (S 0 , ID, u) = (S 0 , OP)

? * (S 0 , ID, k) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, +) = (S 0 , OP)

? * (S 0 , u,)) = (S 0 , I OP)

? * (S 0 , ID1, *) = (S 0 , ID)

? * (S 0 , ID1, ?) = (S 0 , ID)

? * (S 0 , ID1, () = (S 0 , ID)

? * (S 0 , ID1,)) = (S 0 , ID)

? * (S 0 , ID1, u) = (S 0 , ID)

? * (S 0 , ID1, k) = (S 0 , ID)

? * (S 0 , ID1, -) = (S 0 , ID)

? * (S 0 , ID1, +) = (S 0 , ID)

? * (S 0 , u,)) = (S 0 , ID)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, k) = (S 0 , ID)

? * (S 0 , u, *)) = (S 0 , ID)

? * (S 0 , u, -)) = (S 0 , ID)

? * (S 0 , u, +)) = (S 0 , ID)

? * (S 0 , u, d)) = (S 0 , ID)

? * (S 0 , u, t)) = (S 0 , ID)

? * (S 0 , u, =)) = (S 0 , ID)

? * (S 0 , CO, ?) = (S 0 , CO)

? * (S 0 , CO, +) = (S 0 , CO)

? * (S 0 , CO, -) = (S 0 , CO)

? * (S 0 , CO, *) = (S 0 , CO)

? * (S 0 , CO,;) = (S 0 , CO)

? * (S 0 , CO, d) = (S 0 , CO)

? * (S 0 , CO, t) = (S 0 , CO)

? * (S 0 , CO,)) = (S 0 , CO)

? * (S 0 , k, +) = (S 0 , CO)

? * (S 0 , k, -) = (S 0 , CO)

? * (S 0 , k, *) = (S 0 , CO)

? * (S 0 , k,;) = (S 0 , CO)

?? * (S 0 , k, d) = (S 0 , CO)

? * (S 0 , k, t) = (S 0 , CO)

? * (S 0 , k,)) = (S 0 , CO)

? * (S 0 , k, () = (S 0 , CO)

2.2.3 Softverska implementacija parsera

Parser (parser) čita datoteku tokena koju je generirao leksički analizator, provodi gramatičku analizu, prikazuje poruke o sintaktičkim pogreškama, ako postoje, i stvara međuoblik izvornog programa. Osnova za razvoj parsera je dizajn i implementacija odgovarajućeg pushdown automata.

Za raščlanjivanje odozdo prema gore za deterministički razrješivač odozdo prema gore, nakon njegovog pretvaranja u prava vrsta potrebno je pomoću funkcija AFTER i CONVERT dizajnirati push-pull stroj s detaljnim opisom svih prijelaza unutar prijelazne funkcije.

Prilikom razvoja pushdown automata izgradili smo prijelazne funkcije koje će biti osnova parsera. Sve prijelazne funkcije mogu se podijeliti u dvije vrste:

Ciklus rada push-pull stroja bez očitavanja ulaznog simbola (prazan ciklus);

Ciklus push-pull automata s čitanjem ulaznog simbola.

Prilikom implementacije leksičkog analizatora, podijelili smo program na tokene i upisali ih u listu. Zatim obrađujemo ovaj popis u parseru. Na ulazu šaljemo naš program (listu), početni simbol (PG) i donji marker automatskog spremnika (h0), nakon čega odabiremo željenu funkciju tranzicija i vrši se rekurzivan poziv.

Shema radnog programa parsera dana je u Dodatku B na slici B.2.

2.2.4 Razvoj modula tumačenja

Pri razvoju interpretacijskog modula kao posrednog oblika izvornog programa najčešće korišteni postfiksni oblik notacije, koji olakšava provedbu procesa izvršavanja (tumačenja) programa koji se prevodi.

Razmotrimo osnovna načela formiranja i izvođenja postfiksnog oblika izraza.

Osnovna pravila za pretvaranje infiks notacije izraza u postfiks su sljedeća.

Operandi za čitanje dodaju se postfiksnoj notaciji, operacije se guraju na stog.

Ako operacija na vrhu stoga ima viši (ili jednak) prioritet od trenutne operacije čitanja, tada se operacija sa stoga dodaje postfiksnom unosu, a trenutna operacija se gura na stog. U suprotnom (s najnižim prioritetom), samo se trenutna operacija gura na stog.

Čitaj otvorenu zagradu gura se na hrpu.

Nakon čitanja zatvorene zagrade, sve operacije do prve otvarajuće zagrade izvlače se iz stoga i dodaju postfiksnom zapisu, nakon čega se i otvarajuća i zatvarajuća zagrada odbacuju, tj. ne stavljaju se na postfiksni zapis ili na hrpu.

Nakon što je cijeli izraz pročitan, preostale operacije na stogu se dodaju postfiksnom unosu.

Postfiksna notacija izraza omogućuje njegovu procjenu na sljedeći način.

Ako je token operand, tada se gura na stog. Ako je token operacija, tada se navedena operacija izvodi na zadnjim elementima (zadnji element) gurnutim na stog, a ti elementi (element) se zamjenjuju na stogu rezultatom operacije.

Ako su leksičke i sintaktičke analize uspješno prošle, prelazimo na tumačenje. Prvo sastavljamo rečenice od riječi, zatim prevodimo izraze u postfiksalni zapis i računamo.

Shema rada tumača data je u Dodatku B na slici B.3.

2.3 Kodiranje

Program je implementiran u C# u programskom okruženju Visual Studio 2010. Tekst programa prikazan je u Dodatku A.

Program ima pet razreda. Korisničko sučelje implementirano je pomoću klase MainForn. Uz pomoć klase LexAnalysis implementiran je modul leksičke analize, SynAnalysis je modul za parsiranje, Intepreter je modul za tumačenje, ProgramisciJakPolska je pomoćna klasa za prevođenje izraza u obrnuti poljski zapis (postfiks).

Svrha postupaka i funkcija implementiranih u program opisana je u tablicama 6,7,8.

Tablica 6 - Svrha postupaka i funkcije leksičke analize

Slični dokumenti

Prevoditelj je program ili tehničko sredstvo koje obavlja prevođenje programa. Razmatranje glavnih značajki konstrukcije leksičkog analizatora. Poznavanje faza razvoja prevoditelja iz ograničenog podskupa jezika visoke razine.

seminarski rad, dodan 06.08.2013


Dizajniranje leksičkih analizatora i analizatora raščlanjivanja nastavni jezik. Pravila za pretvaranje logičkih izraza u POLIZ. Formiranje trijada, optimizacija njihovog popisa. Logička struktura programa. Testiranje prevoditeljsko-tumačkih modula.

seminarski rad, dodan 28.05.2013


Opće karakteristike i ocjena mogućnosti programskog jezika C-sharp, njegove sličnosti i razlike od C++ i Jave. Razvoj uz pomoć ovog programskog jezika leksičkog i parsera. Sastavljanje proračunskih tablica.

seminarski rad, dodan 11.06.2010


Dizajniranje programa analizatora koji se sastoji od dva dijela: leksički analizator koji rastavlja izvorni tekst programa na tokene i popunjava tablicu imena; parser koji provjerava odgovara li tekst zadanoj gramatici.

seminarski rad, dodan 14.06.2010


Pisanje programa koji provodi leksičku i sintaktičku analizu ulaznog programskog jezika, generira tablicu leksema s naznakom njihovih vrsta i vrijednosti, te također gradi sintaktičko stablo; tekst jezika unosa unosi se s tipkovnice.

seminarski rad, dodan 23.02.2012


Tehnika razvoja i djelomična implementacija prevoditelja za jezik "C" korištenjem jezika "C++", koji početni niz znakova dijeli na minimalne nedjeljive jezične konstrukcije na temelju vokabulara jezika. Analiza programa.

seminarski rad, dodan 19.03.2012


Struktura, klasifikacija i zahtjevi za implementaciju prevoditelja. Dizajn i implementacija analitičkog dijela C++ prevoditelja. Načini provedbe leksičke analize. Algoritam parsera. Principi implementacije softvera.

seminarski rad, dodan 26.01.2013


Izrada prevoditelja koji obrađuje programski kod u jeziku Pascal i generira C program koristeći ekvivalentne operatore. Osobitosti vanjske specifikacije i rada leksičkog analizatora. Struktura programa, prikaz rezultata na ekranu.

seminarski rad, dodan 02.07.2011


Metode gramatičke analize. Razvoj strukture obrazovnog prevoditelja u osnovnom programskom jeziku Object Pascal u okruženju objektno orijentiranog vizualnog programiranja Borland DELPHI 6.0 uz korištenje operacijskog sustava Windows XP.

seminarski rad, dodan 12.05.2013


Implementacija softvera desktop aplikacija pomoću programskog jezika C#. Dizajn i struktura korisničkog sučelja, zahtjevi za njim i ocjena funkcionalnosti. Izrada korisničkog priručnika i njegovo korištenje.

Svako računalo ima vlastiti programski jezik - jezik instrukcija ili strojni jezik - i može izvršavati samo programe napisane na tom jeziku. Uz pomoć strojnog jezika, u načelu, moguće je opisati bilo koji algoritam, ali će troškovi programiranja biti iznimno visoki. To je zbog činjenice da vam strojni jezik omogućuje opisivanje i obradu samo primitivnih struktura podataka - bit, bajt, riječ. Programiranje u strojnim kodovima zahtijeva pretjerane detalje programa i dostupno je samo programerima koji dobro poznaju dizajn i rad računala. Za prevladavanje ove poteškoće dopušteni su jezici visoke razine (Fortran, PL/1, Pascal, C, Ada itd.) s razvijenim strukturama podataka i sredstvima za njihovu obradu, neovisno o jeziku određenog računala.

Algoritamski jezici visoke razine omogućuju programeru da jednostavno i prikladno opiše algoritme za rješavanje mnogih primijenjenih problema. Takav opis naziva se izvorni program, a jezik visoke razine je jezik unosa.

jezični procesor odnosi se na program na strojnom jeziku koji računalu omogućuje razumijevanje i izvršavanje programa na ulaznom jeziku. Postoje dvije glavne vrste jezičnih procesora: tumači i prevoditelji.

Tumač je program koji prihvaća program na ulaznom jeziku kao ulaz i, kako se konstrukcije ulaznog jezika prepoznaju, implementira ih, proizvodeći na izlazu rezultate izračuna koje propisuje izvorni program.

Prevoditelj je program koji prima izvorni program na ulazu i generira na svom izlazu program koji je funkcionalno ekvivalentan izvornom, tzv. objekt. Objektni program je napisan u objektnom jeziku. U određenom slučaju strojni jezik može poslužiti kao objektni jezik, au tom slučaju se program dobiven na izlazu prevoditelja može odmah izvršiti na računalu (interpretirati). U ovom slučaju računalo je interpretator objektnog programa u strojnim kodovima. Općenito, objektni jezik ne mora biti strojni jezik ili sličan njemu (autokod). Objektni jezik može biti neki posredni jezik je jezik koji se nalazi između ulaznog i strojnog jezika.

Ako se kao objektni jezik koristi srednji jezik, tada su moguće dvije opcije za konstruiranje prevoditelja.

Prva opcija je da za međujezik postoji (ili se razvija) još jedan prevoditelj iz međujezika u strojni jezik, a koristi se kao zadnji blok projektiranog prevoditelja.

Druga opcija za izgradnju prevoditelja pomoću srednjeg jezika je izgradnja prevoditelja naredbi srednjeg jezika i njegovo korištenje kao posljednjeg bloka prevoditelja. Prednost tumača očituje se u otklanjanju pogrešaka i dijaloških prevoditelja koji omogućuju rad korisnika u dijaloškom načinu rada, sve do izmjene programa bez potpunog ponovnog prevođenja.

Interpreteri se također koriste u emulaciji programa, tj. izvršavanju na tehnološkom stroju programa napisanih za drugi (objektivni) stroj. Ova opcija, posebno, koristi se za otklanjanje pogrešaka programa na glavnom računalu koji će se izvršavati na specijaliziranom računalu.

Prevoditelj koji koristi jezik sličan stroju (autokod ili asembler) kao svoj ulazni jezik tradicionalno se naziva asembler. Poziva se prevoditelj za jezik visoke razine sastavljač.

U izgradnji kompilatora za posljednjih godina postignut je značajan napredak. Prvi sastavljači koristili su tzv metode izravnog emitiranja- to su pretežno heurističke metode, u kojima se na temelju opće ideje za svaki jezični konstrukt razvija vlastiti algoritam za prevođenje u strojni ekvivalent. Ove su metode bile spore i nisu bile strukturne prirode.

Metodologija dizajna za suvremene prevoditelje temelji se na kompozicijska metoda vođena sintaksom jezična obrada. Kompozicijski u smislu da se proces pretvaranja izvornog programa u objektni program provodi sastavljanjem funkcionalno neovisnih preslikavanja s eksplicitno razlikovanim ulaznim i izlaznim strukturama podataka. Ta su preslikavanja izgrađena uzimajući u obzir izvorni program kao sastav glavnih aspekata (razina) opisa ulaznog jezika: vokabular, sintaksa, semantika i pragmatika, te identificirajući te aspekte iz izvornog programa tijekom njegove kompilacije. Razmotrimo ove aspekte kako bismo dobili pojednostavljeni model prevoditelja.

Osnova svakog prirodnog ili umjetnog jezika je abeceda– skup elementarnih znakova dopuštenih u jeziku (slova, brojke i posebni znakovi). Znakovi se mogu kombinirati u riječi- elementarne konstrukcije jezika, koje se u tekstu (programu) smatraju nedjeljivim simbolima koji imaju određeno značenje.

Riječ također može biti jedan znak. Na primjer, u jeziku Pascal, riječi su identifikatori, ključne riječi, konstante i separatori, posebno znakovi aritmetičkih i logičkih operacija, zagrade, zarezi i drugi simboli. Rječnik jezika, zajedno s opisom načina na koji su predstavljeni, jest vokabular Jezik.

Riječi se u jeziku spajaju u složenije strukture – rečenice. U programskim jezicima najjednostavnija rečenica je izjava. Rečenice se grade od riječi i jednostavnijih rečenica prema pravilima sintakse. Sintaksa jezik je opis ispravnih rečenica. Opis značenja rečenica, tj. značenja riječi i njihove unutarnje veze, is semantika Jezik. Osim toga, napominjemo da određeni program ima određeni učinak na prevoditelja - pragmatizam. Zajedno, sintaksa, semantika i pragmatizam jezičnog oblika semiotika Jezik.

Prijevod programa s jednog jezika na drugi, u općem slučaju, sastoji se u promjeni abecede, vokabulara i sintakse programskog jezika uz zadržavanje njegove semantike. Proces prevođenja izvornog programa u objektni obično se dijeli na nekoliko neovisnih podprocesa (faza prevođenja), koje provode odgovarajući blokovi prevoditelja. Pogodno je razmotriti glavne faze prevođenja kao leksičku analizu, sintaktičku analizu, semantičku analizu i

sinteza objektnog programa. Međutim, u mnogim stvarnim prevoditeljima te su faze podijeljene u nekoliko podfaza, a mogu postojati i druge faze (kao što je optimizacija objektnog koda). Na sl. 1.1 prikazuje pojednostavljeno funkcionalni model prevoditelj.

Prema ovom modelu, ulazni program se prije svega podvrgava leksičkoj obradi. Svrha leksičke analize je prevesti izvorni program u interni jezik prevoditelja, u kojem su ključne riječi, identifikatori, oznake i konstante dovedeni u isti format i zamijenjeni uvjetnim kodovima: numeričkim ili simboličkim, koji se nazivaju deskriptori. Svaki deskriptor sastoji se od dva dijela: klase (tipa) tokena i pokazivača na memorijsku adresu gdje su pohranjene informacije o određenom tokenu. Obično su te informacije organizirane u tablice. Istovremeno s prijevodom izvornog programa na interni jezik, u fazi leksičke analize, leksička kontrola- Identifikacija nedopuštenih riječi u programu.

Parser uzima izlaz leksičkog analizatora i prevodi niz uzoraka tokena u oblik međuprograma. Međuprogram je u biti prikaz stabla sintakse programa. Potonji odražava strukturu izvornog programa, tj. reda i komunikacije između njegovih operatera. Tijekom konstrukcije stabla sintakse, kontrola sintakse - otkrivanje sintaktičkih grešaka u programu.

Stvarni izlaz analize može biti niz naredbi potrebnih za izgradnju međuprograma, pristup tablicama pretraživanja, izdavanje dijagnostičke poruke kada je potrebno.

Riža. 1.1. Pojednostavljeni funkcionalni model prevoditelja

Sinteza objektnog programa počinje, u pravilu, dodjelom i dodjelom memorije za glavne programske objekte. Zatim se ispituje svaka rečenica izvornog programa i generiraju se semantički ekvivalentne rečenice objektnog jezika. Kao ulazne informacije ovdje se koriste stablo sintakse programa i izlazne tablice leksičkog analizatora - tablica identifikatora, tablica konstanti i drugi. Analiza stabla omogućuje vam da identificirate slijed generiranih naredbi objektnog programa, a tablica identifikatora određuje vrste naredbi koje vrijede za vrijednosti operanda u generiranim naredbama (na primjer, koje naredbe treba generirati : fiksna ili plutajuća točka, itd.).

Stvarnom generiranju objektnog programa često prethodi semantička analiza, što uključuje različite vrste semantičke obrade. Jedna vrsta je provjera semantičkih konvencija u programu. Primjeri takvih dogovora: jedinstvenost opisa svakog identifikatora u programu, definicija varijable prije njezine upotrebe itd. Semantička analiza može se provesti u kasnijim fazama prijevoda, kao što je faza optimizacije programa, koja se također može uključiti u prevoditelj. Cilj optimizacije je smanjiti vremenske resurse ili resurse RAM memorija potreban za izvođenje objektnog programa.

Ovo su glavni aspekti procesa prevođenja s jezika visoke razine. Organizacija različitih faza prevođenja i povezane praktične metode za njihov matematički opis detaljnije se razmatraju u nastavku.

Ciljevi i zadaci discipline. Osnovni pojmovi i definicije. Osnovne značajke programski jezici i prevoditelji. Generalizirana struktura prevoditelja. Varijante interakcije blokova prevoditelja.

Ciljevi i zadaci discipline

Trenutačno se umjetni jezici koji koriste prikaz teksta za opisivanje predmetnog područja široko koriste ne samo u programiranju, već iu drugim područjima. Uz njihovu pomoć, struktura raznih dokumenata, trodimenzionalna virtualni svjetovi, grafička sučelja korisnika i mnoge druge objekte koji se koriste u modelima iu stvarnom svijetu. Kako bi se ovi tekstualni opisi ispravno sastavili, a zatim ispravno prepoznali i protumačili, koriste se posebne metode njihove analize i transformacije. Metode se temelje na teoriji jezika i formalnih gramatika, kao i na teoriji automata. Programski sustavi, namijenjeni analizi i tumačenju tekstova, nazivaju se prevoditelji.

Unatoč činjenici da su do danas razvijene tisuće različitih jezika i njihovih prevoditelja, proces stvaranja novih aplikacija u ovom području ne prestaje. To je povezano kako s razvojem tehnologije za proizvodnju računalnih sustava, tako i s potrebom rješavanja sve složenijih primijenjenih problema. Osim toga, elementi teorije jezika i formalne gramatike primjenjivi su u raznim drugim područjima, na primjer, kada se opisuju strukture podataka, datoteke, slike, predstavljene ne u tekstu, već u binarnom formatu. Ove su metode također korisne pri razvoju vaših prevoditelja, čak i tamo gdje već postoje odgovarajući analozi. Takav razvoj može biti posljedica raznih razloga, posebice funkcionalnih ograničenja, nedostatka lokalizacije, niske učinkovitosti. Na primjer, jedan od najnovijih događaja Microsoft je programski jezik C#, a jedan od razloga nastanka je želja da se smanji popularnost programskog jezika Java. Postoje mnogi drugi primjeri u kojima razvijanje vlastitog prevoditelja može biti relevantno. Dakle, temelji teorije jezika i formalne gramatike, kao i praktične metode Razvoj prevoditelja u temelju je obrazovanja inženjera informatike i računalne tehnologije.

Predloženi materijal dotiče osnove metoda razvoja kompilatora i sadrži informacije potrebne za proučavanje logike njihovog funkcioniranja, matematičkog aparata koji se koristi (teorija formalni jezici i formalne gramatike, metajezici). Koristi se kao dio semestralnih predavanja za različite specijalnosti na Fakultetu informatike i računalnog inženjerstva Krasnojarskog državnog tehničkog sveučilišta. U tijeku laboratorijske nastave provodi se neposredno upoznavanje s pojedinim metodama izrade translatora.

Svrha discipline: pružiti znanja o osnovama teorije jezika i formalne gramatike, teorije automata, metoda za razvoj prevoditelja.

Za postizanje ovog cilja u nastavi discipline rješavaju se sljedeći zadaci:

1. Tijekom predavanja razmatraju se opća načela organizacije procesa prevođenja i struktura prevoditelja. Proučavaju se osnove teorije konstruiranja prevoditelja.
2. U laboratorijskim sastancima i tijekom samostalan rad provodi se praktična konsolidacija primljenog teorijskog znanja: razvija se prevoditelj za jednostavan programski jezik.

Osnovni pojmovi i definicije

Većina razmatranih definicija posuđena je iz [ARNFTS Englesko-rusko-njemačko-francuski rječnik računarstva i obrade podataka, 4132 pojma. Pod, ispod. izd. A.A. Dorodnjicin. M.: 1978. 416 str.) ].

Prevoditelj - servisni program, koji pretvara izvorni program dat u ulaznom programskom jeziku u radni program dat u objektnom jeziku.

Gornja definicija odnosi se na sve vrste emitiranih programa. Međutim, svaki od ovih programa može imati svoje osobitosti u organizaciji procesa prevođenja. Trenutno se prevoditelji dijele u tri glavne skupine: asembleri, prevoditelji i interpreteri.

asembler - uslužni program sustava koji pretvara simboličke konstrukcije u instrukcije strojnog jezika. Specifičnost asemblera je da jednu simboličku instrukciju doslovno prevode u jednu strojnu instrukciju. Stoga je asemblerski jezik (također nazvan autocode) dizajniran da olakša percepciju računalnog skupa instrukcija i ubrza programiranje u tom skupu instrukcija. Programeru je puno lakše zapamtiti mnemoničku oznaku strojnih instrukcija nego njihov binarni kod. Stoga se glavni dobitak ne postiže povećanjem snage pojedinih naredbi, već povećanjem učinkovitosti njihove percepcije.

Istodobno, asemblerski jezik, uz analogne strojne instrukcije, sadrži mnoge dodatne direktive koje olakšavaju, posebice, upravljanje računalnim resursima, pisanje fragmenata koji se ponavljaju i izgradnju višemodulnih programa. Stoga je izražajnost jezika mnogo bogatija od samog jezika simboličkog kodiranja, što uvelike povećava učinkovitost programiranja.

kompajler - je pomoćni program koji prevodi u strojni jezik program napisan u izvornom programskom jeziku. Kao asembler, prevodilac pretvara program iz jednog jezika u drugi (najčešće u jezik određenog računala). Međutim, naredbe izvornog jezika značajno se razlikuju po organizaciji i snazi ​​od naredbi strojnog jezika. Postoje jezici u kojima se jedna instrukcija izvornog jezika prevodi u 7-10 strojnih instrukcija. Međutim, postoje i jezici u kojima svaka instrukcija može odgovarati 100 ili više strojnih instrukcija (na primjer, Prolog). Osim toga, u izvornim jezicima često se koristi striktno tipiziranje podataka koje se provodi njihovim preliminarnim opisom. Programiranje se ne mora oslanjati na kodiranje algoritma, već na pažljivo razmišljanje o strukturama podataka ili klasama. Proces prevođenja s takvih jezika obično se naziva kompilacija, a izvorni jezici obično se nazivaju programski jezici visoke razine (ili jezici visoke razine). Apstrakcija programskog jezika iz sustava naredbi računala dovela je do neovisnog stvaranja širokog spektra jezika usmjerenih na rješavanje specifičnih problema. Pojavili su se jezici za znanstvene izračune, ekonomske izračune, pristup bazama podataka i drugo.

Tumač - program ili uređaj koji izvodi operator-po-operator prijevod i izvršavanje izvornog programa. Za razliku od prevoditelja, tumač ne proizvodi program na strojnom jeziku kao izlaz. Nakon što prepozna naredbu izvornog jezika, odmah je izvršava. I kompajleri i interpreteri koriste iste metode parsiranja izvorni kod programa. Ali tumač vam omogućuje da počnete s obradom podataka nakon što napišete čak i jednu naredbu. To čini proces razvoja i otklanjanja pogrešaka programa fleksibilnijim. Osim toga, odsutnost izlaznog strojnog koda omogućuje da se vanjski uređaji ne "zasipaju" dodatnim datotekama, a sam tumač može se vrlo lako prilagoditi bilo kojoj strojnoj arhitekturi, nakon što ga je razvio samo jednom u široko korištenom programskom jeziku. Stoga, tumačeni jezici poput JavaScript, VB Script, postali su široko rasprostranjeni. Nedostatak interpretera je mala brzina izvođenja programa. Tipično, interpretirani programi rade 50 do 100 puta sporije od programa napisanih u strojnom kodu.

Emulator - program ili softverski i hardverski alat koji omogućuje, bez reprogramiranja, izvršavanje na danom računalu programa koji koristi kodove ili metode za izvođenje operacije koja se razlikuje od ovog računala. Emulator je sličan tumaču po tome što izravno izvršava program napisan na nekom jeziku. Međutim, najčešće je to strojni jezik ili međukod. Oba predstavljaju upute u binarnom kodu koje se mogu odmah izvršiti nakon prepoznavanja operacijskog koda. Za razliku od tekstualnih programa, nije potrebno prepoznati strukturu programa, odabrati operande.

Emulatori se često koriste u različite svrhe. Na primjer, kada se razvijaju novi računalni sustavi, prvo se kreira emulator koji pokreće programe koji se razvijaju za računala koja još ne postoje. To vam omogućuje procjenu sustava zapovijedanja i razvoj osnovnog softverčak i prije nego što je stvorena odgovarajuća oprema.

Vrlo često se emulator koristi za pokretanje starih programa na novima. računala. Obično su novija računala brža i bolje kvalitete. periferna oprema. To vam omogućuje da emulirate starije programe učinkovitije nego da ih pokrećete na starijim računalima. Primjer ovakvog pristupa je razvoj emulatora kućnog računala ZX Spectrum s mikroprocesorom Z80. Do sada postoje ljubitelji igranja na emulatoru u zastarjelim, ali još uvijek nisu izgubili svoju nekadašnju atraktivnost, programi za igrice. Emulator se također može koristiti kao jeftiniji analog modernog računalni sustavi, dok pruža prihvatljive performanse ekvivalentne nižim modelima neke obitelji arhitektura. Primjer su IBM PC emulatori. kompatibilna računala implementiran na snažnijim Apple računalima. Brojni emulatori napisani za IBM PC uspješno zamjenjuju razne igraće konzole.

Srednji emulator reprezentacije, poput tumača, može se lako prenijeti s jedne računalne arhitekture na drugu, omogućujući stvaranje mobilnog softvera. To je svojstvo koje je unaprijed odredilo uspjeh programskog jezika Java, iz kojeg se program prevodi u međukod. Izvršavanje ovog koda virtualna java stroj nije ništa više od emulatora koji pokreće bilo koji moderni operativni sustav.

Transkoder - program ili uređaj za programiranje, prevođenje programa napisanih na strojnom jeziku jednog računala u programe napisanih na strojnom jeziku drugog računala. Ako je emulator manje inteligentan analog interpretera, tada transkoder djeluje u istom svojstvu u odnosu na kompajler. Slično, izvorni (i obično binarni) strojni kod ili intermedijarna reprezentacija pretvaraju se u drugi sličan kod u jednoj instrukciji i bez ikakve opće analize strukture izvornog programa. Transkoderi su korisni pri prijenosu programa s jedne računalne arhitekture na drugu. Također se mogu koristiti za rekonstrukciju teksta jezičnog programa visoke razine iz dostupnog binarnog koda.

Makroprocesor - program koji zamjenjuje jedan niz znakova drugim[Smeđa]. To je neka vrsta kompilatora. Generira izlazni tekst obradom posebnih umetaka koji se nalaze u izvornom tekstu. Ovi umetci su napravljeni na poseban način i pripadaju jezičnim konstruktima, koji se nazivaju makro jezik. Makroprocesori se često koriste kao dodaci programskim jezicima, povećavajući funkcionalnost programskih sustava. Gotovo svaki asembler sadrži makroprocesor, što povećava učinkovitost razvoja strojnih programa. Takvi programski sustavi obično se nazivaju makro asembleri.

Makroprocesori se također koriste s jezicima visoke razine. Povećavaju funkcionalnost jezika kao što su PL/1, C, C++. Makroprocesori se posebno široko koriste u C i C++, što olakšava pisanje programa. Primjer raširene upotrebe makro procesora je biblioteka klasa Microsoft Foundation Classes (MFC). Kroz makroumetke implementira mape poruka i drugo programski objekti. U isto vrijeme, makroprocesori povećavaju učinkovitost programiranja bez promjene sintakse i semantike jezika.

Sintaksa - skup pravila određenog jezika koji određuju oblikovanje njegovih elemenata. Drugim riječima, ovo skup pravila za formiranje semantički smislenih nizova znakova u određenom jeziku. Sintaksa je određena pomoću pravila koja opisuju koncepte određenog jezika. Primjeri koncepata su: varijabla, izraz, operator, procedura. Redoslijed pojmova i njihova dopuštena uporaba u pravilima određuje sintaktički ispravne strukture koje tvore programe. Kroz sintaksu je definirana hijerarhija objekata, a ne način na koji oni međusobno djeluju. Na primjer, operator se može pojaviti samo u proceduri, dok se izraz u operatoru, varijabla može sastojati od imena i izbornih indeksa, i tako dalje. Sintaksa nije povezana s takvim pojavama u programu kao što su "skakanje na nepostojeću oznaku" ili "varijabla s danim imenom nije definirana". To je ono što semantika radi.

Semantika - pravila i uvjeti koji određuju odnos između elemenata jezika i njihovih semantičkih značenja, kao i tumačenje značenjskog značenja sintaktičkih konstrukcija jezika. Objekti programskog jezika ne samo da su smješteni u tekstu u skladu s određenom hijerarhijom, već su i dodatno međusobno povezani kroz druge koncepte koji tvore različite asocijacije. Na primjer, varijabla za koju sintaksa definira valjanu lokaciju samo u deklaracijama i nekim izjavama, ima specifičan tip, može se koristiti s ograničenim skupom operacija, ima adresu, veličinu i mora se deklarirati prije upotrebe u program.

Sintaktički analizator - komponenta prevoditelja koja provjerava usklađenost izvornih naredbi s pravilima sintakse i semantikom zadanog programskog jezika. Unatoč nazivu, analizator provjerava i sintaksu i semantiku. Sastoji se od nekoliko blokova, od kojih svaki rješava svoje probleme. Razmotrit će se detaljnije pri opisu strukture prevoditelja.

Opće značajke programskih jezika i prevoditelja

Programski jezici se prilično razlikuju jedni od drugih u svrhu, strukturi, semantičkoj složenosti, metodama implementacije. To nameće svoje specifičnosti razvoju pojedinih prevoditelja.

Programski jezici su alati za rješavanje problema u različitim predmetnim područjima, što određuje specifičnosti njihove organizacije i razlike u namjeni. Primjeri uključuju Fortran za znanstveno računanje, C za sistemsko programiranje, Prolog za učinkovito opisivanje problema zaključivanja i Lisp za rekurzivnu obradu popisa. Ovi primjeri se mogu nastaviti. Svako od predmetnih područja ima svoje zahtjeve za organizaciju samog jezika. Stoga možemo primijetiti raznolikost oblika predstavljanja operatora i izraza, razliku u skupu osnovnih operacija, smanjenje učinkovitosti programiranja pri rješavanju problema koji nisu povezani s predmetnim područjem. Jezične razlike odražavaju se i na strukturu prevoditelja. Lisp i Prolog se najčešće izvode u interpretativnom načinu jer koriste dinamičko generiranje tipa podataka tijekom izračuna. Fortranove prevoditelje karakterizira agresivna optimizacija rezultirajućeg strojnog koda, što postaje moguće zahvaljujući relativno jednostavnoj semantici jezičnih konstrukcija - posebice zbog nepostojanja alternativnih mehanizama imenovanja varijabli putem pokazivača ili referenci. Prisutnost pokazivača u jeziku C nameće posebne zahtjeve na dinamičku dodjelu memorije.

Struktura jezika karakterizira hijerarhijske odnose između njegovih koncepata, koji su opisani sintaktičkim pravilima. Programski jezici mogu se međusobno jako razlikovati u organizaciji pojedinačnih koncepata i u odnosu među njima. Programski jezik PL/1 dopušta proizvoljno ugniježđivanje procedura i funkcija, dok u C-u sve funkcije moraju biti na vanjskoj razini ugniježđivanja. Jezik C++ dopušta deklaraciju varijabli u bilo kojem trenutku programa prije njegove prve uporabe, dok u Pascalu varijable moraju biti definirane u posebnom deklaracijskom području. PL/1 ide još dalje po ovom pitanju, što dopušta da se varijabla deklarira nakon što je korištena. Ili možete potpuno izostaviti opis i slijediti zadana pravila. Ovisno o donesenoj odluci, prevoditelj može analizirati program u jednom ili više prolaza, što utječe na brzinu prijevoda.

Semantika programskih jezika varira u vrlo širokom rasponu. Razlikuju se ne samo u specifičnostima implementacije pojedinih operacija, već iu programskim paradigmama koje određuju temeljne razlike u metodama razvoja programa. Specifičnosti provedbe operacija mogu se odnositi i na strukturu obrađenih podataka i na pravila obrade istih vrsta podataka. Jezici kao što su PL/1 i APL podržavaju matrične i vektorske operacije. Većina jezika prvenstveno radi sa skalarima, pružajući procedure i funkcije koje su napisali programeri za rukovanje nizovima. Ali čak i kada se izvodi operacija zbrajanja dva cijela broja, jezici poput C i Pascala mogu se ponašati drugačije.

Uz tradicionalno proceduralno programiranje, koje se također naziva imperativnim, postoje paradigme kao što su funkcionalno programiranje, logičko programiranje i objektno orijentirano programiranje. Nadam se da će proceduralno-parametarska paradigma programiranja koju sam predložio [Legalov2000] također zauzeti svoje mjesto u ovoj seriji. Struktura koncepata i objekata jezika snažno ovisi o odabranoj paradigmi, što također utječe na implementaciju prevoditelja.

Čak se isti jezik može implementirati na nekoliko načina. To je zbog činjenice da teorija formalnih gramatika dopušta različite metode raščlanjivanja istih rečenica. Sukladno tome, prevoditelji na različite načine mogu dobiti isti rezultat (objektni program) iz izvornog izvornog teksta.

Međutim, svi programski jezici imaju niz zajedničkih karakteristika i parametara. To zajedništvo također određuje principe organiziranja prevoditelja koji su slični za sve jezike.

1. Programski jezici osmišljeni su kako bi olakšali programiranje. Stoga su njihovi operatori i podatkovne strukture moćniji nego u strojnim jezicima.
2. Da bi se povećala vidljivost programa, umjesto numeričkih kodova koriste se simbolički ili grafički prikazi jezičnih konstrukata koji su prikladniji za njihovu percepciju od strane osobe.
3. Za bilo koji jezik definirano je:

• Skup simbola pomoću kojih se mogu napisati ispravni programi (abeceda), osnovni elementi.
• Skup ispravnih programa (sintaksa).
• "Značenje" svakog ispravnog programa (semantika).

Bez obzira na specifičnosti jezika, bilo koji prevoditelj može se smatrati funkcionalnim pretvaračem F koji omogućuje nedvosmisleno preslikavanje X u Y, gdje je X program na izvornom jeziku, Y je program na ciljnom jeziku. Stoga se sam proces prevođenja može formalno prikazati vrlo jednostavno i jasno:

Formalno, svaki točan program X je niz simbola iz neke abecede A, transformiran u odgovarajući niz Y, sastavljen od simbola abecede B.

Programski jezik, kao i svaki složeni sustav, definiran je kroz hijerarhiju koncepata koja definira odnos između njegovih elemenata. Ovi pojmovi su međusobno povezani u skladu sa sintaktičkim pravilima. Svaki od programa izgrađenih prema ovim pravilima ima odgovarajuću hijerarhijsku strukturu.

U tom smislu, za sve jezike i njihove programe mogu se dodatno razlikovati sljedeće zajedničke značajke: svaki jezik mora sadržavati pravila koja omogućuju generiranje programa koji odgovaraju tom jeziku ili prepoznavanje korespondencije između pisanih programa i danog jezika.

Odnos između programske strukture i programskog jezika naziva se sintaktičko preslikavanje.

Kao primjer, razmotrite odnos između hijerarhijske strukture i niza znakova koji definira sljedeći aritmetički izraz:

U većini programskih jezika ovaj izraz definira hijerarhiju programskih objekata koji se mogu prikazati kao stablo (Slika 1.1.):

Krugovi predstavljaju simbole koji se koriste kao elementarne konstrukcije, a pravokutnici predstavljaju složene koncepte koji imaju hijerarhijsku i, moguće, rekurzivnu strukturu. Ova hijerarhija je definirana uz pomoć sintaktičkih pravila napisanih na posebnom jeziku koji se naziva metajezik (metajezici će biti detaljnije obrađeni prilikom proučavanja formalnih gramatika):

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>

<множитель> ::= <буква> | (<выражение>)

<буква>

Bilješka. Znak "::=" se čita kao "jest". Okomita crta "|" čitati kao "ili".

Ako su pravila drugačije napisana, onda je hijerarhijska struktura. Kao primjer može se navesti sljedeći način pisanja pravila:

<выражение> ::= <операнд> | <выражение> + < операнд > | <выражение> * < операнд >

<операнд> ::= <буква> | (<выражение>)

<буква>::= a | b | c | d | ja | f | g | h | ja | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Kao rezultat raščlanjivanja istog aritmetički izraz izgradit će se hijerarhijska struktura, prikazana na sl. 1.2.

Treba napomenuti da hijerarhijska struktura u općem slučaju ne mora biti ni na koji način povezana sa semantikom izraza. U oba slučaja, prioritet izvođenja operacija može se implementirati u skladu s općeprihvaćenim pravilima, kada množenje prethodi zbrajanju (ili obrnuto, sve operacije mogu imati isti prioritet pod bilo kojim skupom pravila). Međutim, prva struktura eksplicitno podržava daljnju implementaciju zajedničkog prvenstva, dok je druga prikladnija za implementaciju operacija s istim prioritetom i njihovo izvršavanje s desna na lijevo.

Proces pronalaženja sintaktičke strukture zadanog programa naziva se raščlanjivanje.

Sintaktička struktura koja je ispravna u jednom jeziku može biti pogrešna u drugom. Na primjer, u Forthu, gornji izraz neće biti prepoznat. Međutim, za ovaj jezik, postfiks izraz će biti točan:

Njegova sintaktička struktura opisana je pravilima:

<выражение> ::= <буква> | <операнд> <операнд> <операция>

< операнд > ::= < буква > | < выражение >

< операция > ::= + | *

<буква>::= a | b | c | d | ja | f | g | h | ja | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Hijerarhijsko stablo koje definira sintaktičku strukturu prikazano je na sl. 1.3.

Još jedna karakteristična značajka svih jezika je njihova semantika. Određuje značenje jezičnih operacija, ispravnost operanda. Lanci koji imaju istu sintaktičku strukturu u različitim programskim jezicima mogu se razlikovati u semantici (što se, na primjer, opaža u C ++, Pascal, Basic za gornji fragment aritmetičkog izraza).

Poznavanje semantike jezika omogućuje njegovo odvajanje od njegove sintakse i korištenje za pretvaranje u drugi jezik (za generiranje koda).

Opis semantike i prepoznavanje njezine ispravnosti obično je najdugotrajniji i najobimniji dio prevoditelja, budući da je potrebno nabrojati i analizirati skup mogućih kombinacija operacija i operanda.

Generalizirana struktura prevoditelja

Opća svojstva i obrasci svojstveni su različitim programskim jezicima i prevoditeljima s tih jezika. Imaju slične procese pretvaranja izvornog teksta. Unatoč činjenici da se interakcija ovih procesa može organizirati na različite načine, moguće je izdvojiti funkcije čije izvršavanje dovodi do istih rezultata. Takve funkcije nazivamo fazama procesa prevođenja.

S obzirom na sličnost prevoditelja i interpretera, razmotrimo faze koje postoje u prevoditelju. Ističe:

1. Faza leksičke analize.
2. Faza parsiranja, koja se sastoji od:

• prepoznavanje sintaktičke strukture;
• semantičko parsiranje, tijekom kojeg se provodi rad s tablicama, generiranje međusemantičke reprezentacije ili objektni model Jezik.

Faza generiranja koda, koja izvodi:

• semantička analiza komponenata međureprezentacije ili objektnog modela jezika;
• prevođenje posredne reprezentacije ili objektnog modela u objektni kod.

Uz glavne faze procesa prevođenja moguće su i dodatne faze:

2a. Faza istraživanja i optimizacije intermedijarne reprezentacije, koja se sastoji od:

2a.1. analiza ispravnosti posrednog prikaza;
2a.2. intermedijarna optimizacija predstavljanja.

3a. Faza optimizacije objektnog koda.

Interpretator se razlikuje po tome što se faza generiranja koda obično zamjenjuje fazom emulacije elemenata međureprezentacije ili objektnog modela jezika. Osim toga, tumač obično ne optimizira posredni prikaz, već ga odmah emulira.

Osim toga, moguće je izdvojiti jedan proces za sve faze analize i ispravljanja grešaka koje postoje u obrađenom izvornom kodu programa.

Generalizirana struktura prevoditelja, uzimajući u obzir faze koje postoje u njemu, prikazana je na sl. 1.4.

Sastoji se od leksičkog analizatora, parsera, generatora koda, analizatora grešaka. U interpreteru se umjesto generatora koda koristi emulator (sl. 1.5), u koji se, osim elemenata međureprezentacije, prenose i izvorni podaci. Izlaz emulatora je rezultat izračuna.

Leksički analizator (poznat i kao skener) čita ulazni niz znakova i grupira ih u elementarne konstrukte koji se nazivaju tokeni. Svaki token ima klasu i vrijednost. Obično elementarne konstrukcije jezika, na primjer, identifikator, pravi broj, komentar, djeluju kao kandidati za ulogu leksema. Rezultirajući tokeni prosljeđuju se parseru. Skener nije obavezni dio prevoditelja. Međutim, omogućuje povećanje učinkovitosti procesa prevođenja. Leksička analiza se detaljnije razmatra u temi: "Organizacija leksičke analize".

Parser analizira izvorni program koristeći dolazne tokene, gradi sintaktičku strukturu programa i provodi semantičku analizu s formiranjem objektnog modela jezika. Objektni model predstavlja sintaktičku strukturu dopunjenu semantičkim vezama između postojećih pojmova. Ove veze mogu biti:

• reference varijabli, tipovi podataka i nazivi procedura smješteni u tablice naziva;
• veze koje određuju redoslijed izvršavanja naredbi;
• poveznice koje određuju ugniježđenje elemenata objektnog modela jezika i druge.

Dakle, parser je prilično složen prevoditeljski blok. Stoga se može podijeliti na sljedeće komponente:

• prepoznavač;
• blok semantičke analize;
• objektni model ili intermedijarni prikaz koji se sastoji od tablice imena i sintaktičke strukture.

Generalizirana struktura parsera prikazana je na sl. 1.6.

Prepoznavač prima lanac tokena i na temelju njega ga analizira u skladu s korištenim pravilima. Tokeni se, nakon uspješnog analiziranja pravila, prosljeđuju semantičkom analizatoru, koji gradi tablicu imena i popravlja fragmente sintaktičke strukture. Osim toga, dodatne semantičke veze su fiksirane između tablice naziva i sintaktičke strukture. Kao rezultat, formira se objektni model programa, oslobođen vezivanja za sintaksu programskog jezika. Često se umjesto sintaktičke strukture koja u potpunosti kopira hijerarhiju jezičnih objekata, stvara njezin pojednostavljeni analog, koji se naziva intermedijarni prikaz.

Analizator pogrešaka prima informacije o pogreškama koje se javljaju u različitim blokovima prevoditelja. Koristeći primljene informacije, generira poruke korisniku. Osim, ovaj blok može pokušati ispraviti pogrešku kako bi nastavio s daljnjim analiziranjem. Također je odgovoran za točan završetak programa u slučaju da se daljnji prijenos ne može nastaviti.

Generator koda gradi objektni strojni kod na temelju analize objektnog modela ili posredne reprezentacije. Konstrukciju koda prati dodatna semantička analiza povezana s potrebom pretvaranja generaliziranih naredbi u kodove za određeno računalo. U fazi takve analize konačno se utvrđuje mogućnost transformacije i odabiru učinkovite opcije. Samo generiranje koda je kodiranje jednih naredbi u druge.

Mogućnosti interakcije za blokove prevoditelja

Organizacija procesa prevođenja, koja određuje provedbu glavnih faza, može se provesti na razne načine. To je određeno različitim opcijama za interakciju blokova prevoditelja: leksički analizator, parser i generator koda. Unatoč istom krajnjem rezultatu, razne opcije Interakcije blokova prevoditelja pružaju različite opcije za pohranjivanje posrednih podataka. Postoje dvije glavne opcije za interakciju blokova prevoditelja:

• višeprolazna organizacija, u kojoj je svaka od faza neovisan proces koji kontrolu prenosi na sljedeću fazu tek nakon završetka potpune obrade svojih podataka;
• organizacija s jednim prolazom, u kojoj sve faze predstavljaju jedan proces i prenose podatke jedna drugoj u malim fragmentima.

Na temelju dvije glavne opcije, također možete stvoriti različite kombinacije od njih.

Višeprolazna organizacija interakcije blokova prevoditelja

Ova varijanta interakcije blokova, koristeći kompilator kao primjer, prikazana je na slici 1.7.

Leksički analizator u potpunosti obrađuje izvorni tekst, tvoreći lanac koji se sastoji od svih primljenih leksema na izlazu. Tek nakon toga kontrola se prenosi na parser. Parser prima formirani lanac tokena i na temelju njega formira međureprezentaciju ili objektni model. Nakon što primi cijeli objektni model, predaje kontrolu generatoru koda. Generator koda, na temelju objektnog modela jezika, gradi potrebni strojni kod

Prednosti ovog pristupa uključuju:

1. Izolacija pojedinih faza, što omogućuje njihovu neovisnu implementaciju i korištenje.
2. Mogućnost pohranjivanja podataka dobivenih kao rezultat rada svake od faza na vanjske uređaje za pohranu i njihovo korištenje po potrebi.
3. Mogućnost smanjenja količine RAM-a potrebne za rad prevoditelja, zbog sekvencijalnog pozivanja faza.

Treba uzeti u obzir nedostatke.

1. Prisutnost velikih količina posrednih informacija, iz kojih ovaj trenutak potrebno je samo malo vremena.
2. Usporavanje brzine prijevoda zbog sekvencijalnog izvođenja faza i upotrebe vanjskih uređaja za pohranu radi uštede RAM-a.

Ovaj pristup može biti prikladan pri izradi prevoditelja iz programskih jezika sa složenom sintaktičkom i semantičkom strukturom (na primjer, PL/I). U takvim je situacijama teško prevesti u jednom prolazu, pa je lakše prikazati rezultate prethodnih prolaza kao dodatne međupodatke. Treba napomenuti da složene semantičke i sintaktičke strukture jezika mogu rezultirati dodatnim prolazima potrebnim za uspostavljanje potrebnih ovisnosti. Ukupan broj prolaza može biti veći od deset. Na broj prolaza također može utjecati programsko korištenje specifičnih jezičnih značajki, kao što je deklariranje varijabli i procedura nakon njihove upotrebe, primjena zadanih pravila deklaracije i tako dalje.

Jednoprolazna organizacija interakcije blokova prevoditelja

Jedna od opcija za interakciju blokova prevoditelja s organizacijom s jednim prolazom prikazana je na slici. 1.8.

U ovom slučaju, proces prevođenja odvija se na sljedeći način. Leksički analizator čita fragment izvornog teksta koji je potreban za dobivanje jednog tokena. Nakon formiranja leksema poziva parser i prosljeđuje mu kreirani leksem kao parametar. Ako parser može konstruirati sljedeći element posredne reprezentacije, on to čini i prosljeđuje konstruirani fragment generatoru koda. U suprotnom, parser vraća kontrolu skeneru, čime daje do znanja da je sljedeći token obrađen i da su potrebni novi podaci.

Generator koda funkcionira na sličan način. Na temelju primljenog fragmenta međureprezentacije kreira odgovarajući fragment objektnog koda. Nakon toga kontrola se vraća parseru.

Po završetku obrade izvornog teksta i završetka obrade svih međupodataka po svakom od blokova, leksički analizator pokreće proces završetka programa.

Najčešće, jednoprolazni prevoditelji koriste drugu kontrolnu shemu, u kojoj parser igra ulogu glavnog bloka (slika 1.9).

Leksički analizator i generator koda djeluju kao potprogrami koje pozivaju. Čim parser treba još jedan token, poziva skener. Kada se primi fragment međureprezentacije, upućuje se poziv generatoru koda. Završetak procesa prevođenja događa se nakon primanja i obrade posljednjeg tokena, a pokreće ga parser.

Prednosti sheme s jednim prolazom uključuju odsutnost velikih količina posrednih podataka, velika brzina obrade zbog kombinacije faza u jednom procesu i nedostatka pristupa vanjskim uređajima za pohranu.

Nedostaci uključuju: nemogućnost implementacije takve sheme prevođenja za jezike sa složenim strukturama i nedostatak posrednih podataka koji se mogu koristiti za složenu analizu i optimizaciju.

Takva se shema često koristi za programske jezike koji su jednostavni u semantičkim i sintaktičkim strukturama, kako u kompajlerima tako iu interpreterima. Basic i Pascal su primjeri takvih jezika. Klasični tumač obično se gradi prema shemi s jednim prolazom, budući da se izravno izvođenje provodi na razini pojedinačnih fragmenata međureprezentacije. Organizacija interakcije blokova takvog tumača prikazana je na sl. 1.10.

Kombinirane interakcije blokova prevoditelja

Kombinacije višeprolaznih i jednoprolaznih shema prevođenja dovode do niza kombiniranih opcija, od kojih se mnoge uspješno koriste. Pogledajmo neke od njih kao primjer.

Na sl. 1.11 prikazuje dijagram interakcije blokova prevoditelja, koji cijeli proces dijeli u dva prolaza. U prvom prolazu generira se potpuna međureprezentacija programa, a u drugom prolazu se vrši generiranje koda. Korištenje takve sheme olakšava prijenos prevoditelja s jednog računalnog sustava na drugi prepisivanjem generatora koda.

Osim toga, umjesto generatora koda, lako je spojiti posredni emulator reprezentacije, koji vrlo jednostavno omogućuje razvoj programskog sustava na određenom jeziku koji je orijentiran na različita izvršna okruženja. Primjer takve organizacije interakcije blokova prevoditelja prikazan je na sl. 1.12.

Uz sheme koje uključuju zamjenu generatora koda emulatorom, postoje prevoditelji koji im omogućuju da se koriste zajedno. Jedna od tih shema prikazana je na sl. 1.13.

Proces prevođenja, uključujući generiranje koda, može se dovršiti u bilo kojem broju prolaza (primjer koristi prijevod s jednim prolazom predstavljen ranije u ). Međutim, generirani objektni kod se ne izvršava na odgovarajućem računalnom sustavu, već se emulira na računalu s drugačijom arhitekturom. Takva se shema primjenjuje u okruženju izgrađenom oko jezika Java programiranje. Sam prevoditelj generira kod Java virtualnog stroja koji se emulira posebnim sredstvima kako samostalno tako iu okruženju internetskog preglednika.

Prikazana shema može imati širu interpretaciju u odnosu na bilo koji kompilator koji generira strojni kod. Stvar je u tome što je većina modernih računala implementirana pomoću mikroprogramske kontrole. Mikroprogramski upravljački uređaj može se smatrati programom koji emulira strojni kod. To nam omogućuje da govorimo o širokoj upotrebi posljednje predstavljene sheme.

Kontrolna pitanja i zadaci

1. Navedi razlike:

• prevodilac prevoditelj;
• kompajler iz asemblera;
• transkoder iz prevoditelja;
• emulator iz tumača;
• sintaksa iz semantike.

1. Recite nam o najnovijim dostignućima u programskim jezicima koje poznajete. Navedite glavne karakteristike ovih jezika.
2. Navedite konkretne primjere korištenja metoda prevođenja u područjima koja nisu povezana s programskim jezicima.
3. Navedite konkretne primjere kompiliranih programskih jezika.
4. Navedite konkretne primjere interpretiranih programskih jezika.
5. Navedite konkretne primjere programskih jezika za koje su dostupni i kompajleri i interpreteri.
6. Glavne prednosti i nedostaci kompilatora.
7. Glavne prednosti i nedostaci tumača.
8. Opišite glavne razlike u sintaksi dva programska jezika koja poznajete.
9. Opišite glavne razlike u semantici dva programska jezika koja poznajete.
10. Navedite glavne faze procesa prevođenja i njihovu svrhu.
11. Navedite specifičnosti jednoprolaznog prevođenja.
12. Navedite specifičnosti višeprolaznog prevođenja.
13. Navedite primjere mogućih kombinacija jednoprolaznog i višeprolaznog prevođenja. Reci o praktičnu upotrebu ove sheme.