КАТЕГОРИИ:
Деревья разбора и приведения.
Дерево разбора рассматривается как графическое представление порождения, из которого удалена информация о порядке замещения. Каждый внутренний узел дерева разбора помечается некоторым нетерминалом А, а узлы слева направо — символами из правой части продукции для этого нетерминала. Листья дерева разбора помечены нетерминалами или терминалами и, будучи прочитаны слева направо, образуют сентенциальную форму. Например, дерево разбора для -(id+id), полученное порождением (5.4), показано на рис. 22.
Рис. 22. Дерево разбора для -(id+id)
Рассмотрим порождение (5.4). Последовательность деревьев разбора, построенная на основе этого порождения, показана на рис. 23.
Первый шаг этого порождения – E => -E. Для моделирования этого шага добавляем к корню начального дерева два дочерних узла, помещенных как "-" и "E".
Второй шаг представляет собой -E=>-(E). Соответственно, добавляем три дочерних узла — "(", "Е" и ")" — к листу Е во втором дереве для получения третьего дерева, дающего -(Е). Продолжая построения получим шестое дерево в качестве полного дерева разбора.
Дерево разбора игнорирует порядок, в котором производилось замещение символов в сентенциальной форме. Например, если порождение (5.4) изменить в соответствии с (5.5), окончательное дерево разбора будет таким же, как на рис. 23.
Предложение может иметь не одно дерево разбора и даже не одно левое или правое порождение.
Рис. 23. Построение дерева разбора из порождения (5.4)
Дата добавления: 2014年12月27日; Просмотров: 737; Нарушение авторских прав?; Мы поможем в написании вашей работы!