в, яка є неподільною, назівається словником або алфавітом , а символи, что входять в множини - літерами алфавіту. Послідовність букв алфавіту назівається словом або ланцюжком цього алфавіту, число букв, что входити у слово, назівається йо Довжина.
Если задано алфавіт А, то А * - це множини всех ланцюжків, Які можна побудуваті з алфавіту А. $ - порожній рядок (рядок, что НЕ містіть жодної букви) такоже входити в А. Для позначені всех ланцюжків алфавіту А, что НЕ містять порожніх вікорістовується А + .
формальність Граматик Г назівається сукупність таких об'єктів
Г = {V T , V N , , R},
Де V T - термінальній алфавіт (словник). З букв цього алфавіту будуються ланцюжкі, Які породжують Граматик.
V N - нетермінальній (допоміжній) алфавіт. Его букви Використовують при побудові ланцюжків, смороду могут входити в проміжні ланцюжкі, альо НЕ могут входити в результат побудова.
- початковий символ.
R - множини правил Виведення.
множини кінцевіх ланцюжків термінального алфавіту V T граматики Г, виведення з початкових символу назівають мовою , яка породжена Граматик Г и позначається L (Г).
Если правило Виведення граматики мініть один нетермінальній символ, як в лівій, так и в правій частіні, то таке правило назівається рекурсивно .
Тіпі формальних Граматик
Віділяють 4 тіпі формальних Граматик. Ці граматики візначаються Шляхом накладання обмежень на правила граматики.
Граматика типом 0 - граматика Загальний вигляд, немає обмежень на правила породження.
Граматика типом 1 - контекстно залежна.
правило: П‡ 1 П‡ 2 в†’ П‡ 1 П‰П‡ 2 .
Ланцюжкі П‡ 1 и П‡ 2 залішаються незміннімі при застосуванні правил, тому їх назівають контекстом , а граматику - контекстно перелогових.
Граматика типом 2 - контекстно вільна.
Правило: в†’ О±, де.
Ці правила слідують Із правил граматики типу 1 за умови П‡ 1 = П‡ 2 = $.
Граматика типом 3 - автоматні.
Правила Виведення: в†’ a або в†’ a або в†’ a, де
.
спосіб завдання схем Граматик
Схема граматики містіть правила Виведення, Які візначають синтаксис мови або ВСІ ланцюжкі породженої мови. Для задання правил Використовують Різні форми Опис:
Символічна
форма Бекуса-Наура (ФБН)
ітераційна
синтаксичні діаграмі
символьних мова передбачає Використання ЕЛЕМЕНТІВ нетермінального словника и стрілки, як роздільніка правої и лівої Частини. Альо при опісі конкретних мов програмування доводитися вводіті велику кількість НЕ термінальніх сімволів и символьних форма запису втрачає свою наочність. br/>
