Компіля́тор ( від — збирати в ціле) — комп'ютерна програма (або їх набір), що перетворює (компілює) початковий код, написаний певною мовою програмування (вихідна мова, ), на семантично еквівалентний код в іншій мові програмування (цільова мова, ), який зазвичай необхідний для виконання програми машиною, наприклад, комп'ютером. В СРСР, зокрема в УРСР, з 1952 року до середини 1960-х років використовувався термін програмувальна програма (ПП).
Коротко компілятор можна визначити як програму або технічний засіб, що виконує компіляцію.
Історично компілятором називалась програма, що зв'язувала підпрограми, чим і зумовлено походження слова. Сьогодні це завдання виконує компонувальник.
Для виконання програма не завжди повинна бути перекладена компілятором, існує також інший принцип: покрокове виконання програмних інструкцій інтерпретатором.
Історія розвитку Термін «компілятор» вперше з'явився на початку 50-х років, коли почала формуватися потреба підвищення продуктивності програмістів шляхом запровадження високорівневих мов програмування. Від початку комп'ютерні програми писали на асемблері — низькорівневій, апаратно-залежній мові. Зі збільшенням розміру пам'яті первісних комп'ютерів виникали нові можливості для оптимізації процесу створення програм і переходу на сутності вищого рівня.
Авторкою першого компілятора вважається Ґрейс Гопер, яка у 1952 році створила компілятор для мови А-0 СистемаHopper, Grace. «The Education of a Computer». Proceedings of the Association for Computing Machinery Conference 1952, reprinted Vol. 9, No. 3-4, 1952, pp. 271—281.. Цей компілятор являв собою окремий пристрій, який при завантаженні програм до оперативної пам'яті комп'ютера, без використання процесора, перекодовував програму у мнемонічних кодах (асемблері) у двійкові програмні коди. Тому цей перший компілятор функціонував як завантажувач та компонувальник, та його складно віднести до компілятора у сучасному розумінні цього терміна.
Першими компіляторами були програмувальні програми ПП-1 (1954 рік) та ПП-2 (1955 рік), які були реалізовані на ЕОМ «Стріла» в Москві.
Перший в світі компілятор універсальної мови програмування високого рівня — Адресної мови програмування (1955 р.) з опосередкованою адресацією (вказівниками) є Програмуюча Програма Адресної мови для ЕОМ "Київ" (ПП-АК) та ПП-2 (1955). Адресної мови програмування була реалізована під різними платформами, зокрема: комп'ютери М-20 (БЕСМ-3, БЕСМ-4), Урал, Дніпро, Мінськ тощо. Компілятори Адресної мови програмування писались на так званій ідеальній адресній обчислювальній машині (ІАОМ), яка є базовою частиною (підмножиною) Адресної мови програмування.
Оскільки Адресна мова програмування (1955 р.) мало відома закордоном, то часто помилково вважають авторами першого в світі повноцінного компілятора команду розробки мови програмування Фортран на чолі з Джоном Бакусом, яка представила винахід у 1957 році.
У 1960 році був представлений компілятор мови програмування Кобол, який теж мав можливість компілювати програми під різні платформи. Помилково вважають, що компілятор мови програмування Лісп 1962 року був першим компілятором, написаним мовою джерела компіляції, оскільки про технологію розробки компіляторів Адресної мови програмування мало кому відомо. Відтоді написання компілятора на мові, яку він компілює, стало поширеною практикою, відомими прикладами якої стали мови програмування С і Паскаль.
Процес компіляції
Процес, у якому компілятор читає записану початковою мовою програму та записує цільовою мовою, називають компіляцією (трансляцією, перекладом). Залежно від типу компілятора та налаштувань, цей процес може бути як простим однопрохідним зчитуванням і записом результату, так і розгалуженою багатокроковою ресурсомісткою обробкою й аналізом вхідного коду для численних оптимізацій та налаштувань.
Загалом компіляцію поділяють на такі послідовні та залежні кроки:
Аналіз (front-end) — зчитування та розбиття початкової програми на складові частини для створення проміжного представлення. Лексичний аналіз — на цьому етапі послідовність символів сирцевого файлу перетворюється в послідовність лексем. Синтаксичний аналіз, під час якого послідовність лексем перетворюється в дерево розбору. Семантичний аналіз — перевірка відповідності правилам вхідної мови та побудова таблиці символів. Генератор проміжного коду будує проміжне представлення для подальших оптимізацій. Синтез (back-end) — побудова цільової програми на базі проміжного представлення. Попередній аналіз проміжного представлення на залежності, потік даних та інші контекстні властивості, важливі для оптимізації. Оптимізація — покращення для швидкодії, розміру, паралелізму тощо. Генератор цільового коду створює кінцевий результат роботи компілятора — цільову програму.
У конкретних реалізаціях компіляторів ці етапи можуть бути розділені або, навпаки, поєднані в тому чи іншому вигляді.
Початкова мова визначається її синтаксисом — описом того, з яких конструкцій складається мова, та семантикою — набором правил, що визначають суть цих конструкцій.
Аналіз (front-end) Протягом аналізу, або початкової стадії (front-end), програму розбивають на частини, на які накладається граматична структура. Наступним кроком на базі цієї структури створюють проміжне представлення програми. Важливими елементами аналізу є виявлення синтаксичних помилок та семантичних невідповідностей, які відображає компілятор.
Також протягом фази аналізу збирається інформація до таблиці символів, ключової для фази компонування.
До фази аналізу зачислюють лексичний, синтаксичний та семантичний аналізи та фазу генерації проміжного коду.
Лексичний розбір
Лексичний розбір виділяють для спрощення побудови компілятора. Це лінійне сканування вхідної програми, при якому символи групують в токени — послідовності символів, що мають певне сукупне значення. Наступний рядок мовою Паскаль len := 3.14 * r; складається з таких токенів: Ідентифікатор len Символ присвоєння := Числова стала 3,14 Знак множення * Ідентифікатор r Роздільник операторів ;
Синтаксичний аналіз
Послідовність машинних символів, які утворюють токен, називають лексемою токена. Токени мають тип (наприклад, ідентифікатор, числова стала — це типи токенів). Деякі токени мають лексичне значення (наприклад, значення числової чи рядкової константи, утвореної з лексеми токена). Завдання лексичного аналізатора — виокремити лексеми токенів і повідомити синтаксичний аналізатор про тип токена та його лексичне значення.
Ієрархічний аналіз називають розбором () чи синтаксичним аналізом, у ході якого відбувається групування токенів програми. В синтаксичному аналізі символом називають токени (термінали) та групи токенів, об'єднаних у логічне ціле в процесі аналізу (нетермінали).
Синтаксис звичайно визначається контекстно-незалежною граматикою, що складається з символів — терміналів і нетерміналів, стартового символу що належить множині нетерміналів, та контекстно-незалежних продукцій.
Програма є послідовністю терміналів, яку можна вивести зі стартового символу, послідовно застосовуючи правила виводу (продукції). Продукція — це заміна послідовності символів S1 на послідовність символів S2 (Позначається. S1 : S2 або S1 -> S2). Продукція називається контекстно-незалежною, якщо S1 — один символ. Зазвичай розглядають лише контекстно-незалежні продукції.
Задача синтаксичного аналізатора — встановити шлях, яким вхідна програма виводиться зі стартового символу.
Наприклад, наступна граматика із трьох продукцій описує вирази (expression), що можуть складатись з ідентифікаторів (identifier), чисел (number) і знаку додавання +
expression : identifier expression : number expression : expression + expression
Перший рядок означає, що будь-який ідентифікатор є виразом. Другий рядок означає що будь-яке число є виразом. Третій рядок означає, що будь-яка послідовність з двох виразів, розділених знаком додавання, теж є виразом.
В цій граматиці символами є expression, number, identifier та +. Expression є стартовим символом і нетерміналом, решта символів є терміналами.
Семантичний аналіз На базі синтаксичного дерева семантичний аналізатор перевіряє вхідну програму на відповідність правилам і визначенням мови програмування. Важливою частиною цієї фази є перевірка відповідності типів даних. Саме протягом семантичного аналізу виявляють помилки приведення типів, використання неініційованих змінних, відкладеного визначення типів.
У ході аналізу будується таблиця символів — ключове джерело посилань для подальшого компонування програми.
Генератор проміжного коду Протягом своєї роботи компілятор може мати одне, або навіть декілька проміжних представлень коду, як вхідні параметри для різних фаз компіляції. Так, синтаксичне дерево побудоване протягом синтаксичного аналізу є прикладом такої проміжної структури.
Проте типовим принципом побудови компіляторів є генерація проміжного коду у кінці фази аналізу для подальшої оптимізації та трансляції у вихідну мову. Цей проміжний код ще не є вихідним кодом, але має важливі властивості: він має досить легко генеруватися та легко транслюватися у цільову мову.
Синтез (back-end) На базі проміжного представлення та наповненої таблиці функції конструюється вихідна програма.
Оскільки початковий вхідний код (а відповідно і проміжне представлення) може бути оптимізований як на базі високорівневих покращень, так і беручи до уваги детальне знання конкретної архітектури виходного коду, він підлягає декільком фазам аналізу. Аналізується час життя даних та їх проміжне переміщення за час роботи програми, деякі блоки коду ідентифікуються, як можливі кандидати до підстановки низькорівневим кодом. Після аналізу відбувається оптимізація та результат покращень транслюється у вихідну мову.
На цій фазі компіляції деякі фази вже є необов'язковими (аналіз, оптимізація) і можуть бути пропущені.
Попередній аналіз проміжного коду З часів первинних компіляторів, коли проміжний код безпосередньо транслювався у вихідну мову, було розроблено велику кількість покращень, уточнень та оптимізацій в залежності від змісту вхідної програми. Сучасні компілятори можуть виконувати великий набір досліджень вхідного коду, щоб досягти переваги у продуктивності, використовуваній пам'яті, розмірі вихідного файла тощо. Приклад розповсюджених видів аналізу: Аналіз потоку даних () — побудова ланцюга використання-визначення () на базі якого у подальшого виконуються численні оптимізації. Аналіз залежностей — пошук інструкцій та блоків коду, які не залежать від послідовності виконання в певному контексті. Пошук псевдонімів () — в залежності від того, чи вказують певні змінні у певний момент часу на один і той самий об'єкт у пам'яті (є псевдонімами), можна робити припущення щодо взаємної їх підстановки та оптимізації. Аналіз області видимості () — динамічний аналіз часу життя та області видимості вказівників для ефективнішого використання пам'яті. На цьому етапі також будується граф викликів — структура послідовності викликів функцій у вхідному коді, та граф потоку керування.
Оптимізація проміжного коду Оптимізація є проміжним етапом перед кінцевою побудовою вихідного коду, під час якого код може бути покращений задля швидкодії, розміру результуючого файлу, ефективних обчислень на паралельних потоках виконання, об'єму використовуваній пам'яті тощо. За масштабом дії оптимізацію можна поділити на локальну, та глобальну.
Локальна оптимізація відбувається у межах базового блоку (групи послідовних команд без розґалуджень і переходів) і полягає у локальних поліпшеннях: видалення коду, який не використовується, пошук тотожних підвиразів, зниження складності підрахунків шляхом заміни на більш дешеві операції (як приклад, степінь замінити множенням), згорання констант () — підрахунок і заміна констант їх значеннями, поліпшення повернення значення локальне розподілення регістрів ()