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

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — это формальная грамматика, в которой правила вывода имеют вид \( A \to \gamma \), где \( A \) — нетерминальный символ, а \( \gamma \) — строка, состоящая из терминальных и нетерминальных символов (возможно, пустая). КС-грамматики являются одним из основных классов формальных грамматик в иерархии Хомского и порождают контекстно-свободные языки. Они широко используются в теории языков программирования, компиляторах, обработке естественного языка и биоинформатике.

¶Определение и формальное описание

Формально контекстно-свободная грамматика задаётся четвёркой \( G = (N, \Sigma, P, S) \), где:

• \( N \) — конечное множество нетерминальных символов (переменных);
• \( \Sigma \) — конечное множество терминальных символов (алфавит), причём \( N \cap \Sigma = \varnothing \);
• \( P \) — конечное множество правил вывода (продукций) вида \( A \to \alpha \), где \( A \in N \), \( \alpha \in (N \cup \Sigma)^* \);
• \( S \in N \) — начальный нетерминал (аксиома).

Вывод (деривация) строки из терминалов начинается с \( S \) и последовательно заменяет нетерминалы согласно правилам. Язык, порождаемый грамматикой \( G \), обозначается \( L(G) \) и состоит из всех строк \( w \in \Sigma^* \), которые можно вывести из \( S \).

¶Пример

Рассмотрим грамматику \( G = (\{S\}, \{a, b\}, P, S) \) с правилами:

• \( S \to aSb \)
• \( S \to \varepsilon \) (пустая строка)

Эта грамматика порождает язык \( \{ a^n b^n \mid n \ge 0 \} \), состоящий из строк вида «ab», «aabb», «aaabbb» и т.д. Вывод строки «aabb»: \( S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb \).

¶Свойства контекстно-свободных грамматик

¶Иерархия Хомского

КС-грамматики занимают второй уровень в иерархии Хомского (тип 2). Они менее мощны, чем контекстно-зависимые грамматики (тип 1), но мощнее, чем регулярные грамматики (тип 3). Регулярные языки являются подмножеством контекстно-свободных, однако существуют языки, не являющиеся контекстно-свободными (например, \( \{ a^n b^n c^n \mid n \ge 0 \} \)).

¶Замкнутость и неразрешимость

Класс контекстно-свободных языков замкнут относительно следующих операций:

• объединение;
• конкатенация;
• итерация (звезда Клини);
• пересечение с регулярным языком;
• гомоморфизм.

Однако он не замкнут относительно пересечения и дополнения. Например, пересечение двух КС-языков \( \{ a^n b^n c^m \mid n, m \ge 0 \} \) и \( \{ a^m b^n c^n \mid n, m \ge 0 \} \) даёт язык \( \{ a^n b^n c^n \mid n \ge 0 \} \), который не является контекстно-свободным.

Для КС-грамматик неразрешимы следующие проблемы:

• эквивалентность двух грамматик;
• однозначность грамматики;
• пустота пересечения двух языков;
• принадлежность строки языку, порождённому произвольной грамматикой (хотя для конкретных грамматик это разрешимо).

¶Деревья вывода и однозначность

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

• \( E \to E + E \mid E * E \mid (E) \mid id \)

является неоднозначной, так как строка «id + id * id» может быть выведена двумя способами, соответствующими разным приоритетам операций. Для устранения неоднозначности вводят дополнительные нетерминалы или правила.

¶Классификация и виды

¶По форме правил

• Нормальная форма Хомского (Chomsky Normal Form, CNF): все правила имеют вид \( A \to BC \) или \( A \to a \), где \( A, B, C \in N \), \( a \in \Sigma \). Исключение составляет правило \( S \to \varepsilon \), если пустая строка принадлежит языку. Любая КС-грамматика может быть преобразована в CNF.
• Нормальная форма Грейбах (Greibach Normal Form, GNF): все правила имеют вид \( A \to a\alpha \), где \( a \in \Sigma \), \( \alpha \in N^* \). В GNF каждый шаг вывода добавляет один терминал, что удобно для синтаксического анализа.

¶По типу порождаемого языка

• Детерминированные контекстно-свободные языки: порождаются грамматиками, которые могут быть распознаны детерминированным автоматом с магазинной памятью (ДМП-автоматом). Например, язык \( \{ a^n b^n \mid n \ge 0 \} \) является детерминированным.
• Недетерминированные: требуют недетерминированного МП-автомата. Например, язык палиндромов \( \{ ww^R \mid w \in \{a, b\}^* \} \).

¶По приложениям

• LL(k)-грамматики: допускают нисходящий синтаксический анализ с просмотром \( k \) символов вперёд. Используются в компиляторах (например, ANTLR).
• LR(k)-грамматики: допускают восходящий анализ. Являются более мощными, чем LL(k). Используются в генераторах парсеров (Yacc, Bison).
• LALR(1): подмножество LR(1), наиболее распространённое на практике.

¶Применение

¶Языки программирования

Синтаксис большинства языков программирования (C, Java, Python, JavaScript) описывается с помощью КС-грамматик. Например, грамматика языка C (ANSI C) содержит около 200 правил. Компиляторы используют синтаксические анализаторы, построенные на основе КС-грамматик, для проверки корректности программы и построения абстрактного синтаксического дерева (AST).

¶Обработка естественного языка

В лингвистике КС-грамматики применяются для моделирования синтаксической структуры предложений. Например, грамматика фразовых структур (Phrase Structure Grammar) описывает предложения через составляющие: \( S \to NP \, VP \), \( NP \to Det \, N \), \( VP \to V \, NP \). Однако для полного описания естественных языков требуются более мощные формализмы (например, трансформационные грамматики).

¶Биоинформатика

КС-грамматики используются для моделирования вторичной структуры РНК. Например, грамматика:

• \( S \to aSu \mid uSa \mid cSg \mid gSc \mid \varepsilon \)

описывает шпильки и петли, характерные для РНК. Также применяются стохастические КС-грамматики для предсказания структуры.

¶Теория формальных языков

КС-грамматики служат основой для изучения свойств языков, разрешимости и сложности. Они связаны с автоматами с магазинной памятью (МП-автоматами), которые являются распознавателями для КС-языков.

¶Алгоритмы синтаксического анализа

¶Нисходящий анализ (Top-Down)

• Рекурсивный спуск: рекурсивная реализация правил грамматики. Требует отсутствия левой рекурсии.
• LL-анализ: использует таблицу предсказаний. Работает для LL(k)-грамматик.
• Алгоритм Кока-Янгера-Касами (CYK): работает для грамматик в нормальной форме Хомского. Сложность \( O(n^3) \), где \( n \) — длина строки.

¶Восходящий анализ (Bottom-Up)

• LR-анализ: использует автомат с состояниями и таблицу действий. Для LR(1) сложность \( O(n) \).
• Алгоритм Эрли: работает для произвольных КС-грамматик, сложность \( O(n^3) \) в худшем случае, но для детерминированных грамматик — \( O(n) \).

¶Интересные факты

• Понятие контекстно-свободной грамматики ввёл Ноам Хомский в 1956 году в рамках иерархии формальных грамматик.
• Язык \( \{ a^n b^n c^n \mid n \ge 0 \} \) является классическим примером неконтекстно-свободного языка. Его можно доказать с помощью леммы о накачке (pumping lemma) для КС-языков.
• В 1960-х годах Джон Бэкус и Питер Наур разработали форму Бэкуса-Наура (BNF) для описания синтаксиса Алгола-60, которая является нотацией для КС-грамматик.
• Существуют грамматики, порождающие все строки над алфавитом (например, \( S \to aS \mid bS \mid \varepsilon \)), но они не являются контекстно-свободными, так как требуют контекстной зависимости.

¶Критика и ограничения

• КС-грамматики не могут описывать все синтаксические конструкции естественных языков (например, согласование по роду и числу, перекрёстные зависимости).
• Для языков программирования КС-грамматики часто дополняются контекстными условиями (например, проверка типов, объявление переменных до использования), которые не могут быть выражены в рамках КС-формализма.
• Неоднозначность грамматик может приводить к проблемам при синтаксическом анализе, требуя дополнительных правил разрешения конфликтов.

¶Источники

• Хомский Н. «Синтаксические структуры» (1957).
• Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений» (3-е издание, 2006).
• Ахо А., Лам М., Сети Р., Ульман Дж. «Компиляторы: принципы, технологии и инструменты» (2-е издание, 2008).
• Гинзбург С. «Математическая теория контекстно-свободных языков» (1966).
• Лемма о накачке для контекстно-свободных языков (Бар-Гилель, 1961).