Компілятор

Компілятор (англ. Compiler від англ. to compile збирати в ціле) - комп'ютерна програма (або набір к. програм), що перетворює (компілює) програмний код, написаний певною мовою програмування (мова джерела, англ. source language), на семантично еквівалентний код в іншій мові програмування (мова цілі, англ. target language), який, як правило, необхідний для виконання програми машиною, наприклад, комп'ютером.

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

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

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

Історія розвитку

Перші компілятори з'явилися на початку 50-х років. Відтоді теорія і техніка побудови компіляторів істотно розвилися. Тоді ж велись інтенсивні наукові дослідження та утворювались групи та комітети з розробки універсальної проміжної мови. Однак їхня діяльність великого "індустріального" успіху не мала.

Теоретичний вступ

Компілятор – це програма, що читає програму записану початковою мовою і записує цільовою мовою. Цей процес називають компіляцією (трансляцією, перекладом). Він складається з двох частин

1. Аналіз (parsing) – розбиття початкової програми на складові частини та створення проміжного представлення
2. Синтез – побудова цільової програми з проміжного представлення

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

Фази компіляції

Концептуально компілятор працює фазово, в процесі кожної фази відбувається перетворення початкової програми з одного представлення до іншого. На практиці фази можуть об'єднуватись і деякі проміжні представлення можуть не будуватись в явному вигляді. Типове розбиття компілятора на фази:

1. Лексичний аналізатор
2. Синтаксичний аналізатор
3. Семантичний аналізатор
4. Генератор проміжного коду
5. Оптимізатор
6. Генератор цільового коду

Аналіз (розбір)

Лексичний розбір

Лексичний розбір виділяють для спрощення побудови компілятора. Це лінійне сканування вхідної програми, при якому символи групуються в токени - послідовності символів, що мають певне сукупне значення. Наступний рядок мовою Паскаль

len := 3.14 * r;

складається з наступних токенів

1. Ідентифікатор len
2. Символ присвоєння :=
3. Числова стала 3.14
4. Знак множення *
5. Ідентифікатор r
6. Роздільник операторів ;

Синтаксичний аналіз

Послідовність машинних символів, що утворюють токен, називають лексемою токена. Токени мають тип (наприклад, ідентифікатор, числова стала — це типи токенів). Деякі токени мають лексичне значення (наприклад, значення числової чи рядкової константи утвореної з лексеми токена). Задача лексичного аналізатора – виокремити лексеми токенів і повідомити синтаксичний аналізатор про тип токена та його лексичне значення.

Ієрархічний аналіз називається розбором (англ. parsing) чи синтаксичним аналізом, у ході якого відбувається групування токенів програми. В синтаксичному аналізі символом називають токени (термінали) та групи токенів об'єднаних у логічне ціле в процесі аналізу (нетермінали).

Синтаксис звичайно визначається контекстно-незалежною граматикою, що складається з символів – терміналів та нетерміналів, стартового символу що належить множині нетерміналів, та контесктно-незалежних продукцій.

Програма є послідовністю терміналів, яку можна вивести зі стартового символу послідовно застосовуючи правила виводу (продукції). Продукція – це заміна послідовності символів S₁ на послідовність символів S₂ (Позначається. S₁ : S₂ або S₁ -> S₂). Продукція називається контесктно-незалежною, якщо S₁ – один символ. Звичайно розглядаються лише контесктно-незалежні продукції.

Задача синтаксичного аналізатора – встановити шлях, яким вхідна програма виводиться з стартового символа.

Наприклад, наступна граматика із трьох продукцій описує вирази (expression), що можуть складатись з ідентифікаторів (identifier), чисел (number), та знаку додавання +

expression : identifier
expression : number
expression : expression + expression

Перший рядок означає що будь-який ідентифікатор є виразом. Другий рядок означає що будь-яке число є виразом. Третій рядок означає що будь-яка послідовність з двох виразів розділених знаком додавання теж є виразом.

В цій граматиці символами є expression, number, identifier та +. Expression є стартовим символом і нетерміналом, решта символів є терміналами.

Відомі компілятори

• GCC

Генератори аналізаторів

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

В Unix поширені генератор лексичних аналізаторів (F)Lex, та генератори синтаксичних аналізаторів Bison та Yacc.