Компілятор

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

Компілятор (англ. 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. doi:10.1145/857076.857077. ISSN 0360-0300. Процитовано 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.