Компілятор

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Компілятор (англ. 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) чи синтаксичним аналізом, у ході якого відбувається групування токенів програми. В синтаксичному аналізі символом називають токени (термінали) та групи токенів об'єднаних у логічне ціле в процесі аналізу (нетермінали).

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

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

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

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

expression : identifier
expression : number
expression : expression + expression

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

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

Класифікація компіляторів[ред.ред. код]

Відомі компілятори[ред.ред. код]

Генератори аналізаторів[ред.ред. код]

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

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

Посилання[ред.ред. код]

Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.