Prevoditelj je ... Vrste prevoditelja. Pretvori i prevodi program

Programi, poput ljudi, zahtijevaju da prevoditelj ili prevoditelj prevede s jednog jezika na drugi.

Osnovni pojmovi

Program je jezični prikaz računanja: i → P → P (i). Tumač je program koji se unosi u program P i neke ulazne podatke x. Izvodi P na x: I (P, x) = P (x). Činjenica da postoji samo jedan prevoditelj sposoban za obavljanje svih mogućih programa (koji mogu biti zastupljeni u formalnom sustavu) vrlo je duboko i značajno otkriće Turinga.

Procesor je prevoditelj programa na jeziku stroja. Obično je preskupo napisati tumače za jezike na visokoj razini, pa su prevedeni u oblik koji je lakše tumačiti.

Neke vrste prevoditelja imaju vrlo čudna imena:

• Assembler prevodi programe u montažeru na strojni jezik.
• Kompilator prevodi od jezika visoke razine do jezika nižeg nivoa.

Prijenos - je program koji uzima kao input program na neki jezik S i proizvodi T programa na takav način da su obojica imaju iste semantiku: P → X → Q. To jest, forall-x. P (x) = Q (x).

Ako prevodite cijeli program u nešto što se interpretira, onda se to zove kompilacija prije izvršenja ili AOT-kompilacija. AOT-kompilatori se mogu koristiti sekvencijalno, od kojih je posljednja često sastavljač, na primjer:

Izvorni kod → Compiler (prevodilac) → Assembler code → Assembler (prevoditelj) → Šifra stroja → CPU (interpreter).

Online ili dinamička kompilacija nastaje ako se dio programa prevodi kada se izvrše drugi sastavljeni dijelovi. JIT-prevoditelji se sjećaju onoga što su već učinili, kako ne bi ponavljali izvorni kod opet i ponovo. Oni čak mogu proizvesti prilagodljivu kompilaciju i rekompiliranje, na temelju ponašanja okruženja programa runtime.

Mnogi jezici omogućuju vam izvršavanje koda tijekom prijevoda i sastavljanje novog koda tijekom izvođenja.

Faze prevođenja

Prijevod se sastoji od faza analize i sinteze:

Izvorni kôd → Analizator → Konceptualni pregled → Generator (sintesajzer) → Ciljni kôd.

To je zbog sljedećih razloga:

• Bilo koja druga metoda nije prikladna. Riječ po riječ prijevod jednostavno ne funkcionira.
• Dobro inženjersko rješenje: ako trebate pisati prevoditelje za M izvornog jezika i N ciljnih jezika, morat ćete samo pisati M + N jednostavne programe (semicompilers) umjesto M × N kompleksa (puni prevoditelji).

Ipak, u praksi, pojmovno predstavljanje vrlo je rijetko dovoljno izražajno i moćno za pokrivanje svih mogućih izvora i ciljnih jezika. Iako su se neki od njih mogli približiti tome.

Stvarni sastavljači prolaze kroz mnoge faze. Prilikom izrade vlastitog prevodioca ne morate ponoviti sav trud koji su ljudi već učinili prilikom izrade pregleda i generatora. Možete prevesti svoj jezik izravno u jаvascript ili C i koristiti postojeće jаvascript motore i C prevodioce kako bi učinili ostalo. Također možete koristiti postojeće prikaze medija i virtualni strojevi.

Zapisnik prevoditelja

Prevoditelj je program ili tehnički alat u kojem su uključeni tri jezika: izvor, cilj i osnovni. Može ih se napisati u obliku T-a, stavljajući izvor na lijevu stranu, cilj s desne strane i bazu u nastavku.

Postoje tri vrste sastavljača:

• Prevoditelj je self-compiler ako njegov izvorni jezik odgovara osnovnom jeziku.
• Prevodilac, čiji je ciljni jezik jednak osnovnom jeziku, zove se samostalan.
• Prevoditelj je unakrsni prevodilac, ako ima drugačiji cilj i osnovni jezik.

Zašto je to važno?

Čak i ako nikada niste pravi prevodilac, dobro je znati o tehnologiji njegova stvaranja, jer se koncepti koji se koriste za to primjenjuju svugdje, na primjer u:

• oblikovanje tekstova;
• upita jezika na baze podataka;
• proširene arhitekture računala;
• generalizirani problemi optimizacije;
• grafička sučelja;
• skriptni jezici;
• kontroleri;
• virtualni strojevi;
• strojni prijevodi.

Osim toga, ako želite napisati predprocesore, graditelje, punjače, ispravljače ili profilere, morate proći kroz iste korake kao kod pisanja prevoditelja.

Također možete naučiti kako bolje pisati programe, budući da stvaranje prevoditelja za jezik znači bolje razumijevanje svojih suptilnosti i dvosmislenosti. Učenje općih načela prevođenja također omogućava da postane dobar dizajnerica jezika. Je li to tako važno, koliko je oštar jezik, ako se ne može učinkovito ostvariti?

Sveobuhvatna tehnologija

Tehnologija prevoditelja obuhvaća mnoga različita područja računalne znanosti:

• formalna jezična teorija: gramatika, raščlanjivanje, računanje;
• računalna arhitektura: skup uputa, RISC ili CISC, cjevovod, jezgre, satni ciklusi, itd.;
• koncepti programskih jezika, na primjer, obavljanje kontrole slijedom, uvjetna izvršavanja, iteracija, rekurzije, funkcionalna dekompozicija, modularnost, sinkronizacije, meta-programiranje, opseg, stalno pod-vrste, predloške, izlaz tipa, prototipovi, bilješke, protoka, monadama, poštanski sandučići, i dalje , zamjenske znakove, regularni izraz, transakcijski memorije, nasljeđivanje, polimorfizam, postavke načina, i tako dalje itd..;
• apstraktni jezici i virtualni strojevi;
• algoritmi i strukture podataka: Redoviti izrazi, analitički algoritmi, grafički algoritmi, dinamičko programiranje, osposobljavanje;
• programski jezici: sintaksa, semantika (statička i dinamička), podrška paradigmama (strukturna, OOP, funkcionalna, logička, stog, konkurencija, metaprogramiranje);
• stvaranje softver (prevodiocima, obično veliki i složeni): lokalizacija, caching, componentize, API-sučelja, ponovno korištenje, sinkronizacija.

Izrada kompilera

Neki problemi koji nastaju pri razvoju pravog prevoditelja:

• Problemi s izvornim jezikom. Je li ga lako sastaviti? Postoji li preprocesor? Kako se vrste obrađuju? Postoje li knjižnice?
• Grupiranje prevodilaca prolazi: single- ili multi-pass?
• Stupanj željene optimizacije. Brzi i nečisti prijevod programa s malo ili nimalo optimizacije može biti normalno. Pretjerana optimizacija usporit će prevodilac, ali najbolji kôd pri izvođenju može biti vrijedan toga.
• Potrebna stopa otkrivanja pogrešaka. Može li prevoditelj samo zaustaviti prvu pogrešku? Kada bi trebao zaustaviti? Vjerujem li prevodilac ispraviti pogreške?
• Dostupnost alata. Ako izvorni jezik nije vrlo mali, skener i generator analizatora su obvezni. Postoje i generatori generatora kodova, ali nisu tako česti.
• Vrsta ciljnog koda za generaciju. Trebali biste odabrati čisti, povećani ili virtualni kôd stroja. Ili napišite samo unos koji stvara popularne prikaze interakcije, kao što su LLVM, RTL ili JVM. Ili izvodite prijevod s izvornog koda u C ili jаvascript.
• Oblik ciljnog koda. Možete odabrati jezik skupljača, prijenosni strojni kod, strojni kod slike memorije.
• Preusmjeravanja. Uz puno generatora, dobro je imati zajednički ulazni dio. Iz istog razloga, bolje je imati jedan generator za mnoge ulazne dijelove.

Arhitektura prevoditelja: komponente

To su glavne funkcionalne komponente prevodioca koji generira kôd stroja (ako je izlazni program C program ili virtualni stroj, onda nisu potrebni mnogi koraci):

• Ulazni program (tok znakova) ulazi u skener (leksički analizator), koji ga pretvara u tok tokena.
• Parser (parser) konstruira od njih apstraktni sintaktički stablo.
• Semantički analizator razgrađuje semantičke informacije i provjerava čvorove stabla za pogreške. Rezultat je semantički grafikon - apstraktno sintaksa s dodatnim svojstvima i instaliranim referencama.
• Generator srednjeg koda konstruira grafički tok (tuple su grupirane u glavne blokove).
• Alat za optimizaciju koda neovisan o stroju obavlja lokalno (unutar osnovnog bloka) i globalno (za sve blokove) optimizaciju, u osnovi ostaje unutar potprogramima. Smanjuje višak koda i pojednostavljuje izračune. Rezultat je izmijenjeni grafički dijagram toka.
• Generator ciljnog koda povezuje osnovne blokove s pravocrtnim kodom s prijenosom kontrole, stvarajući objektnu datoteku u asembleru s virtualnim registrima (možda neučinkovit).
• Alat za optimizaciju veza bez stroja alokira memoriju između registara i naredbi rasporeda. Pretvara program u montažeru na pravi sastavljač s dobrom upotrebom cjevovoda.

Nadalje, upotrebljavaju se podsustavi za otkrivanje pogrešaka i upravitelj tablice simbola.

Leksička analiza (skeniranje)

Skener pretvara tok znakova izvornog koda u tok tokena, uklanja razmake, komentare i širi makronaredbe.

Skeneri se često susreću s takvim problemima kao što su prihvaćanje ili ne uzimajući u obzir registar, uvlake, linije i ugniježđene komentare.

Pogreške koje se mogu pojaviti tijekom skeniranja nazivaju se leksičkim i uključuju:

• znakove koji nisu u abecedi;
• prekoračenje broja znakova u jednoj riječi ili nizu;
• a ne zatvoreni znak ili niz znakova;
• kraj datoteke u komentarima.

Analiza sintakse (raščlanjivanje)

Parser pretvara niz tokena u abstraktni sintaktički stablo. Svaki stablo čvora se sprema kao objekt s imenovanim poljima, od kojih su mnogi sami čvorovi stabla. U ovoj fazi nema ciklusa. Prilikom izrade parsera treba obratiti pažnju na razinu složenosti gramatike (LL ili LR) i saznati postoje li pravila za uklanjanje dvosmislenosti. Neki jezici zahtijevaju semantičku analizu.

Pogreške na koje se naišlo u ovoj fazi nazivaju se sintaksnim pogreškama. Na primjer:

• k = 5 * (7-y;
• j = / 5;
• 56 = x * 4.

Semantička analiza

Tijekom semantička analiza potrebno je provjeriti pravila o dopuštenosti i vezati dijelove stabla sintaksa (dopuštajući reference o imenu, umetanje operacija za implicitno lijevanje vrsta itd.) kako bi se stvorio semantički grafikon.

Očito, skup pravila o dopuštenosti za različite jezike različit je. Ako se jezici slični Java sastavljaju, prevoditelji mogu pronaći:

• višestruke deklaracije varijable unutar svog djelokruga;
• upućivanje na varijablu prije njezine izjave;
• reference na neprijavljeno ime;
• kršenje pravila o pristupačnosti;
• prevelik ili nedovoljan broj argumenata pri nazivanju metode;
• tip neusklađenosti.

generacija

Generirajući srednji kod stvara grafikon protoka koji se sastoji od tuplica grupiranih u osnovne blokove.

Generiranje koda stvara pravi strojni kod. U tradicionalnim prevodilima za RISC strojeve, u prvoj fazi, sastavljač se stvara s beskonačnim brojem virtualnih registara. Za CISC strojeve to se vjerojatno neće dogoditi.