5.3. Формальні граматики. Нбф-граматика

Граматикою називається формальний опис синтаксису мови програмування.

Граматика визначається набором правил (іноді їх називають правилами підстановки), які визначають побудову із лексем достовірних програм.

Формальна граматика використовує строгу систему позначень. Існують різні типи граматик. НБФ-граматика (граматика Наура-Бэкуса або граматика Бэкуса-Наура - БНФ-граматика) є контекстно-вільною граматикою. Ця граматика використовує НБФ-нотації, запропоновані Джоном Бэкусом в кінці 50-х років для опису синтаксису мови ALGOL.

Проста НБФ-нотація дозволяє описувати всі достовірні конструкції мови програмування, використовуючи наступні символи:

• символ ::= має значення "визначається як" і використовується для визначення всіх допустимих значень, синтаксичної одиниці визначення;

• символ | має значення "або" і використовується для опису альтернативних варіантів;

• пара символів < > обмежує ім’я синтаксичної одиниці, яку називають також не термінальним символом або синтаксичною категорією.

Значення, які стоять поза дужками < >, називаються термінальними символами.

НБФ-граматика складається із набору правил (їх іще називають мета лінгвістичними формулами або продукціями), які записуються за допомогою НБФ-нотації.

Наприклад:

<цифра>::= 0|1|2|3|4|5|6|7|8|9

<цілочисельне значення> ::= цифра | цифра <цілочисельне значення>

Тут символи 0, 1, 2, 3 и т.д. будуть термінальними символами.

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

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

Можна сказати, що граматика складається із множин термінальних і не термінальних символів, початкового не термінального символу і набору правил. В 1959 році Ноам Хомський запропонував таку класифікацію граматик:

• регулярні граматики, які використовуються для побудови лексичних аналізаторів;

• контекстно-вільні граматики, використовуються для побудови дерева граматичного розбору. До цього типу відносяться і НБФ-граматики;

• контекстно-залежні граматики, задаються набором правил типу x->y, в яких х може бути довільним ланцюжком не термінальних символів, а y – ланцюжком термінальних і не термінальних символів.

• граматики з фразовою структурою задаються набором правил типу x->y, в яких х може бути довільним ланцюжком не термінальних символів, а y – ланцюжком термінальних і не термінальних символів (тут не має ніяких обмежень на довжину отримуваних ланцюжків). Більшість таких граматик не мають практичного застосування.

Розширена НБФ-нотація вводить ряд додаткових елементів, які дозволяють значно покращити наглядність представлення правил НБФ-граматики:

• необов’язкові елементи обмежуються квадратними дужками;

• альтернативні елементи, описані за допомогою символу вертикальної риски, також можуть бути необов’язковими елементами, якщо вони взяті в квадратні дужки;

• послідовність декількох однотипних елементів позначається заключенням їх в фігурні дужки, за якими ставиться символ зірочка або плюс({<ціле>}*). Зірочка позначає одне і більше повторення, а плюс – нуль і більше повторень.