Деревья вывода

 

Для представления вывода в грамматике применяют деревья вывода. Корень дерева – начальный символ грамматики. Внутренние вершины дерева – нетерминалы. Листья дерева – терминалы. Если в дереве имеется некоторый узел, например

 

 

то в грамматике имеется правило X®Y₁Y₂Y₃.

Пример: G= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; A®Bbc; B®ab.

1) S®AaB®BbcaB®abbcaB®abbcaab

2) S®AaB®Aaab®BbcaaB®abbcaab

В дереве вывода отражается, какие правила были применены и к каким вхождениям нетерминалов. Однако дерево не несет никакой информации о порядке применения правил (подстановок).

В данном примере имеется два вывода левосторонний (1) и правосторонний (2). Для каждого дерева существует единственный левый вывод, так как благодаря условию выбора самого левого нетерминала, место каждой подстановки устанавливается единственным образом, а по дереву можно определить то единственное правило, которое должно применяться при этой подстановке.

Аналогично, существует единственный правосторонний вывод. Многие методы обработки языков рассчитаны исключительно на левые, или правые выводы, так как они очень удобны для систематической обработки.

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

Не для каждой грамматики можно построить дерево вывода. Деревом вывод можно представить в грамматиках, у которых левая часть правил состоит из одного нетерминала. Такие грамматики называются контекстно-свободными (КС-грамматиками).

Выводы:

1) Каждой цепочке, выводимой в данной КС-грамматике, соответствует одно или несколько деревьев вывода.

2) Каждому дереву соответствует один или несколько выводов.

3) Каждому дереву соответствует единственный правый или единственный левый выводы.

4) Если каждой цепочке, выводимой в данной КС-грамматике, соответствует единственное дерево вывода, эта грамматика называется однозначной в противном случае её называют неоднозначной.

Вопросы и упражнения

1. Можно ли построить дерево вывода для грамматики G из упражнения 1 п.п.4.5. ? Поясните.