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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Контекстно-вільна граматика (скорочено КВ граматика) — формальна граматика типу 2 в ієрархії Чомскі.

Визначення[ред.ред. код]

Контекстно-вільна граматика G це четвірка (N,T,P,S):

  • S \in N
  • N та T скінченні множини, що не перетинаються
  • P скінченна підмножина N \times (N \cup T)^*

При цьому, використовують такі назви: N — множина нетермінальних символів, T — множина термінальних символів, P — множина правил виводу S початковий символ. Правила (\alpha, \beta) \in P записують як \alpha \rightarrow \beta.

В лівій частині правила виводу має знаходитись одна змінна (нетермінальний символ). Формально, має виконуватись \alpha\in N, \beta\in(N\cup T)^*, wobei |\beta|\geq 1.

Розширенням КВ-граматик є стохастичні КВ граматики. Правилам виведення співставляють ймовірність використання: \rho: P\rightarrow\mathbb{R} де \sum_{p_r \in P_r} \rho(p_r) = 1

Нормальні форми[ред.ред. код]

Для КВ граматик визначено різні нормальні форми. В нормальних формах Чомскі (НФЧ) скорочуюють праву частину правил виводу, тобто, права частина може складатись або з одного термінального символу, або з двох нетермінальних. Якщо в лівій частині знаходиться початковий символ, права частина може породжувати порожнє слово. Існує алгоритм, який переводить довільну КВ граматику в НФЧ.

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

Породжена мова[ред.ред. код]

Контекстно-вільні граматики породжують контекстно-вільні мови, тобто, кожна КВ граматика породжує КВ мову, і для кожної КВ мови існує КВ граматика, що її породжує.

Контекстно-вільну мову L, породжену КВ граматикою G позначають L(G), де:

L(G) = \{ w | w\in T^*, S \rightarrow_G^* w \}

Символом \rightarrow_G^* позначають послідовність правил виводу граматики G, в результаті застосування якої отримують слово w мови L(G). Також L(G)\subset T^*.

Контекстно-вільні мови можна розпізнати недетермінованим автоматом з магазинною пам'ятю. За умови існування детермінованого автомату, здатного розпізнати мову, її називають детермінованою КВ мовою. Ця підмножина КВ мов утворює теоретичну основу для синтаксиса багатьох мов програмування.

Контекстно-вільні мови можуть містити порожнє слово, наприклад, через правило виводу (S \rightarrow \varepsilon).

Властивості[ред.ред. код]

Приналежність слова[ред.ред. код]

Задача визначення приналежності слова КВ мові, або визначення можливості породження слова w КВ граматикою алгоритмічно розв'язна.[1] Під час розв'язання цієї задачі можна побудувати дерево виводу. Його також називають деревом синтаксичного аналізу, а програму, яка його будує — синтаксичним аналізатором. Для кожної КВ граматики можна автоматично побудувати синтаксичний аналізатор (див. також генератор синтаксичних аналізаторів та CYK-алгоритм). Часова складність для найгіршого випадку синтаксичного аналізу довільної КВ граматики знаходиться на рівні O(n^3). Для детермінованих КВ граматик можна побудувати синтаксичний аналізатор, час роботи якого знаходиться на рівні O(n). Типовим прикладом застосування ефективних синтаксичних аналізаторів з лінійним часом роботи є синтаксичний аналіз вихідних текстів програм в компіляторі.

Якщо слово w мови L (w\in L(G)) в граматиці G може бути отримане декілька різними способами, то таку граматику називають багатозначною. Синтаксичний аналізатор для багатозначної граматики може побудувати декілька різних дерев синтаксичного аналізу. Багатозначність не важлива для розв'язання задачі належності слова, але якщо різним деревам співставляють різне значення, то один й той самий текст може мати різні значення. Наприклад, однозначність граматики важлива для процесу компіляції, аби отримати правильний код.

Багатозначність[ред.ред. код]

Задача розпізнавання багатозначності серед КВ граматик алгоритмічно не розв'язна.[2]. Однак існують способи перевірки на багтозначність або однозначність для деяких окремих випадків КВ граматик[3].

Еквівалентність[ред.ред. код]

Задача визначення еквівалентності граматик G_1 та G_2, або породження ідентичних мов L(G_1) = L(G_2) алгоритмічно нерозв'язна.[4]

Підмножина[ред.ред. код]

Задача визначення чи породжена КВ граматикою G_1 мова також може бути породжена іншою КВ граматикою G_2, тобто, чи L(G_1)\subseteq L(G_2) алгоритмічно нерозв'язна.[5]

Об'єднання[ред.ред. код]

Об'єднання G двох КВ граматик G_1=(N_1,T_1,P_1,S_1), G_2=(N_2,T_2,P_2,S_2) (G=G_1\cup G_2) також КВ граматика. Тобто, G=(N_1\cup N_2,T_1\cup T_2, P_1\cup P_2\cup\{S\rightarrow S_1, S\rightarrow S_2\}, S).

Перетин[ред.ред. код]

Задача визначення приналежності перетину двох КВ граматик G_1, G_2 до класу КВ граматик алгоритмчно не розв'язувана.[6]

Доповнення[ред.ред. код]

Доповнення КВ граматики не контекстно-вільне.

Приклади[ред.ред. код]

Нехай G=(N,T,P,S) — КВ граматика

T = \{ x, y, z \}
N = \{ S, A, B\}
P складається з чотирьох правил виводу:

\begin{align}
S & \rightarrow & A \\
A & \rightarrow & x A y \\
A & \rightarrow & x B y \\
B & \rightarrow & z
\end{align}

w_1 = xxzyy в граматиці G можна отримати наступною послідовністю застосування правил виводу:

t(w_1) = S(A(x,A(x,B(z),y),y))

тут t(w_1) — дерево виведення. Корінь дерева та проміжні вузли позначені нетермінальними символами, а листи дерева позначені термінальними символами.

Таким чином, w_1\in L(G).

Слово w_2 де w_2 = z не належить до мови L(G), оскільки нетермінальний символ B не початковий, а всі слова утворені від початкового мають знаходитись посеред термінальних x та y. Формально це записують:

w_2\notin L(G)

Граматика G не багатозначна.

Приклад багатозначності[ред.ред. код]

В якості прикладу багатозначної граматики можна навести: G_2=(N_2,T_2,P_2,S_2).

T_2 = \{ x, y \}
N_2 = \{ S_2, A\}
P_2 містить такі правила виводу:

\begin{align}
S_2 & \rightarrow & A \\
A & \rightarrow & AA \\
A & \rightarrow & x A y \\
A & \rightarrow & \varepsilon
\end{align}

До w_3=xy можна застосувати правила S(A(x,A(\varepsilon),y)), S(A(\varepsilon),A(x,A(\varepsilon),y)) та S(A(x,A(\varepsilon),y),A(\varepsilon)). Таким чином G_2 — багатозначна.

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]

  1. Schöning, 2001, S.21
  2. Alfred V. Aho and Jeffrey D. Ullman The Theory of Parsing, Translation, and Compiling. Volume 1: Parsing. — Prentice-Hall, 1972. — ISBN 0-13-914556-7.
  3. H. J. S. Basten Ambiguity Detection Methods for Context-Free Grammars.
  4. Schöning, 2001, S.137
  5. Schöning, 2001, S.137
  6. Schöning, 2001, S.137

Література[ред.ред. код]

  • Uwe Schöning Theoretische Informatik - kurzgefasst. — 4.. — Spektrum Akademischer Verlag, 2001. — С. 13, 51. — ISBN 3-8274-1099-1.