Контекстно-свободная грамматика

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала.

Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.

Следует заметить, что по сути КС-грамматика — другая форма БНФ.

Применение

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

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

Типы КС грамматик

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

Примеры

Примеры КС-грамматик и соответствующих им КС-языков:

Слово с переворотом

Задаётся формулой $L=\{w \in \Sigma* | w = w^R\}$

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

Вложенные скобки

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

Этой грамматикой задаётся язык вложенных скобок { (ⁿ)ⁿ | n≥0 }.

Арифметическое выражение

• Терминалы: '+', '-', '*', '/', '(', ')', 'x'
• нетерминалы: <выражение>, <слагаемое>, <множитель>
• продукции:

<выражение> → <выражение> + <слагаемое>,
<выражение> → <выражение> - <слагаемое>,
<выражение> → <слагаемое>,
<слагаемое> → <слагаемое> * <множитель>,
<слагаемое> → <слагаемое> / <множитель>,
<слагаемое> → <множитель>,
<множитель> → ( <выражение> ),
<множитель> → x,

• начальный нетерминал: <выражение>.

Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действия над переменной x. Если заменить терминал 'x' на нетерминал <число>, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножения и деления над целыми числами.

Ограничения возможностей КС грамматик

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

См. также

• Контекстно-зависимая грамматика
• Матричная грамматика

Литература

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