Знаймо![]() приховати рекламу
| Цей текст може містити помилки. ВведенняФормальна граматика або просто граматика в теорії формальних мов - спосіб опису формальної мови, тобто виділення деякого підмножини з множини всіх слів деякого кінцевого алфавіту. Розрізняють породжують і розпізнають (або аналітичні) граматики - перші задають правила, за допомогою яких можна побудувати будь-яке слово мови, а другі дозволяють по даному слову визначити, входить воно в мову чи ні. 1. Терміни
2. Породжують граматикиСловами мови, заданого граматикою, є всі послідовності терміналів, що виводяться (породжувані) з початкового нетермінала за правилами виводу. Щоб задати граматику, потрібно задати алфавіти терміналів і нетерміналів, набір правил виведення, а також виділити в безлічі нетерміналів початковий. Отже, граматика визначається наступними характеристиками:
2.1. ВисновокВисновком називається послідовність рядків, що складаються з терміналів і нетерміналів, де першою йде рядок, що складається з одного стартового нетермінала, а кожна наступна рядок отримана з попередньої шляхом заміни деякої підрядка по одному (будь) з правил. Кінцевою рядком є рядок, повністю складається з терміналів, і отже є словом мови. Існування виводу для деякого слова є критерієм його приналежності до мови, що визначається даної граматикою. 2.2. Типи граматикЗа ієрархії Хомського, граматики діляться на 4 типи, кожний наступний є більш обмеженим підмножиною попереднього (але й легше піддається аналізу):
2.3. Застосування
2.4. Приклад - арифметичні вираження Розглянемо просту мову, що визначає обмежена підмножина арифметичних формул, що складаються з натуральних чисел, дужок і знаків арифметичних дій. Варто зауважити, що тут у кожному правилі з лівого боку від стрілки Термінальний алфавіт: Σ = {0 ", '1 ', '2', '3 ', '4', '5 ', '6', '7 ', '8', '9','+','-', '*','/','(',')'}. Нетермінальний алфавіт: {ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА} Правила: 1. ФОРМУЛА Початковий нетермінал: ФОРМУЛА
Виведемо формулу (12 +5) за допомогою перерахованих правил виводу. Для наочності, сторони кожної заміни показані попарно, в кожній парі замінна частина підкреслена.
3. Аналітичні граматикиПороджують граматики - не єдиний вид граматик, однак найбільш поширений в додатках до програмування. На відміну від граматик, аналітична (розпізнає) граматика задає алгоритм, що дозволяє визначити, чи належить дане слово мови. Наприклад, будь-який регулярний мова може бути розпізнаний за допомогою граматики, що задається кінцевим автоматом, а будь-контекстно-вільна граматика - за допомогою автомата з стекової пам'яттю. Якщо слово належить мові, то такий автомат будує його висновок в явному вигляді, що дозволяє аналізувати семантику цього слова. Джерела
Цей текст може містити помилки. Схожі роботи | скачати Схожі роботи: Формальна семантика Формальна логіка Формальна система Формальна верифікація Формальна мова Формальна верифікація Формальна система Ім'я (граматика) Граматика |