Компілятор компіляторів Bison – перше знайомство
Bison – це GNU-випуск відомої програми YACC, призначеної для породження компіляторів за описаною користувачем КС-граматикою.
Одним із наслідків розширення можливостей та доступності використання обчислювальної техніки стало виробництво прикладних програмних систем із все більш різноманітною та складною поведінкою. При цьому наріжний принцип кібернетики - принцип необхідного і достатнього розмаїття, сформульований М. Віннером і Р. Ешбі ще до 1960 р., свідчить, що ступінь розмаїття управління такою сутністю має відповідати ступеню розмаїття її поведінки.
З якогось рівня різноманітності (складності) управління такою системою виявляється простіше і надійніше запропонувати користувачеві строго певну формальну мову, за допомогою якої користувач повідомляє системі завдання виконання тих чи інших її основних завдань, у т.ч. визначає склад та періодичність видачі облікових та повідомчих повідомлень про хід цього виконання тощо.
Наприклад, керувати повітряним рухом, зокрема. в Україні, відповідними міжнародними організаціями розроблено і використовується формальна мова з кількох десятків пропозицій, що однозначно повідомляють в автоматизованому та ручному режимах про кожну досить значну подію у використанні літака та його характеристики: зльоті, зміні курсу, проходженні контрольної точки польоту, посадці, виникненні різних і можливих причин, які можна і необхідно передбачити . Звичайним є доповнення та уточнення час від часу цього списку команд та/або їх параметрів щодо вирішення відповідних комітетів. Ці зміни необхідно швидко та надійно вносити до відповідних систем управління.
Для перевірки правильності таРозбір пропозицій таких формальних мов, як відомо, використовують програму, що називається компілятор.
Якщо ми такий компілятор навчимося отримувати автоматично на основі граматики, що описує цю мову, то зможемо всі зміни (наприклад, доповнення) до користувальницької мови, вносити дуже швидко і при цьому, що дуже важливо, цілком надійно.
Важливість і все більша поширеність цієї задачі була усвідомлена в програмуванні досить швидко і тому з'явився ряд різноманітних програмних інструментів для автоматизованої розробки компіляторів для мов, які визначаються контекстно-вільними граматиками. Так, сама назва відомого більше двох десятиліть компілятора YACC перекладається як «ще один компілятор компіляторів» (Yet another compiler compiler). Як проба сил і відточування майстерності виробництво подібних систем продовжується і зараз, особливо в технічних університетах (див., наприклад,http://www.forth.org.ua).
Свій компілятор компіляторів під назвою «СУПЕР» був створений понад 15 років тому і у ВЦ АН СРСР (нині ВЦ РАН, www.ccas.ru) під рук. л аур. держ. премії, зав. сект. ВЦ РАН, доц. МФТІ, к.ф.м.н. Володимира Михайловича Курочкіна, нині покійного. Останній понад 30 років тому заснував на ФУПМе та курс «Теорія та реалізація мов програмування».
Однак більшість цих систем (включаючи YACC) було розроблено в комерційному варіанті, або не мало достатньої універсальності, надійності та ефективності. Тому важливою подією у світі вільного (в сенсі ліцензії GNU) програмного забезпечення стала розробка GNU-аналогу компілятора YACC, який отримав назву BISON. Тепер цим компілятором можна компіляторів можнакористуватися для розробки програмних комплексів з найвищими вимогами до якості ліцензування інструментальних засобів, що застосовуються.
2. Хто його підтримує і під якою ОС він пасеться
Bison доступний для встановлення у всіх поширених різновидах ОС Linux. Можливо, вона вже встановлена на вашій системі. Просто наберіть bison без параметрів і подивіться на її відгук.
3. Де знаходиться вихідний опис роботи з Bison і де – його український переклад
4. Загальна схема отримання компілятора користувача за допомогою Bison
4.1. Записати КС-граматику у зрозумілому для Bison вигляді
Тип н/д має бути”. y ” (спадщина YACC і спосіб прямої (але не зворотної, тобто Bison ширше YACC) сумісності з YACC). Наприклад, foo. y або task. y.
Тип лексем (основних знаків), що приймаються майбутнім компілятором, визначається макро YYSTYPE , наприклад:
#define YYSTYPE char
#define YYSTYPE double
При цьому основні знаки алфавіту граматики користувача позначаються словами з великих (латинських) букв і повинні явно визначатися після ключового слова % token , наприклад:
% token ONE, TWO // Про визначаються два осн. знаки ONE та TWO.
Допоміжні знаки відразу можна використовувати в правилах, їх прийнято позначати словами з латинських малих літер. Наприклад, для граматики a^n:
exp : exp A // S -> Sa (вид позначень у поясненнях - вже з курсу ганчір'я)
// або, що теж саме:
Початковим знаком (аксіомою) граматики за замовчуванням вважається перший уживаний допоміжний знак у першому наведеному правилі граматики. У разі як аксіома буде розпізнана “ exp ”.
У фігурних дужках після кожного правила граматики можна вказати пов'язані з нимдії у стилі оператора Сі. Наявність таких зв'язок (правило + дія) говорить про те, що це не просто КС-граматика, а атрибутна граматика (див. гл. 5 за курсом ганчір'я).
У цьому прикладі підраховується ступінь правильно введеного ланцюжка з n знаків 'a' (розпізнаних у лексичному аналізаторі yylex(), який пишеться (забезпечується) користувачем). Заодно за допомогою printf() показується порядок застосування правил.
4.2. Запустити Bison для записаної граматики:
За відсутності помилок ви повинні отримати н/д з ім'ям foo. tab. c містить текст розбирача пропозицій yyparse ().
4.3. Підготувати вручну або з використанням інших інструментальних засобів (наприклад, LEX ) лексичний розпізнавач yylex(), обробник помилок yyerror() та головну програму main()
Програма main () викликає породжений Bison ' ом розбирач пропозицій yyparse (). Остання програма, у свою чергу, звертається при необхідності за черговою лексемою до yylex(), а при виявленні помилки розбору - до yyerror(). Зверніть увагу, що в граматиці для синтаксичного розбирача * yyparse () необхідно передбачити обробку (породження) знаків кінця рядка і кінця всього н/д, інакше ніякий введений ланцюжок не буде визнаний правильним, оскільки містить хоча б один із цих знаків.
Приклади програмування зазначених функцій для відповідних мов наведені нижче у параграфах 4.2 та 4.3.
4.4. Спільна компіляція підготовлених програм звичайним компілятором
Ви можете, наприклад, додати тексти програм yylex(), yyerror() і main() в кінець н/д з текстом програми yyparse в н/д foo. tab. c або створити коротку програму з найпростішими включеннями їх текстів, наприклад,
# include “main. з ”
І відкомпілювати їх звичайним компілятором Сі. Під Linux ця команда виглядає так (якщо всі програми для компіляції вже зібрані в н/д simple _ CF . tab . c , а програму ми хочемо назвати simple _ CF ):
cc - o simple _ CF simple _ CF . tab. c
4.5. Запуск отриманого компілятора
Виготовляється як завжди. Наприклад, це:
Знаки”. / “ з десь, як завжди, вказують, що пошук здійснюваного н/д проводиться у поточній папці.
5. Закінчені приклади застосування Bison для деяких простих граматик
5.1. Приклад граматики < а^ n n >= 0>.
(Приклади ланцюжків: а, аа, ааа, …, а^n).
5.1.1. Вхідний набір даних Bison , що вказує граматику, за якою має бути побудований текст шуканого розбирача пропозицій (синтаксичного аналізатора)
/* Simplest Context free grammar (a^n) */
#define YYSTYPE char // Тип вхідного знака
void yyerror (char const*);
// Main symbols of grammar (синонімів: terminals, tokens, etc.)
%% /* Правила граматики та пов'язані з ними дії */