Пример 2.10

Пример 2.9

Грамматика G = ({if, then, else, a, b}, {S}, P, S),

где P = {S ® if b then S else S | if b then S | a} является неоднозначной, так как в этой грамматике для цепочки if b then if b then a else a можно построить два дерева вывода.

Язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Если грамматика G – неоднозначна, это не означает, что язык L(G), порождаемый этой грамматикой, обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, то есть для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной. В примере 2.9 разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

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

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

1) A ® AA | a

2) A ® AaA | b

3) A ® aA | Ab | g

4) A ® aA | aAbA | g

Язык L = {aⁱ b^j c^k | i = j или j = k} является неоднозначным КС-языком.

Интуитивно это объясняется тем, что цепочки с i=j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j=k. Но тогда, по крайней мере, некоторые из цепочек с i=j=k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L является неоднозначным, приведено в [3, стр. 235-236].

Одна из грамматик, порождающих L, такова:

G=({a, b, c}, {A, B, C, D, S}, Р, S), где

Р={ S ® AB | DC, A ® aA | e, B ® bBc | e, C ® cC | e, D ® aDb | e}

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящимспособом.

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

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S: на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

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