Преводачът е ... Видове преводачи. Преобразувайте и превеждайте програмата

Програмите, като хората, изискват преводач или преводач да превежда от един език на друг.

Основни понятия

Програмата е езиково представяне на изчисленията: i → P → P (i). Тълкувателят е програма, която се подава към програмата P и някои входни данни x. Изпълнява P на x: I (P, x) = P (x). Фактът, че има само един преводач, способен да изпълнява всички възможни програми (които могат да бъдат представени във формалната система), е много дълбоко и значимо откритие на Тюринг.

Процесорът е преводач на програми на езика на машината. Обикновено е твърде скъпо да се пишат преводачи за езици на високо ниво, така че те се превеждат във форма, която е по-лесна за интерпретация.

Някои видове преводачи имат много странни имена:

• Assembler превежда програмите в асемблер на машинен език.
• Компилаторът превежда от език на високо ниво на език от по-ниско ниво.

Трансултантът е програма, която взима програмите на някакъв език S и изработва програма на езика Т по такъв начин, че те имат една и съща семантика: P → X → Q. Това означава, forall-х. P (x) = Q (х).

Ако преведете цялата програма в нещо, което се интерпретира, това се нарича компилация преди изпълнение или AOT-компилация. AOT компилаторите могат да се използват последователно, последният от които често е асемблер, например:

Изходен код → Компилатор (компилатор) → Код на асемблера → Асемблер (преводач) → Код на машината → CPU (преводач).

Онлайн или динамична компилация се получава, ако част от програмата се превежда, когато се изпълняват други компилирани части. JIT-преводачите си спомнят какво са направили, за да не повтарят изходния код отново и отново. Те дори могат да произвеждат адаптивна компилация и recompilation, базирани на поведението на средата на програмата за изпълнение.

Много езици ви позволяват да изпълнявате код по време на превод и да компилирате нов код по време на изпълнение.

Етапи на превод

Преводът се състои от етапите на анализ и синтез:

Източник код → Анализатор → Концептуален изглед → Генератор (синтезатор) → Целеви код.

Това се дължи на следните причини:

• Всеки друг метод не е подходящ. Преводът дума по дума просто не работи.
• Добро инженерно решение: ако трябва да напишете преводачи за M изходен език и N целеви езици, ще трябва само да напишете M + N прости програми (semicompilers), а не M × N complex (пълни преводачи).

Въпреки това на практика концептуалното представяне много рядко е достатъчно изразително и мощно, за да обхване всички възможни източници и целеви езици. Въпреки че някои от тях можеха да се доближат до това.

Реалните компилатори преминават през много етапи. Когато създавате свой собствен компилатор, не е нужно да повторите цялата упорита работа, която хората вече са направили при създаването на изгледи и генератори. Можете да превеждате вашият език директно в jаvascript или C и да използвате останалите двигатели на jаvascript и компилатори C, за да направите останалото. Можете да използвате съществуващи междинни изгледи и виртуални машини.

Запис на преводача

Транслейтър е програма или технически инструмент, в който се включват три езика: източник, целева и основна. Те могат да бъдат написани в Т-образна форма, като източникът се поставя отляво, целта отдясно и основата по-долу.

Има три вида компилатори:

• Преводачът е авто-компилатор, ако неговият изходен език съответства на основен език.
• Компилаторът, чийто целеви език е равен на базовия език, се нарича самостоятелно пребиваващ.
• Преводачът е кръстосан компилатор, ако има различен целеви език и базов език.

Защо това е важно?

Дори и да не правите истински компилатор, добре е да знаете за технологията на създаването му, тъй като използваните за тази цел понятия се прилагат навсякъде, например:

• форматиране на текстове;
• езици на заявката до бази данни;
• разширени компютърни архитектури;
• генерализирани проблеми с оптимизацията;
• графични интерфейси;
• скриптови езици;
• контролери;
• виртуални машини;
• машинни преводи.

Освен това, ако искате да напишете предпроцесори, строители, товарачи, дебъгери или профили, трябва да минете през същите стъпки, както при писането на компилатора.

Можете също да научите как да пишете програми по-добре, тъй като създаването на преводач за език означава по-добро разбиране на нейните тънкости и неясноти. Изучаването на общите принципи на превод също прави възможно да се превърне в добър език дизайнер. Дали е толкова важно, колко остро е езикът, ако не може да се осъществи ефективно?

Цялостна технология

Технологията на съставителите обхваща много различни области на компютърната наука:

• теоретична езикова теория: граматика, анализ, изчислимост;
• компютърна архитектура: набори от инструкции, RISC или CISC, тръбопроводи, ядки, часовникови цикли и др .;
• концепции за програмни езици, например, извършване на контрол последователност, условно изпълнение, итерация, рекурсия, функционален разлагане, модулност, синхронизация, мета-програмиране, обхват, постоянни подтипове, шаблони, тип продукция, прототипи, анотации, поток, монадите, пощенски кутии, продължават , заместващи символи, регулярни изрази, транзакционна памет, наследяване, полиморфизъм, режими на параметрите и т.н .;
• абстрактни езици и виртуални машини;
• алгоритми и структури от данни: Редовните изрази, алгоритмите за анализ, графичните алгоритми, динамично програмиране, обучение;
• езици за програмиране: синтаксис, семантика (статичен и динамичен), поддръжка на парадигми (структурни, OOP, функционални, логически, стек, конкуренция, метапрограмиране);
• създаване на софтуер (компилатори, като правило, големи и сложни): локализация, кеширане, компонентизация, API интерфейси, повторна употреба, синхронизация.

Проектиране на компилатора

Някои проблеми, които възникват при разработването на истински преводач:

• Проблеми с изходния език. Лесно ли е да го компилирате? Има ли препроцесор? Как се обработват видовете? Има ли библиотеки?
• Групирането на компилатора минава: едно или няколко пропуска?
• Степента на желаната оптимизация. Бързият и нечист превод на програмата с малко или никаква оптимизация може да бъде нормален. Прекалената оптимизация ще забави компилатора, но най-добрият код по време на изпълнение може да си струва.
• Изисквана честота на откриване на грешки. Може ли преводачът просто да спре при първата грешка? Кога трябва да спре? Вярвам на компилатора да коригира грешките?
• Наличие на инструменти. Ако изходният език не е много малък, генераторът на скенера и анализатора е задължителен. Съществуват и генератори на генератори на кодове, но те не са толкова често срещани.
• Тип целеви код за генериране. Трябва да избирате между чист, разширен или виртуален машинен код. Или просто напишете вход, който създава популярни междинни изгледи, като LLVM, RTL или JVM. Или преводът от източника към изходния код в C или jаvascript.
• Форматът на целевия код. Можете да изберете езикът на асемблера, преносим код на машината, код на машината на изображението на паметта.
• Пренасочване. С много генератори е добре да имате обща входна част. По същата причина е по-добре да имате един генератор за много входящи части.

Архитектура на съставителите: компоненти

Това са основните функционални компоненти на компилатора, който генерира машинен код (ако изходната програма е C програма или виртуална машина, тогава не са необходими много стъпки):

• Входната програма (поток от знаци) влиза в скенера (лексикален анализатор), който го превръща в поток от символи.
• Parser (parser) конструира абстрактно синтаксисно дърво от тях.
• Семантичният анализатор разлага семантичната информация и проверява възлите на дървото за грешки. Резултатът е семантична графика - абстрактно синтаксирано дърво с допълнителни свойства и инсталирани референции.
• Генериращият междинен код генерира график на потока (нулите се групират в главните блокове).
• Машинно-независимият кодов оптимизатор извършва както локална (в основния блок), така и глобална (за всички блокове) оптимизация, която основно остава в подпрограмите. Намалява излишния код и опростява изчисленията. Резултатът е модифицирана графика на потока.
• Генераторът на целевия код свързва базовите блокове с правилния код с прехвърлянето на контрола, като създава обемен файл в асемблер с виртуални регистри (възможно е неефективен).
• Оптимизаторът на линкове, независим от машината, разпределя паметта между регистрите и програмните команди. Преобразува програмата в асемблер в истински асемблер с добра употреба на тръбопроводи.

Освен това се използват подсистемите за откриване на грешки и мениджъра на таблицата със символи.

Лексикален анализ (сканиране)

Скенерът преобразува потока от знаци на изходния код в поток от символи, като премахва интервали, коментари и разширяващи се макроси.

Скенерите често срещат такива проблеми като приемането или невземането под внимание на регистъра, тиретата, линиите и вложените коментари.

Грешките, които могат да възникнат по време на сканирането, се наричат ​​лексикални и включват:

• символи, които не са в азбуката;
• надвишаване на броя знаци в дума или низ;
• не е затворен знак или низ буквално;
• края на файла в коментарите.

Синтаксисният анализ (синтактичен анализ)

Parser преобразува последователността от символи в абстрактно синтаксисово дърво. Всеки възел на дърво се запазва като обект с имена полета, много от които са самите възли на дървото. На този етап няма цикли. Когато създавате анализатор, трябва да обърнете внимание на нивото на сложност на граматиката (LL или LR) и да разберете дали съществуват правила за отстраняване на двусмислието. Някои езици изискват семантичен анализ.

Грешките, възникнали на този етап, се наричат ​​синтактични грешки. Например:

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

Семантичен анализ

По време на семантичен анализ е необходимо да се проверят правилата за допустимост и да се обвържат частите от дървото на синтаксиса (позволявайки препратки на имена, вмъкване на операции за имплицитно заличаване на типове и т.н.), за да се създаде семантична графика.

Очевидно е, че наборът от правила за допустимост за различните езици е различен. Ако се компилират езици, подобни на Java, преводачите могат да намерят:

• множество декларации за променлива в нейния обхват;
• позоваване на променлива преди нейната декларация;
• препратки към недекларираното име;
• нарушаване на правилата за достъпност;
• твърде голям или недостатъчен брой аргументи при извикване на метода;
• тип несъответствие.

поколение

Генерирането на междинен код води до графика на потока, съставена от типове, групирани в базови блокове.

Кодовото поколение произвежда реален код на машината. В традиционните компилатори за машини RISC, на първия етап се създава асемблер с безкраен брой виртуални регистри. За машините CISC това вероятно няма да се случи.