S a1A1A2 … Am.

Затем, заменяя переменную A1 и учитывая, что существует лишь единственная продукция, соответствующая паре (A1, a2), получаем:

S a1A1A2 … Am.

Ясно, что на каждом шаге в сентенциальную форму добавляется ровно один терминальный символ, следовательно, через α шагов алгоритм остановится.

Рассмотренная грамматика называется простой грамматикой (или S-грамматикой). Несмотря на кажущуюся простоту S-грам- матик, в них могут быть выражены многие распространенные конструкции языков программирования.

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

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

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

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

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

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

Пример 9.5.

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

S → aSb SSε

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

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

Пример 9.6.

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

E → I,

E → E + E,

E → E E,

E → (E),

I → a b c.

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

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

Рис. 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. Более того, можно показать, что и для любой другой строки, выводимой в этой грамматике, соответствующее дерево вывода единственно. А это означает, что преобразованная грамматика однозначна. Если же учесть, что она эквивалентна исходной грамматике (в чем нетрудно убедиться), то можно считать, что мы достигли цели и избавились от неоднозначности.

a b

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

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

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

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

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

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

Пример 9.8.

Язык L = {anbncm n, m ≥ 0} {anbmcm n, m ≥ 0} является существенно неоднозначным контекстно-свободным языком.

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

L = {anbncm n, m ≥ 0}

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

S1 → aS1bC ε,

C → cC ε,

а язык

L2 = {anbmcm n, m ≥ 0}

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

S2 → aS2 B,

B → bBc ε.

Тогда, очевидно, язык L = L1 L2 порождается грамматикой, множество продукций которой состоит из всех продукций грамматик G1 и G2 и двух дополнительных продукций

S → S1 S2.

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

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

умаляя общности, отказаться от некоторых случаев, которые затрудняют синтаксический анализ. Так, например, можно без изменения порождаемого языка исключить из грамматики продукции вида А → ε и А → В. В связи с этим возникает необходимость изучения проблемы преобразования КС-грамматики к эквивалентному виду, удовлетворяющему определенным ограничениям на вид продукций. Наибольший интерес представляют для нас так называемые нормальные формы КС-грамматик с весьма сильными ограничениями на вид продукций, которые, однако, достаточно широки для того, чтобы любую КСграмматику можно было преобразовать к эквивалентной КСграмматике в нормальной форме. В этой лекции мы рассмотрим две нормальные формы КС-грамматик: нормальную форму Хомского и нормальную форму Грейбах, имеющих исключительно полезные теоретические и практические приложения.