Формальные языки

Грамматики: порождение языков

2+3*4 = 14, а не 20. Это не договорённость - это следствие того, что грамматика арифметических выражений в C++, Python, JavaScript однозначно определяет: умножение связывает сильнее сложения. Если бы грамматика была неоднозначной, тот же исходник мог давать разные числа на разных машинах. Грамматики - это не теория ради теории: это точный механизм, без которого ни один компилятор не работает.

  • **Компиляторы:** парсер GCC/Clang строит AST по КС-грамматике C/C++; неоднозначность = ошибка компиляции или неправильный код
  • **Протоколы:** HTTP, SMTP, DNS описаны грамматиками в RFC (ABNF); неоднозначность в протоколе = уязвимость безопасности
  • **Лингвистика:** «I saw the man with the telescope» - неоднозначность естественного языка, формализуемая через деревья разбора

Бэкус, Наур и рождение BNF

1959 год. Джон Бэкус из IBM и Питер Наур из Дании создают формальную нотацию для описания ALGOL 60 - первого языка программирования, синтаксис которого был задан точными правилами. Backus-Naur Form (BNF) - это продукции в точности в том смысле, который изучается сейчас. До этого языки описывались на естественном языке: «переменная - это буква, за которой могут следовать буквы и цифры». Двусмысленность, споры, несовместимые реализации. BNF убрал всё это одним ударом. Сегодня каждый RFC, каждый стандарт языка, каждая спецификация протокола - написаны потомками той самой нотации.

Предварительные знания

  • The Chomsky Hierarchy

Продукции: правила подстановки

Формальный язык - множество строк. Как задать это множество? Перечислить все строки нельзя - их бесконечно много. Нужен **генератор** - набор правил, порождающих все строки языка и только их. Именно так устроены JSON-парсер, интерпретатор Python, компилятор C++: грамматика описывает язык точнее и компактнее любого другого инструмента.

**Формальная грамматика** G = (V, Σ, R, S), где: **V** - конечное множество нетерминалов (переменных), **Σ** - алфавит терминалов (V ∩ Σ = ∅), **R** - конечное множество продукций (правил подстановки), **S ∈ V** - стартовый нетерминал. **Терминалы** - символы итогового языка (a, b, 0, 1). **Нетерминалы** - вспомогательные переменные (S, A, B), которых не будет в итоговой строке.

КомпонентОбозначениеПример (G для a^n b^n)Аналогия
НетерминалыV{S}Переменные в уравнении
ТерминалыSigma{a, b}Конечные символы (буквы)
ПродукцииR{S->aSb, S->ab}Правила подстановки
Стартовый символSSНачальная точка вывода

**Соглашение о записи:** нетерминалы обозначают ЗАГЛАВНЫМИ буквами (S, A, B, E, T, F), терминалы - строчными (a, b, 0, 1) или специальными символами (+, *, скобки). Вертикальная черта | объединяет альтернативы: S -> aSb | ab означает «S заменяется на aSb ИЛИ на ab».

Грамматика: S -> 0S1 | 01. Какой язык она порождает?

Вывод: от S к строке

Грамматика задаёт правила. **Вывод** (derivation) - последовательность применений правил, превращающая стартовый символ S в строку из терминалов. Каждый шаг: выбираем нетерминал, выбираем правило, заменяем. Процесс заканчивается, когда нетерминалов не осталось. Именно так работает рекурсивный спуск в GCC/Clang - это буквально вычисление левого вывода в реальном времени.

**Вывод (derivation)** - последовательность S => alpha_1 => alpha_2 => ... => w, где каждый шаг => - применение одной продукции. **Левый вывод (leftmost):** на каждом шаге заменяется самый левый нетерминал. **Правый вывод (rightmost):** самый правый нетерминал. Обозначения: =>_lm (leftmost), =>_rm (rightmost), =>* (ноль или более шагов).

**Язык грамматики** L(G) - множество всех терминальных строк, выводимых из S: L(G) = {w in Sigma* : S =>* w}. Две грамматики **эквивалентны**, если L(G_1) = L(G_2). Одному языку могут соответствовать разные грамматики.

ПонятиеОбозначениеЗначение
Один шаг выводаalpha => betaЗаменён один нетерминал
Ноль или более шаговalpha =>* betaТранзитивное замыкание
Левый вывод=>_lmВсегда самый левый нетерминал
Правый вывод=>_rmВсегда самый правый нетерминал
Язык грамматикиL(G){w in Sigma* : S =>* w}

S -> AB, A -> a, B -> b. Левый вывод строки 'ab'?

Сентенциальная форма

На каждом шаге вывода - строка с терминалами и нетерминалами вперемешку. Например: E+T*F - тут E, T, F ещё нетерминалы, а + и * уже терминалы. Такие промежуточные строки называются **сентенциальными формами**. Это не абстракция ради абстракции - каждый шаг парсинга в recursive descent parser производит именно сентенциальную форму.

**Сентенциальная форма (sentential form)** - любая строка alpha in (V ∪ Sigma)*, выводимая из S: S =>* alpha. Может содержать и терминалы, и нетерминалы. Если alpha содержит только терминалы (alpha in Sigma*), она называется **предложением** (sentence) языка. L(G) - множество всех предложений.

СтрокаТипНетерминалы?Дальнейший вывод
SСентенциальная формаДа (S)Нужно продолжить
E+TСентенциальная формаДа (E, T)Нужно продолжить
n+T*FСентенциальная формаДа (T, F)Нужно продолжить
n+n*nПредложение (sentence)НетВывод завершён
xyzНе сентенциальная форма-Не выводится из S

**Дерево разбора (parse tree)** - визуализация вывода. Корень - S, внутренние узлы - нетерминалы, листья - терминалы. Каждое применение правила A -> X_1 X_2...X_k добавляет к узлу A дочерние узлы X_1, X_2, ..., X_k. Чтение листьев слева направо даёт выведенную строку.

Строка 'aAbB' в грамматике с V={S,A,B}, Sigma={a,b} - это:

Неоднозначность грамматики

Грамматика E -> E+E | E*E | n для строки «n+n*n» допускает ДВА разных дерева разбора. Одно интерпретирует как (n+n)*n, другое как n+(n*n). Это не академическая проблема - неоднозначная грамматика порождает недетерминированный компилятор. Один и тот же код даёт разный результат в зависимости от того, какое дерево выбрал парсер. Именно поэтому все промышленные языки тщательно проектируют однозначные грамматики.

**Неоднозначная грамматика (ambiguous grammar)** - грамматика, в которой существует строка w in L(G), имеющая два или более **различных деревьев разбора** (или, эквивалентно, два различных левых вывода). Грамматика **однозначна (unambiguous)**, если каждая строка имеет ровно одно дерево разбора.

ПроблемаНеоднозначная грамматикаОднозначная альтернатива
Приоритет операцийE -> E+E | E*E | nE -> E+T | T; T -> T*F | F; F -> n
АссоциативностьE -> E-E | nE -> E-T | T (левая ассоц.)
Dangling elseS -> if E then S else S | if E then SРазделить на matched/unmatched
СпискиL -> L,L | itemL -> L,item | item (левая рекурсия)

**Как устранить неоднозначность?** Для выражений: ввести **приоритет** (отдельные нетерминалы E, T, F для +, *, атомов) и **ассоциативность** (левая рекурсия E -> E+T для левой ассоциативности). Для if-else: разделить на «полные» и «неполные» утверждения.

**Не каждую неоднозначную грамматику можно исправить!** Существуют **inherently ambiguous languages** - языки, для которых ВСЕ грамматики неоднозначны. Пример: L = {a^i b^j c^k : i=j или j=k}. Строки с i=j=k принадлежат обоим «правилам», и никакая грамматика не устранит двойственность.

Любую неоднозначную грамматику можно переписать в однозначную, сохранив язык

Существуют inherently ambiguous languages - КС-языки, для которых НЕ существует ни одной однозначной КС-грамматики. Пример: L = {a^i b^j c^k : i = j или j = k}

Строки вида a^n b^n c^n (где i=j=k) «покрываются» двумя правилами: i=j и j=k. Любая грамматика вынуждена иметь два «пути» для таких строк. Это доказано через свойства pumping lemma для КС-языков.

Грамматика E -> E-E | n для строки «n-n-n» даёт два дерева: (n-n)-n и n-(n-n). Как сделать грамматику однозначной с левой ассоциативностью?

Ключевые идеи

  • **Грамматика G = (V, Sigma, R, S)** - набор правил подстановки для порождения строк языка
  • **Вывод S =>* w** - последовательность применений продукций; левый вывод заменяет самый левый нетерминал
  • **Сентенциальная форма** - промежуточная строка вывода; предложение - сентенциальная форма без нетерминалов
  • **Неоднозначная грамматика** допускает два дерева разбора для одной строки; исправляется введением приоритета и ассоциативности

Связанные темы

Грамматики - инструмент порождения языков; автоматы - инструмент распознавания:

  • Иерархия Хомского — Тип грамматики определяет класс порождаемого языка
  • Операции над языками — Объединение, конкатенация и замыкание - алгебра над грамматиками
  • LL и LR парсеры — Практическая реализация разбора по КС-грамматикам

Вопросы для размышления

  • JSON-грамматика: object -> { pairs } | {}, pairs -> pair , pairs | pair, pair -> string : value. Является ли эта грамматика однозначной? Почему?
  • Почему Python не имеет проблемы dangling else, хотя C/Java имеют? Как синтаксис Python устраняет неоднозначность?
  • Вернёмся к 2+3*4: если бы грамматика была неоднозначной, компилятор мог бы выдать 14 ИЛИ 20. Какие ещё реальные проблемы создаёт неоднозначность в компиляторах?

Связанные уроки

  • fl-02-chomsky — Иерархия Хомского определяет классы грамматик, изучаемых здесь
  • fl-12-cfg — Контекстно-свободные грамматики - развитие продукций из этого урока
  • fl-17-ll-lr — LL/LR парсеры - практическая реализация разбора по КС-грамматикам
  • comp-10-cfg — CFG в компиляторах - прямое применение грамматик к реальным языкам
  • nlp-01 — NLP использует те же формальные грамматики для синтаксического разбора
  • fl-11-pumping-lemma — Pumping lemma доказывает пределы того, что грамматики могут породить
  • ml-04
Грамматики: порождение языков

0

1

Войти