Русская Википедия:Контекстно-свободная грамматика
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала (в отличие от общего случая неограниченной грамматики Хомского).
Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.
По сути КС-грамматика — другая форма БНФ.
Применение
КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т. д. (см. грамматический анализ)
Для разбора КС-грамматики достаточно автомата с магазинной памятью, для разбора не-КС-грамматик может потребоваться полная машина Тьюринга.
Типы КС грамматик
- LL-грамматика
- LALR-грамматика (см.: LALR(1))
- LR-грамматика
- SLR-грамматика (см.: SLR(1))
Распознаватели
Существуют два разных класса распознавателей (автоматов для распознавания) КС-языков. Их названия связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку символов слева направо, поскольку предполагается такая нотация в написании исходного текста программ.
Нисходящие распознаватели
Нисходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз.
Они используют модификации алгоритма с подбором альтернатив. При их создании применяется метод, который позволяет однозначно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно).
Восходящие распознаватели
Восходящие распознаватели, которые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх.
Восходящие распознаватели используют модификации алгоритма «сдвиг-свертка» (или «перенос-свертка», что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением «сдвига» («переноса») или «свертки» на каждом шаге работы расширенного МП-автомата, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка. Алгоритм «сдвиг-свертка».
Примеры
Примеры КС-грамматик и соответствующих им КС-языков:
Слово с переворотом
Шаблон:Main Задаётся формулой <math>L=\{w \in \Sigma^* | w = w^R\}</math>
- Терминалы: буквы алфавита <math>\Sigma</math>;
- Нетерминал: <math>S</math>;
- Продукции: <math>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</math>
- Начальный нетерминал — <math>S</math>.
Вложенные скобки
- Терминалы: <math>(</math> и <math>)</math>;
- нетерминал: <math>S</math>;
- продукции: <math>S \rightarrow (S) \mid \varepsilon</math>;
- начальный нетерминал — <math>S</math>.
Этой грамматикой задаётся язык вложенных скобок <math>\{ \left(^n \right)^n \mid n \geq 0\}</math>.
Язык Дика
Арифметическое выражение
- Терминалы: '+', '-', '*', '/', '(', ')', 'x'
- нетерминалы: <выражение>, <слагаемое>, <множитель>
- продукции:
<выражение> → <выражение> + <слагаемое>, <выражение> → <выражение> - <слагаемое>, <выражение> → <слагаемое>, <слагаемое> → <слагаемое> * <множитель>, <слагаемое> → <слагаемое> / <множитель>, <слагаемое> → <множитель>, <множитель> → ( <выражение> ), <множитель> → x,
- начальный нетерминал: <выражение>.
Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действия над переменной x. Если заменить терминал 'x' на нетерминал <число>, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножения и деления над целыми числами.
Ограничения возможностей КС-грамматик
Не все языки могут быть заданы с помощью КС-грамматик. Проще всего это можно доказать так: КС-грамматики образуют счётное множество, в то время как мощность множества всех языков — континуум. Конструктивное доказательство этого же факта может быть получено, например, на основе того, что язык {anbncn | n≥1} не является контекстно-свободным; однако короткого доказательства последнего утверждения, по-видимому, не существует: опубликованные доказательства опираются на теорему о разрастании для контекстно-свободных языков.
Обобщения
Грамматика сложения деревьев обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы.
См. также
Литература