Loading AI tools
З Вікіпедії, вільної енциклопедії
Контекстно-вільна граматика (скорочено КВ-граматика) — формальна граматика типу 2 в ієрархії Чомскі.
Контекстно-вільна граматика — це четвірка :
Використовують такі назви: — множина нетермінальних символів, — множина термінальних символів, — множина правил виводу, — початковий символ. Правила записують як .
У лівій частині правила виводу має міститися одна змінна (нетермінальний символ). Формально має виконуватись: , де .
Розширенням КВ-граматик є стохастичні КВ-граматики. Правилам виведення співставляють ймовірність використання: де
Для КВ-граматик визначено різні нормальні форми. В нормальних формах Чомскі (НФЧ) скорочуюють праву частину правил виводу, тобто права частина може складатись або з одного термінального символу, або з двох нетермінальних. Якщо в лівій частині міститься початковий символ, права частина може породжувати порожнє слово. Існує алгоритм, який переводить довільну КВ-граматику в НФЧ.
Контекстно-вільна граматика визначена в нормальній формі Грейбах (НФГ), якщо вона не породжує порожнього слова та права частина правил виводу починається з щонайбільше одного термінального символу, слідом за яким йдуть нетермінальні символи. Кожна КВ-граматика, яка не породжує порожнє слово, може бути перетворена в НФГ алгоритмом.
Контекстно-вільні граматики породжують контекстно-вільні мови, тобто кожна КВ-граматика породжує КВ-мову, і для кожної КВ-мови існує КВ-граматика, що її породжує.
Контекстно-вільну мову , породжену КВ- граматикою , позначають , де:
Символом позначають послідовність правил виводу граматики , унаслідок застосування якої отримують слово мови . Також .
Контекстно-вільні мови можна розпізнати недетермінованим автоматом з магазинною пам'яттю. Якщо існує детермінований автомат, здатний розпізнати мову, її називають детермінованою КВ-мовою. Ця підмножина КВ-мов утворює теоретичну основу для синтаксиса багатьох мов програмування.
Контекстно-вільні мови можуть містити порожнє слово, наприклад, через правило виводу .
Задача визначення належності слова КВ-мові, або визначення можливості породження слова КВ-граматикою, алгоритмічно розв'язна.[1] Під час розв'язання цієї задачі можна побудувати дерево виводу. Його також називають деревом синтаксичного аналізу, а програму, яка його будує, — синтаксичним аналізатором. Для кожної КВ-граматики можна автоматично побудувати синтаксичний аналізатор (див. також генератор синтаксичних аналізаторів та CYK-алгоритм). Часова складність для найгіршого випадку синтаксичного аналізу довільної КВ-граматики O. Для детермінованих КВ-граматик можна побудувати синтаксичний аналізатор, час роботи якого . Типовим прикладом застосування ефективних синтаксичних аналізаторів з лінійним часом роботи є синтаксичний аналіз вихідних текстів програм в компіляторі.
Якщо слово мови () в граматиці може бути отримане кількома різними способами, то таку граматику називають багатозначною. Синтаксичний аналізатор для багатозначної граматики може побудувати кілька різних дерев синтаксичного аналізу. Багатозначність не важлива для розв'язання задачі належності слова, але якщо різним деревам співставляють різне значення, то той самий текст може мати різні значення. Наприклад, однозначність граматики важлива для процесу компіляції, аби отримати правильний код.
Задача розпізнавання багатозначності серед КВ-граматик алгоритмічно не розв'язна.[2]. Однак існують способи перевірки на багатозначність або однозначність для деяких окремих випадків КВ-граматик[3].
Задача визначення еквівалентності граматик та , або породження ідентичних мов , алгоритмічно нерозв'язна.[4]
Задача визначення чи породжена КВ-граматикою мова також може бути породжена іншою КВ-граматикою , тобто чи , алгоритмічно нерозв'язна.[4]
Об'єднання двох КВ-граматик () також КВ-граматика. Тобто, .
Задача визначення належності перетину двох КВ-граматик до класу КВ-граматик алгоритмічно не розв'язувана.[4]
Доповнення КВ-граматики не контекстно-вільне.
Нехай — КВ-граматика
в граматиці можна отримати такою послідовністю застосування правил виводу:
, тут — дерево виведення. Корінь дерева та проміжні вузли позначені нетермінальними символами, а листи дерева позначені термінальними символами.
Таким чином, .
Слово де не належить до мови , оскільки нетермінальний символ не початковий, а всі слова утворені від початкового мають розташовуватися посеред термінальних та . Формально це записують:
Граматика не багатозначна.
Як приклад багатозначної граматики можна навести: .
До можна застосувати правила , та . Таким чином, — багатозначна.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.