Генератор синтаксичних аналізаторів, сумісний з YACC для Bison версії 1.35, 25 лютого 2002 Автори: Чарльз Доннеллі, Річард Столлмен Переклад: Ілля Корнійко Ориґінал англійською html єдиний дивитись звантажити html по розділах зміст звантажити texi info російською html texi info
Вступ
Bison -- це генератор синтаксичних аналізаторів загального призначення, який перетворює опис контекстно-вільної LALR(1) граматики в програму мовою C для розбору цієї граматики. Якщо ви опануєте Bison, ви зможете використовувати його для розробки аналізаторів мов досить широкого класу: від тих, що використовуються в простих настільних калькуляторах до складних мов програмування.
Bison зворотньо сумісний з Yacc: всі правильні граматики Yacc повинні без змін працювати з Bison. Кожен, хто добре знає Yacc, не повинен мати великих проблем при використанні Bison. Вам потрібно мати навички програмування на C для того, щоб використовувати Bison і щоб розуміти це керівництво.
Ми почнемо з навчальних глав, які пояснюють основні принципи Bison і містять три повністю завершених приклади з поясненнями. Якщо ви не знаєте ні Bison, ні Yacc, почніть з них. Потім йдуть глави, що детально описують специфічні особливості Bison.
Bison написаний, в основному, Робертом Корбеттом (Robert Corbett). Річард Столлмен (Richard Stallman) зробив його сумісним з Yacc. Вільфред Хансен (Wilfred Hansen) з Carnegie Mellon Univerisity додав підтримку багатосимвольних літералів та інші можливості.
Ця редакція стосується Bison версії 1.35.
Умови використання Bison
Починаючи з версії Bison 1.24 ми змінили умови поширення yyparse, дозволивши використовувати результат роботи Bison в невільних програмах. Раніше аналізатори, створені Bison, могли бути використані лише в програмах, які є вільним програмним забезпеченням.
Інші інструменти GNU для програмування, такі як компілятор C GNU, ніколи не містили такої вимоги. Вони завжди могли використовуватися в невільному програмному забезпеченні. Bison відрізнявся від них не через якесь особливе політичне рішення, просто до всього первісного коду Bison застосовувалася звичайна Універсальна Громадська Ліцензія (GPL).
Вихід Bison -- файл аналізатора Bison -- містить точну копію частини Bison як код функції yyparse (всі дії вашої граматики вставляються в функцію в одному місці, решта функції при цьому не змінюється). У результаті застосування умов GPL до коду yyparse, використання виходу Bison було обмежене вільним програмним забезпеченням.
Ми не змінювали умови через наше ставлення до людей, що хочуть робити програми приватно-власними (пропрієтарними). Програми мають бути вільними. Але ми зрозуміли, що обмеження використання Bison вільним програмним забезпеченням не занадто сприяє виробництву з його допомогою інших вільних програм. І ми вирішили зробити практичні умови використання Bison тими, що й для інших інструментів GNU.
GNU GENERAL PUBLIC LICENSE
Preamble TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION Appendix: How to Apply These Terms to Your New Programs
2. Принципи Bison У главі вводиться багато основних понять, без яких детальний опис Bison не матиме сенсу. Якщо ви ще не знаєте, як використовувати Bison чи Yacc, ми пропонуємо вам розпочати з уважного читання цієї глави.
2.1 Мови та контекстно-вільні граматики
Для того, щоб Bison міг розібрати програму якоюсь мовою, ця мова має бути описана контекстно-вільною граматикою. Це означає, що ви визначаєте одну або більше синтаксичних груп і задаєте правила складання їх із складових частин. Наприклад, мовою C одна з груп називається `Вислів'. Правило для складання вислову може виглядати так: "Вислів може складатись із знака `мінус' й іншого вислову". Інше правило: "Висловом може бути ціле число". Як ви може бачити, правила часто бувають рекурсивними, але має бути принаймні одне правило, що обриває рекурсію.
Найбільш поширеною формальною системою для подання таких правил у зручному для людини вигляді є форма Бекуса-Наура(БНФ, Backus-Naur Form, BNF), що була розроблена для опису мови Algol 60. Будь-яка граматика, виражена у формі Бекуса-Наура, є контекстно-вільною граматикою. Bison приймає на вхід, по суті, особливий вид БНФ, адаптований для машинної обробки.
Bison може працювати не з усіма контекстно-вільними граматиками, а лише з граматиками класу LALR(1). Коротко, це означає, що має бути можливим розібрати будь-яку частину входу, зазираючи вперед не більше, ніж на одну лексему. Строго кажучи, це опис LR(1)-граматики, клас LALR(1) має додаткові обмеження, які не так просто пояснити. Але в звичайній практиці рідко трапляються LR(1)-граматики, які не є LALR(1). Див. розділ 6.7 Загадкові конфлікти згортка/згортка, для одержання докладнішої інформації.
У правилах формальної граматики мови кожен вид синтаксичних одиниць чи груп називається символом. Ті з них, які формуються угрупуванням менших конструкцій відповідно до правил граматики, називаються нетермінальними символами, а ті, що не можуть бути розбиті -- термінальними символами чи типами лексем. Ми називаємо частину вхідного тексту, що відповідає одному термінальному символу, лексемою, а відповідну нетермінальному символу -- групою.
Для прикладу термінальних і нетермінальних символів можна використати мову C. Лексемами C є ідентифікатори, сталі (числові та рядкові), різні ключові слова, знаки арифметичних операцій і пунктуації. Таким чином, термінальні символи граматики C це: 'ідентифікатор', 'число', 'рядок' і по одному символу на кожне ключове слово, знак операції чи пунктуації: 'if', 'return', `const', 'static', 'int', 'char', 'знак плюс', 'відкрита дужка', 'закрита дужка', 'кома' та багато інших (ці лексеми були розбиті на літери, але це вже стосується лексики, а не граматики).
Ось проста функція мовою C, розбита на лексеми:
int /* ключове слово 'int' */ square ( /* ідентифікатор, відкрита кругла дужка, */ int x /* ключове слово 'int', ідентифікатор, */ ) /* закрита кругла дужка */ { /* відкрита фігурна дужка */ return x * /* ключове слово 'return', ідентифікатор, зірочка, */ x; /* ідентифікатор, крапка з комою */ } /* закрита фігурна дужка */
Синтаксичні групи C це: вислів, оператор, оголошення і визначення функції. Вони представлені в граматиці C нетермінальними символами 'вислів', 'оператор', 'оголошення' і 'визначення функції'. Повна граматика, для того, щоб висловити зміст цих чотирьох, використовує десятки додаткових мовних конструкцій, кожній з яких відповідає свій нетермінальний символ. Приклад вище є визначенням функції, він містить одне оголошення і один оператор. У оператора кожне 'x', так само, як і 'x * x' є висловлюваннями.
Кожному нетермінальному символу мають бути співвіднесені правила граматики, які показують, як він збирається з простіших конструкцій. Приміром, одним з операторів C є оператор return, це може бути описано правилом граматики, неформально записаним так:
'Оператор' може з складатися з ключового слова 'return', 'вислову' і 'крапки з комою'.
Має існувати безліч інших правил для 'оператор', по одному на кожен вид оператора C.
Один нетермінальний символ має бути відзначено як спеціальний, що визначає завершене висловлювання мовою. Він називається початковим символом. У компіляторі це означає повну програму на вході. У C цю роль відіграє нетермінальний символ 'послідовність визначень і оголошень'.
Наприклад, '1 + 2' є правильним виразом C -- правильною частиною програми на C -- але не є правильною повною програмою на C. У контекстно-вільній граматиці C це слідує з того, що 'вислів' не є початковим символом.
Аналізатор Bison читає на вході послідовність лексем і групує їх, використовуючи правила граматики. Якщо вхід правильний, кінцевим результатом буде згортка всієї послідовності лексем в одну групу, якій відповідає початковий символ граматики. Якщо ми використовуємо граматику C, весь вхідний текст в цілому є 'послідовністю визначень і оголошень'. Якщо це не так, аналізатор повідомить про синтаксичну помилку.
2.2 Від формальних правил до вхідного тексту Bison
Формальна граматика -- це математична конструкція. Щоб визначити мову для Bison, ви повинні написати файл, що описує граматику в синтаксисі Bison -- файл граматики Bison. Див. розділ 4. Файли граматики Bison.
Нетермінальний символ формальної граматики на вході Bison має бути ідентифікатором, таким самим як ідентифікатор C. За згодою їх потрібно записувати в нижньому регістрі, наприклад: expr, stmt чи declaration.
Подання в Bison термінальних символів також називається типом лексем. Типи лексем також можуть бути представлені ідентифікаторами в стилі C. За згодою ці ідентифікатори слід записувати у верхньому регістрі, щоб відрізнити їх від нетерміналів, наприклад, INTEGER, IDENTIFIER, IF, чи RETURN. Термінальний символ, відповідний конкретному ключовому слову мови слід називати так само, як це ключове слово виглядає у верхньому регістрі. Термінальний символ error зарезервований для відновлення після помилок. Див. розділ 4.2 Символи, термінальні та нетермінальні.
Термінальний символ також може бути представлений як однолітерна константа, подібно до однолітерної константи C. Вам варто робити так завжди, коли лексема представляє собою просто одиночну літеру (дужку, знак плюс тощо) -- використовуйте ту ж літеру для термінального символу для цієї лексеми.
Третій спосіб подання термінального символу -- подання рядковою сталою C з кількох літер. Див. розділ 4.2 Символи, термінальні та нетермінальні для одержання більшої інформації.
Правила граматики також містять вислови в синтаксисі Bison. Наприклад, ось правило Bison для оператора C return. Крапка з комою в лапках є однолітерною лексемою, що представляє частину синтаксису оператора C, а окрема крапка з комою та двокрапка є знаками пунктуації Bison, використовуваними в в усіх правилах.
stmt: RETURN expr ';'
Див. розділ 4.3 Синтаксис правил граматики.
2.3 Семантичні значення
Формальна граматика вибирає лексеми лише з їх виду, наприклад, якщо у правилі згадується термінальний символ `цілочислова стала', це означає, що у цій позиції граматично припустима будь-яка цілочислова стала. Точне значення константи не має значення для розбору -- якщо `x+4' граматично припустимо, то `x+1' чи `x+3989' теж допустимі.
Але точне значення дуже важливе, щоб після розбору визначити, що означає вхідний текст. Компілятор, не здатний розрізнити у програмі константи 4, 1 і 3989, нічого не вартий! Тому кожна лексема в граматиці Bison характеризується як типом лексеми, так і семантичним значенням. Див. розділ 4.5 Визначення семантики мови.
Тип лексеми -- це термінальний символ, визначений в граматиці, такий як INTEGER, IDENTIFIER чи ','. Він дає всю інформацію, необхідну для прийняття рішення, де припустима поява лексеми і як групувати її з іншими лексемами. Правила граматики не знають про лексеми нічого, крім їх типів.
Семантичне значення несе решту інформації про значення лексеми, таку як значення цілого числа чи ім'я ідентифікатора (такі лексеми як ',', що є просто знаками пунктуації, не потребують ніякого семантичного значення).
Наприклад, вхідна лексема може класифікуватися як лексема типу INTEGER і мати семантичне значення 4. Інша вхідна лексема може мати той же тип INTEGER, але значення 3989. Якщо правило граматики каже, що припустима лексема типу INTEGER, буде прийнята будь-яка з цих двох лексем, бо вони обидві мають тип INTEGER. Коли аналізатор приймає лексему, він відстежує її семантичне значення.
Кожна група, так само як її нетермінальний символ, може мати семантичне значення. Наприклад, у калькуляторі вислів зазвичай має семантичне значення, що являє собою число. У компіляторі мови програмування вислів зазвичай має семантичне значення у вигляді дерева, що описує зміст виразу.
2.4 Семантичні дії