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

Из предыдущих рассуждений ясно, что для произвольной строки   L(G) грамматический разбор методом полного перебора дает нам некоторое дерево вывода для . Если существует несколько таких деревьев для одной и той же строки, то говорят, что имеет место неоднозначность.

Определение 9.4.

Контекстно-свободная грамматика G называется неоднозначной, если существует некоторая строка   L(G), которая имеет в G, по крайней мере, два различных дерева вывода. В противном случае КС-грамматика называется однозначной.

Нетрудно заметить, что неоднозначность влечет существование двух или более различных левосторонних (или правосторонних) выводов.

Пример 9.5.

Покажем, что грамматика

S  aSbSS

неоднозначна. Для этого возьмем строку  = aabb и построим для нее два вывода в этой грамматике:

а) S б) S

a b S S

S a b

a b  S

S a b

S





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

Пример 9.6.

Рассмотрим грамматику G = (N, T, S, P), где N = {E, I}, T = {a, b, c, +, , (,)} и Р - множество следующих продукций:

E  I,

E  E + E,

E  E  E,

E  (E),

I  abc.

Нетрудно видеть, что эта грамматика порождает собственное подмножество арифметических выражений в таких языках программирования, как, например, Паскаль или Фортран.

Покажем, что эта грамматика неоднозначна. Возьмем строку a+bc, которая принадлежит языку L(G), и построим для нее два дерева вывода:

а) Е б) Е

Е + Е Е  Е

I E  E E + E I

a I I I I c

b c a b

Рис. 9.1. Два дерева вывода для a+bc

Для того чтобы устранить неоднозначность, в подобных случаях иногда вводят дополнительные правила, устанавливающие относительные приоритеты арифметических операций. Так, обычно считают, что операция умножения  связывает операнды сильнее, чем сложение +. Тогда на рис. 9.1 дерево вывода а) должно будет рассматриваться как правильное, соответствующее тому, что произведение bc является подформулой, значение которой должно быть вычислено раньше, чем будет произведено сложение. Однако эти правила не соответствуют нашим грамматическим правилам, имеющим строго определенную форму продукций. Поэтому попробуем так видоизменить данную грамматику, чтобы она стала однозначной. Для этого в качестве N возьмем следующее множество переменных: {E, M, F, I} и новый набор продукций:

E  M ,

M  F ,

F  I ,

E  E + M ,

M  MF ,

F  (E) ,

I  abc.

В этой грамматике строка a+bc будет иметь уже единственное дерево вывода, представленное на рис. 9.2. Более того, можно показать, что и для любой другой строки, выводимой в этой грамматике, соответствующее дерево вывода единственно. А это означает, что преобразованная грамматика однозначна. Если же учесть, что она эквивалентна исходной грамматике (в чем нетрудно убедиться), то можно считать, что мы достигли цели и избавились от неоднозначности.

E

E + M

M M  F

F F I

I I c

a b

Рис. 9.2. Единственное дерево вывода для a+bc

К сожалению, не всегда так легко удается решить проблему неоднозначности. Даже вопрос, однозначна грамматика или нет, часто оказывается очень трудным, впрочем, как и вопрос, эквивалентны ли две грамматики. В действительности, ни для первого, ни для второго вопросов не существует универсальных алгоритмов, которые всегда давали бы ответы.

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

Определение 9.7.

Контекстно-свободный язык L называется однозначным, если для него существует однозначная грамматика. Если же любая грамматика, порождающая L, неоднозначна, то такой язык называется существенно неоднозначным.

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

Пример 9.8.

Язык L = {aⁿbⁿc^m  n, m  0}{aⁿb^mc^m  n, m  0} является существенно неоднозначным контекстно-свободным языком.

Покажем, что язык L – контекстно-свободный. Нетрудно проверить, что язык

L = {aⁿbⁿc^m  n, m  0}

порождается грамматикой G₁:

S₁  aS₁bC,

C  cC,

а язык

L₂ = {aⁿb^mc^m  n, m  0}

порождается грамматикой G₂:

S₂  aS₂B,

B  bBc.

Тогда, очевидно, язык L = L₁  L₂ порождается грамматикой, множество продукций которой состоит из всех продукций грамматик G₁ и G₂ и двух дополнительных продукций

S  S₁S₂.

Мы не будем приводить здесь технически сложное доказательство существенной неоднозначности языка L, а отметим только, что эта неоднозначность связана с невозможностью выразить с помощью одного и того же множества продукций два "противоречивых" требования: в языке L₁ количества символов a и b в строке должны совпадать между собой и почти всегда отличаться от количества символов с, тогда как в языке L₂ количества символов b и c в строке совпадают между собой и почти всегда отличаются от количества символов a.