Дерево синтаксического анализа

Дерево частотного словаря

Дерево частотного словаря - это результат построения дерева двоичного поиска не для чисел, а для слов некоторого текста. Генерирование дерева частотного словаря полезно при подсчете количества вхождений каждого слова в некоторый текст.

Приведем описание структуры этого дерева:

type ukazatel = ^tree; derevo = record slovo: string[20]; kolichestvo: integer; levyj: ukazatel; pravyj: ukazatel; end;

Дерево синтаксического анализа арифметического выражения - это бинарное дерево, листьями которого служат операнды, а остальными вершинами - операции, причем уровень вершины соответствует приоритету выполнения операции: чем ближе к листьям, тем приоритет выше.

Например, на рис. 11.15 изображено дерево синтаксического анализа для выражения ((a / (b + c)) + (x * (y - z))).

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

Рис. 11.15. Дерево синтаксического анализа

¹⁾ Ныне - Калининград.
²⁾ Более корректно: Е - это множество двухэлементных подмножеств (неупорядоченных пар) множества V, называемых ребрами. Из такого определения видно, что любые две вершины могут быть соединены не более чем одним ребром.

12. Лекция: Алгоритмы на графах и деревьях:
Примеры алгоритмов обработки деревьев и графов. Сравнение рекурсивных и итеративных алгоритмов, решающих некоторые классические задачи теории графов.

В этой лекции мы рассмотрим некоторые классические алгоритмы, использующие графы и деревья, приведем и сравним рекурсивные и итеративные их варианты.

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

Дата добавления: 2014-01-03