Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала.
Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.
Следует заметить, что по сути КС-грамматика — другая форма БНФ.
Содержание
- 1 Применение
- 2 Типы КС грамматик
- 3 Примеры
- 4 Ограничения возможностей КС грамматик
- 5 См. также
- 6 Литература
Применение
КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т. д. (см. грамматический анализ)
Для разбора КС-грамматики достаточно автомата со стеком, для разбора не-КС-грамматик может потребоваться полная машина Тьюринга.
Типы КС грамматик
- LL-грамматика
- LALR-грамматика (см.: LALR(1))
- LR-грамматика
- SLR-грамматика (см.: SLR(1))
Примеры
Примеры КС-грамматик и соответствующих им КС-языков:
Слово с переворотом
Основная статья: Палиндром
Задаётся формулой L={w∈Σ∗|w=wR}{displaystyle L={win Sigma *|w=w^{R}}}
- Терминалы: буквы алфавита Σ;
- Нетерминал: S;
- Продукции: S→αSα,α∈Σ;S→ε;S→α,α∈Σ{displaystyle Srightarrow alpha Salpha ,alpha in Sigma ;Srightarrow varepsilon ;Srightarrow alpha ,alpha in Sigma }
- Начальный нетерминал — S.
Вложенные скобки
- Терминалы: ‘(‘ и ‘)’;
- нетерминал: S;
- продукции: S→(S), S→ε;
- начальный нетерминал — S.
Этой грамматикой задаётся язык вложенных скобок { (n)n | n≥0 }.
Язык Дика
Основная статья: Язык Дика
Арифметическое выражение
- Терминалы: ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, ‘)’, ‘x’
- нетерминалы: <выражение>, <слагаемое>, <множитель>
- продукции:
<выражение> → <выражение> + <слагаемое>,<выражение> → <выражение> — <слагаемое>,<выражение> → <слагаемое>,<слагаемое> → <слагаемое> * <множитель>,<слагаемое> → <слагаемое> / <множитель>,<слагаемое> → <множитель>,<множитель> → ( <выражение> ),<множитель> → x,
- начальный нетерминал: <выражение>.
Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действия над переменной x. Если заменить терминал ‘x’ на нетерминал <число>, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножения и деления над целыми числами.
Ограничения возможностей КС грамматик
Не все языки могут быть заданы КС-грамматикой. Так, язык { anbncn | n≥1 } не является контекстно-свободным.
См. также
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
