Prekladateľ je ... Typy prekladateľov. Konvertovať a preložiť program

Programy, ako ľudia, vyžadujú, aby prekladateľ alebo prekladateľ prekladal z jedného jazyka do druhého.

Základné pojmy

Program je jazykovou reprezentáciou výpočtov: i → P → P (i). Tlmočník je program, ktorý prijíma vstup P a niektoré vstupné dáta x. Vykonáva P na x: I (P, x) = P (x). Skutočnosť, že existuje jediný prekladateľ schopný vykonať všetky možné programy (ktoré môžu byť zastúpené vo formálnom systéme) je veľmi hlboký a významný objav Turinga.

Procesor je tlmočníkom programov v jazyku stroja. Zvyčajne je príliš drahé písať tlmočníkov pre jazyky vyššej úrovne, takže sú preložené do formy, ktorú je možné ľahšie interpretovať.

Niektoré typy prekladateľov majú veľmi zvláštne názvy:

• Assembler prekladá programy v assembleri do jazyka počítača.
• Kompilátor prekladá z jazyka vysokej úrovne do jazyka nižšej úrovne.

Prekladateľ je program, ktorý prijíma program v nejakom jazyku S ako jeho vstup a vytvára program v T takým spôsobom, že obaja majú rovnakú sémantiku: P → X → Q. To znamená ∀x. P (x) = Q (x).

Ak preložíte celý program do niečoho, čo sa interpretuje, potom sa to nazýva kompilácia pred vykonaním alebo kompilácia AOT. AOT kompilátory môžu byť použité postupne, z ktorých posledný je často assembler, napríklad:

Zdrojový kód → Prekladač (kompilátor) → Kód pre assembler → Assembler (prekladač) → Kód stroja → CPU (tlmočník).

Online alebo dynamická kompilácia sa vyskytuje, ak je časť programu preložená, keď sú vykonané iné kompilované časti. JIT-prekladatelia si pamätajú, čo už urobili, aby nezopakovali zdrojový kód znovu a znovu. Môžu dokonca vytvárať prispôsobivú kompiláciu a kompiláciu založenú na správaní runtime prostredia.

Mnoho jazykov umožňuje vykonávať kód počas prekladu a zostavovať nový kód počas behu.

Etapy prekladu

Preklad pozostáva z fáz analýzy a syntézy:

Zdrojový kód → Analyzátor → Koncepčné zobrazenie → Generátor (syntetizátor) → Cieľový kód.

Je to spôsobené nasledujúcimi dôvodmi:

• Iná metóda nie je vhodná. Preklad slovom po hlavičke jednoducho nefunguje.
• Dobré technické riešenie: ak potrebujete písať prekladateľov pre zdrojové jazyky M a N cieľové jazyky, musíte napísať iba M + N jednoduché programy (semicompilers), nie MxN komplex (plné preklady).

Avšak v praxi je koncepčné vyjadrenie veľmi zriedka dostatočne výrazné a silné na to, aby pokrylo všetky mysliteľné zdrojové a cieľové jazyky. Aj keď sa niektorí z nich môžu dostať blízko k tomu.

Skutočné kompilátory prechádzajú mnohými etapami. Pri vytváraní vlastného kompilátora nemusíte opakovať všetku tvrdú prácu, ktorú ľudia urobili pri vytváraní zobrazení a generátorov. Môžete preložiť svoj jazyk priamo do jazyka JavaScript alebo C a používať existujúce motory JavaScript a kompilátory C, aby ste mohli robiť zvyšok. Môžete tiež použiť existujúce prechodové zobrazenia a virtuálne stroje.

Záznam prekladateľa

Prekladateľ je program alebo technický nástroj, v ktorom sú zapojené tri jazyky: zdroj, cieľ a základné. Môžu byť napísané vo forme T, pričom zdroj umiestnený vľavo, cieľ vpravo a základňa nižšie.

Existujú tri typy kompilátorov:

• Prekladateľ je vlastný prekladač, ak jeho zdrojový jazyk zodpovedá základnému jazyku.
• Kompilátor, ktorého cieľový jazyk sa rovná základnému jazyku, sa nazýva osoba s trvalým pobytom.
• Prekladateľ je krížový kompilátor, ak má iný cieľový jazyk a základný jazyk.

Prečo je to dôležité?

Aj keby ste nikdy nevytvorili skutočného kompilátora, je dobré vedieť o technológii jeho tvorby, pretože použité pojmy sa uplatňujú všade, napríklad v:

• Formátovanie textov;
• Jazyky dopytov do databáz;
• Rozšírené počítačové architektúry;
• Generalizované problémy s optimalizáciou;
• Grafické rozhrania;
• Skriptovacie jazyky;
• regulátory;
• Virtuálne stroje;
• Strojové preklady.

Okrem toho, ak chcete napísať preprocesory, staviteľa, nakladače, debuggery alebo profilárov, musíte postupovať rovnako, ako pri písaní kompilátora.

Môžete sa tiež naučiť, ako lepšie napísať programy, keďže vytvorenie prekladateľa pre jazyk znamená lepšie pochopenie jeho jemností a nejednoznačností. Učenie sa o všeobecných zásadách prekladu tiež umožňuje stať sa dobrým jazykovým dizajnérom. Je také dôležité, aký je jazyk, ak sa nemôže efektívne realizovať?

Komplexná technológia

Technológia kompilátorov pokrýva rôzne oblasti počítačovej vedy:

• Formálna jazyková teória: gramatika, analýza, výpočet;
• Počítačová architektúra: inštrukčné súpravy, RISC alebo CISC, pipelining, jadrá, cykly hodín, atď .;
• Koncepty programovacích jazykov: napríklad sekvenčné riadenie, podmienené vykonávanie, iterácia, rekurzia, funkčný rozklad, modularita, synchronizácia, metaprogramovanie, rozsah, konštanty, podtypy, šablóny, typ výstupu, prototypy, anotácie, vlákna, monády, poštové schránky, rozšírenia , Zástupné znaky, regulárne výrazy, transakčná pamäť, dedičnosť, polymorfizmus, režimy parametrov atď .;
• Abstraktné jazyky a virtuálne stroje;
• Algoritmy a dátové štruktúry: regulárne výrazy, parsovacie algoritmy, grafické algoritmy, dynamické programovanie, učenie;
• Programovacie jazyky: syntax, sémantika (statická a dynamická), podpora paradigiem (štrukturálne, OOP, funkčné, logické, zásobník, súbežnosť, metaprogramovanie);
• Tvorba softvéru (kompilátory, spravidla veľké a komplexné): lokalizácia, ukladanie do vyrovnávacej pamäte, komponenty, API rozhrania, opätovné použitie, synchronizácia.

Navrhovanie kompilátora

Niektoré problémy, ktoré vznikajú pri vývoji skutočného prekladateľa:

• Problémy so zdrojovým jazykom. Je ľahké ho zostaviť? Existuje preprocesor? Ako sa s týmito druhmi zaobchádza? Existujú knižnice?
• Zoskupenie priečinkov prekladača: jedno- alebo viacstupňové?
• Stupeň požadovanej optimalizácie. Rýchly a nečistý preklad programu s malou alebo žiadnou optimalizáciou môže byť normálny. Nadmerná optimalizácia spomalí kompilátor, ale najlepší kód za behu môže stáť za to.
• Požadovaná miera zisťovania chýb. Môže sa prekladateľ zastaviť len pri prvej chybe? Kedy by mal prestať? Veríte kompilátorovi na opravu chýb?
• Dostupnosť nástrojov. Ak zdrojový jazyk nie je veľmi malý, generátor skenera a analyzátora je povinný. Existujú aj generátory kódových generátorov, ale nie sú tak bežné.
• Typ cieľového kódu pre generovanie. Mali by ste si vybrať z čistého, rozšíreného alebo virtuálneho stroja kód. Alebo stačí napísať vstup, ktorý vytvára obľúbené medziľahlé zobrazenia, napríklad LLVM, RTL alebo JVM. Alebo vykonajte preklad zo zdroja do zdrojového kódu v C alebo JavaScript.
• Formát cieľového kódu. Môžete vybrať jazyk pre zostavu, prenosný kód stroja, kód stroja pre pamäťový obrázok.
• Presmerovanie. S množstvom generátorov je dobré mať spoločnú vstupnú časť. Z toho istého dôvodu je lepšie mať jeden generátor pre mnoho vstupných častí.

Architektúra kompilátorov: Komponenty

Jedná sa o hlavné funkčné komponenty prekladateľa, ktorý generuje strojový kód (ak je výstupný program C alebo virtuálny stroj, nevyžaduje sa veľa krokov):

• Vstupný program (prúd znakov) vstupuje do skenera (lexikálny analyzátor), ktorý ho konvertuje na tok symbolov.
• Analyzátor (syntaktický analyzátor) z nich vytvára abstraktný syntaktický strom.
• Sémantický analyzátor rozkladá sémantické informácie a kontroluje uzly stromu kvôli chybám. V dôsledku toho je vytvorený sémantický graf - abstraktný syntaktický strom s ďalšími vlastnosťami a inštalovanými referenciami.
• Generátor medziľahlých kódov vytvára graf prietoku (nuly sú zoskupené do hlavných blokov).
• Optimalizátor kódov nezávislý od stroja vykonáva optimalizáciu lokálnych (v základnom bloku) a globálnej (pre všetky bloky), v podstate zostávajúcich v podprogramoch. Znižuje redundantný kód a zjednodušuje výpočty. Výsledkom je upravený graf toku.
• Generátor cieľového kódu spája základné bloky s riadiacim kódom s riadiacim prenosom, čím vytvára súbor objektov v assembleri s virtuálnymi registrami (možno neefektívne).
• Optimalizátor odkazovačov nezávislý od stroja prideľuje pamäť medzi registrami a príkazmi plánovania. Prevádza program do assemblera na skutočného assemblera s dobrým použitím pipeline.

Okrem toho sa používajú podsystémy detekcie chýb a správca tabuliek symbolov.

Lexikálna analýza (skenovanie)

Skener prevádza prúd znakov zdrojového kódu do toku tokenov, odstraňuje medzery, komentáre a rozširuje makrá.

Skenery sa často stretávajú s problémami, ako je napríklad prijímanie alebo neberanie do úvahy registra, zarážok, informačných kanálov a vnorených komentárov.

Chyby, ktoré sa môžu vyskytnúť počas skenovania, sa nazývajú lexikálne a zahŕňajú:

• Znaky, ktoré nie sú v abecede;
• Prekročenie počtu znakov v slove alebo reťazci;
• Nie je uzavretý znak alebo reťazec doslovný;
• Koniec súboru v komentári.

Analýza syntaxe (analýza)

Analyzátor konvertuje poradie žetónov na strom abstraktných syntaktí. Každý uzol stromu sa uloží ako objekt s pomenovanými poľami, z ktorých mnohé sú uzly stromu. V tomto štádiu nie sú žiadne cykly. Pri vytváraní analyzátora by ste mali venovať pozornosť úrovni zložitosti gramatiky (LL alebo LR) a zistiť, či existujú pravidlá na odstránenie nejednoznačnosti. Niektoré jazyky vyžadujú sémantickú analýzu.

Chyby vyskytujúce sa v tomto štádiu sa nazývajú syntaktické chyby. Napríklad:

• K = 5 * (7 - y;
• J = 5;
• 56 = x * 4.

Sémantická analýza

Počas sémantickej analýzy je potrebné skontrolovať pravidlá prípustnosti a spájať časti stromu syntaxe (umožňujúce odkazy na názvy, vkladanie operácií pre implicitné odlievanie typov atď.) A vytvárať sémantický graf.

Samozrejme, súbor pravidiel prípustnosti pre rôzne jazyky je odlišný. Ak sa jazyky, ktoré sa podobajú jazyku Java, môžu prekladatelia nájsť:

• Viacnásobné vyhlásenia premennej v rámci jej rozsahu;
• Odkaz na premennú pred jej vyhlásením;
• Odkazy na neodoslané meno;
• Porušenie pravidiel prístupu;
• Príliš veľký alebo nedostatočný počet argumentov pri volaní metódy;
• Nesúlad typu.

generácie

Generovanie medzipriestoru vytvára graf toku pozostávajúci z n-tiel zoskupených do základných blokov.

Generovanie kódu vytvára skutočný kód stroja. V tradičných kompilátoch pre stroje RISC, prvý stupeň vytvára zostavu s nekonečným počtom virtuálnych registrov. Pri strojoch CISC sa to pravdepodobne nestane.