Порождающие грамматики¶

Порождающие грамматики — это формальные системы, задающие множество допустимых цепочек (предложений) языка путем применения конечного набора правил подстановки к начальному символу. В лингвистике и теоретической информатике порождающая грамматика определяется как четверка \( G = (V, T, P, S) \), где \( V \) — конечный набор нетерминальных символов, \( T \) — терминальный алфавит, \( P \) — конечный набор правил вида \( \alpha \to \beta \), а \( S \) — стартовый нетерминал. Язык, порождаемый грамматикой, представляет собой множество всех терминальных цепочек, выводимых из \( S \) последовательным применением правил.

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

Классификация порождающих грамматик была предложена Ноамом Хомским в 1956 году и включает четыре типа, различающихся ограничениями на вид правил:

• Тип 0 (грамматики без ограничений) — правила имеют произвольный вид \( \alpha \to \beta \), где \( \alpha, \beta \) — любые цепочки. Они порождают все рекурсивно перечислимые языки и эквивалентны машинам Тьюринга.
• Тип 1 (контекстно-зависимые) — правила вида \( \alpha A \beta \to \alpha \gamma \beta \), где \( A \) — нетерминал, а \( \gamma \) — непустая цепочка. Такие грамматики порождают контекстно-зависимые языки, распознаваемые линейно ограниченными автоматами.
• Тип 2 (контекстно-свободные) — правила вида \( A \to \gamma \), где \( A \) — одиночный нетерминал. Это наиболее изученный класс, используемый для описания синтаксиса языков программирования; распознаются магазинными автоматами.
• Тип 3 (регулярные) — правила вида \( A \to aB \) или \( A \to a \). Порождают регулярные языки, соответствующие конечным автоматам и регулярным выражениям.

Каждый следующий тип является подмножеством предыдущего, что образует строгую иерархию: регулярные \( \subset \) контекстно-свободные \( \subset \) контекстно-зависимые \( \subset \) рекурсивно перечислимые.

¶Основные понятия и свойства

Вывод — последовательность цепочек, начинающаяся со стартового символа, где каждая следующая цепочка получается заменой подцепочки по одному из правил. Дерево вывода (синтаксическое дерево) — графическое представление вывода, где корень — стартовый символ, листья — терминальные символы, а внутренние узлы — нетерминалы. Неоднозначность возникает, когда для одной цепочки существует несколько различных деревьев вывода; такие грамматики называются неоднозначными.

Ключевой проблемой для контекстно-свободных грамматик является проблема разбора — определение, принадлежит ли данная цепочка языку, и построение дерева вывода. Для этого разработаны алгоритмы: метод рекурсивного спуска, алгоритмы Эрли и Кока — Янгера — Касами (CYK), а также LR- и LL-анализ, применяемые в компиляторах.

¶Применение в лингвистике

В генеративной лингвистике порождающие грамматики используются для моделирования естественного языка. Хомский ввел различие между поверхностной и глубинной структурой предложения, что легло в основу трансформационной грамматики. Позднее развились управление и связывание (Government and Binding theory) и минималистская программа, где порождающий аппарат дополнен операциями слияния и перемещения. Контекстно-свободные грамматики применяются для описания синтаксиса большинства естественных языков, хотя некоторые конструкции (например, перекрестные зависимости в швейцарском немецком) требуют более мощных формализмов.

¶Применение в информатике

В программировании порождающие грамматики лежат в основе формального описания синтаксиса языков программирования. Форма Бэкуса — Наура (БНФ) и расширенная БНФ (EBNF) являются нотациями для записи контекстно-свободных грамматик, используемых в спецификациях языков (например, в стандартах C, Java, Python). На основе грамматик строятся генераторы парсеров: Yacc, Bison, ANTLR, которые автоматически создают синтаксические анализаторы.

Атрибутные грамматики расширяют контекстно-свободные грамматики семантическими правилами, позволяя вычислять значения (атрибуты) узлов дерева вывода. Они применяются для статического анализа, генерации кода и проверки типов в компиляторах.

¶Ограничения и расширения

Контекстно-свободные грамматики не могут описать все явления естественного языка, такие как согласование по числу и роду в длинных конструкциях или перекрестные зависимости. Для этого разработаны грамматики составляющих с зависимостями (Tree-Adjoining Grammar, TAG) и категориальные грамматики, обладающие большей выразительной силой при сохранении полиномиальной сложности разбора. В теории формальных языков также изучаются грамматики с контекстными условиями (например, грамматики Ван Вийнгаардена) и грамматики с программируемыми правилами.

¶Значение

Порождающие грамматики образуют фундамент теории формальных языков, связывая лингвистику, математическую логику и информатику. Они предоставляют строгий аппарат для описания синтаксиса, используются при проектировании компиляторов, обработке естественного языка, биоинформатике (описание структуры РНК) и в системах проверки корректности входных данных. Иерархия Хомского остается центральной классификацией, определяющей вычислительную сложность распознавания языков и границы применимости различных алгоритмов.

¶Источники

• Хомский Н. Три модели описания языка // Кибернетический сборник. — 1961. — Вып. 2.
• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978.
• Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.
• Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2008.