Компілятор

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

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

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

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

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

Історія розвитку[ред.ред. код]

Термін "компілятор" вперше з'явився на початку 50-х років, коли почала формуватися потреба підвищення продуктивності програмістів шляхом запровадження високорівневих мов програмування. Від початку комп'ютерні програми писали на асемблері – низькорівневій, апаратно-залежній мові. Зі збільшенням розміру пам'яті первісних комп'ютерів виникали нові можливості для оптимізації процесу створення програм і переходу на сутності вищого рівня.

Автором першого компілятора вважається Ґрейс Гопер, яка у 1952 році створила компілятор для мови А-0 Система[1]. Цей перший компілятор функціонував більше як завантажувач і компонувальник, аніж компілятор у сучасному розумінні. Авторами повноцінного компілятора вважають команду розробки мови програмування Фортран на чолі з Джоном Бакусом, яка представила винахід у 1957 році.

У 1960 році був представлений компілятор мови програмування Кобол, який вперше мав можливість компілювати програми під різні платформи. Компілятор мови програмування Лісп 1962 року був першим компілятором, написаним на мові джерела компіляції. Відтоді написання компілятора на мові, яку він компілює, стало поширеною практикою, відомими прикладами якої стали мови програмування С і Паскаль.

Процес компіляції[ред.ред. код]

Процес, у якому компілятор читає записану початковою мовою програму та записує цільовою мовою, називають компіляцією (трансляцією, перекладом). Залежно від типу компілятора та налаштувань, цей процес може бути як простим однопрохідним зчитуванням і записом результату, так і розгалуженою багатокроковою ресурсомісткою обробкою й аналізом вхідного коду для численних оптимізацій та налаштувань.

Загалом компіляцію поділяють на такі послідовні та залежні кроки:

  1. Аналіз (front-end) – зчитування та розбиття початкової програми на складові частини для створення проміжного представлення.
    1. Лексичний аналіз — на цьому етапі послідовність символів сирцевого файлу перетворюється в послідовність лексем.
    2. Синтаксичний аналіз, під час якого послідовність лексем перетворюється в дерево розбору.
    3. Семантичний аналіз — перевірка відповідності правилам вхідної мови та побудова таблиці символів.
    4. Генератор проміжного коду будує проміжне представлення для подальших оптимізацій.
  2. Синтез (back-end) — побудова цільової програми на базі проміжного представлення.
    1. Попередній аналіз проміжного представлення на залежності, потік даних та інші контекстні властивості, важливі для оптимізації.
    2. Оптимізація – покращення для швидкодії, розміру, паралелізму тощо.
    3. Генератор цільового коду створює кінцевий результат роботи компілятора — цільову програму.

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

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

Аналіз (front-end)[ред.ред. код]

Протягом аналізу, або початкової стадії (front-end), програму розбивають на частини, на які накладається граматична структура. Наступним кроком на базі цієї структури створюють проміжне представлення програми. Важливими елементами аналізу є виявлення синтаксичних помилок та семантичних невідповідностей, які відображає компілятор.

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

До фази аналізу зачислюють лексичний, синтаксичний та семантичний аналізи та фазу генерації проміжного коду[2].

Лексичний розбір[ред.ред. код]

Докладніше: Лексичний аналіз

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

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 є стартовим символом і нетерміналом, решта символів є терміналами.

Семантичний аналіз[ред.ред. код]

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

У ході аналізу будується таблиця символів – ключове джерело посилань для подальшого компонування програми.

Генератор проміжного коду[ред.ред. код]

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

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

Синтез (back-end)[ред.ред. код]

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

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

На цій фазі компіляції деякі фази вже є необов'язковими (аналіз, оптимізація) і можуть бути пропущені.

Попередній аналіз проміжного коду[ред.ред. код]

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

  1. Аналіз потоку даних (англ. data-flow analysis) – побудова ланцюга використання-визначення (англ. Use-define chain) на базі якого у подальшого виконуються численні оптимізації.
  2. Аналіз залежностей – пошук інструкцій та блоків коду, які не залежать від послідовності виконання в певному контексті.
  3. Пошук псевдонімів (англ. alias) – в залежності від того, чи вказують певні змінні у певний момент часу на один і той самий об'єкт у пам'яті (є псевдонімами), можна робити припущення щодо взаємної їх підстановки та оптимізації.
  4. Аналіз області видимості (англ. escape analysis) – динамічний аналіз часу життя та області видимості вказівників для ефективнішого використання пам'яті.

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

Оптимізація проміжного коду[ред.ред. код]

Оптимізація є проміжним етапом перед кінцевою побудовою вихідного коду, під час якого код може бути покращений задля швидкодії, розміру результуючого файлу, ефективних обчислень на паралельних потоках виконання, об'єму використовуваній пам'яті тощо. За масштабом дії оптимізацію можна поділити на локальну, та глобальну.[3]

Локальна оптимізація відбувається у межах базового блоку (групи послідовних команд без розґалуджень і переходів) і полягає у локальних поліпшеннях[3]:

  • видалення коду, який не використовується,
  • пошук тотожних підвиразів,
  • зниження складності підрахунків шляхом заміни на більш дешеві операції (як приклад, степінь замінити множенням),
  • згорання констант (англ. constant folding) – підрахунок і заміна констант їх значеннями,
  • поліпшення повернення значення
  • локальне розподілення регістрів (англ. register allocation)

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

  • Глобальне розподілення регістрів (англ. global register allocation)

Генерація цільового коду програми[ред.ред. код]

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

Виділяють такі задачі, притаманні фазі генерації:

  • Вибір команд – саме трансляція команд входу у код цілі.
  • Впорядкування команд – визначення порядку слідування команд, місце для останніх можливих оптимізацій.
  • Розподіл та призначення регістрів – вибір змінних, які будуть знаходитися у пам'яті в у кожен момент часу програми, та їх розміщення у конкретних регістрах.
  • Налагоджувальна інформація (англ. debug data) додається саме на цій фінальній стадії.

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

За принципом роботи можна виділити такі види компіляторів[4]:

  • Однопрохідні – компіляція здійснюється в один прохід пропускаючи багато проміжних кроків оптимізацій і перевірок. Перші компілятори мови Pascal.[5]
  • Компілятори у зшитий код (англ. threaded code) — код, який повністю складається з підпрограм. По суті компілятор просто замінює кожну інструкцію вхідного коду на підпрограму вихідного — зшиває з заготівок.[6] Такий компілятор має мова програмування Forth.[7]
  • Інкрементальні компілятори – деякі функції можуть бути скомпільовані під час виконання інкрементально, наприклад у поєднанні з інтерпретованим виконанням. Такий тип компіляторів поширений у сімействі LISP.
  • Передфінальний компілятор (англ. stage compiler), який компілює у вихідну мову теоретичної машини. Такий компілятор реалізований для мови програмування Prolog; він генерує вихідний код для абстрактної машини Уоррена (англ. Warren Abstract Machine).[8]
  • Динамічний компілятор (англ. JIT, just-in-time) - компіляція на льоту. Див. нижче.
  • Компілятор зі змінним цілями (англ. retargetable), який відносно просто можна змінити для генерації цільового коду під іншу архітектуру процесору. Загалом така властивість досягається шляхом зниження якості вихідного коду (у порівнянні з цільовими компіляторами під конкретний процесор). Представником такого типу компіляторів є набір GCC.
  • Компілятор розпаралелення, який генерує вихідних код для запуску на паралельній архітектурі.

Стратегії компіляції[ред.ред. код]

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

Поширені стратегії компіляції:

  1. Компіляція перед виконанням (англ. AOT, ahead-of-time). Класичний принцип, коли компіляція проводиться окремо від виконання, зазвичай у відмінному від місця виконання середовищі. Компілятори мов програмування Pascal, C, C++, BASIC, Fortran, COBOL використовують стратегію такої попередньої компіляції.
  2. Компіляція під час виконання (англ. JIT, just-in-time), відома також як динамічна компіляція. Суть полягає у компіляції часу виконання (англ. run time), коли текст вхідної мови перетворюється у машинний код на льоту й тут же виконується. Ця техніка поєднує у собі методи як попередньої компіляції у проміжний код так і інтерпретації цього проміжного коду під час виконання. Будучи більш продвинутою технікою, компіляція на льоту має досить суворі вимоги до простоти компіляції, і не є доцільною для певних мов програмування.[9] Принциповим представником JIT компіляції є середовище виконання мови Java, піонером же вважається Smalltalk.
  3. Транскомпіляція, або компіляція з однієї високорівневої мови в іншу (англ. source-to-source). Принциповою відмінністю даної стратегії є те, що як вхідний так і вихідний код є мовами програмування високого рівня. Типовими прикладами використання є підготовка коду для паралельної оптимізації, перекомпіляція старішого коду для нової версії стандарту мови програмування, компіляція мов-надбудов у базову мову. Представниками таких мов програмування є CoffeeScript[10], Dart, Haxe, Coccinelle[11].
  4. Перекомпіляція — динамічна компіляція частин програми під час виконання (англ. dynamic recompilation). Особливість деяких серед виконання — емуляторів та віртуальних машин, перекомпільовувати деяку частину програми під час її роботи. Ця техніка використовується для переносу коду на іншу архітектуру під час його виконання, зокрема для запуску застарілих програм на сучасних операційних системах. Широко використовується Java run time[12] та .Net Common Language Runtime[13], а також багатьма віртуальними машинами.

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

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

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

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

Література[ред.ред. код]

  1. Compilers: Principles, Techniques, and Tools (English) (вид. 2nd edition). Addison Wesley. 2006-09-10. ISBN 9780321486813.
  2. Engineering a Compiler, Second Edition(English) (вид. 2 edition). Morgan Kaufmann. 2011-02-21. ISBN 9780120884780.
  3. Advanced Compiler Design and Implementation (English) (вид. 1 edition). Morgan Kaufmann. 1997-08-15. ISBN 9781558603202.
  4. Compiler Design in C (English). Prentice-Hall. 1990-01-01. ISBN 9780131550452.
  5. Modern Compiler Implementation in Java(English) (вид. 2nd edition). Cambridge University Press. 2002-10-21. ISBN 9780521820608.
  6. Understanding and Writing Compilers: A do-it-yourself guide (English) (вид. 3rd ed. edition). Palgrave. 1979-10-01. ISBN 9780333217320.
  7. Let's Build a Compilercompilers.iecc.com. Процитовано 2016-03-27.

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

  1. 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.
  2. Principles of Compiler Design (English) (вид. 2nd edition). Addison-Wesley. 1977-08-01. ISBN 9780201000221. 
  3. а б Вильямс книга Компиляторы: принципы, технологии и инструментарий (Книга Дракона-2), 2 издание. www.williamspublishing.com. с. 705–706. Процитовано 2016-03-30. 
  4. compilers.net > paedia > compiler. www.compilers.net. Процитовано 2016-03-30. 
  5. Turbo Pascal 3.0 Compiler and Code Generation Internals. www.pcengines.ch. Процитовано 2016-03-30. 
  6. Threaded Code. www.complang.tuwien.ac.at. Процитовано 2016-03-30. 
  7. Horn, Joe. What Exactly *Is* RPL?. 
  8. Warren's Abstract Machine: A Tutorial Reconstruction. wambook.sourceforge.net. Процитовано 2016-04-02. 
  9. Aycock, John (2003-06-01). A Brief History of Just-in-time. ACM Comput. Surv. 35 (2). с. 97–113. ISSN 0360-0300. doi:10.1145/857076.857077. Процитовано 2016-03-27. 
  10. List of languages that compile to JS jashkenas/coffeescript. GitHub. Процитовано 2016-03-27. 
  11. Semantic patching with Coccinelle [LWN.net]. lwn.net. Процитовано 2016-03-27. 
  12. Java theory and practice: Dynamic compilation and performance measurement. www.ibm.com (en). 2004-12-21. Процитовано 2016-03-27. 
  13. Understanding ASP.NET Dynamic Compilation. msdn.microsoft.com. Процитовано 2016-03-27.