Транслятор - це... Види трансляторів. Перетворення і трансляція програми

Програмами, як і людям, для перекладу з однієї мови на іншу потрібно перекладач, або транслятор.

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

Програма представляє собою лінгвістичне подання обчислень: i → P → P (i). Інтерпретатор представляє собою програму, на вхід якої подається програма Р і деякі вхідні дані x. Він виконує P на х: I (P, x) = P (x). Той факт, що існує єдиний транслятор, здатний виконувати всі можливі програми (які можна уявити у формальній системі), є дуже глибоким і значним відкриттям Тьюринга.

Процесор є інтерпретатором програм на машинній мові. Як правило, занадто дорого писати інтерпретатори для мов високого рівня, тому їх транслюють в форму, яку інтерпретувати легше.

Деякі види трансляторів мають дуже дивні імена:

  • Асемблер транслює програми на асемблері в машинну мову.
  • Компілятор транслює з мови високого рівня на мову більш низького.

Транслятор - це програма, яка приймає в якості вхідних даних програму на деякій мові S і видає програму на мові T таким чином, що обидві вони мають ту ж семантику: P → X → Q. Тобто, ∀x. P (х) = Q (х).

транслятор це

Якщо транслювати всю програму в щось інтерпретується, то це називається компіляцією перед виконанням, або АОТ-компіляцією. АОТ-компілятори можуть використовуватися послідовно, останній з яких часто є асемблером, наприклад:

Вихідний код → Компілятор (транслятор) → ассемблерного код → Асемблер (транслятор) → Машинний код → ЦПУ (інтерпретатор).

Оперативна або динамічна компіляція відбувається, якщо частина програми транслюється, коли виконуються інші раніше скомпільовані частини. JIT-транслятори запам’ятовують те, що вони вже виконали, щоб не повторювати вихідний код знову і знову. Вони здатні навіть виробляти адаптивну компіляцію і перекомпіляцію, засновану на поведінці середовища виконання програми.

Багато мови дозволяють виконувати код під час трансляції та компілювати новий код під час виконання програми.

Етапи трансляції

Трансляція складається з етапів аналізу і синтезу:

Вихідний код → Аналізатор → Концептуальне уявлення → Генератор (синтезатор) → Цільовий код.

Це обумовлено такими причинами:

  • Будь-який інший спосіб не підходить. Послівний переклад просто не працює.
  • Гарне інженерне рішення: якщо потрібно написати транслятори для M вихідних мов і N цільових, потрібно написати тільки M + N простих програм (полукомпіляторов), а не M × N комплексних (повних трансляторів).

види трансляторів

Проте на практиці концептуальне уявлення дуже рідко буває досить виразним і потужним, щоб охопити всі мислимі вихідні і цільові мови. Хоча деякі і змогли до цього наблизитися.

Реальні компілятори проходять через безліч етапів. При створенні власного компілятора не потрібно повторювати всю важку роботу, яку люди вже виконали при створенні уявлень і генераторів. Можна транслювати свою мову прямо в JavaScript або C і скористатися існуючими JavaScript-двигунами і компіляторами мови C, щоб зробити все інше. Також можна використовувати існуючі проміжні представлення і віртуальні машини.

Запис транслятора

Транслятор - це програма або технічний засіб, в якому задіяні три мови: вихідний, цільової і базисний. Їх можна записати в Т-формі, розташувавши вихідний зліва, цільової справа і базисний нижче.

Існує три види компіляторів:

  • Транслятор - це самокомпілятор, якщо у нього вихідний мову відповідає базисному.
  • Компілятор, у якого мову перекладу дорівнює базисному, називається саморезідентним.
  • Транслятор - це крос-компілятор, якщо у нього цільової і базисний мови різні.

трансляція програми

Чому це важливо?

Навіть якщо ви ніколи не зробите справжній компілятор, добре знати про технології його створення, тому що використовуються для цього концепції застосовуються повсюдно, наприклад в:

  • Форматуванні текстів;
  • Мовах запитів до баз даних;
  • Розширених комп'ютерних архітектур;
  • Узагальнених задачах оптимізації;
  • Графічних інтерфейсах;
  • Мовах сценаріїв;
  • Контролерах;
  • Віртуальних машинах;
  • Машинних перекладах.

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

Також можна дізнатися, як краще писати програми, так як створення транслятора для мови означає краще розуміння його тонкощів і неясностей. Вивчення загальних принципів трансляції також дозволяє стати хорошим дизайнером мови. Чи так це важливо, наскільки крутий мову, якщо він не може бути реалізований ефективно?

Всеосяжна технологія

Технологія компілятора охоплює безліч різних областей інформатики:

  • Формальну теорію мови: граматику, парсинг, вичіслімость;
  • Комп'ютерну архітектуру: набори інструкцій, RISC або CISC, конвеєрну обробку, ядра, тактові цикли і т. д.;
  • Концепції мов програмування: наприклад, управління послідовністю виконання, умовне виконання, ітерації, рекурсії, функціональне розкладання, модульність, синхронізацію, метапрограмування, область видимості, константи, підтипи, шаблони, тип виведення, прототипи, анотації, потоки, монади, поштові ящики, продовження, групові символи, регулярні вирази, трансакціонної пам'ять, успадкування, поліморфізм, режими параметрів і т. д.;
  • Абстрактні мови і віртуальні машини;
  • Алгоритми і структури даних: регулярні вирази, алгоритми парсинга, графічні алгоритми, динамічне програмування, навчання;
  • Мови програмування: синтаксис, семантику (статичну і динамічну), підтримку парадигм (структурної, ООП, функціональної, логічної, стековой, паралелізму, метапрограмування);
  • Створення ПО (компілятори, як правило, великі і складні): локалізацію, кешування, компонентізацію, API-інтерфейси, повторне використання, синхронізацію.

перетворення програми

Проектування компілятора

Деякі проблеми, що виникають при розробці реального транслятора:

  • Проблеми з вихідним мовою. Чи легко його скомпілювати? Чи є препроцесор? Як обробляються типи? Чи є бібліотеки?
  • Угруповання проходів компілятора: одно - або багатоходова?
  • Ступінь бажаної оптимізації. Швидка і нечиста трансляція програми практично без оптимізації може бути нормальною. Надмірна оптимізація буде гальмувати компілятор, але кращий код під час виконання може того коштувати.
  • Необхідна ступінь виявлення помилок. Чи може транслятор просто зупинитися на першій помилку? Коли він повинен зупинитися? Довірити компілятору виправлення помилок?
  • Наявність інструментів. Якщо вихідний мова не є дуже маленьким, сканер і генератор аналізаторів є обов'язковими. Також існують генератори генераторів коду, але вони не так поширені.
  • Вид цільового коду для генерації. Слід вибирати з чистого, доповненого або віртуального машинного коду. Або просто написати вхідну частину, яка створює популярні проміжні представлення, такі як LLVM, RTL або JVM. Або зробити трансляцію від вихідного в вихідний код на C або JavaScript.
  • Формат цільового коду. Можна вибрати мову асемблера, стерпний машинний код, машинний код способу пам'яті.
  • Перенацеливание. При безлічі генераторів добре мати загальну вхідну частину. З цієї ж причини краще мати один генератор для багатьох вхідних частин.

динамічна компіляція

Архітектура компілятора: компоненти

Це головні функціональні компоненти транслятора, що генерує машинний код (якщо вихідний програмою є програма на С або віртуальна машина, то буде потрібно не так багато етапів):

  • Вхідна програма (потік знаків) надходить в сканер (лексичний аналізатор), який перетворює її в потік токенів.
  • Парсер (синтаксичний аналізатор) будує з них абстрактне синтаксичне дерево.
  • Семантичний аналізатор розкладає семантичну інформацію і перевіряє вузли дерева на помилки. В результаті будується семантичний граф - абстрактне синтаксичне дерево з додатковими властивостями і встановленими посиланнями.
  • Генератор проміжного коду будує граф потоку (кортежі групуються в основні блоки).
  • Машінонезавісімий оптимізатор коду проводить як локальну (всередині базового блоку), так і глобальну (по всіх блоках) оптимізацію, в основному залишаючись в рамках підпрограм. Скорочує надлишковий код і спрощує обчислення. В результаті виходить модифікований граф потоку.
  • Генератор цільового коду пов'язує базові блоки в прямолінійний код з передачею управління, створюючи об'єктний файл на асемблері з віртуальними регістрами (можливо, неефективними).
  • Машінозавісімий оптимізатор-компоновщик розподіляє пам'ять між регістрами і виробляє планування команд. Здійснює перетворення програми на асемблері в справжній асемблер з хорошим використанням конвеєрної обробки.

Крім того, використовуються підсистеми виявлення помилок і менеджер таблиць символів.

об'єктний файл

Лексичний аналіз (сканування)

Сканер конвертує потік знаків вихідного коду в потік токенів, прибираючи прогалини, коментарі і розширюючи макроси.

Сканери часто зустрічаються з такими проблемами, як приймати чи не приймати до уваги регістр, відступи, переклад рядка і вкладені коментарі.

Помилки, які можуть зустрітися при скануванні, називаються лексичними і включають:

  • Символи, відсутні в алфавіті;
  • Перевищення числа знаків в слові або рядку;
  • Не закриті знак або строковий літерал;
  • Кінець файлу в коментарі.

Синтаксичний аналіз (парсинг)

Парсер перетворює послідовність токенів в абстрактне синтаксичне дерево. Кожен вузол дерева зберігається як об’єкт з іменованими полями, багато з яких самі є вузлами дерева. На цьому етапі цикли відсутні. При створенні парсеру необхідно звернути увагу на рівень складності граматики (LL або LR) і з’ясувати, чи є які-небудь правила зняття неоднозначності. Деякі мови дійсно вимагають проведення семантичного аналізу.

Помилки, що зустрічаються на цьому етапі, називаються синтаксичними. наприклад:

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

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

Під час проведення семантичного аналізу необхідно перевірити правила допустимості і зв’язати частини синтаксичного дерева (дозволяючи посилання імен, вставляючи операції для неявного приведення типів і т. Д.) Для формування семантичного графа.

Очевидно, що набір правил допустимості у різних мов різний. Якщо компілюються Java-подібні мови, транслятори можуть знайти:

  • Множинні оголошення змінної в межах області її дії;
  • Посилання на змінну до її оголошення;
  • Посилання на неоголошене ім'я;
  • Порушення правил доступності;
  • Занадто велике або недостатня кількість аргументів при виклику методу;
  • Невідповідність типів.

вхідна програма

Генерація

Генерація проміжного коду виробляє граф потоку, складений з кортежів, згрупованих в базові блоки.

Генерація коду виробляє реальний машинний код. У традиційних компіляторах для RISC-машин на першому етапі створюється асемблер з нескінченним числом віртуальних регістрів. Для CISC-машин, ймовірно, цього не станеться.



ЩЕ ПОЧИТАТИ