Головна |
Ланцюжок належить мові, породжуваному граматикою, тільки в тому випадку, якщо існує її висновок з мети цієї граматики. Процес побудови такого висновку (а, отже, і визначення приналежності ланцюжка мови) називається розбором.
З практичної точки зору найбільший інтерес представляє розбір по контекстно-вільним (КС і УКБ) граматика. Їх породжує потужності достатньо для опису більшої частини синтаксичноїструктури мов програмування, для різних підкласів КВ-граматик є добре розроблені практично прийнятні шляхи вирішення завдання розбору.
Розглянемо основні поняття і визначення, пов'язані з розбором по КС- граматиці.
У граматиці для однієї і тієї ж ланцюжка може бути кілька висновків, еквівалентних в тому сенсі, що в них в одних і тих же місцях застосовуються одні і ті ж правила виведення, але в різному порядку.
Тут (2) - лівобічний висновок, (3) - правосторонній, а (1) не є ні лівостороннім, ні правостороннім, але всі ці висновки є еквівалентними в зазначеному вище сенсі.
Для КС-граматик можна ввести зручне графічне представлення виведення, зване деревом виведення, причому для всіх еквівалентних висновків дерева виведення збігаються.
Дерево виведення часто називають деревом граматичного розбору, або синтаксичним деревом, а процес побудови дерева виведення - граматичним розбором (синтаксичним аналізом).
Це твердження еквівалентно тому, що ланцюжок ? має два або більше різних лівосторонніх (або правобічних) висновків.
визначення:в іншому випадку граматика називається однозначної.
визначення:мова, що породжується граматикою, називається неоднозначним, Якщо він не може бути породжений ніякої однозначної граматикою.
Однак це не означає, що мова L (G) обов'язково неоднозначний. Певна нами неоднозначність - це властивість граматики, а не мови, т. Е. Для деяких неоднозначних граматик існують еквівалентні їм однозначні граматики.
Якщо граматика використовується для визначення мови програмування, то вона повинна бути однозначною.
Проблема, породжує дана КС-граматика однозначна мову (т. Е. Чи існує еквівалентна їй однозначна граматика), є алгоритмічно нерозв'язною.
Дерево виведення можна будувати спадним або висхідним способом.
При низхідному розборі дерево виведення формується від кореня до листя; на кожному кроці для вершини, поміченої нетермінальним символом, намагаються знайти таке правило виводу, щоб наявні в ньому термінальні символи "проектувалися" на символи початкового ланцюжка.
Метод висхідного розбору полягає в тому, що вихідну ланцюжок намагаються "згорнути" до початкового символу S; на кожному кроці шукають подцепочку, яка збігається з правою частиною будь-якого правила виведення; якщо така подцепочка знаходиться, то вона замінюється нетерміналом з лівої частини цього правила. Якщо граматика однозначна, то при будь-якому способі побудови буде отримано одне і те ж дерево розбору.
(С68-69)
Приклади розв'язання задач на слайді (С70)
- Контекстно-вільні граматики широко застосовуються для визначення граматичної структури в граматичному аналізі.
- Регулярні граматики (у вигляді регулярних виразів) широко застосовуються як шаблони для текстового пошуку, розбиття та підстановки, в тому числі в лексичному аналізі.
Класифікація граматик і мов по Хомського (с61-62) | лекція №5
Методи доказу алгоритмічної нерозв'язності | Другий тип алгоритмічних моделей. | Оператор примітивної рекурсії (С41) | Оператор мінімізації (С42) | Примітивно-рекурсивні та частково-рекурсивних функцій. (С43) | усічена різницю | Марковские підстановки. | Приклад (С49). | Нормально обчислюваної функції і принцип нормалізації Маркова. | Формальні граматики і мови |