9. Дерево разбора
Пусть G – КС-грамматика. Пусть в G выводимо
S Þ* a
где a - цепочка терминалов. Такие a называются сентенциями. Рассмотрим какой-нибудь вывод этой сентенции.
S = a0Þ a1 Þ a2 Þ … Þ an = a
Благодаря тому, что на каждом шаге в очередной цепочке происходит замена только одной нетерминальной буквы на новое слово, этот вывод можно изобразить в виде дерева с вершиной S. Концевые вершины (листья) состоят из терминалов и составят слово a, если обойти их вдоль кроны слева направо. Если в выводе встречается применение e-правила, то соответствующий лист дерева является символом e. На самом деле такая ситуация почти не вчтречается, т. к. перед анализом выводов желательно исключить в грамматике e-правила.
Пример. Рассмотрим в грамматике
N = { S }, T = { +, a, b, c }
S ® a| S + S
вывод
S Þ S + S Þ S + S + S Þ a + S + S Þ a + b + S Þ a + b + c
Его дерево разбора:
Дерево разбора хорошо иллюстрирует выводимость. К тому же одно и то же дерево может соответствовать разным выводам одной и той же сентенции. Так в нашем примере после вывода S + S + S можно сначала левое S заменить на a, а затем второе S - на b и, наконец, третье S - на c. А можно это сделать и в ином порядке. Дерево разбора будет одно и то же. Это говорит о том, что понятие дерева глубже отражает суть выводимости, чем просто цепочка преобразований. Было бы идеально, если всегда разным выводам одной и той же сентенции отвечало бы одно и то же дерево разбора. К сожалению это не так. В нашем примере для той же сентенции можно построить и иное дерево
отражающее иной порядок вывода S + S + S.
Случай, когда для одной и той же цепочки существуют разные деревья разбора плох прежде всего потому, что при автоматическом построении вывода всместе с деревом возникают альтернативные варианты, часть из которых ведет в тупик. Поиск правильного дерева требует перебора, который очень быстро делает процедуру неэффективной.
Пример. Рассмотрим в грамматике
N = { Z, E, T, F }, T = { +, -, /, *, (, ), a }
S ® E
E ® E+ T| E – T| T
T ® T * F | T/ F | F
F ® a|(E)
вывод сентенции a *( a + a)
S Þ E Þ T Þ T * F Þ F * F Þ a * F Þ a * (E) Þ a * (E+ T) Þ
a*(T + T) Þ a*( F+ T) Þ a*(a+T) Þ a*(a+F) Þ a*(a+ a).
Дерево разбора
КС-грамматика G называется однозначной, если в ней для любой сентенции существует единственное дерево разбора. (Сентенция – выводимая цепочка терминалов).
КС-язык L называется однозначным, если существует определяющая его однозначная КС-грамматика.
Язык, определяемый грамматикой S ® a| S + S конечно является однозначным. Надо просто заменить правила на S ® a| S + a.
Оказывается, что существуют и неоднозначные КС-языки. Иными словами – не всякая контекстно-свободная грамматика эквивалентна однозначной КС-грамматике. Примером может служить множество цепочек алфавита {a,b,c}, состоящее из всех слов вида anbncm и вида anbmcm, где n³1, m³1.
