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

Лекция

Привет, Вы узнаете о том , что такое контекстно-свободная грамматика, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое контекстно-свободная грамматика, кс-грамматика, бесконтекстная грамматика , настоятельно рекомендую прочитать все из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности.

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

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

По сути КС-грамматика — другая форма БНФ.

Применение

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

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

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

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

Распознаватели

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

Нисходящие распознаватели

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

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

Восходящие распознаватели

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

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

Примеры

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

Слово с переворотом Палиндром

Задается формулой Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика)

Терминалы: буквы алфавита ;
Нетерминал: ;
Продукции:
Начальный нетерминал — .

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

Терминалы: и ;
нетерминал: ;
продукции: ;
начальный нетерминал — .

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

Язык Дика

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

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

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

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

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

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

Не все языки могут быть заданы с помощью КС-грамматик. Проще всего это можно доказать так: КС-грамматики образуют счетное множество, в то время как мощность множества всех языков − континуум. Конструктивное доказательство этого же факта может быть получено, например, на основе того, что язык {aⁿbⁿcⁿ | n≥1} не является контекстно-свободным; однако короткого доказательства последнего утверждения, по-видимому, не существует: опубликованные доказательства опираются на теорему о разрастании для контекстно-свободных языков.

Обобщения

Грамматика сложения деревьев обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы.

Вау!! 😲 Ты еще не читал? Это зря!

Данная статья про контекстно-свободная грамматика подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое контекстно-свободная грамматика, кс-грамматика, бесконтекстная грамматика и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности

Из статьи мы узнали кратко, но содержательно про контекстно-свободная грамматика