Як влаштований компілятор?

В шостому номері "Комп'ютерних вістей" за цей рік я розповів вам про те, як влаштований відладчик. Звичайно, з тих пір пройшло вже чимало часу, але дізнаватися нове ніколи не пізно. Сьогодні ми з вами поговоримо про пристрій нітрохи не менш важливого для програміста інструменту - компілятора.

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


З висоти пташиного польоту...

... компілятор являє собою моноліт - такий собі чорний ящик , Який прожёвивает вихідний код програми, а потім видає на-гора або виконуваний файл , Або, хоча б, просто якийсь виконуваний байт-код, який потім може бути успішно згодую віртуальній машині. Але, звичайно ж, насправді така складна річ, як компілятор, не може бути просто монолітним шматком - будь-який компілятор складається з декількох частин, які повинні бути "зістиковано" в певному порядку.

Отже, що ж це за частини? Це лексичний аналізатор, або сканер; синтаксичний аналізатор, або парсер; семантичний аналізатор; а також один або кілька генераторів коду і один або кілька оптимізаторів. Також до компілятору часто відносять додаткові інструменти, потрібні для створення виконуваного файлу - складальник і компонувальник.

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


Від А до Я"

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

Слідом за лексичним аналізом може бути препроцесор. Тим, хто знайомий з мовами програмування C або С ++, немає потреби пояснювати, в чому полягає його функція. Для інших же скажу, що основне завдання препроцесора - це заміна одних лексем іншими, які були заздалегідь визначені в тексті програми. Використовується препроцесор також для умовної компіляції (тобто коли шматок коду повинен бути откомпилирован тільки при виконанні певних умов - для певної платформи, тільки при отладочном білді і т.д. і т.п.), для виконання певних макросів (як в тому ж C / C ++) і деяких інших подібних речей. Препроцесор не є обов'язковою частиною компілятора, оскільки багато мов програмування не потребують його.

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

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

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

Сучасні компілятори, навіть самі слабенькі і поганенькі, підтримують хоча б базову оптимізацію коду. Більш потужні комерційні компілятори містять в собі дуже потужні алгоритми оптимізації коду, які дозволяють при деяких умовах зробити її в рази швидше. Особливо потужними в плані оптимізації давним-давно тому вважалися компілятори виробництва Watcom, зараз, начебто, поступово відновлюють свою колишню славу у вигляді open-source продукту. Потім пальма першості перейшла до компіляторам Intel, і зараз саме вони вважаються найкращими компиляторами в плані оптимізації. Що ж, це досить логічно - кому, як не творцям процесорів, знати, як найкраще оптимізувати програми для роботи на них. Втім, не важливо, погана оптимізація в компіляторі чи ні - головне, що в будь-якому оптимизирующем компіляторі є модуль, званий оптимізатором, який починає свою роботу після генератора проміжного коду. Справедливості заради варто сказати, що оптимізатор може працювати і після генерації вже виконуваного коду, але в наші дні така схема зустрічається вже рідко, оскільки виробники компіляторів, як правило, випускають цілу лінійку подібних продуктів для різних мов програмування і намагаються робити оптимізатори, які можна вбудувати в будь-який з цих компіляторів. Якими саме методами оптимізатор може підвищувати швидкість роботи програми - це тема окремої статті, яку, можливо, ви коли-небудь і зможете побачити на сторінках "Комп'ютерних вістей".

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

Для того, щоб ви легше могли уявити собі роботу компілятора і послідовність роботи його складових частин, я вирішив забезпечити статтю невеликою схемою. На ній чорним кольором зображені ті компоненти, які присутні в будь-якому компіляторі, а сірим - необов'язкові для ряду компіляторів складові частини.

На ній чорним кольором зображені ті компоненти, які присутні в будь-якому компіляторі, а сірим - необов'язкові для ряду компіляторів складові частини


додаткові компоненти

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

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

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

Компоновщик створює з того коду, який згенерував асемблер, виконувані файли. Навіть для однієї і тієї ж процесорної архітектури виконувані файли будуть відрізнятися в залежності від операційної системи. Наприклад, для Windows формат виконуваних файлів - це Portable Executable (PE), а для Linux - Executable Linked File (EXE).


резюме

Як бачите, якщо дивитися на компілятори з боку, то все в них просто і не викликає ніяких особливо хитромудрі питань. На практиці все, м'яко кажучи, трохи складніше. І якщо ви раптом вирішите написати власний компілятор, то не варто заздалегідь лякатися, хоча до певних складнощів потрібно, як і в будь-якій новій роботі, бути готовим. Я б особисто рекомендував починати знайомство з предметом з написання якогось простого езотеричного мови на зразок Brainfuck або Whitespace. Оскільки сам я свого часу цікавився завдяки своєму знайомому Марату Духанов першим з них, то і вам рекомендую його.

Взагалі, якщо ж ви раптом вирішили проникнути глибше в таємниці створення компіляторів, то в Інтернеті для вас знайдеться маса літератури - і простий, і академічно точної і докладної. Почати можна, наприклад, звідси: kit.kulichki.net . Хоча сайт вже не оновлювався цілу вічність, інформація, розміщена на ньому, підійде для новачка і не застаріє ще не один десяток років. Взагалі, якщо погуглити, інформації знайдете дуже багато, навіть доведеться її фільтрувати. Так що успіхів вам з компіляторами!

Вадим СТАНКЕВИЧ

Отже, що ж це за частини?