Пример 11. Деревья разбора и приведения

Деревья разбора и приведения.

Дерево разбора рассматривается как графическое представление порождения, из которого удалена информация о порядке замещения. Каждый внутренний узел дерева разбора помечается некоторым нетерминалом А, а узлы слева направо — символами из правой части продукции для этого нетерминала. Листья дерева разбора помечены нетерминалами или терминалами и, будучи прочитаны слева направо, образуют сентенциальную форму. Например, дерево разбора для -(id+id), полученное порождением (5.4), показано на рис. 22.

Рис. 22. Дерево разбора для -(id+id)

Рассмотрим порождение (5.4). Последовательность деревьев разбора, построенная на основе этого порождения, показана на рис. 23.

Первый шаг этого порождения – E => -E. Для моделирования этого шага добавляем к корню начального дерева два дочерних узла, помещенных как "-" и "E".

Второй шаг представляет собой -E=>-(E). Соответственно, добавляем три дочерних узла — "(", "Е" и ")" — к листу Е во втором дереве для получения третьего дерева, дающего -(Е). Продолжая построения получим шестое дерево в качестве полного дерева разбора.

Дерево разбора игнорирует порядок, в котором производилось замещение символов в сентенциальной форме. Например, если порождение (5.4) изменить в соответствии с (5.5), окончательное дерево разбора будет таким же, как на рис. 23.

Предложение может иметь не одно дерево разбора и даже не одно левое или правое порождение.

		E

Рис. 23. Построение дерева разбора из порождения (5.4)

Дата добавления: 2014-12-27