r1 - 25 Feb 2005 - 12:27:25 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > SynIdent > АлгоритмПроектирования
При описании действий Рефал-машины, выполняющей синтаксическое отождествление, будем опираться на процесс (алгоритм) проектирования типового выражения L на объектное выражение Е.

Типовым выражением называется выражение, не содержащее конкретизационых скобок.

Объектным выражением называется выражение, не содержащее ни конкретизационных скобок, ни свободных переменных.

Элементами выражений L и E являются символы, скобки, свободные переменные. Узлы - промежутки между элементами и концы выражений.

Предполагается, что перед началом процесса концы выражения L спроектированы на концы выражения E.

Если узлу из L сопоставлен узел из E, будем говорить, что первый узел спроектирован на второй. Если в L узел К1 расположен левее узла K2, то в E проекция узла К1 не может находиться правее проекции узла К2. Если R1 и R2 - проекции концов некоторого элемента, то выражение, ограниченное узлами R1 и R2 называется проекцией элемента.

Проекции свободных переменных (значения) должны удовлетворять требованиям, предъявляемым к значениям.

Проекции остальных элементов должны быть тождественны самим элементам.

Жесткие элементы - символы, скобки, свободные переменные символа и термы.

Если типовое выражение состоит из одних лишь жестких элементов, то следующее правило полностью определяет проекционные номера и весь алгоритм проектирования.

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

Каждому вхождению свободной переменной в L будет соответствовать определенный проекционный номер. Если некоторая переменная входит в L несколько раз, то вхождение с наименьшим проекционным номером называется главным, остальные вхождения - повторными. Повторные вхождения всех свободных переменных относятся к жестким элементам.

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

Если левый конец спроектирован, и жестких элементов со спроектированным концом больше нет, такие вхождения переменных называются открытыми . В этом случаев сначала правый конец проектируется на тот же узел, что и левый конец, то есть переменная получает пустое значение и процесс проектирования продолжается. Как только возникает тупиковая ситуация, происходит возврат к последней открытой переменной, которая получила значение, и удлиняется ее значение, то есть проекция ее правого конца переносится на один терм вправо и с этого места проектирование продолжается, элементам L приваиваются новые проекции. Если удлинение последней открытой переменной невозможно, то удлиняется предпоследняя и т.д. Если в тупиковой ситуации ни одной переменной удлинить нельзя, то отождествление невозможно. Если на каком-то этапе возникает несколько кокурирующих между собой открытых или закрытых переменных, то меньший проекционный номер получает то элемент, что расположен левее.

-- Luba Parmyonova - 25 Feb 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback