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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Применение[править | править вики-текст]

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

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

Типы КС грамматик[править | править вики-текст]

Распознаватели[править | править вики-текст]

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

Нисходящие распознаватели[править | править вики-текст]

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

Они используют модификации алгоритма с подбором альтернатив. При их создании применяется метод, который позволяет однозначно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно).

Восходящие распознаватели[править | править вики-текст]

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

Восходящие распознаватели используют модификации алгоритма «сдвиг-свертка» (или «перенос-свертка», что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением «сдвига» («переноса») или «свертки» на каждом шаге работы расширенного МП-автомата, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка. Алгоритм «сдвиг-свертка».

Примеры[править | править вики-текст]

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

Слово с переворотом[править | править вики-текст]

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

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

Вложенные скобки[править | править вики-текст]

  • Терминалы: ( и );
  • нетерминал: S;
  • продукции: S \rightarrow (S) \mid \varepsilon;
  • начальный нетерминал — S.

Этой грамматикой задаётся язык вложенных скобок \{ \left(^n \right)^n \mid n \geq 0\}.

Язык Дика[править | править вики-текст]

Арифметическое выражение[править | править вики-текст]

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

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

Ограничения возможностей КС грамматик[править | править вики-текст]

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

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