Унификация алгебраических выражений (стр. 2 из 3)

Рисунок 4- Диаграмма классов для алгоритма унификации

В рассматриваемом примере реализации алгоритма унификации основную структурную единицу задает класс Lisp_item. Имя класса указывает на то, что проводится аналогия с понятием символа языка LISP. Суть заключается в том, что в LISP символ может обозначать константу, переменную, список, функцию или выражение, которое можно обрабатывать. Чтобы конкретизировать, что задает экземпляр класса Lisp_item, в его состав вводится атрибут typ. Атрибут itmбудет задавать ссылку на объект (константу, переменную или тройку – выражение, состоящее из операции и двух операндов). Причем, любой из операндов может быть экземпляром класса Lisp_item.

Таблица 3- Назначение операций класса Lisp_item

Имя операции	Описание
unifikacia(ArrayList sp, ref ArrayList SV,TextBox tbox)	Выполняет унификацию данного экземпляра Lisp_item, где sp – список продукций (подстановок); SV – формируемый список свободных переменных; tbox – компонента для вывода текстовых сообщений.
Primen_prod(ArrayList sp, ref ArrayList SV, TextBox tbox)	Проверяет применимость к данному экземпляру класса Lisp_item продукций из заданного списка SV. Назначение остальных параметров то же, что и в предыдущем случае.
zamena(ArrayList SV)	Выполняет замену свободных переменных в результирующем выражении на соответствующие им фрагменты исходного выражения. SV – список свободных переменных

Для задания продукций (подстановок), используемых для унификации выражений, применяется класс podst. В соответствии с определением продукции атрибутами класса являются left_part и right_part. При этом и левая, и правая части могут представлять произвольные выражения и задаются как объекты класса Lisp_item.

Таблица 4- Назначение операций класса podst

Имя операции	Описание
primenima(Lisp_item E, ref ArrayList SV)	Определяет применимость левой части продукции к заданному выражению. Е – унифицируемое выражение; SV – формируемый список свободных переменных.
zamena(ArrayListSV)	Выполняет замену свободных переменных в правой части удачно примененной продукции.

Для работы с выражением в префиксной форме предназначен класс trojka. Атрибуты этого класса предназначены для определения основных элементов и признаков выражения в префиксной форме: operation – символ операции; priority – приоритет операции; is_func – операция является функцией; op1, op2 – операнды.

Таблица 5- Назначение операций класса trojka

Имя операции	Описание
primenima(Lisp_item E, ref ArrayList SV)	Определяет применимость тройки из левой части продукции к тройке заданного выражения. Е – унифицируемое выражение; SV – формируемый список свободных переменных.

4. Операции класса Lisp_item

4.1 Операция выполнения унификации (unifikacia)

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

Если удается удачно применить какую-либо продукцию из заданного списка, то выполняется выход. В противном случае, операция унификации (unifikacia) вызывается для каждого из операндов выражения.

4.2 Операция проверки применимости продукций(Primen_prod)

Действия данной операции определяются схемой на рисунке 6 и складываются из следующего. Организуется цикл просмотра списка продукций.

Для очередной продукции из списка (rpod) вызывается операция проверки применимости продукции (Primenima). Если операция возвращает истинное значение, то вызывается операция замены свободных переменных в правой части продукции.

Если же ни одной продукции применить не удалось, то возвращается ложное значение.

4.3 Операция замены свободных переменных (zamena)

Действия данной операции определяются схемой на рисунке 7 и складываются из следующего. Состав выполняемых действий зависит от типа обрабатываемого элемента выражения.

В случае константы никаких действий не выполняется.

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

5. Операции класса podst

5.1 Операция проверки применимости (primenima)

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

Если левая часть – константа, то выполняется сравнение значений констант из левой части продукции и заданного выражения. Результат сравнения возвращается как результат выполнения операции.

Если левая часть продукции – переменная, то формируется элемент списка свободных переменных и помещается в список. Для задания элементов списка свободных переменных используется класс sv_perem, атрибутами которых являются:

nm_sv– имя свободной переменной;

fragment- фрагмент выражения, соответствующий переменной (тип Lisp_item).

Если левая часть – тройка, то выполняется выделение выражений тройки из левой части продукции и унифицируемого выражения, после чего вызывается операция класса trojka для проверки применимости тройки из продукции к тройке из выражения (primenima).

Рисунок5 -СхемаалгоритмаоперацииLisp_item.unifikacia

Рисунок6 - Схема алгоритма операции Lisp_item.Primen_prod

Рисунок7 - Схема алгоритма операции Lisp_item.zamena

Рисунок8 - Схема алгоритма операции podst.primenima

6. Операции класса trojka

6.1 Операция проверки применимости (primenima)

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

При совпадении операций троек, анализируется тип первого операнда.

В случае константы выполняется сравнение значений констант, стоящих на месте первого операнда в сравниваемых тройках. При несовпадении – выполняется выход.

Если первый операнд переменная, то ей сопоставляется первый операнд из тройки унифицируемого выражения и заносится в список свободных переменных.

Если первый операнд тройка, то для этого объекта вызывается описываемая операция primenima. При неудачном завершении этой операции выполняется выход из операции со значением false.

Поскольку в тройке может отсутствовать второй операнд (например, функции с одним аргументом, или одноместные операции типа (notx)), то если это подтверждается, то работа операции завершается со значением true. Если же второй операнд присутствует, то прежде всего проверяется возможное условие совпадения первого и второго операндов.

Если же в тройке из продукции операнды различны, то выполняется обработка второго операнда. Алгоритм обработки аналогичен алгоритму обработки первого операнда.

Рисунок 9, лист 1- Схема алгоритма операции trojka.primenima

Рисунок 9, лист 2.

Выводы

Таким образом, процесс унификации выражения складывается из трех последовательно выполняемых этапов:

преобразование выражения в инфиксной форме в выражение в префиксной форме Þ унификация выражения в префиксной форме Þ преобразование результата унификации из префиксной формы в инфиксную форму.