Двоичное дерево. Матрица связей и таблица подстановок.

Особое место в анализе цепочек формального языка занимает двоичное дерево, в состав которого входят корень и два непересекающихся двоичных поддерева, называемые левым и правым поддеревьями данного корня. В отличие, от дерева разбора из корня и каждого узла дерева исходит не более двух дуг. Такое дерево оказывается более удобным для применения системы составляющих в анализе синтаксических конструкций цепочек. Для перехода от дерева разбора к его двоичному эквиваленту следует воспользоваться следующими правилами: правило Формирования левого поддерева: если вершина "К" является самым левым потомком вершины "J" в дереве разбора, то эта вершина формирует вершину-сток левого поддерева двоичного дерева и является левым потомком вершины "J" двоичного дерева; вершина-исток левого поддерева есть образ символа, находящегося в левой части правила грамматики, а вершина-сток - образ первого символа правой части правила грамматики, правило Формирования правого поддерева: если вершина "L" является старшим среди оставшихся (после удаления вершины "К" для формирования левого поддерева) братьев - потомков вершины "J" в дереве разбора, то эта вершина формирует вершину-сток правого поддерева двоичного дерева и является правым потомком старшего брата - вершины "К" ; все последующие братья - потомки вершины "J" в дереве разбора являются правыми потомками братьев по старшинству и формируют правые поддеревья двоичного дерева; вершина-исток правого поддерева есть образ предшествующего левого символа в правой части правила, а вершина-сток - образ следующего справа символа в правой части правила. Существует много алгоритмов анализа цепочек формального языка при обходе вершин двоичного дерева сверху-вниз и снизу-вверх. Для объяснения их работы чаще всего используют матрицу связей и таблицу подстановок. Матрицу связей представляет логическая функция двух переменных, описывающая наличие левых поддеревьев двоичного дерева:М true, если существует левое поддерево; Р(Ai;Wi)= Н 0 false, если нет такого поддерева, где Аi - нетерминальный символ левой части правила, т. е. АiOVn;Wi- первый символ правой части правила . т. е. WiOV. Матрицу связей удобно представить списком или матрицей смежности, строки которой - символы левой части правила, столбцы - первый символ правой части правила, а элементы - значения 0 или 1, что соответствует значениям false или true логической функции P(Ai:Wi). Матрица связей позволяет найти максимальные левые поддеревья, определить позвоночник и указать индекс скелета. Таблицу подстановок представляет также логическая функция двух переменных, описывающая наличие максимальных правых поддеревьев М true, если существует правое поддерево P(i;bi\Wi)=H 0 false, если нет такого поддерева, где i – номер правила, для которого дается описание хвоста правой части правила; bi\wi - хвост правой части правила, первый символ которой Wi принадлежит матрице связей. Таблица подстановок представляет множество максимальных правых поддеревьев и хранит корни всех левых поддеревьев. Связь таблицы с матрицей выполняется по номеру правила. Таблицу подстановок удобно изобразить так: