Сборник по задачам и примерам Assembler



Сеть

Неважно, что кто-то идет неправильно,
возможно, это хорошо выглядит...
Первый закон Скотта (Прикладная Мерфология)

Выше мы уделили достаточно внимания работе с матрицами и списками, и это сделано не случайно. Еще более обобщая понятие списка, мы придем к определению многосвязного списка, для которого характерно наличие произвольного количества указателей на другие элементы списка. Можно говорить, что каждый конкретный элемент входит в такое количество односвязных списков, сколько у него есть указателей. Многосвязный список получается «прошитым» односвяз-ными списками, поэтому такие многосвязные списки называют прошитыми, или плексами. С помощью многосвязных списков можно моделировать такую структуру данных, как сеть или граф. Частный случай сети — дерево. Рассмотрим варианты представления в памяти компьютера этих структур данных.
Сетью называется кортеж G — (V,E), где V — конечное множество вершин, Е -^ конечное множество ребер, соединяющих пары вершин из множества V. Две вершины и и v из множества V называются смежными, если в множестве Е существует ребро (u, v), соединяющее эти вершины. Сеть может быть ориентированной и неориентированной. Это зависит от того, считаются ли ребра (u, v) и (v, u) разными. В практических приложениях часто ребрам приписываются веса, то есть некоторые численные значения. В этом случае сеть называется взвешенной. Для каждой вершины v в сети есть множество смежных вершин, то есть таких вершин Uj (i = l..n), для которых существуют ребра (v, и:). Это далеко не все определения, касающиеся сети, но для нашего изложения их достаточно, так как его цель — иллюстрация средств ассемблера для работы с различными структурами данных. Поэтому рассмотрим варианты представления сетей в памяти компьютера в виде, пригодном для обработки. Какой из этих вариантов лучше, зависит от конкретной задачи. Мы также не будем проводить оценку эффективности того или иного вида представления.

  • Матрица смежности. Сеть, имеющую М вершин, можно представить в виде матрицы размерностью МхМ. При условии, что вершины помечены v,, v2,..., vm, значение матрицы ау = 1 говорит о существовании ребра между вершинами v, и v,. Иначе говоря, эти вершины являются смежными. Для ориентированной сети матрица смежности будет симметричной.
  • Матрица инцидентности. В основе этого представления также лежит матрица, но строки в ней соответствуют вершинам, а столбцы — ребрам (рис. 2.15). Из рисунка видно, что каждый столбец содержит две единицы в строках, причем одинаковых столбцов в матрице нет.

Рис. 2.15. Представление сети матрицей инцидентности

Рис. 2.16. Представление сети векторами смежности

Векторы смежности. Этот вариант представления также матричный (рис. 2.16). Все вершины пронумерованы. Каждой вершине соответствует строка матрицы, в которой перечислены номера вершин, смежных с данной.
В качестве примера рассмотрим фрагмент сканера для распознавания вещественных чисел в директивах ассемблера dd, dq, dt. Правило описания этих чисел в виде синтаксической диаграммы приведено в уроке 19 «Архитектура и программирование сопроцессора» учебника. Ему соответствует показанное ниже регулярное выражение и детерминированный конечный автомат (рис. 2.17):

(+|-)dd*.dd*e(+|-)dd*

Рис. 2.17. Грамматика языка описания вещественных чисел в директиве dd и соответствующий ей детерминированный конечный автомат

Программа будет состоять из двух частей:

  • построение списка — здесь выполняется построение многосвязного списка по заданному регулярному выражению;
  • обработка входной строки на предмет выяснения того, является ли она правильной записью вещественного числа в директивах ассемблера dd, dq, dt.

При выполнении первого пункта возникает проблема — как задавать элемент многосвязного списка, если в общем случае различные элементы списка могут иметь разное количество связей? Как показано на рисунке, различные состояния имеют разное количество связей. Можно предложить разные подходы к выбору программной реализации этих связей. Выберем следующий. Организуем все исходящие связи каждого конкретного элемента в односвязный список. В этом случае многосвязный список будет содержать элементы двух типов:

  • описывающие состояния автомата — они организованы в двусвязный список;
  • описывающие ссылки или переходы от данного состояния к другим состояниям в зависимости от очередного входного символа — эти ссылки организованы в виде односвязных списков для каждого из состояний.

В случае нелинейной организации двусвязного списка его построение таит ряд проблем. Часть из них снимается при статическом способе построения списка, который для конечных автоматов является наилучшим. При необходимости, используя приведенные ниже структуры, читатель может самостоятельно описать такой список в своем сегменте данных. Далее мы займемся динамическим, более сложным вариантом организации нелинейного списка, реализующим конечный автомат. Напомним, что его задачей является распознавание лексемы — описания шестнадцатеричного числа в директивах ассемблера dd, dq, dt. Для построения нелинейного многосвязного списка разработаем ряд макрокоманд. С их помощью построение проводится в два этапа:

  • создание двусвязного списка состояний конечного автомата;
  • создание односвязных списков переходов.

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

;но при необходимости можно создать и доп. кучу с помощью HeapCreate :HANDLE GetProcessHeap (VOID);
call GetProcessHeap
mov Hand_Head.eax :сохраняем дескриптор .запрашиваем и инициализируем блоки памяти из кучи:
xorebx.ebx :здесь будут указатели на предыдущ. элементы
xorecx.ecx ;dl - номер элемента состояния (двоичный) rept N_state
push ecx :LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes);
push type descr ;размер структуры
push 0 :флаги не задаем
push HandJHead ;описатель кучи
call HeapAlloc
mov [eax].prev_state.ebx запоминаем адрес предыдущ. (if ebx=0. то это первый)
movebx.eax запоминаем адрес текущего в ebx
raov [eax].current_state,eax (И в descr.current_state
pop ecx
mov [eax].id_state_state,cl
inc cl endm
указатель на последний элемент списка состояний в поле-указатель на начало списка head
mov head.ebx .восстанавливаем регистры
pop ebx
pop eax endm

Создание односвязного списка переходов для состояния конечного автомата

Также опишем структуру элемента списка переходов и макрокоманду для создания этого элемента. Особенность в том, что в отличие от списка состояний макрокоманда строит не весь список, а только один его элемент. Другая особенность в том, что указатель на полученный односвязный список является ссылкой на последний выделенный элемент списка и именно к этому элементу осуществляется привязка элемента состояния к своему списку переходов, что на самом деле особого значения не имеет.

item_l1st_cross struc ;элемент списка переходов
simbol db 0 :входной символ, при котором автомат переходит
:в состояние ниже (поля id_state_cross и nextjtem) id_state_crossdb 0 идентификатор состояния в списке состояний,
:в которое производится переход
point_state dd 0 ;адрес элемента состояния, в которое производится переход next_item dd 0 :адрес следующего элемента в списке переходов для этого состояния
create_item_cross macro sim:REQ.state:REQ.descr:REQ.head:REQ. Hand_Head:REQ
local ml,@@cycl.exit_m
:создание элемента списка переходов для определенного состояния
:вход:
;регистр ЕВХ - адрес предыдущего (для поля descr.nextjtern),
.-Для первого должен быть равен нулю
:sim - символ ASCII, при поступлении которого производится переход в состояние state
:descr - имя структуры-элемента списка переходов
:state - номер состояния, в которое производится переход
;(если двузначное, то в скобках <>)
:head - имя переменной для хранения указателя на конец списка состояний
;Hand_Head - дескриптор кучи процесса по умолчанию
: выход:
регистр ЕВХ - адрес созданного элемента списка переходов
:флаг cf=l - ошибка: нет такого состояния
сохраняем регистры
push eax
:запрашиваем и инициализируем блок памяти из кучи: :LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags. DWORD dwBytes); push type descr ;размер структуры push 0 -.флаги не задаем
push Hand_Head ;описатель кучи call HeapAlloc
mov [eax].next_item.ebx :адрес предыдущего movebx.eax запоминаем адрес текущего
mov [eax].simbol,"&sim" инициализируем поле simbol текущего элемента mov [eax].id_state_cross.state ;номер состояния в поле descr.id_state_cross :теперь нужно определить адрес элемента в списке состояний state для выполнения дальнейших переходов и инициализации поля point_state push ebx mov ebx.head clc
(a@cycl :cmp [ebx].id_state_state,state je ml jc exit_m
mov ebx,[ebx].prev_state ;адрес предыдущего состояния в списке состояний cmpebx.O :последний элемент?
jne @@cycl stc
jmp @@cycl ml: :нашли!
mov [eax].poi nt_state,ebx exitjn: восстанавливаем регистры pop ebx pop eax endm
Далее приведена вспомогательная макрокоманда, которая по номеру состоя-ия определяет адрес соответствующего элемента в списке состояний. def_point_item_state macro N_state:REQ,head:REQ local @(acy,@@ml сохраняем регистры :вход:
:N_state - номер состояния
:head - имя ячейки, где хранится указатель на список состояний :выход: регистр ЕВХ - адрес элемента в списке состояний
mov eax.head
@@су: cmp [eax].id_state_state,N_state :ищем ... je @@ml ;нашли?
moveax,[eax].prev_state ;адрес следующего состояния cmp eax. О последний элемент? jne @@cy
stc ;cf=l если состояния с таким номером не существует
jmp @@су
@@ml: :нашли!
endm

Собственно программа prg02_ll.asm, выполняющая построение и инициализацию конечного автомата для распознавания лексемы вещественного числа в директивах dd, dq и dt, достаточно велика.


Книжный магазин