Формальная грамматика

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

История

Идея формализации грамматики восходит к работам древнеиндийского лингвиста Панини (около V века до н. э.), который создал систематическое описание санскрита с помощью правил, напоминающих современные формальные грамматики. Однако в современном виде формальная грамматика была разработана в середине XX века.

Вклад Ноама Хомского

Ключевую роль в становлении теории сыграл американский лингвист Ноам Хомский. В 1956 году он опубликовал работу «Три модели описания языка», а в 1959 году — «О некоторых формальных свойствах грамматик». Хомский предложил иерархию формальных грамматик (известную как иерархия Хомского), которая классифицирует грамматики по их выразительной силе. Эта иерархия стала основой для дальнейших исследований в области синтаксиса естественных языков, теории автоматов и компиляции.

Развитие в информатике

В 1960-х годах формальные грамматики начали активно применяться в информатике. В 1959 году Джон Бэкус и Питер Наур разработали форму Бэкуса — Наура (БНФ) — нотацию для описания синтаксиса языков программирования, основанную на контекстно-свободных грамматиках. Эта нотация была использована для описания Алгола-60. Позднее были разработаны расширенные версии БНФ (РБНФ), а также другие формализмы, такие как грамматики с атрибутами и грамматики зависимостей.

Определение и основные понятия

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

• \( N \) — конечное множество нетерминальных символов (нетерминалов). Это вспомогательные символы, обозначающие синтаксические категории (например, «предложение», «существительное», «выражение»).
• \( \Sigma \) — конечное множество терминальных символов (терминалов). Это основные символы, из которых состоят цепочки языка (например, буквы, цифры, операторы). Множества \( N \) и \( \Sigma \) не пересекаются.
• \( P \) — конечное множество правил вывода (продукций). Каждое правило имеет вид \( \alpha \rightarrow \beta \), где \( \alpha \) и \( \beta \) — цепочки, состоящие из символов \( N \cup \Sigma \), причём \( \alpha \) содержит хотя бы один нетерминал.
• \( S \) — начальный символ (аксиома), \( S \in N \). С него начинается вывод.

Процесс вывода

Вывод цепочки в грамматике — это последовательность замен подстрок, соответствующих левой части правила, на правую часть. Процесс начинается с начального символа \( S \) и заканчивается, когда цепочка состоит только из терминалов. Множество всех терминальных цепочек, которые можно вывести из \( S \), называется языком, порождаемым грамматикой \( G \), и обозначается \( L(G) \).

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

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

Тип 0: Грамматики без ограничений

• Правила: Любые правила вида \( \alpha \rightarrow \beta \), где \( \alpha \) и \( \beta \) — произвольные цепочки, \( \alpha \) не пуста.
• Языки: Рекурсивно перечислимые языки. Распознаются машинами Тьюринга.
• Применение: Теоретическая основа для изучения вычислимости. На практике используются редко из-за неразрешимости многих проблем (например, проблемы принадлежности).

Тип 1: Контекстно-зависимые грамматики (КЗ-грамматики)

• Правила: Имеют вид \( \alpha A \beta \rightarrow \alpha \gamma \beta \), где \( A \in N \), \( \alpha, \beta, \gamma \) — цепочки, \( \gamma \) не пуста. Это означает, что нетерминал \( A \) может быть заменён на \( \gamma \) только в контексте \( \alpha \) и \( \beta \).
• Языки: Контекстно-зависимые языки. Распознаются линейно ограниченными автоматами (недетерминированными машинами Тьюринга с памятью, пропорциональной длине входной строки).
• Применение: Описание некоторых синтаксических конструкций естественных языков (например, согласование по числу и роду). В информатике используются редко из-за сложности анализа.

Тип 2: Контекстно-свободные грамматики (КС-грамматики)

• Правила: Имеют вид \( A \rightarrow \gamma \), где \( A \in N \), \( \gamma \) — произвольная цепочка. Левая часть правила — один нетерминал, контекст не учитывается.
• Языки: Контекстно-свободные языки. Распознаются автоматами с магазинной памятью (стековыми автоматами).
• Применение: Наиболее широко используемый тип в информатике. Описывают синтаксис большинства языков программирования (Pascal, C, Java, Python). Используются в компиляторах для синтаксического анализа.

Тип 3: Регулярные грамматики (праволинейные и леволинейные)

• Правила: Имеют вид \( A \rightarrow aB \) или \( A \rightarrow a \) (для праволинейных) или \( A \rightarrow Ba \) или \( A \rightarrow a \) (для леволинейных), где \( A, B \in N \), \( a \in \Sigma \).
• Языки: Регулярные языки. Распознаются конечными автоматами.
• Применение: Описание лексики языков программирования (идентификаторы, числа, ключевые слова), регулярные выражения, поиск и замена текста, лексический анализ.

Применение

В информатике

• Компиляторы и интерпретаторы: Формальные грамматики (преимущественно КС-грамматики) используются для описания синтаксиса языков программирования. На основе грамматики строятся синтаксические анализаторы (парсеры), которые проверяют корректность исходного кода и строят его синтаксическое дерево.
• Лексический анализ: Регулярные грамматики применяются для описания лексем (токенов) — минимальных единиц языка (идентификаторы, числа, операторы).
• Теория автоматов: Формальные грамматики тесно связаны с различными типами автоматов (конечные автоматы, стековые автоматы, машины Тьюринга). Эта связь используется для доказательства свойств языков.
• Обработка естественного языка (NLP): Хотя современные подходы в NLP часто используют статистические и нейросетевые методы, формальные грамматики остаются важным инструментом для синтаксического анализа, построения деревьев зависимостей и моделирования грамматических структур.

В лингвистике

• Порождающая грамматика: Теория Хомского, основанная на формальных грамматиках, пытается описать врождённую языковую способность человека. Формальные грамматики используются для моделирования синтаксиса естественных языков.
• Сравнительное языкознание: Формальные методы применяются для анализа и сравнения грамматических структур разных языков.

В математике

• Теория формальных языков: Является разделом математической логики и дискретной математики. Изучает свойства языков, порождаемых грамматиками, и их связь с автоматами.
• Аксиоматические системы: Формальные грамматики используются для описания синтаксиса формальных теорий (например, исчисления высказываний, теории множеств).

Пример формальной грамматики

Рассмотрим грамматику для простого арифметического выражения, состоящего из цифр \( 0, 1 \) и операторов \( +, * \).

• \( N = \{ E, T, F \} \) (выражение, терм, множитель)
• \( \Sigma = \{ 0, 1, +, *, (, ) \} \)
• \( S = E \)
• Правила \( P \):

1. \( E \rightarrow E + T \)
2. \( E \rightarrow T \)
3. \( T \rightarrow T * F \)
4. \( T \rightarrow F \)
5. \( F \rightarrow (E) \)
6. \( F \rightarrow 0 \)
7. \( F \rightarrow 1 \)

Эта грамматика порождает все корректные арифметические выражения, использующие цифры 0 и 1, операторы + и , а также скобки. Например, цепочка \( 1 + 0 1 \) выводится следующим образом: \[ E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow 1 + T \Rightarrow 1 + T F \Rightarrow 1 + F F \Rightarrow 1 + 0 F \Rightarrow 1 + 0 1 \]

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

Формальные грамматики, особенно в контексте естественных языков, подвергаются критике. Основные замечания:

• Неполнота: Формальные грамматики Хомского не могут адекватно описать многие явления естественных языков, такие как контекстная зависимость, семантика, прагматика, идиомы и метафоры.
• Сложность анализа: Для контекстно-зависимых и неограниченных грамматик задача синтаксического анализа может быть неразрешимой или требовать экспоненциального времени.
• Альтернативные модели: В современной лингвистике и NLP активно используются другие модели, такие как грамматики зависимостей, грамматики с атрибутами, а также вероятностные и нейросетевые подходы, которые часто оказываются более гибкими и эффективными.

Источники

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