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


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

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

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

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

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

Нисходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз.