Сеть
В качестве примера рассмотрим фрагмент сканера для распознавания вещественных чисел в директивах ассемблера 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