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

В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.

Грамматики некоторых языков программирования неоднозначны. При разборе таких языков необходимо учитывать семантическую информацию для выбора правильного варианта. Например, на языке C следующая запись:

x * y;

может быть проинтерпретирована как либо:

• объявление идентификатора y с типом указатель-на-x, или
• выражение, в котором x умножается на y, а результат игнорируется.

Чтобы выбрать между этими интерпретациями, компилятор должен обратиться к своей таблице символов, чтобы узнать, было ли объявление x в качестве имени typedef в данной области видимости.

Пример

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

A → A + A | A − A | a

является неоднозначной, так как есть два левосторонних вывода для строки a + a + a:

	A	→ A + A		A	→ A + A
		→ a + A			→ A + A + A
		→ a + A + A			→ a + A + A
		→ a + a + A			→ a + a + A
		→ a + a + a			→ a + a + a

Также, грамматика является неоднозначной, поскольку есть два дерева разбора для строки a + a − a:

Однако, язык, который она порождает, не является существенно неоднозначным, поскольку следующая однозначная грамматика порождает этот же язык:

A → A + a | A − a | a

Распознавание неоднозначной грамматики

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

Существует очевидная трудность в синтаксическом анализе неоднозначной грамматики детерминированным анализатором, но недетерминированный анализ приводит к значительному проигрышу в эффективности. Большинство конструкций, требующих синтаксического анализа, могут быть распознаны однозначными грамматиками. Некоторые неоднозначные грамматики могут быть преобразованы в однозначные, но общей процедуры для этого преобразования нет, так же как нет и алгоритма определения неоднозначности грамматики. Генераторы компиляторов, такие как YACC, способны устранять некоторые виды неоднозначности, например используя ограничения приоритета и ассоциативности.

Существенно неоднозначные языки

В то время как некоторые языки (множества строк, порождаемых грамматикой) имеют как однозначные, так и неоднозначные грамматики, существуют языки, для которых не существует однозначной грамматики. Примером существенно неоднозначного языка является объединение $\{a^n b^m c^m d^n | n, m > 0\}$ и $\{a^n b^n c^m d^m | n, m > 0\}$. Это контекстно-свободный язык как объединение контекстно-свободных языков, но Введение в теорию автоматов… содержит доказательство того, что нет возможности однозначно разобрать строки в (не контекстно-свободном) подмножестве $\{a^n b^n c^n d^n | n > 0\}$, являющемся пересечением этих двух языков.