Prevajalec je ... Vrste prevajalcev. Pretvarjanje in prevajanje programa

Programi, tako kot ljudje, zahtevajo, da prevajalec ali prevajalec prevede iz enega jezika v drugega.

Osnovni pojmi

Program je jezikovna predstavitev izračunov: i → P → P (i). Prevajalec je program, ki se napaja v program P in nekaj vhodnih podatkov x. Izvaja P na x: I (P, x) = P (x). Dejstvo, da obstaja le en prevajalec, ki je sposoben opravljati vse možne programe (ki se lahko predstavljajo v formalnem sistemu), je zelo globoko in pomembno odkritje Turinga.

Procesor je tolmač programov v strojnem jeziku. Običajno je predrag za pisanje tolmačev za jezike na visoki ravni, zato so prevedeni v obrazec, ki je lažje interpretirati.

Nekatere vrste prevajalcev imajo zelo čudna imena:

• Assembler prevaja programe v zbiralniku v strojni jezik.
• Prevajalnik prevaja iz jezika na visoki ravni v jezik nižjega nivoja.

Izdajatelj - je program, ki ima kot vhod program v nekaterih jezikovnih S in proizvaja programa T na tak način, da imata oba enako semantiko: P → X → Q. To je, forall-x. P (x) = Q (x).

Če prevedete celoten program v nekaj, kar se razlaga, se to imenuje kompilacija pred izvedbo ali AOT-kompilacija. Kompilatorji AOT se lahko uporabijo zaporedno, slednji pa je pogosto asembler, na primer:

Izvorna koda → Prevajalnik (prevajalnik) → Koda zbirke → Asembler (prevajalnik) → Koda naprave → CPU (tolmača).

Spletno ali dinamično zbiranje se zgodi, če je del programa preveden, ko se izvedejo drugi sestavljeni deli. JIT-prevajalci se spomnite, kaj so že naredili, da ne bi ponovili izvorne kode znova in znova. Lahko celo ustvarijo adaptivno kompilacijo in prevedbo, ki temelji na obnašanju okolja programa.

Številni jeziki vam omogočajo, da med prevodom izvršite kodo in zbrišete novo kodo ob zagonu.

Faze prevajanja

Prevod sestavljajo faze analize in sinteze:

Izvorna koda → Analizator → Idejni pogled → Generator (sintetizator) → Ciljna koda.

To je posledica naslednjih razlogov:

• Katera koli druga metoda ni primerna. Prevajanje besed po besedah ​​preprosto ne deluje.
• Dobra rešitev inženiring: če želite napisati prevajalcev M in N izvirnih jezikih ciljnih treba napisati le preproste programe M + N (polukompilyatorov) namesto M × N kompleksa (skupno prevajalcev).

Kljub temu pa je v praksi konceptualna predstavitev zelo redko dovolj izrazna in močna za pokrivanje vseh možnih virov in ciljnih jezikov. Čeprav bi se nekateri lahko približali temu.

Resnični prevajalniki gredo skozi več stopenj. Pri ustvarjanju lastnega prevajalnika vam ni treba ponoviti vsega trdega dela, ki so ga ljudje že naredili pri ustvarjanju pogledov in generatorjev. Jezik lahko prevedete neposredno v jаvascript ali C in za preostale delate obstoječe jаvascript motorje in prevajalce C. Uporabite lahko tudi obstoječe vmesne preglede in virtualni stroji.

Posnetek prevajalca

Prevajalec je program ali tehnično orodje, v katerem sodelujejo trije jeziki: vir, cilj in osnovno. Lahko jih zapišemo v T-obrazcu, postavimo vir na levo, cilj na desni in spodnji del osnove.

Obstajajo tri vrste prevajalcev:

• Prevajalec je samocililec, če njegov izvorni jezik ustreza osnovnemu jeziku.
• Prevajalnik, katerega ciljni jezik je enak osnovnemu jeziku, se imenuje samozaposleni.
• Prevajalec je navzkrižni prevajalnik, če ima cilj in osnovni jezik drugačen.

Zakaj je to pomembno?

Tudi če nikoli ne ustvarite pravega prevajalnika, je dobro vedeti o tehnologiji njenega ustvarjanja, saj se uporabljajo koncepti za to povsod, na primer pri:

• oblikovanje besedil;
• jeziki poizvedbe do baz podatkov;
• razširjene računalniške arhitekture;
• splošni optimizacijski problemi;
• grafični vmesniki;
• skriptni jeziki;
• kontrolorji;
• virtualni stroji;
• strojni prevodi.

Poleg tega, če želite napisati preprocessors, builders, loaders, debugers ali profilers, morate iti skozi iste korake kot pri pisanju prevajalnika.

Prav tako se lahko naučite bolje pisati programe, saj ustvarjanje prevajalca za jezik pomeni boljše razumevanje njenih plodov in dvoumnosti. Učenje splošnih načel prevajanja omogoča tudi, da postane dober oblikovalec jezika. Ali je tako pomembno, kako oster je jezik, če se ne more učinkovito uresničiti?

Celovita tehnologija

Tehnologija prevajalnika zajema številna področja računalništva:

• formalna teorija jezikov: slovnica, razčlenjevanje, računanje;
• računalniška arhitektura: sklopi navodil, RISC ali CISC, cevovodi, jedra, ura ciklusi itd .;
• koncepti programskih jezikov, na primer, ki opravljajo nadzor zaporedno, pogojna izvršitve, ponovitev, rekurzija, funkcionalna razpad, modularnost, sinhronizacijo, meta-programiranje, obseg, stalne podtipi, predloge, izhod tipa, prototipi, pripisi, pretoka, monads, nabiralniki, še naprej , nadomestni znaki, regularni izrazi, transakcijski spomin, dedovanje, polimorfizem, načini parametrov itd.
• abstraktni jeziki in virtualni stroji;
• algoritmi in podatkovne strukture: Redni izrazi, algoritmi razčlenjevanja, grafični algoritmi, dinamično programiranje, usposabljanje;
• programskih jezikov: sintaksa, semantika (statične in dinamične), nosilni paradigm (strukturna, OOP, funkcionalen, logično, sklad, vzporednost, meta-programiranje);
• ustvarjanje programske opreme (prevajalniki so praviloma veliki in zapleteni): lokalizacija, predpomnjenje, komponentiranje, vmesniki API, ponovna uporaba, sinhronizacija.

Oblikovanje prevajalnika

Nekateri problemi, ki nastanejo pri razvoju resničnega prevajalca:

• Težave z izvornim jezikom. Ali ga je enostavno sestaviti? Ali obstaja predprocesor? Kako se obravnavajo vrste? Ali obstajajo knjižnice?
• Združevanje prevajalcev prevajalnika: eno ali večkratno?
• Stopnja želene optimizacije. Hitri in nečisti prevod programa z malo ali nič optimizacije je lahko običajen. Prekomerna optimizacija bo upočasnila prevajalnik, vendar bi bila morda najboljša koda v času izvajanja.
• Zahtevana stopnja odkrivanja napak. Ali se lahko prevajalec preprosto ustavi pri prvi napaki? Kdaj naj ustavi? Ali verjamem, da je prevajalnik popravil napake?
• Razpoložljivost orodij. Če izvorni jezik ni zelo majhen, sta generatorja skenerja in analizatorja obvezna. Obstajajo tudi generatorji generatorjev kode, vendar niso tako pogosti.
• Vrsta ciljne kode za generiranje. Izberite čisto, razširjeno ali navidezno strojno kodo. Ali pa samo napišite vhod, ki ustvarja priljubljene vmesne poglede, kot so LLVM, RTL ali JVM. Ali pa prevedite iz vira v izvorno kodo v C ali jаvascript.
• Oblika ciljne kode. Izberete lahko jezik asemblerja, prenosna strojna koda, strojna koda pomnilniške slike.
• Perenatselivanie. Z veliko generatorji je dobro imeti skupen vhodni del. Iz istega razloga je bolje imeti en generator za številne vhodne dele.

Arhitektura sestavnega dela: komponente

To so glavne funkcionalne komponente prevajalnika, ki ustvarja strojno kodo (če je izhodni program program C ali navidezni stroj, potem ni potrebno veliko korakov):

• Vhodni program (tok znakov) vstopi v skener (lexical analyzer), ki ga pretvori v tok žetonov.
• Razčlenjevalnik (parser) iz njih izdeluje abstraktno sintakso.
• Semantični analizator razpade semantične podatke in preveri vozlišča drevesa za napake. Rezultat je semantični graf - abstraktno sintaktično drevo z dodatnimi lastnostmi in nameščenimi referencami.
• Vmesni kodni generator konstruira pretočni graf (tulepi so združeni v glavne bloke).
• Strojno neodvisen koda optimizer opravlja tako lokalno (znotraj osnovnega bloka) kot globalno (za vse bloke) optimizacijo, ki v bistvu ostane znotraj podprogramov. Zmanjša odvečno kodo in poenostavlja izračune. Rezultat je spremenjeni grafični tok.
• Generator ciljne kode povezuje osnovne baze z ravno črtno kodo s krmilnim prenosom, tako da ustvari datoteko s predmeti v zbirniku z navideznimi registri (morda neučinkovita).
• Strojno neodvisen linker optimizer dodeljuje pomnilnik med registri in ukazi za urnike. Pretvarja program v zbiralniku realnemu zbiralcu z dobro uporabo pipelininga.

Poleg tega se uporabljajo podsistemi za odkrivanje napak in upravljalnik tabličnih simbolov.

Leksikalna analiza (skeniranje)

Skener pretvori tok znakov izvorne kode v tok žetonov, odstranjuje presledke, pripombe in razširja makre.

Skenerji pogosto naletijo na take težave, kot so sprejemanje ali neupoštevanje registra, nakaznic, vrstičnih virov in ugnezdenih komentarjev.

Napake, ki se lahko pojavijo med skeniranjem, se imenujejo lexical in vključujejo:

• znaki, ki niso v abecedi;
• presega število znakov v besedi ali nizu;
• ni zaprt znak ali niz besed;
• konec datoteke v komentarjih.

Sintaktična analiza (razčlenjevanje)

Razčlenjevalnik pretvori zaporedje žetonov v abstraktno sintaktično drevo. Vsako drevo vozlišča se shrani kot objekt z imenovanimi polji, od katerih so mnoge same vozlišča drevesa. Na tej stopnji ni ciklov. Ko ustvarjate razčlenjevalnik, bodite pozorni na stopnjo kompleksnosti slovnice (LL ali LR) in ugotovite, ali obstajajo pravila za odpravo dvoumnosti. Nekateri jeziki zahtevajo semantično analizo.

Napake, ki so se pojavile v tej fazi, se imenujejo sintaktične napake. Na primer:

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

Semantična analiza

V času semantična analiza je treba preveriti pravila o dopustnosti in povezati dele drevesa sintakse (omogočiti sklicevanje na ime, vstavljanje operacij za implicitno oddajo tipov itd.), da se oblikuje semantični graf.

Očitno je, da so pravila dopustnosti za različne jezike drugačna. Če so zbrani jeziki, ki so podobni Java, lahko prevajalci najdejo:

• večkratne deklaracije spremenljivke v okviru njene uporabe;
• sklic na spremenljivko pred njeno izjavo;
• sklicevanje na neprijavljeno ime;
• kršitev pravil dostopa;
• preveliko ali nezadostno število argumentov pri klicanju metode;
• neusklajenost tipa.

Generacija

Generiranje vmesne kode proizvede pretočni graf, sestavljen iz tuplesov, združenih v osnovni blok.

Generacija kode proizvaja pravo strojno kodo. V tradicionalnih prevajalnikih za RISC stroje je v prvi fazi sestavljen zbiralnik z neskončnim številom navideznih registrov. Za stroje CISC se to verjetno ne bo zgodilo.