Page 11 - 4761

би гарантовано виконував розбір речення за обмежений час на базі обмежених
обчислювальних ресурсів.
На жаль, всі природні мови спілкування між людьми відносяться до типу 0.
Тип 1: контекстно-залежні мови (КЗ-мови) .
Другий по складності тип. Час на розпізнавання речень мови, що відносяться до 1-
го типу, експоненціально залежить від довжини початкового ланцюга символів мови типу
1. Застосовують при аналізі та перекладі текстів на природні мови.
В компіляторах КЗ-мови не використовуються, оскільки мови програмування
мають більш складну структуру.
Тип 2 : контекстно-вільні мови (КВ-мови).
КВ-мови лежать в основі побудови синтаксичних конструкцій більшості сучасних
мов програмування. Час на розпізнавання речень мови, поліноміально залежить від
довжини вхідного ланцюга символів (квадратична чи кубічна залежність), буває й лінійна.
Тип 3 : регулярні мови (РМ).
РМ – самий простий тип. Час на розпізнавання символів – лінійно залежить від
довжини вхідного ланцюга символів.
РМ лежать в основі найпростіших конструкцій мов програмування, крім того, на
їхній основі побудовано мнемо коди машинних команд, а також командні процесори та
інші подібні структури.
РМ – дуже зручний засіб. Для роботи з ними можна використовувати регулярні
множини і вирази та кінцеві автомати.

1.5 Форми задання граматики

В множині правил граматики може бути декілька правил, які мають одинакові
праві частини. Тоді ці правила об’єднують разом і записують в одному рядку, розділяючи
кожне правило у правій часині символом «|». Таку форму запису граматики називають
формою Бекуса-Наура. Ця форма передбачає також, що нетермінальні символи беруть у
кутові дужки <>.
Приклад 1. 1.
Побудувати граматику для отримання цілих десяткових чисел зі знаком.
G ({0,1,2,3,4,5,6,7,8,9, , },{ число    }, чс  , цифра  , P  число ) 
Р:
<число><чс>|+<чс>|-<чс>
<чс> <цифра>|<чс><цифра>
<цифра>0|1|2|3|4|5|6|7|8|9
Любий нетермінальний символ можна замінити.

Прикла 1.2
Побудувати граматику, яка дозволяє вивести арифметичні вирази для множини
цілих чисел {0,1,2,3,4,5,6,7,8,9}.
G ({ , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0  , , , ,   (, , )}, {S , A , B }, , P ) S
Р:
S(A+B)|(A-B)|(A B)|(A B)|(A^B)
A(A+B)|(A-B)|(A B)|(A B)|(A^B)
A0|1|2|3|4|5|6|78|9
B(A+B)|(A-B)|(A B)|(A B)|(A^B)
B0|1|2|3|4|5|6|7|8|9

Використаємо її для виводу арифметичного виразу ((2+3)*(4+5)) почнемо з правила
S(A B), потім A(A+B) і B(A+B), шоб отримати ((А+В)*(А+В)). Правило А2 і
В3 дають ((2+3)*(A+B)) і на кінець А4 і В5, дадуть ((2+3)*(4+5))
9