В теории формальных языков для разбора синтаксической конструкции цепочки используют синтаксические
txt fb2 ePub html
на телефон придет ссылка на файл выбранного формата
Шпаргалки на телефон — незаменимая вещь при сдаче экзаменов, подготовке к контрольным работам и т.д.
Благодаря нашему сервису вы получаете возможность скачать
на телефон шпаргалки по математической логике.
Все шпаргалки представлены в популярных форматах fb2, txt, ePub , html,
а также существует версия java шпаргалки в виде удобного приложения для мобильного телефона, которые можно скачать за символическую плату.
Достаточно скачать шпаргалки по математической логике — и никакой экзамен вам не страшен!
Не нашли что искали?
Если вам нужен индивидуальный подбор или работа на заказа — воспользуйтесь этой формой.
Двоичное дерево. Матрица связей и таблица подстановок.
Особое место в анализе цепочек формального языка занимает двоичное дерево, в состав которого входят корень и два непересекающихся двоичных поддерева, называемые левым и правым поддеревьями данного корня. В отличие, от дерева разбора из корня и каждого узла дерева исходит не более двух дуг. Такое дерево оказывается более удобным для применения системы составляющих в анализе синтаксических конструкций цепочек.
Для перехода от дерева разбора к его двоичному эквиваленту следует воспользоваться следующими правилами:
правило Формирования левого поддерева: если вершина "К" является самым левым потомком вершины "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 принадлежит матрице связей.
Таблица подстановок представляет множество максимальных правых поддеревьев и хранит корни всех левых поддеревьев. Связь таблицы с матрицей выполняется по номеру правила. Таблицу подстановок удобно изобразить так: