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

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

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

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

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


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

Реальні компілятори проходять через безліч етапів. При створенні власного компілятора не потрібно повторювати всю важку роботу, яку люди вже виконали при створенні уявлень і генераторів. Можна транслювати свою мову прямо в 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-машин, ймовірно, цього не станеться.