Неоднозначна граматика

В інформатики неоднозначною граматикою називається формальна граматика, яка може породити деяку рядок більш ніж одним способом (тобто для рядка є більше одного дерева розбору). Мова називається істотно неоднозначним, якщо він може бути породжений тільки неоднозначними граматиками.

Граматики деяких мов програмування неоднозначні. При розборі таких мов необхідно враховувати семантичну інформацію для вибору правильного варіанту. Наприклад, на мові C наступна запис:

 x * y; 

може бути проинтерпретирована як або:

Щоб вибрати між цими інтерпретаціями, компілятор повинен звернутися до своєї таблиці символів, щоб дізнатися, чи було оголошення x в якості імені typedef в даній області видимості.


Приклад

Контекстно вільна граматика

A → A + A | A - A | a

є неоднозначною, оскільки є два лівосторонніх виводу для рядка a + a + a:

A → A + A A → A + A
→ a + A → A + A + A
→ a + A + A → a + A + A
→ a + a + A → a + a + A
→ a + a + a → a + a + a

Також, граматика є неоднозначною, оскільки є два дерева розбору для рядка a + a - a:

Leftmostderivations jaredwf.png

Однак, мова, який вона породжує, не є суттєво неоднозначним, оскільки наступна однозначна граматика породжує цей же мова:

A → A + a | A - a | a

Розпізнавання неоднозначною граматики

Загальна задача визначення, чи є граматика неоднозначною, алгоритмічно нерозв'язна. Не може існувати алгоритму, що визначає неоднозначність граматики, оскільки нерозв'язна завдання відповідності Посту зводиться до задачі неоднозначності.

Існує очевидна трудність в синтаксичному аналізі неоднозначною граматики детермінованим аналізатором, але недетермінірованний аналіз призводить до значного програшу в ефективності. Більшість конструкцій, що вимагають синтаксичного аналізу, можуть бути розпізнані однозначними граматиками. Деякі неоднозначні граматики можуть бути перетворені в однозначні, але загальної процедури для цього перетворення немає, так само як немає і алгоритму визначення неоднозначності граматики. Генератори компіляторів, такі як YACC, здатні усувати деякі види неоднозначності, наприклад використовуючи обмеження пріоритету та асоціативності.


Істотно неоднозначні мови

У той час як деякі мови (безлічі рядків, породжуваних граматикою) мають як однозначні, так і неоднозначні граматики, існують мови, для яких не існує однозначної граматики. Прикладом істотно неоднозначного мови є об'єднання \ {A ^ n b ^ m c ^ m d ^ n | n, m> 0 \} і \ {A ^ n b ^ n c ^ m d ^ m | n, m> 0 \} . Це контекстно-вільна мова як об'єднання контекстно-вільних мов, але Введення в теорію автоматів ... містить доказ того, що немає можливості однозначно розібрати рядки в (не контекстно-вільній) підмножині \ {A ^ n b ^ n c ^ n d ^ n | n> 0 \} , Що є перетином цих двох мов.