EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 9 минут
#контекстно-свободная грамматика#формальные языки#дерево разбора#правила вывода#синтаксический анализ
Контекстно-свободная грамматика: правила и примеры

Контекстно-свободная грамматика - это набор правил, который строит строки из начального символа, последовательно заменяя отдельные нетерминалы. Она позволяет описать вложенные конструкции: например, поставить столько же букв bb после группы букв aa, сколько букв было в первой группе. Меняя число пар в инструменте, проследите, как рекурсивное правило создаёт слово, а завершающее правило убирает последний нетерминал.

Из чего состоит грамматика

Формально грамматику записывают как G=(N,Σ,P,S)G=(N,\Sigma,P,S). В этой четвёрке:

  • NN - конечное множество нетерминалов, промежуточных обозначений синтаксических категорий;
  • Σ\Sigma - конечный алфавит терминалов, из которых состоят готовые слова; множества NN и Σ\Sigma не пересекаются;
  • PP - конечное множество правил, или продукций;
  • S∈NS\in N - начальный символ, с которого начинают вывод.

Каждое правило имеет вид A→αA\to\alpha: слева стоит ровно один нетерминал AA, справа - любая конечная последовательность терминалов и нетерминалов, в том числе пустая. Пустую строку обозначают ε\varepsilon. Символ ε\varepsilon не добавляет букву в результат: он означает отсутствие символов.

Грамматика задаёт язык L(G)L(G) - множество всех конечных строк из терминалов, которые можно вывести из SS. Промежуточная строка ещё может содержать нетерминалы; пока они остались, это не готовое слово языка. Например, aaSbbaaSbb - промежуточная форма, а aabbaabb - конечная строка нашего примера.

Почему грамматику называют контекстно-свободной

Правило A→αA\to\alpha можно применить к любому вхождению AA независимо от того, какие символы стоят по соседству. Если промежуточная строка имеет вид xAyxAy, замена даёт xαyx\alpha y: части xx и yy остаются на месте и не влияют на допустимость правила. Именно в этом технический смысл слова «контекстно-свободная».

Это не утверждение, что значения слов в естественном языке независимы от ситуации. Здесь «контекст» - окружение нетерминала в формальной строке. Например, у замыканий JavaScript слово «контекст» связано с лексической областью видимости и обозначает другую идею. В грамматике же важно, что выбор правила для AA не проверяет его соседей.

Вывод языка с одинаковым числом букв

Возьмём N={S}N=\{S\}, Σ={a,b}\Sigma=\{a,b\} и два правила:

S→aSb∣ε.S\to aSb\mid\varepsilon.

Вертикальная черта разделяет альтернативы: вместо SS разрешено подставить либо aSbaSb, либо пустую строку. Первое правило добавляет одну aa слева и одну bb справа, сохраняя SS посередине. Второе завершает вывод. Так для трёх пар получаем:

S⇒aSb⇒aaSbb⇒aaaSbbb⇒aaabbb.S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aaaSbbb\Rightarrow aaabbb.

Каждое применение правила добавляет a слева и b справа, а замена S на пустую строку завершает вывод; затем последовательность возвращается к началу.

Если первое правило применено nn раз, перед завершением имеем anSbna^nSb^n, а после него - anbna^nb^n. При n=0n=0 сразу получается ε\varepsilon. Грамматика задаёт в точности язык {anbn∣n≥0}\{a^nb^n\mid n\geq 0\}: все aa предшествуют всем bb, и их количества равны. Строка abababab сюда не входит, хотя обеих букв в ней поровну: порядок тоже является условием.

Обоснование работает в обе стороны. Каждое рекурсивное применение добавляет ровно одну пару и сохраняет порядок; других способов добавить буквы нет. Наоборот, для любого неотрицательного nn достаточно nn раз выбрать первое правило и один раз второе. Поэтому ни лишних строк, ни пропущенных значений nn не возникает.

Ещё один способ увидеть устройство правила - сравнить соседние значения. Для двух пар вывод заканчивается словом aabbaabb, а для трёх - словом aaabbbaaabbb. Новая буква aa возникает перед центральным нетерминалом, новая bb - после него. Поэтому при добавлении очередной пары прежние буквы не перемешиваются. Это удобно проверять на графике: каждый шаг увеличивает суммарное число терминалов ровно на два, а завершающая замена на пустую строку его не меняет.

Завершение обязательно: бесконечная последовательность применений первого правила не является готовым словом. Даже если процесс можно продолжать сколь угодно долго, определение языка включает только результаты конечных выводов, в которых нет нетерминалов. С другой стороны, выбор завершения на первом шаге допустим и даёт слово длины ноль.

Дерево разбора и порядок замен

Вывод можно изобразить деревом: корень - SS, а дети каждого нетерминала соответствуют правой части выбранного для него правила. У узла SS, раскрытого по правилу S→aSbS\to aSb, три потомка: aa, SS и bb. Последний SS раскрывается в ε\varepsilon. Читая терминальные листья слева направо и пропуская пустую строку, получаем aaabbbaaabbb.

Дерево вывода aaabbb: три вложенных применения S → aSb и завершение правилом S → ε
Дерево вывода aaabbb: три вложенных применения S → aSb и завершение правилом S → ε

В этом дереве три рекурсивных узла добавляют по паре букв: итог содержит три aa, три bb и шесть терминалов. Корень, внутренние узлы и листья - общие понятия теории деревьев; отдельно разобраны высота и глубина дерева. В учебных рисунках ε\varepsilon часто показывают отдельным листом, хотя в самом слове символа для него нет.

Когда в промежуточной форме несколько нетерминалов, их можно раскрывать в разном порядке. Левосторонний вывод всегда выбирает самый левый, правосторонний - самый правый. Разный порядок замен сам по себе ещё не означает разные деревья: структуру определяют применённые правила и их связи, а не хронология независимых шагов.

Неоднозначность: одно слово, два дерева

Рассмотрим другую грамматику: E→E+E∣E∗E∣aE\to E+E\mid E*E\mid a. Для строки a+a∗aa+a*a возможны два дерева. В одном корневое правило - сложение: получается структура a+(a∗a)a+(a*a). В другом корневое правило - умножение: структура (a+a)∗a(a+a)*a. Исходная последовательность символов одинакова, но группировка различается.

Грамматику называют неоднозначной, если хотя бы одна строка её языка имеет два разных дерева разбора. Это свойство грамматики, а не просто утверждение о строке вне правил. Иногда ту же совокупность строк можно описать другой, однозначной грамматикой. Для арифметики обычно вводят отдельные уровни выражений и множителей, чтобы умножение связывалось сильнее сложения; ассоциативность также надо задать явно.

Проверка неоднозначности на примере требует именно двух разных деревьев для одной строки. Два вывода с разным порядком раскрытия независимых нетерминалов могут давать одно дерево и тогда ничего не доказывают. Этот критерий соответствует определению разбора в конспекте Корнеллского университета.

Зачем грамматика нужна анализатору

При обработке программы текст обычно сначала разбивают на токены: идентификаторы, числа, знаки операций. Затем синтаксический анализатор проверяет их последовательность по грамматике и строит структуру. Дерево помогает понять, какие части выражения относятся друг к другу; следующие этапы могут проверять типы и имена или выполнять преобразования.

КС-грамматика хорошо описывает рекурсивную вложенность, но одной грамматики часто недостаточно для всех правил языка программирования. Например, согласованность объявления и использования имени обычно проверяют дополнительными средствами. В естественном языке задача ещё сложнее: структура предложения может зависеть от лексики и смысла. Трансформационная грамматика рассматривает более широкую лингвистическую теорию, а универсальная грамматика - гипотезу о языковой способности; их не следует отождествлять с формальным определением КС-грамматики.

Регулярные языки тоже можно задавать грамматиками, но они образуют более узкий класс. Язык anbna^nb^n контекстно-свободен и не регулярен: конечному автомату с фиксированным числом состояний недостаточно памяти, чтобы для произвольно большого nn запомнить точное число букв aa. Связь регулярных выражений и конечных автоматов раскрывает теорема Клини. При этом не всякий формальный язык контекстно-свободен: у класса есть собственные ограничения.

Разбор идёт от готовой последовательности к возможной структуре, а вывод удобно читать в обратном направлении: от начального символа к строке. Это две постановки вокруг одних и тех же правил. Не следует считать, что любой выбранный алгоритм синтаксического анализа одинаково подходит для всех грамматик: при проектировании анализатора важно учитывать форму правил и возможную неоднозначность. Для учебной проверки принадлежности достаточно предъявить корректный конечный вывод; для отказа нужно обосновать, что ни один допустимый вывод данной строки не существует.

Как проверить грамматику в задаче

Сначала выпишите алфавит и условие для строк, включая пустую строку и граничные случаи. Затем найдите повторяющуюся структуру и базу рекурсии. В примере это добавление пары по краям и завершение через ε\varepsilon. После записи правил выведите несколько разрешённых строк и попытайтесь получить запрещённые: такая проверка помогает заметить ошибки, но конечного набора примеров недостаточно для доказательства.

Для полного обоснования покажите два включения: любой завершённый вывод удовлетворяет условию, и любую строку, удовлетворяющую условию, можно вывести. В первом направлении удобно доказать инвариант каждого шага; во втором - предложить конкретную последовательность правил для произвольной строки. Отдельно проверьте, не осталось ли нетерминалов и не изменился ли нужный порядок символов.

Частые ошибки

  • Считать ε\varepsilon обычным символом. Он обозначает пустую строку и не входит в длину слова.
  • Принимать промежуточную форму за слово языка. Строка с SS ещё не состоит только из терминалов.
  • Проверять только равенство количеств. Для anbna^nb^n все буквы aa должны идти раньше всех bb.
  • Путать два вывода с двумя деревьями. Разный порядок независимых замен может сохранить одну структуру.
  • Делать вывод по нескольким примерам. Для совпадения языка грамматики с заданным множеством нужны оба включения.

FAQ

Может ли КС-грамматика породить пустую строку?

Да. В примере правило S→εS\to\varepsilon позволяет получить её сразу. Но наличие пустого слова зависит от конкретных правил и не обязательно для каждой грамматики.

Любая ли КС-грамматика рекурсивна?

Нет. Правила могут вообще не возвращаться к уже встреченному нетерминалу. Рекурсия полезна для компактного описания неограниченной вложенности, но не входит в определение.

Всегда ли у строки есть единственное дерево?

Нет. У строки, не принадлежащей языку грамматики, нет дерева разбора; у принадлежащей может быть одно или несколько. Последний случай свидетельствует о неоднозначности данной грамматики.

Коротко

Контекстно-свободная грамматика заменяет один нетерминал за шаг независимо от его окружения. Правила S→aSb∣εS\to aSb\mid\varepsilon порождают ровно anbna^nb^n, а дерево разбора показывает вложенную структуру вывода. Чтобы обосновать решение задачи, проверяйте и отсутствие лишних слов, и возможность вывести каждое требуемое слово.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Магазинный автомат: стек, переходы и примеры

Магазинный автомат: стек, переходы и примеры

Магазинный автомат простыми словами: как состояние и стек управляют переходами, как разобрать скобки и язык aⁿbⁿ, чем различаются условия принятия и связь с грамматиками.

8 ноября 20268 минут
Регулярная грамматика: правила, примеры и автомат

Регулярная грамматика: правила, примеры и автомат

Регулярная грамматика простыми словами: как устроены праволинейные правила, как вывести слово, построить конечный автомат и проверить границы модели на примерах.

8 ноября 20269 минут
Иерархия Хомского: типы грамматик и автоматы

Иерархия Хомского: типы грамматик и автоматы

Иерархия Хомского простыми словами: четыре типа формальных грамматик, вложенность классов языков, соответствующие автоматы и примеры для решения учебных задач.

8 ноября 20269 минут
Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов описывает свойства объектов и отношения между ними. Разбираем устройство формул, пошаговый пример доказательства и поиск контрмодели.

8 ноября 20268 минут
Система натурального вывода: правила и примеры

Система натурального вывода: правила и примеры

Система натурального вывода по шагам: правила введения и устранения связок, временные допущения, построение доказательства и типичные ошибки в логике.

8 ноября 20269 минут
Машина Тьюринга недетерминированная: модель и сила

Машина Тьюринга недетерминированная: модель и сила

Машина Тьюринга недетерминированная (НМТ): чем отличается от детерминированной, как работает дерево вычислений, почему она не сильнее по разрешимости и при чём тут класс NP.

5 мая 20267 минут