Bison

для 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.

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 Семантичні дії

Щоб бути корисною, програма має робити щось більше, ніж розбір вхідного тексту -- вона повинна також створювати певний вивід, оснований на вводі. У граматиці Bison правило граматики може містити дію, що складається з операторів C. Щоразу, коли аналізатор розпізнає текст, відповідний правилу, виконується його дія. Див. розділ 4.5.3 Дії.

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

Наприклад, ось правило, де говориться, що вислів може бути сумою двох підвисловів.

expr: expr '+' expr { $$ = $1 + $3; } ;

Дія вказує, як отримати семантичне значення вислову суми зі значень двох підвиразів.

2.5 Положення

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

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

Як і з семантичними значеннями, в діях можна отримати доступ до положення, використовуючи спеціальний набір конструкцій. У наведеному вище прикладі становище групи в цілому -- @$, тоді як положення підвиразів -- @1 і @3.

Коли виявляється текст, що відповідає правилу, для обчислення семантичного значення його лівої частини використовується замовчальна дія (див. розділ 4.5.3 Дії). Так само, для положень використовується інша замовчальна дія. Проте дія для положень у більшості випадків досить загальна, в тому сенсі, що зазвичай не треба описувати формування @$ для кожного правила. При обчисленні нового положення для певної групи за умовчанням аналізатор бере початок першого символу і кінець останнього.

2.6 Вивід Bison: файл аналізатора

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

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

Лексеми надходять із функції, званої лексичним аналізатором, яку ви повинні так чи інакше надати (наприклад, написавши її на C). Анализатор Bison викликає лексичний аналізатор щоразу, коли йому потрібна нова лексема. Він не знає, що "всередині" лексеми (хоча її семантичне значення може відбивати це). Зазвичай лексичний аналізатор отримує лексеми аналізом літер тексту, але Bison не залежить від цього. Див. розділ 5.2 Функція лексичного аналізатора yylex.

Файл аналізатора Bison -- це код на C, що визначає функцію yyparse, що реалізує граматику. Ця функція не утворює завершену програму на C -- ви повинні надати деякі додаткові функції. Одна з них -- лексичний аналізатор. Інша -- функція, що визивається аналізатором для повідомлення про помилку. Крім того, виконання програми на C повинне починатися з функції main: ви повинні створити її та викликати з неї yyparse, інакше аналізатор ніколи не запуститься. Див. розділ 5. Інтерфейс аналізатора на C.

Усі назви змінних і функцій в файлі аналізатора Bison, крім створених вами у діях та назв типів лексем, починаються з `yy' чи `YY'. Сюди входять інтерфейсні функції, такі як функція лексичного аналізатора yylex, функція повідомлення про помилку yyerror і сама функція аналізатора yyparse. Також це стосується числовиих ідентификаторів, вживаних у внутрішніх цілях. Тому вам слід уникати використання ідентифікаторів C, які починаються з `yy' чи `YY' в граматиці Bison, за винятком вказаних в цьому керівництві.

У деяких випадках файл аналізатора Bison включає системні заголовки, і тоді при написанні вашого коду слід враховувати, що деякі ідентифікатори зарезервовані такими заголовками. На деяких не-GNU системах включаються заголовки <alloca.h>, <stddef.h> і <stdlib.h>, оскільки це необхідно для оголошення функцій виділення пам'яті і пов'язаних типів. Інші системні заголовки можуть бути включені, якщо ви задасте ненульове значення YYDEBUG (див. розділ 9. Відладження вашого аналізатора).

2.7 Етапи використання Bison

Дійсний процес розробки мови з використанням Bison, від задання граматики до працюючого компілятора чи інтерпретатора, містить такі етапи:

1. Формально описати граматику у вигляді, що розпізнається Bison (див. розділ 4. Файли граматики Bison). Для кожного правила граматики мови описати дії, що мають виконуватися при розпізнаванні тексту, відповідного цьому правилу. Дія описується послідовністю операторів C.
2. Написати лексичний аналізатор для обробки вхідного тексту і передачі лексем аналізатору. Лексичний аналізатор може бути написаний вручну на C (див. розділ 5.2 Функція лексичного аналізатора yylex). Він також може бути створений за допомогою Lex, але використання Lex в цьому керівництві не обговорюється.
3. Написати керівну функцію, що викликає аналізатор, створений Bison.
4. Написати процедуру повідомлення про помилки.

Щоб перетворити цей джерельний код в робочу програму, ви повинні виконати такі кроки:

1. Пропустіть опис граматики через Bison, щоб отримати аналізатор.
2. Скомпілюйте код, створений Bison, так само, як будь-який інший файл із джерельним кодом.
3. Зберіть об'єктні файли, щоб отримати кінцевий продукт.

2.8 Огляд схеми граматики Bison

Вхідний файл утиліти Bison -- це файл граматики Bison. Загальний вид файла граматики Bison наступний:

%{ 
Оголошення C 
%}

Оголошення Bison

%% 
Правила граматики 
%% 
Додатковий код на C

`%%', `%{' і `%}' -- це знаки пунктуації, присутні в будь-якому файлі граматики Bison для поділу його секцій.

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

Оголошення Bison вказують назви термінальних та нетермінальних символів і можуть також описувати пріоритет операцій і типи даних семантичних значень різних символів.

Правила граматики визначають, як кожен нетермінальний символ збирається зі своїх частин.

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

3. Приклади

Зараз ми наведемо і пояснимо три прості програми, написані з використанням Bison: калькулятор зворотної польської нотації, калькулятор алгебраїчної (інфіксної) нотації, і багатофункціональний калькулятор. Всі три протестовані під BSD Unix 4.3, кожна з них дає придатний для використання, хоча й обмежений, інтерактивний настільний калькулятор.

Ці приклади прості, але граматики Bison для реальних мов програмування пишуться таким самим чином.

3.1 Калькулятор зворотної польської нотації

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

Вихідний код цього калькулятора називається `rpcalc.y'. За згодою для вхідних файлів Bison використовується розширення `.y'.

3.1.1 Оголошення для rpcalc

Це оголошення C і Bison для калькулятора зворотної польської нотації. Як і в C, коментарі вміщаються між `/*...*/'.

/* Калькулятор зворотної польської нотації. */

%{ #define YYSTYPE double #include <math.h> %}

%token NUM

%% /* Далі йдуть правила граматики і дії */

Секція оголошень C (див. розділ 4.1.1 Секція оголошень C) містить дві директиви препроцесора.

Директива #define визначає макрос YYSTYPE. Це задає тип даних C для семантичних значень як лексем, так і груп (див. розділ 4.5.1 Типи даних семантичних значень). Анализатор Bison використовуватиме будь-який тип, заданий YYSTYPE, а якщо ви не визначили його -- тип за умовчанням int. Оскільки ми зазначили double, кожній лексемі і кожному виразу буде асоційовано дійсне число.

Директива #include використовується для оголошення функції зведення до степеня pow.

З другої секції, оголошень Bison, Bison отримує інформацію про типи лексем (див. розділ 4.1.2 Секція оголошень Bison). Тут має бути оголошено будь-який термінальний символ, який не є однолітерною сталою (вони, як правило, не потребують оголошення). У цьому прикладі всі арифметичні операції позначаються однолітерними сталими, тому потрібно оголосити лише термінальний символ NUM, тип лексеми для числових констант.

3.1.2 Правила граматики для rpcalc

Це правила граматики для калькулятора зворотної польської нотації.

input:    /* пусто */
        | input line
;

line:     '\n'
        | exp '\n'  { printf ("\t%.10g\n", $1); }
;

exp:      NUM             { $$ = $1;         }
        | exp exp '+'     { $$ = $1 + $2;    }
        | exp exp '-'     { $$ = $1 - $2;    }
        | exp exp '*'     { $$ = $1 * $2;    }
        | exp exp '/'     { $$ = $1 / $2;    }
      /* зведення до степеня */
        | exp exp '^'     { $$ = pow ($1, $2); }
      /* унарний минус        */
        | exp 'n'         { $$ = -$1;        }
;
%%

Тут визначено групи "мови" rpcalc: вислів (названий exp), рядок введення (line), і кінцевий вхідний текст (input). У кожного з цих нетермінальних символів є кілька альтернативних правил, об'єднаних знаком `|', що означає "або". У наступних розділах пояснюється, що означають ці правила.

Семантика мови визначається діями при розпізнаванні групи. Дії -- це код на C, що знаходиться між фігурними дужками. Див. розділ 4.5.3 Дії.

Ви повинні писати ці дії на C, проте Bison надає спосіб передачі семантичних значень між правилами. У кожному дії псевдозмінна $$ означає семантичне значення групи, яку збирає це правило. Присвоєння $$ значення -- основна робота більшості дій. На семантичні значення компонентів правила можна посилатися як на $1, $2 тощо.

4. Файли граматики Bison

5. Інтерфейс аналізатора на C

6. Алгоритм аналізатора Bison

8. Обробка контекстних залежностей

10. Виклик Bison

C. Копіювання цього керівництва