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

Контекстно-вільна граматика (КС-граматика, бесконтекстная граматика) - окремий випадок формальної граматики (тип 2 по ієрархії Хомського), у якій ліві частини всіх продукцій є поодинокими нетерміналу. Зміст терміну "контекстно-вільна" полягає в тому, що можливість застосувати продукцію до нетерміналу, на відміну від загального випадку необмеженої граматики Хомського, не залежить від контексту цього нетермінала.

Мова, який може бути заданий КС-граматикою, називається контекстно-вільним мовою або КС-мовою.

Слід зауважити, що по суті КС-граматика - інша форма БНФ.


1. Застосування

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

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


2. Типи КС граматик

  • LL-граматика
  • LALR-граматика (див.: LALR (1))
  • LR-граматика
  • SLR-граматика (див.: SLR (1))

3. Приклади

Приклади КС-граматик і відповідних їм КС-мов:

3.1. Слово з переворотом

Задається формулою L = \ {ww ^ R, w \ in \ Sigma * \}

  • Термінали: літери алфавіту Σ;
  • Нетермінал: S;
  • Продукції: S \ rightarrow \ alpha S \ alpha, \ alpha \ in \ Sigma; S \ rightarrow \ varepsilon
  • Початковий нетермінал - S.

3.2. Вкладені дужки

  • Термінали: '(' і ')';
  • нетермінал: S;
  • продукції: S → (S), S → ε;
  • початковий нетермінал - S.

Цією граматикою задається мову вкладених дужок {(n) n | n ≥ 0}.

3.3. Мова Діка

3.4. Арифметичне вираз

  • Термінали: '+', '-', '*', '/', '(', ')', 'x'
  • нетерміналу: <вираз>, <доданок>, <множник>
  • продукції: 
 <Вираз> → <вираз> + <доданок>, <вираз> → <вираз> - <доданок>, <вираз> → <доданок>, <доданок> → <доданок> * <множник>, <доданок> → <доданок > / <множник>, <доданок> → <множник>, <множник> → (<вираз>), <множник> → x,
  • початковий нетермінал: <вираз>.

Цією граматикою задається арифметичне вираз, що містить найпростіші арифметичні дії над змінної x. Якщо замінити термінал 'x' на нетермінал <число>, то вийде граматика, задаюча арифметичний вираз, що складається з операцій додавання, віднімання, множення і ділення над цілими числами.


4. Обмеження можливостей КС граматик

Не всі мови можуть бути задані КС-граматикою. Так, мову {a n b n c n | n ≥ 1} не є контекстно-вільним.

Література

  • Джон Хопкрофт, Раджив Мотвані, Джеффрі Ульман Введення в теорію автоматів, мов і обчислень = Introduction to Automata Theory, Languages, and Computation. - М .: "Вильямс", 2002. - С. 528. - ISBN 0-201-44124-1