Překladatel je ... Typy překladatelů. Převést a přeložit program

Programy, stejně jako lidé, vyžadují, aby překladatel nebo překladatel překládali z jednoho jazyka do druhého.

Základní pojmy

Program je jazykovou reprezentací výpočtů: i → P → P (i). Tlumočník je program, jehož vstup je dán programem P a některými vstupními daty x. Vykonává P na x: I (P, x) = P (x). Skutečnost, že existuje jediný překladatel schopný provádět všechny možné programy (které mohou být zastoupeny ve formálním systému) je velmi hlubokým a významným objevem Turinga.

Procesor je tlumočník programů v jazyce stroje. Obvykle je příliš nákladné psát tlumočníky pro jazyky vysoké úrovně, takže jsou překládány do formy, která je jednodušší interpretovat.

Některé typy překladatelů mají velmi podivné názvy:

• Assembler převádí programy do assembleru do jazyka počítače.
• Kompilátor převádí z jazyka na vyšší úroveň do jazyka nižší úrovně.

Překladatel je program, který přijímá program v nějakém jazyce S jako jeho vstup a produkuje program v T takovým způsobem, že oba mají stejnou sémantiku: P → X → Q. To znamená ∀x. P (x) = Q (x).

Převedete-li celý program na něco, co je interpretováno, pak se to nazývá kompilace před provedením nebo kompilací AOT. Kompilátory AOT mohou být použity postupně, poslední z nich je často assembler, například:

Zdrojový kód → Kompilátor (kompilátor) → Kód assembleru → Assembler (překladatel) → Kód stroje → CPU (tlumočník).

On-line nebo dynamické kompilace dochází, pokud část programu je přeložen, když jiné kompilované části jsou spuštěny. Překladatelé JIT si pamatují, co již udělali, aby znovu a znovu nezopakovali zdrojový kód. Mohou dokonce produkovat adaptivní kompilaci a recompilaci založenou na chování prostředí běhu.

Mnoho jazyků umožňuje provádět kód během překladu a kompilovat nový kód za běhu.

Etapy překladu

Překlad se skládá z etap analýzy a syntézy:

Zdrojový kód → Analyzátor → Koncepční pohled → Generátor (syntetizátor) → Cílový kód.

To je způsobeno následujícími důvody:

• Jiný způsob není vhodný. Přeložení slov po druhém jednoduše nefunguje.
• Dobré technické řešení: pokud potřebujete napsat překladatele pro zdrojové jazyky M a N cílové jazyky, musíte napsat pouze M + N jednoduché programy (semikompily), ne MxN komplex (plné překladače).

Nicméně v praxi je koncepční reprezentace velmi zřídka dostatečně expresivní a silná, aby pokryla všechny myslitelné zdrojové a cílové jazyky. Přestože se někteří z nich mohou přiblížit.

Reálné překladače procházejí mnoha etapami. Při vytváření vlastního kompilátoru nepotřebujete opakovat veškerou tvrdou práci, kterou lidé učinili při vytváření pohledu a generátorů. Můžete přeložit svůj jazyk přímo do jazyka JavaScript nebo C a používat ostatní existující motory JavaScriptu a kompilátory C, abyste mohli dělat zbytek. Můžete také použít existující přehledu a virtuální stroje.

Záznam překladatele

Překladatel je program nebo technický nástroj, ve kterém jsou zapojeny tři jazyky: zdroj, cíl a základní. Mohou být zapsány ve tvaru T, umístěním zdroje nalevo, cíle vpravo a podstavce níže.

Existují tři typy kompilátorů:

• Překladatel je překladač, pokud jeho zdrojový jazyk odpovídá základnímu.
• Kompilátor, jehož cílový jazyk se rovná základnímu jazyku, se nazývá osoba s trvalým pobytem.
• Překladatel je křížový překladač, pokud má jiný cílový jazyk a základní jazyk.

Proč je to důležité?

Dokonce i kdybyste nikdy nevytvořili skutečný kompilátor, je dobré vědět o technologii jeho tvorby, protože pojmy použité pro toto jsou použity všude, například v:

• Formátování textů;
• Dotazování jazyků do databází;
• Rozšířené počítačové architektury;
• Generalizované problémy s optimalizací;
• Grafické rozhraní;
• Skriptovací jazyky;
• Kontroléry;
• Virtuální stroje;
• Strojní překlady.

Kromě toho, pokud chcete psát preprocesory, stavitele, načístače, debuggery nebo profilry, musíte projít stejnými kroky jako při psaní kompilátoru.

Můžete se také naučit psát programy lépe, protože vytvoření překladače pro jazyk znamená lepší pochopení jeho jemností a nejednoznačností. Učení se o obecných zásadách překladu také umožňuje stát se dobrým jazykovým výtvarníkem. Je to tak důležité, jak výrazný je jazyk, pokud nemůže být účinně realizován?

Komplexní technologie

Technologie kompilátorů pokrývá mnoho různých oblastí počítačové vědy:

• Formální teorie jazyků: gramatika, analýza, výpočetní schopnost;
• Architektura počítačů: instrukční sady, RISC nebo CISC, potrubí, jádra, cykly hodin atd.;
• Koncepty programovacích jazyků: například sekvenční řízení, podmíněné provedení, iterace, rekurze, funkční rozklad, modularita, synchronizace, metaprogramování, rozsah, konstanty, podtypy, šablony, výstupy, prototypy, anotace, , Zástupné znaky, regulární výrazy, transakční paměť, dědičnost, polymorfismus, parametrické režimy atd.;
• Abstraktní jazyky a virtuální stroje;
• Algoritmy a datové struktury: regulární výrazy, parsing algoritmy, grafické algoritmy, dynamické programování, učení;
• Programovací jazyky: syntaxe, sémantika (statická a dynamická), podpora paradigmat (strukturální, OOP, funkční, logické, zásobník, souběžnost, metaprogramování);
• Tvorba softwaru (kompilátory, zpravidla velké a složité): lokalizace, ukládání do mezipaměti, komponenty, rozhraní API, opakované použití, synchronizace.

Navrhování kompilátoru

Některé problémy, které vznikají při vývoji skutečného překladatele:

• Problémy se zdrojovým jazykem. Je snadné je kompilovat? Existuje preprocesor? Jak se zpracovávají typy? Existují knihovny?
• Seskupování průchodů kompilátorů: jednoduché nebo vícedílné?
• Stupeň požadované optimalizace. Rychlý a nečistý překlad programu s malou nebo žádnou optimalizací může být normální. Nadměrná optimalizace zpomalí kompilátor, ale nejlepší kód za běhu může stát za to.
• Požadovaná míra zjišťování chyb. Může se překladatel zastavit na první chybě? Kdy by měl přestat? Věříte kompilátoru k opravě chyb?
• Dostupnost nástrojů. Pokud zdrojový jazyk není příliš malý, generátor skeneru a analyzátoru je povinný. Existují také generátory kódových generátorů, ale nejsou tak běžné.
• Typ cílového kódu pro generování. Měli byste si vybrat z čistého, rozšířeného nebo virtuálního stroje. Nebo stačí napsat vstup, který vytvoří oblíbené přehledu, například LLVM, RTL nebo JVM. Nebo proveďte překlad ze zdroje do zdrojového kódu v C nebo JavaScript.
• Formát cílového kódu. Můžete zvolit jazyk sestavení, přenosný strojový kód, strojový kód obrazu paměti.
• Perenatselivanie. S mnoha generátory je dobré mít společnou vstupní část. Ze stejného důvodu je lepší mít jeden generátor pro mnoho vstupních částí.

Kompilátorová architektura: Komponenty

Jedná se o hlavní funkční komponenty překladače, který generuje strojový kód (pokud je výstupním programem program C nebo virtuální stroj, pak se nevyžaduje mnoho kroků):

• Vstupní program (proud signálů) vstupuje do skeneru (lexikální analyzátor), který jej převádí do toku tokenů.
• Analyzátor (analyzátor) z nich vytváří abstraktní syntaktický strom.
• Sémantický analyzátor rozkládá sémantické informace a kontroluje uzly stromu kvůli chybám. V důsledku toho je vytvořen sémantický graf - abstraktní syntaktický strom s dalšími vlastnostmi a nainstalovanými odkazy.
• Generátor mezilehlého kódu vytváří graf proudění (nopky jsou seskupeny do hlavních bloků).
• Optimalizátor kódů nezávislý na stroji provádí optimalizaci lokální (v základním bloku) a globální (pro všechny bloky), která v podstatě zůstává v rámci podprogramů. Snižuje redundantní kód a zjednodušuje výpočty. Výsledkem je upravený graf toku.
• Generátor cílových kódů propojuje základní bloky s přímým kódem s přenosem řídicího systému a vytváří soubor objektů v assembleru s virtuálními registry (možná neúčinnými).
• Optimalizátor linkerů nezávislý na stroji přiděluje paměť mezi registry a rozvrhy příkazů. Převede program do assembleru na reálného assembleru s dobrým použitím pipeline.

Kromě toho se používají subsystémy detekce chyb a správce tabulky symbolů.

Lexikální analýza (skenování)

Skener převádí proud znaků zdrojového kódu do tokenů, odstraňuje mezery, komentuje a rozšiřuje makra.

Skenery se často setkávají s problémy, jako je například přijetí nebo nezohlednění rejstříku, odrážek, kanálových řádků a vnořených komentářů.

Chyby, které se mohou vyskytnout během skenování, se nazývají lexikální a zahrnují:

• Znaky, které nejsou v abecedě;
• Překročení počtu znaků v jednom slovu nebo řetězci;
• Ne uzavřený znak nebo řetězec doslovný;
• Konec souboru v komentáři.

Analýza syntaxe (parsování)

Analyzátor konvertuje posloupnost žetonů do stromu abstraktní syntaxe. Každý uzel stromu je uložen jako objekt s pojmenovanými poli, z nichž mnohé jsou uzly stromu. V této fázi nejsou žádné cykly. Při vytváření analyzátoru byste měli věnovat pozornost úrovni složitosti gramatiky (LL nebo LR) a zjistit, zda existují nějaká pravidla pro odstranění nejednoznačnosti. Některé jazyky vyžadují sémantickou analýzu.

Chyby zjištěné v této fázi se nazývají chyby syntaxe. Například:

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

Sémantická analýza

Během sémantické analýzy je nutné zkontrolovat pravidla přijatelnosti a vázat části stromu syntaxe (umožňující odkazy na názvy, vkládání operací pro implicitní odlévání typů apod.) A vytvořit sémantický graf.

Je zřejmé, že soubor pravidel o přípustnosti pro různé jazyky je jiný. Jsou-li kompilovány jazyky podobné jazykům Java, překladatelé najdou:

• Více deklarací proměnné v rámci rozsahu;
• Odkaz na proměnnou před jejím vyhlášením;
• Odkazy na nenahlášené jméno;
• Porušení pravidel přístupnosti;
• Příliš velký nebo nedostatečný počet argumentů při volání metody;
• Nesoulad typu.

Generování

Generování mezilehlého kódu vytváří graf toku složený z nůček seskupených do základních bloků.

Generování kódu vytváří skutečný kód stroje. V tradičních kompilátorech pro stroje RISC vytvoří první stupeň assembler s nekonečným počtem virtuálních registrů. U strojů CISC se to pravděpodobně nestane.