7. Контекстно-вільні грамматики

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

Поява поняття КВ-граматика практично збіглося з появою метамови Бекуса (або нормальної форми Бекуса), що була вперше використана при описі мови програмування АЛГОЛ-60 і швидко стала узвичаєним способом формального опису мов програмування. Опис мови за допомогою нормальних форм Бекуса являє собою сукупність так званих "металінгвістичних формул" - виразів вигляду    Y₁…Y_n, де Х - деякий текст, укладений у кутові дужки і називаний металінгвістичною змінною, а Y₁, … , Υ_n– послідовності металінгвістичних змінних і основних символів мови (букв, цифр, роздільників, неподільних слів типу "beqin, end, else" і т.д.). Знак ::= називається металінгвістичною зв'язкою і читається як "є" або "це". Знак  - це металінгвістична зв'язка "або". Металінгвістна змінна являє собою ім'я конструкції мови.

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

Приклад 1. Множина ідентифікаторів АЛГОЛ-60 - це множина ланцюжків із букв і цифр, що починаються з букви. Тоді поняття ідентифікатора може бути описане за допомогою таких нормальних форм Бекуса (металінгвістичних формул), в яких ланцюжок із букв і цифр скорочено називається БЦ-ланцюжком:

ідентифікатор буква букваБЦ-ланцюжок

БЦ-ланцюжокбуквацифрабуква

БЦ-ланцюжокцифраБЦ-ланцюжок

букваa |b|... | z

<цифра>::=0 |1|... | 9.

Основні символи мови - це 26 букв латинського алфавіту і 10 цифр.

Приклад 2. Мова арифметичних виразів (без констант і з фіксованою множиною змінних а, b, c) у метамові Бекуса описується в такий спосіб:

<арифм. вираз>::=<терм>|<арифм. вираз>+<терм>|<арифм. вираз>-<терм>

2. <терм>::=<множник>|<терм>*множниктерммножник

множникарифм.вираззмінна

змінна = a | b | c.

Уже з цих прикладів ясно, що нормальні форми Бекуса неважко перетворити в КВ-граматику.

Дійсно, основні символи відповідають термінальним символам граматики, металінгвістичні змінні - нетермінальним символам, зв'язка ::= - знаку →, а без зв'язки  можна обійтися, якщо формулу Х::=Y₁| ... |Y_n замінити системою формул X::=Y₁, ... X::=Y_n. Якщо зазначені перетворення провести для останнього приклада, замінивши <арифм.вираз> на символ І, <терм > - на Т, <множник>- на М, <змінну>- на L, то одержимо таку КВ-граматику:

I→Τ ;







 

І L La; L→b; L→c.

Зазначена відповідність є взаємно-однозначною, і всяка КВ-граматика перетворюється в нормальні форми Бекуса

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

Задачі

1. Дайте визначення умов точного опису такого поняття як "формула".

2. Дайте визначення умов точного опису такого поняття як "масив".

3. Виконайте аналіз алгоритмічної мови Паскаль як формальної системи.

4. Наведіть приклади виведення формул в елементарній алгебрі як формальній теорії.

5. Наведіть приклад гіпотези з таких розділів математики, як математичний аналіз, алгебра, геометрія, алгебра логіки та теорія графів.

6. Наведіть приклад аксіом в таких розділах математики, як математичний аналіз, алгебра, геометрія, алгебра логіки та теорія графів.

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

8. Наведіть приклад застосування правила підстановки в алгебрі логіки.

9. Наведіть приклади одно-, дво- та тримісних предикатів.

10. Наведіть приклад знакової системи.

11. Застосуйте правила виведення в граматиці типу 0 для визначення понять в алгоритмічній мові ПАСКАЛЬ.

12. Застосуйте правила виведення в граматиці типу 1 для визначення понять в алгоритмічній мові ПАСКАЛЬ.

13. Застосуйте правила виведення в граматиці типу 2 для визначення понять в алгоритмічній мові ПАСКАЛЬ.

14. Застосуйте правила виведення в граматиці типу 3 для визначення понять в алгоритмічній мові ПАСКАЛЬ.

15. Побудуйте нормальну форму Бекуса для визначення оператора:

а) арифметичного;

б) умовного;

в) логічного;

г) циклу.

16. За допомогою КВ-граматики дайте визначення операторів, що перелічені в задачі 15.

83