Головна

Розбір ланцюжків (с64-67)

  1.  Aufgabe 2. Вивчіть зразки граматичного розбору простих речень. Виберіть з тексту і розберіть 3 простих пропозиції.
  2.  Агнет (виконавець), що коливається тілесно і розумово, безсовісний, зарозумілий, нерозбірливий, злісний, ледачий, горюющій і повільний, є тамасіческой.
  3.  У таблиці статистичного розподілу, побудованого за вибіркою, одна цифра написана нерозбірливо Ця цифра дорівнює (наберіть число).
  4.  Група 18 Розбірки покриттів і підстав
  5.  Група 98 Улаштування і розбирання тимчасових роз'їздів
  6.  Група 99 Улаштування і розбирання тимчасових Лежневим доріг
  7.  Е2-1-51. Пристрій і розбирання кріплень стінок траншей, котлованів і ям

Ланцюжок належить мові, породжуваному граматикою, тільки в тому випадку, якщо існує її висновок з мети цієї граматики. Процес побудови такого висновку (а, отже, і визначення приналежності ланцюжка мови) називається розбором.

З практичної точки зору найбільший інтерес представляє розбір по контекстно-вільним (КС і УКБ) граматика. Їх породжує потужності достатньо для опису більшої частини синтаксичноїструктури мов програмування, для різних підкласів КВ-граматик є добре розроблені практично прийнятні шляхи вирішення завдання розбору.

Розглянемо основні поняття і визначення, пов'язані з розбором по КС- граматиці.

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

Тут (2) - лівобічний висновок, (3) - правосторонній, а (1) не є ні лівостороннім, ні правостороннім, але всі ці висновки є еквівалентними в зазначеному вище сенсі.

Для КС-граматик можна ввести зручне графічне представлення виведення, зване деревом виведення, причому для всіх еквівалентних висновків дерева виведення збігаються.

Дерево виведення часто називають деревом граматичного розбору, або синтаксичним деревом, а процес побудови дерева виведення - граматичним розбором (синтаксичним аналізом).

Це твердження еквівалентно тому, що ланцюжок ? має два або більше різних лівосторонніх (або правобічних) висновків.

визначення:в іншому випадку граматика називається однозначної.

визначення:мова, що породжується граматикою, називається неоднозначним, Якщо він не може бути породжений ніякої однозначної граматикою.

Однак це не означає, що мова L (G) обов'язково неоднозначний. Певна нами неоднозначність - це властивість граматики, а не мови, т. Е. Для деяких неоднозначних граматик існують еквівалентні їм однозначні граматики.

Якщо граматика використовується для визначення мови програмування, то вона повинна бути однозначною.

Проблема, породжує дана КС-граматика однозначна мову (т. Е. Чи існує еквівалентна їй однозначна граматика), є алгоритмічно нерозв'язною.

Дерево виведення можна будувати спадним або висхідним способом.

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

Метод висхідного розбору полягає в тому, що вихідну ланцюжок намагаються "згорнути" до початкового символу S; на кожному кроці шукають подцепочку, яка збігається з правою частиною будь-якого правила виведення; якщо така подцепочка знаходиться, то вона замінюється нетерміналом з лівої частини цього правила. Якщо граматика однозначна, то при будь-якому способі побудови буде отримано одне і те ж дерево розбору.

(С68-69)

Приклади розв'язання задач на слайді (С70)

- Контекстно-вільні граматики широко застосовуються для визначення граматичної структури в граматичному аналізі.

- Регулярні граматики (у вигляді регулярних виразів) широко застосовуються як шаблони для текстового пошуку, розбиття та підстановки, в тому числі в лексичному аналізі.


 Класифікація граматик і мов по Хомського (с61-62) |  лекція №5


 Методи доказу алгоритмічної нерозв'язності |  Другий тип алгоритмічних моделей. |  Оператор примітивної рекурсії (С41) |  Оператор мінімізації (С42) |  Примітивно-рекурсивні та частково-рекурсивних функцій. (С43) |  усічена різницю |  Марковские підстановки. |  Приклад (С49). |  Нормально обчислюваної функції і принцип нормалізації Маркова. |  Формальні граматики і мови |

© 2016-2022  um.co.ua - учбові матеріали та реферати