1.htm

Сложные структуры данных (Часть 2)

Список

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

В общем случае под списком понимается линейно упорядоченная последовательность элементов данных, каждый из которых представляет собой совокупность одних и тех же полей. Упорядоченность элементов данных может быть двоякой:

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

Последовательные списки

Если количество элементов в списке постоянно, то в зависимости от их типа список вырождается в вектор, массив, структуру или таблицу. Отличие списка от этих структур данных — в длине. Для списков она является переменной. Поэтому программист, разбираясь с самими списками, должен уделить внимание тому, каким образом ему следует выделять память для хранения списка. Обычно языки высокого уровня имеют соответствующие средства в отличие от языка ассемблера. При написании программы на ассемблере программист должен уметь напрямую обратиться к операционной системе для решения проблемы динамического управления памятью. В примерах мы будем использовать соответствующие функции API Win32 как более современные, хотя для общего случая это не принципиально. В MS DOS имеются аналогичные функции (с точки зрения цели использования) — это функции 48h, 49h, 4ah прерывания 21h. Вопрос динамического управления памятью в силу своей важности в контексте настоящего рассмотрения требует особого внимания.
Отличие последовательных списков от связных состоит в том, что добавление и удаление элементов возможно только по концам структуры. В зависимости от алгоритма изменения различают такие виды последовательных списков, как стеки, очереди и деки. Эти виды списков обычно дополняются служебным дескриптором, который может содержать указатели на начало и конец области памяти, выделенной для списка, указатель на текущий элемент.
Зачем нужен, к примеру, стек? Необходимость использования своего стека в программе вполне вероятна, хотя бы исходя из того, что элементы, для хранения которых он создается, могут иметь размер, отличный от 2/4 байта.
Важно понимать, что внутренняя структура элемента практически не зависит от типа последовательного списка. Списки отличает набор операций, которые производятся над ними. Поэтому рассмотрим их отдельно для каждого типа последовательного списка.

Стек

Стек — последовательный список, в котором все включения и исключения элементов производятся на одном его конце — по принципу LIFO (Last In First Out — последним — пришел первым ушел). Для стека определены следующие операции:

создание стека;
включение элемента в стек;
исключение элемента из стека;
очистка стека;
проверка объема стека (числа элементов в стеке);
удаление стека.

Создание стека должно сопровождаться инициализацией специального дескриптора стека, который может содержать следующие поля: имя стека, адреса нижней и верхней границ стека, указатель на вершину стека.
Иллюстрацию организации и работы стека произведем на примере задачи, анализирующей правильность согласования скобок в некотором тексте. Причем условимся, что скобки могут быть нескольких видов: (), {}, [], <>. Программа реализована в виде приложения Win32 с использованием функций API Win32 для работы с кучей (из нее выделяется память для стека).

mov ecx,l_string
lea ebx.string
jmp cycl
e_xit: jmp exit cycl: jcxz e_xit
cmp byte ptr [ebx]."("
je m_push
cmp byte ptr [ebx],"["
je m_push
cmp byte ptr [ebx],"{"
je m_push
cmp byte ptr [ebx]."<"
je m_push
cmp byte ptr [ebx],")"
jneml извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp." ("
jne mes_error
jmp r_next ml: cmp byte ptr [ebx],"]"
jnem2 извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp," ["
jnemes_error
jmp r_next m2: cmp byte ptr [ebx],"}"
jnem3 ¦.извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_err6r
pop_stkchar_stk,<offset temp>
cmp temp."{"
jne mes_error
jmp r_next m3: cmp byte ptr [ebx],">"
jne rjiext извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp,"<"
jne mes__error
jmp r_next m_push: включение скобки в стек
pushstk char_stk.ebx r_next:add ebx,char_stk.si ze_i tern
dec ecx
jmp cycl mes_error: :вывод на экран сообщения об ошибке mes_e
jmp exitexit
exit:
определяем стек на пустоту
pop_stkchar_stk,<offset temp> jncmes_error :стек не пуст :вывод на экран сообщения mes_ok
exit_exit: :выход из приложения
delete_stk char_stk :удаляем блок памяти со стеком

Код, выполняющий работу со стеком, оформлен в виде макрокоманд. При необходимости код можно сделать еще более гибким. Для этого нужно использовать функцию API Win32 HeapReAl 1 ос, которая изменяет размер выделенного блока в сторону его увеличения или уменьшения. В принципе, полезной может оказаться операция определения объема стека, то есть количества элементов в нем. Попробуйте реализовать ее самостоятельно.

Очередь

Очередь — последовательный список, в котором включение элементов производится на одном конце, а исключение на другом, то есть по принципу FIFO (First In First Out — первым пришел — первым ушел). Сторона очереди, на которой производится включение элементов, называется хвостом. Соответственно, противоположная сторона — голова очереди. Очередь описывается дескриптором, который может содержать поля: имя очереди, адреса верхней и нижней границ области памяти, выделенной для очереди, указатели на голову и хвост. Набор операций для очереди:

создание очереди (create_que);
включение элемента в очередь (push_que);
исключение элемента из очереди (popque);
проверка пустоты очереди (TestEmptyQue);
очистка очереди без освобождения памяти для нее (initque);
удаление очереди (delete_que).

При помощи очереди удобно моделировать некоторые обслуживающие действия, например это может быть некоторая очередь запросов к критическому ресурсу или очереди заданий на обработку. К очереди так же, как и стеку, применимы такие параметры, как емкость очереди и размер элемента очереди.
На практике используются очереди двух типов — простые и кольцевые. Очередь обслуживается двумя указателями — головы (Р,) и хвоста очереди (Р2). Указатель головы Р идентифицирует самый старый элемент очереди, указатель хвоста — первый свободный слот после последнего включенного в очередь элемента. Сами элементы физически по очереди не двигаются. Меняется лишь значение указателей. При включении в очередь новый элемент заносится в ячейку очереди, на которую указывает Р2. Операция исключения подразумевает извлечение элемента из ячейки очереди, указываемой Р,. Кроме извлечения элемента операция исключения производит корректировку указателя Р, так, чтобы он указывал на очередной самый старый элемент очереди. Таким образом, Указатель хвоста простой очереди всегда указывает на свободную ячейку очере-Ди и рано или поздно он выйдет за границы блока, выделенного для очереди. И это случится несмотря на то, что в очереди могут быть свободные ячейки
(ячейки А. Чтобы исключить это явление, очередь организуется по принципу кольца. В обоих способах организации очереди важно правильно определить ее емкость. Недостаточный объем очереди может привести в определенный момент к ее переполнению, что чревато потерей новых элементов, претендующих на включение в очередь.
Для иллюстрации порядка организации и работы с очередью рассмотрим пример. Пусть имеется строка символов, которая следующим образом моделирует некоторую вычислительную ситуацию: символы букв означают запросы на некоторый ресурс и подлежат постановке в очередь (имеющую ограниченный размер). Если среди символов встречаются символы цифр в диапазоне 1-9, то это означает, что необходимо изъять из очереди соответствующее значению цифры количество элементов. Если очередь полна, а символов цифр все нет, то происходит потеря заявок (символов букв). В нашей программе будем считать, что очередь кольцевая и ее переполнение помимо потери новых элементов приводит к выводу соответствующего сообщения. Для кольцевой очереди возможны следующие соотношения значений указателей Р, и Р2: Pj < Р2, Pj = Р2 (пустая очередь), Р, > Р2. Память для очереди в нашей задаче выделяется динамически средствами API Win32.
Заметим, что исходя из потребностей конкретной задачи можно изменить дисциплину обслуживания очереди. Например, установить, что при переполнении очереди потере подлежат старые заявки (в голове очереди) и т. п.

jb ml cmpa1.39h
ja ml
xor есх.есх:удгляем из очереди элементы
mov cl,al
subcl,30h преобразуем символ цифры в двоичный эквивалент ш2: pop_quechar_que.<offset temp>
jc cycl ;если очередь пуста
1 oop m2
jmpcycl ml: добавляем элементы в очередь
mov temp,a 1
push_que char_que. <offset temp>
jnc cycl ;ycnex ;вывод на экран сообщения об ошибке - отсутствие места в очереди
jmp cycl
;выход из приложения exit: :удаляем блок памяти с очередью
delete_que char_que

Как и в случае со стеком, код, выполняющий работу с очередью, оформлен в виде макрокоманд. Программа выдает единственное Сообщение о переполнении очереди. Чтобы наблюдать работу программы в динамике, необходимо выполнить следующие действия.

Загрузить исполняемый модуль программы в отладчик td32.exe.
Отследить адрес начала блока памяти, который будет выделен системой по нашему запросу для размещения очереди. Для этого подвергните пошаговому выполнению в окне CPU содержимое макрокоманды createque.
Выяснив адрес начала блока для размещения очереди, отобразите его в окне Dump и нажмите клавишу F7 или F8. Не отпуская этой клавиши, наблюдайте за тем, как изменяется состояние очереди.

Дека

Дека — очередь с двумя концами. Дека является последовательным списком, в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Логическая и физическая структуры деки аналогичны обычной очереди, но относительно деки следует говорить не о хвосте и голове, а о правом и левом конце очереди. Реализацию операций включения и исключения в деку следует также дополнить признаками левого или правого конца. В литературе можно встретить понятие дека с ограниченным вводом. Это дека, в которой элементы могут вставляться в одном конце, а удаляться с обоих.

Связные списки

Связный список — набор элементов, каждый из которых структурно состоит из двух частей — содержательной и связующей. Содержательная часть представляет собой собственно данные или указатель на область памяти, где эти данные
содержатся. Связующая часть предназначена для связи элементов в списке и определяет очередность их следования. Благодаря связующей части в каждом из элементов становятся возможными «путешествия» по списку путем последовательных переходов от одного элемента к другому.
В отличие от последовательного списка связный список относится к динамическим структурам данных. Для них характерны непредсказуемость в числе элементов, которое может быть нулевым, а может и ограничиваться объемом доступной памяти. Другая характеристика связного списка — необязательная физическая смежность элементов в памяти.
Относительно связующей части различают следующие типы связных списков.

Односвязный список — список, начало которого определяется указателем начала, а каждый элемент списка содержит указатель на следующий элемент. Последний элемент должен содержать признак конца списка или указатель на первый элемент списка. В последнем случае мы имеем одно-связный кольцевой список. Преимущество последнего состоит в том, что просмотр всех элементов списка можно начинать с любого элемента, а не только с головы. Более того, в случае кольцевого односвязного списка указателем его начала может быть любой элемент списка. Этот вид списка всегда линейный, так как однозначно задает порядок своего просмотра.
Двусвязный список — список, связующая часть которого состоит из двух указателей — на предыдущий и последующий элементы. Начало и конец списка определяются отдельными указателями. Последние элементы дву-связного списка в каждом из направлений просмотра содержат признаки конца. Если замкнуть эти указатели друг на друга, то мы получим кольцевой двусвязный список. В этом случае потребность в указателе конца списка отпадает. Этот вид списка может быть как линейным (иметь одинаковый порядок просмотра в обоих направлениях), так и нелинейным (второй указатель каждого элемента списка задает порядок просмотра, который не является обратным порядку, устанавливаемому первым указателем).
Многосвязный список — список, связующая часть элементов которого в общем случае содержит произвольное количество указателей. В этом виде списка каждый элемент входит в такое количество односвязных списков, сколько он имеет в себе полей связи.

В общем случае для связанных списков определены следующие операции:

создание связного списка;
включение элемента в связный список, в том числе и после (перед) определенным элементом;
доступ к определенному элементу связного списка (поиск в списке);
исключение элемента из связного списка;
упорядочение (перестройка) связного списка;
очистка связного списка;
проверка объема связного списка (числа элементов в связном списке);
объединение нескольких списков в один;
разбиение одного списка на несколько;
копирование списка;
удаление связного списка.

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

Односвязные списки

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

:prg3_10.asm - пример реализации односвязных списков с помощью двух массивов
:Вход: массивы с данными и указателями.
:Выход: нет. В динамике работа программы наблюдается под управлением отладчика.
.data
masdb 0.55.0.12.0.42.94.0.18.0.06.67.0.58.46 :задаем массив
n=$-mas
point db 0 указатель списка - индекс первого ненулевого элемента в mas
masjraint db n dup (0) определим массив указателей
.code
lea si.mas :b si адрес mas_point
xorbx.bx :b bx будут индексы - кандидаты на включение в массив указателей :ищем первый ненулевой элемент
movcx,n-l cycll: cmpbyte ptr [si][bx].O
jneml :если нулевые элементы
inc bx
loop cycll
jmpexit ;если нет ненулевых элементов ml: mov point.Ы :запоминаем индекс первого ненулевого в point
movdi.bx ;в di индекс предыдущего ненулевого ;просматриваем далее (сх тот же)
inc bx сус12: cmpbyte ptr [si][bx].O
je m2 ;нулевой => пропускаем :формируем индекс
movmas_point[di].bl ;индекс следующего ненулевого в элемент mas_point предыдущего
movdi.bx :запоминаем индекс ненулевого
т2: inc bx
loop cycl2
mov mas_point[di].Offh ;индекс следующего ненулевого в элемент mas_point ;выход :а теперь подсчитаем единичные, не просматривая все. - результат в ах
хог ах.ах
cmp point.0
je exit,
inc ax
mov bl .point cycl3: cmp mas_point[bx].Offh
je exit
inc ax
mov Ы ,mas_point[bx]
jmpcycl3 результат подсчета в ах. с ним нужно что-то делать, иначе он будет испорчен

Если количество нулевых элементов велико, то можно сократить объем хранения данного одномерного массива в памяти (см. ниже материал о разреженных массивах).
Кстати, в качестве еще одного реального примера использования односвязных списков вспомните, как реализован учет распределения дискового пространства в файловой системе MS DOS (FAT).
Далее рассмотрим другой, более естественный вариант организации связанного списка. Его элементы содержат как содержательную, так и связующую части.
Рассуждения относительно содержательной части пока опустим — они напрямую зависят от конкретной задачи. Уделим внимание связующей части. Понятно, что это адреса. Но какие? Можно считать, что существуют два типа адресов, которые могут находиться в связующей части: абсолютные и относительные. Абсолютный адрес в конкретном элементе списка — это, по сути, смещение данного элемента относительно начала сегмента данных или блока данных при динамическом выделении памяти и принципиально он лишь логически связан со списком. Относительный адрес формируется исходя из внутренней нумерации элементов в списке и имеет смысл лишь в контексте работы с ним. Пример относительной нумерации рассмотрен выше при организации списка с помощью двух массивов. Поэтому далее этот способ адресации мы рассматривать не будем, а сосредоточимся на абсолютной адресации.
Для начала разработаем код, реализующий применительно к односвязным спискам основные из обозначенных нами выше операций со связанными списками. Односвязные списки часто формируют с головы, то есть включение новых элементов производится в голову списка.
Первая проблема — выделение памяти для списка. Это можно делать либо статическим способом, зарезервировав место в сегменте данных, либо динамически, то есть так, как мы это делали выше при реализации операций со стеками и очередями. Недостатки первого способа очевидны, хотя в реализации он очень прост. Гораздо интереснее и предпочтительнее второй способ, который предполагает использование кучи для хранения связанного списка. Для придания боль-Шей реалистичности изложению рассмотрим простую задачу: ввести с клавиатуры
символьную строку, ограниченную символом "." (точка), и распечатать ее в обратном порядке.

:prgl5_102.asm - реализация программы инвертирования строки с односвязными списками
:Вход: символьная строка с клавиатуры.
:Выход: вывод на экран инвертированной обратной строки.
;.........
itemjist struc :элемент списка
next dd 0 :адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends
.data
mas db 80 dup С ') :в эту строку вводим
mas revdb 80 dup (' ') :из этой строки выводим
len mas rev=$-mas rev
mesl db 'Введите строку символов (до 80) для инвертирования (с точкой на конце):'
len_mesl=$-mesl
.code
списание макрокоманд работы со связанным списком;
createjist macro descr:REQ.head:REQ
: создание списка - формирование головы списка и первого элемента
;.........
endm
addjist macro descr:REQ.head:REQ.H_Head:REQ
добавление элемента в связанный список
endm
createjtem macro descr:REQ.H_Head:REQ
;создание элемента в куче для последующего добавления в связанный список
¦.........
endm
start proc near :точка входа в программу:
:вывод строки текста - приглашения на ввод строки для инвертирования !.........
:вводим строку в mas
:.........
;создаем связанный список createjist itemJist.HeadJist :первый элемент обрабатываем отдельно
leaesi.mas
moval.[esi]
cmp al."."
je rev_out
mov [ebx].info.al
:вводим остальные символы строки с клавиатуры до тех пор. пока не встретится "." cycl: incesi
mov al.[esi]
cmp al,"."
je rev_out
addj i st i temj i st. HeadJ i st. Hand_Head
mov [ebx].info.al
jmp cycl
:вывод строки в обратном порядке rev_out: mov esi.offset mas_rev
mov ebx,HeadJist cycl2: mov al .[ebx].info
mov [esil.al
inc esi
mov ebx.[ebx].next
cmpebx.Offffffffh
jne cycl2 ; выводим инвертированную строку на экран

Недостаток такого способа построения списка — в порядке включения элементов. Хорошо видно, что он обратный порядку поступления элементов. Для исправления данной ситуации можно, конечно, ввести еще один указатель на последний элемент списка. Есть и другой вариант — организация двусвязного списка. Уделим теперь внимание другим операциям с односвязным списком.

Включение в список

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

itemjist struc элемент списка
next dd 0 ; адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
:а адрес нового элемента - в ЕАХ
mov edx.[ebx].next
mov [eax].next.edx mov [ebx].next.eax

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

itemjist struc :элемент списка
next dd 0 :адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends

предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.

:а адрес нового элемента - в ЕАХ
mov edx.[ebx].next mov [eax].next.edx mov edx.[ebx].info mov [eax].info.edx mov [ebx].next.eax
:осталось заполнить поле info нового элемента

Но если производится включение в упорядоченный список, то логичнее работать с двумя указателями — на текущий и предыдущий элементы списка, так как это показано ниже. При этом предполагается, что новый элемент создается описанной в предыдущей программе макрокомандой create_item.

описание элемента списка
item_list struc :элемент списка
next dd 0 ; адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends
.data
ins_itern itemjist <.15> вставляемый элемент (поле info содержит значение -
:критерий вставки)
Headjist dd Offffffffh указатель на начало списка (Offffffffh - список пуст) Hand_Head dd 0 ;переменная, в которой хранится дескриптор кучи
.code
;здесь мы инициализировали и работали со списком
;список упорядочен по возрастанию
:ищем место вставки
;1 - выбираем первую ячейку
mov ebx.HeadJist .
хогеах.еах ;в еах будет указатель на предыдущий элемент ;2 последняя ячейка? ml: cmpebx.Offffffffh
je noJtern :список пустой :3 - новая ячейка до очередной выбранной? ovd1.CebxJ.info cmpdl.ins_item.info ja nextjtem cmpeax. jne into ;вставить первым
createjtem i temj i st. H_Head :макрос создания элемента в куче mov Headjist.edx :адрес нового в голову списка
mov [edx].next.ebx ;настройка указателей jmpexit :на выход
вставить внутрь списка
into: createjtem item_list.H_Head :макрос создания элемента в куче mov [еах].next.edx :адрес нового в поле next предыдущего mov [edx].next.ebx :в поле next нового адрес текущего jmp exit :на выход
: выбор очередного элемента nextjtem: moveax.ebx:aflpec текущего в еах mov ebx. [ebx].next jmp ml
:4 - список пуст или нет больше элементов no J tern: cmpeax.O
jne no_empty :список непустой :список пуст
mov Headjlist.edx :адрес нового в голову списка
mov [edx].next.Offffffffh:это будет пока единственный элемент в списке
jmpexit :на выход
no_empty: :список не пуст - новая ячейка в конец списка
mov [еах].next.edx
mov [edx].next.Offffffffh:это будет последний элемент в списке
exit: :общий выход

Исключение из списка

Алгоритм предполагает наличие двух указателей — на текущую и предыдущую ячейки. Для разнообразия этот алгоритм предполагает прямой порядок следования элементов в списке. В качестве упражнения читателю предлагается, если нужно, переписать приводимый ниже фрагмент для обратного порядка следования элементов.

:описание элемента списка
itemjist struc -.элемент списка
next dd 0 :адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends
.data
search_b db 0 критерий поиска (поле info экземпляра структуры itemjist)
Headjist dd Offffffffh указатель на начало списка (Offffffffh - список пуст)
.code
:здесь мы инициализировали и работали со списком
:ищеи ячейку, подлежащую удалению ;1 - выбираем первую ячейку
mov ebx.HeadJist
хогеах,еах;в еах будет указатель на предыдущую ячейку ;2 последняя ячейка?
cmpebx.Offffffffh
je no J tem cycl: cmp [ebx].info.search_b сравниваем с критерием поиска
jnechjiextjtem : нашли? ;да. нашли!
cmpeax.
jne no_fist:зто не первая ячейка :первая ячейка (?) »> изменяем указатель на начало списка и на выход
mov edx.[ebx].next
mov Headjist.edx
jmpexit no_fist: mov [eax].next.ebx перенастраиваем указатели -> элемент удален
jmpexit ;на выход
:выбор следующего элемента ch_nextjtem; mov eax.ebx : запомним адрес текущей ячейки в указателе на предыдущую
mov ebx.[ebx].next ;адрес следующего элемента в ebx
jmp cycl
:обработка ситуации отсутствия элемента nojtem:

Остальные обозначенные нами выше операции очевидны и не должны вызвать у читателя трудностей в реализации.
Другой интересный и полезный пример использования односвязных списков — работа с разреженными массивами. Разреженные массивы представляют собой массивы, у которых много нулевых элементов. Представить разреженный массив можно двумя способами: с использованием циклических списков с двумя полями связи и с использованием хэш-таблицы.
С разреженными массивами можно работать, используя методы хэширования. Для начала нужно определиться с максимальным размером хэш-таблицы М для хранения разреженного массива. Это значение будет зависеть от максимально возможного количества ненулевых элементов. Ключом для доступа к элементу хэш-таблицы выступает пара индексов (i,j), где i = l..p, j = l..q. Числовое значение ключа вычисляется по одной из следующих формул
Остальные действия зависят от избранного способа вычисления хэш-функции (см. выше соответствующий раздел о методах хэширования).

Двусвязные списки

Двусвязный список представляет собой список, связующая часть которого состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое — на правого. Кроме этого, со списком связаны два указателя — на голову и хвост списка (рис. 2.13, сверху). Более удобным может быть представление списка, когда функции этих указателей выполняет один из элементов списка, одно из полей связи которого указывает на последний элемент списка (рис. 2.13, снизу).

Рис 2.13. Схемы организации двухсвязных списков

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

start proc near :точка входа в программу ,
:вывод строки текста - приглашение на ввод сроки для инвертирования :вводим строку текста для инвертирования
.-создаем связанный список, для чего инициализируем заголовок списка
create_doubly_li st Doubly_Head_l i st :вводим символы строки с клавиатуры до тех пор. пока не встретится "."
lea esi.mas cycl: mov al .[esi]
cmpal.V
je rev_out
add_li st i tem_l i st.Doubly_Head_li st.Hand_Head
mov [ebx].info.al
incesi
jmp cycl rev_out: ;вывод строки в обратном порядке
mov esi.offset mas_rev
mov ebx.DoublyJHeadJ i st. 1 ast cycl2: mova 1 .[ebx].info
mov [esi].al
incesi
mov ebx,[ebx].prev
cmp [ebx].info.Offh :дошли до последнего элемента списка"?
jnecycl2
:выводим инвертированную строку на экран :......

Включение в список

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

itemjist struc ; элемент списка
prev dd 0 :адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 :адрес следующего элемента
ends
;предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
:а адрес нового элемента - в ЕАХ
push [ebx].next
pop [eax].next :[ebx].next->[eax].next mcv [eax].prev.ebx;адрес предыд. эл-та->[еах].ргеу mov [ebx].next.eax:адрес след. эл-та->[еЬх].пех1
:будьте внимательны - меняем указатель предыд. эл-та в следующем за новым элементом mov ebx.[eax].next;адрес след. эл-та-KebxJ.next mov [ebx].prev.eax;адрес предыд. эл-та->[еЬх].ргеу

Включение элемента перед локализованным выполняется аналогично. Простота работы с двусвязными списками в отличие от односвязных достигается за счет отсутствия проблем с передвижением по списку в обе стороны.

Исключение из списка

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

itemjist struc ;элемент списка
prev dd 0 ;адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 -.адрес следующего элемента
ends
предполагаем, что адрес локализованного элемента находится в регистре ЕВХ
mov eax.[ebx].prev;адрес предыд. эл-та->еах
push [ebx].next
pop [eax].next
mov eax.[ebx].next ;адрес следующ. эл-та->еах
push [ebx].prev
pop [eax].prev

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

Рис. 2.14. Логическая структура нелинейного двусвязного списка

Сеть

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

Выше мы уделили достаточно внимания работе с матрицами и списками, и это сделано не случайно. Еще более обобщая понятие списка, мы придем к определению многосвязного списка, для которого характерно наличие произвольного количества указателей на другие элементы списка. Можно говорить, что каждый конкретный элемент входит в такое количество односвязных списков, сколько у него есть указателей. Многосвязный список получается «прошитым» односвяз-ными списками, поэтому такие многосвязные списки называют прошитыми, или плексами. С помощью многосвязных списков можно моделировать такую структуру данных, как сеть или граф. Частный случай сети — дерево. Рассмотрим варианты представления в памяти компьютера этих структур данных.
Сетью называется кортеж 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, достаточно велика.

Дерево

То, что неясно, следует выяснить. То, что трудно творить, следует делать с великой настойчивостью.
Конфуций Деревом называется сетевая структура, обладающая следующими свойствами:

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

Рис. 2.18. Изображение дерева и соответствующего ему связного списка

Следуя терминологии дерева, можно ввести некоторые определения, касающиеся его структуры. Ребра, соединяющие смежные узлы дерева, называются ветвями. Оконечные узлы дерева, которые не ссылаются на другие узлы, называются листьями. Другие узлы дерева, за исключением корня, называются узлами ветвления. Две смежные вершины дерева состоят в «родственных» отношениях. Вершина X, находящаяся на более высоком уровне дерева по отношению к вершине Y, называется отцом. Соответственно, вершина Y по отношению к X называется сыном. Если вершина X имеет несколько сыновей, то по отношению друг к другу последних называются братьями. В принципе, вместо этих терминов можно использовать следующие: родитель, потомок и т. п. Классификация деревьев производится по степени исхода ветвей из узлов деревьев. Дерево называется m-арным, если степень исхода его узлов не превышает значения m.
В практических приложениях широко используется специальный класс деревьев — бинарные деревья. Бинарное дерево — m-арное дерево при m = 2. Это означает, что степень исхода его вершин не превышает 2. В случае когда m равно 0 или 2, имеет место полное бинарное дерево. Важно то, что любое m-арное дерево можно преобразовать в эквивалентное ему бинарное дерево. В свою очередь, в силу ограничений по степени исхода вершин бинарное дерево легче представлять в памяти и обрабатывать. По этой причине мы основное внимание уделим работе с бинарными деревьями.
Перечислим операции, которые обычно выполняются при работе с деревьями:

представление дерева в памяти;
обход или прохождение дерева (поиск в дереве);
включение в дерево и исключение из дерева определенного узла;
балансировка дерева и операции со сбалансированным деревом.

Представление дерева в памяти

Естественным является представление дерева в памяти компьютера в форме многосвязного списка. Это наиболее динамичное представление. В случае постоянства структуры дерева могут использоваться и другие способы представления дерева в памяти, например в виде массива, как это было во время рассмотрения нами двоичной сортировки. В случае представления дерева в форме многосвязного списка указатель на начало списка должен указывать на элемент списка, являющийся корнем. В свою очередь, узлы дерева связываются между собой так, чтобы корень дерева был связан с корнями его поддеревьев и т. д. При этом можно выделить три случая.

Связь узлов в дереве осуществляется таким образом (рис. 2.19, а), что каждый узел-сын содержит ссылку на вышестоящий узел (узел-отца). В этом случае корень будет содержать нулевой указатель на месте соответствующего указателя. Имея такой тип связей узлов в дереве, можно подниматься от нижних уровней дерева к его корню, что может быть полезным при реализации определенных видов синтаксического разбора.
Каждый узел дерева содержит указатели на свои поддеревья (рис. 2.19, б), то есть каждый отец ссылается на своих сыновей. Этот способ применим для представления деревьев небольшой арности, например бинарных деревьев. Имея указатель на корень дерева, можно достичь любого узла дерева.
Каждый узел дерева ссылается на свои поддеревья с помощью списка, при этом каждый узел содержит два указателя — для представления списка поддеревьев и для связывания узлов в этот список (рис. 2.19, е).

Рис. 2.19. Варианты связи узлов дерева между собой

Бинарное дерево обычно представляется с помощью второго способа (рис. 2.19, б). Минимально для представления узла достаточно трех полей: содержательной части узла и двух указателей — на левого (старшего) и правого (младшего) сыновей. Таким образом, представить бинарное двоичное дерево можно с помощью нелинейного двусвязного списка. Структуру узла в программе можно описать так:

node_tree struc ;узел дерева
simbol db 0 содержательная часть
l_son dd 0 указатель на старшего (левого) сына
r_son dd 0 указатель на младшего (правого) сына
ends

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

Построение двоичного дерева

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

:prg02_12.asm - программа построения и инициализации двоичного дерева.
:Вход: произвольный массив чисел в памяти.
:Выход: двоичное дерево в памяти.
;объявления структур:
node_tree struc :узел дерева
simbol db 0 содержательная часть
l_son dd 0 указатель на старшего (левого) сына
r_son dd 0 указатель на младшего (правого) сына
ends
.data
mas db 37h.12h.8h.65h.4h.54h.llh.02h.32h.5h.4h.87h.7h.21h.65h.45h.22h.
Ilh,77h.51h,26h.73h.35h.l2h.49h.37h.52h l_mas=$-mas
.code
BuildBinTree proc
формируем корень дерева и указатель на дерево HeadTree
:для размещения дерева используем кучу, выделяемую процессу по умолчанию (1 Мбайт).
:но при необходимости можно создать и доп. кучу с помощью HeapCreate
iHANDLE GetProcessHeap (VOID):
call GetProcessHeap
movHand_Head,eax сохраняем дескриптор ;запрашиваем и инициализируем блок памяти из кучи для корня дерева:
xorebx.ebx :здесь будет указатель на предыдущий узел ;LPVOID HeapAllос(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes):
push type node_tree :размер структуры для узла дерева
push 0 ;флаги не задаем
push eax :описатель кучи (он же в Hand_Head)
call НеарАПос
mov HeadTree.eax запоминаем указатель на корень дерева
mov ebx.eax :и в ebx :подчистим выделенную область памяти в куче
push ds
pop es
mov edi .eax
mov ecx.type node_tree
mov al .0 rep stosb
leaesi.mas ;первое число из mas в корень дерева
lodsb ;число в al
mov [ebx].simbol.al
mov ecx.l_mas-l @@cycll: ;далее в цикле работаем с деревом и массивом mas
push ecx ;НеарА11ос портит ecx. возвращая в нем некоторое значение ;запрашиваем блок памяти из кучи для узла дерева: ;LPVOID HeapAllос(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes);
push type node_tree:размер структуры для узла дерева
push 0 :флаги не задаем
push HandJHead :описатель кучи
call НеарАПос
pop ecx
mov ebx.eax запоминаем указатель на узел дерева в ebx
mov NewNode.eax :и во врем, перем. ¦подчистим выделенную область памяти в куче
movedi.eax
push ecx
mov ecx.type node_tree
mov al .0 rep stosb
pop ecx
:читаем очередное число из mas и записываем его в новый узел lodsb :число в al mov [ebx].simbol,al
;ищем место в дереве согласно условиям упорядочивания ;и настраиваем указатели в узлах дерева
mov ebx.HeadTree m_search: cmpal.[ebx].simbol mov edi .ebxпродублируем
jae ml :если al >= [ebxj.simbol :если меньше, то идем по левой ветке
mov ebx.[ebx].l_son
cmp ebx.O
jnem_search ;если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].l_son.ebx
jmp end_cycl 1
:если больше или равно, то по правой ml: mov ebx. [ebx]. r_son
cmp ebx.O
jnem_search :если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].r_son.ebx end_cycll: loop @@cycll
ret ;двоичное дерево поиска построено BuildBinTree endp start proc near :точка входа в программу:
call BuildBinTree

В результате мы должны получить дерево, обойдя которое в определенном порядке, получим упорядоченный массив чисел:

2h.4h.4h,5h.7h,8h.nh.llh,12h.l2h.21h.22h.26h.32h,35h,37h.37h.4*5h.49h.51h.52h. 54h.65h.65h.73h.77h.87h.

бедимся в этом, разработав программу обхода двоичного дерева.

Обход узлов дерева

Возможны три варианта обхода дерева:

сверху вниз — корень, левое поддерево, правое поддерево;
слева направо — левое поддерево, корень, правое поддерево;
снизу вверх — левое поддерево, правое поддерево, корень.

Понятно, что процедура обхода рекурсивна. Под термином «обход дерева» понимается то, что в соответствии с одним из определенных выше вариантов посещается каждый узел дерева и с его содержательной частью выполняются некоторые действия. Для нашей задачи подходит только второй вариант, так как только в этом случае порядок посещения узлов будет соответствовать упорядоченному массиву. В качестве полезной работы будем извлекать значение из узла двоичного дерева и выводить его в массив в памяти. Отметим особенности функции LRBeat, производящей обход дерева. Во-первых, она рекурсивная, во-вторых, в ней для хранения адресов узлов используется свой собственный стек. Стек, поддерживаемый на уровне архитектуры микропроцессора, используется для работы процедурного механизма, и мы со своими проблемами только «путаемся у него под ногами».

:prg02_13.asm - программа обхода двоичного дерева поиска (слева направо). ;Вход: произвольный масиив чисел в памяти. :Выход: двоичное дерево в памяти.
объявления структур: nodejxee struc :узел дерева
ends
: для программного стека
desc_stk struc :дескриптор стека
ends
•.описание макрокоманд работы со стеком:
create_stk macro HandHead:REQ.descr:REQ.Si zeStk:=<256>
¦.создание стека
endm
push_stk macro descr:REQ.rg_item:REQ
добавление элемента в стек
endm
pop_stkmacro descr:REQ. rg_item:REQ
извлечение элемента из стека
endm
.data
исходный массив:
masdb 37h.l2h,8h.65h.4h.54h.llh.02h.32h,5h,4h,87h.7h.21h.65h.45h.22h,llh.77h.
51h.26h.73h.35h.12h.49h.37h.52h l_mas=$-mas
упорядоченный массив (результат см. в отладчике): ordered array db 1 mas dup (0)
doubleWord_stkdesc_stk <> -.дескриптор стека
count call dd 0 :счетчик количества рекурсивного вызова процедуры
.code
BuildBinTree proc ;см. prg02_12.asm
:двоичное дерево поиска построено
ret
BuildBinTree endp LRBeat proc
:рекурсивная процедура обхода дерева - слева направо :(левое поддерево, корень, правое поддерево)
inc count_call ;подсчет количества вызовов процедуры
:(для согласования количества записей и извлечений из стека)
cmp ebx.O
je @@exit_p
mov ebx.[ebx].l_son
cmp ebx, 0
je @@ml
push_stk doubleWord_stk.ebx mini: call LRBeat
pop stkdoubleWord stk.ebx
r r_ —
jnc @@m2
:подчистим за собой стек и на выход raovecx.count_call
dec ecx
pop NewNode:pop "в никуда"
loop $-6
jmp @@exi t_p @@m2: moval,[ebx].simbol
stosb
mov ebx, [ebx]. r_son cmp ebx.O je @@ml push stk doubleWord stk.ebx
c'all LRBeat " @@exit_p: deccount_call
ret
LRBeat endp start proc near ;точка входа в программу:
call BuildBinTree :формируем двоичное дерево поиска ;обходим узлы двоичного дерева слева направо и извлекаем значения ;из содержательной части, нам понадобится свой стек (размер (256 байт) нас устроит. :но макроопределение мы подкорректировали)
create_stk Hand_Head.doubieWord_stk
push ds
pop es
lea edi.ordered_array
mov ebx.HeadTree push_stk doubleWord_stk.ebx указатель на корень в наш стек
call LRBeat

Еще одно замечание о рекурсивной процедуре. Реализация рекурсивное™ в программах ассемблера лишена той комфортности, которая характерна для языков высокого уровня. При реализации рекурсивной процедуры LRBeat возникает несбалансированность стека, в результате после последнего ее выполнения на вершине стека лежит не тот адрес и команда RET отрабатывает неверно. Для устранения подобного эффекта нужно вводить корректировочный код, суть которого заключается в следующем. Процедура LRBeat подсчитывает количество обращений к ней и легальных, то есть через команду RET, выходов из нее. При последнем выполнении анализируется счетчик обращений countcal 1 и производится корректировка стека.
Для полноты изложения осталось только показать, как изменится процедур;!. LRBeat для других вариантов обхода дерева.
Построенное выше бинарное дерево теперь можно использовать для дальнейших операций, в частности поиска. Для достижения максимальной эффективности поиска необходимо, чтобы дерево было сбалансированным. Так, дерево считается идеально сбалансированным, если число вершин в его левых и правых поддеревьях отличается не более чем на 1. Более подробные сведения о сбалансированных деревьях вы можете получить, изучая соответствующую литературу. Здесь же будем считать, что сбалансированное дерево уже построено. Разберемся с тем, как производить включение и исключение узлов в подобном, заранее построенном упорядоченном дереве.

Включение узла в упорядоченное бинарное дерево

Задача включения узла в дерево уже была решена нами при построении дерева. Осталось оформить соответствующий фрагмент программы в виде отдельной процедуры addNodeTree. Чтобы не дублировать код, разработаем рекурсивный вариант процедуры включения — addNodeTree. Он хоть и не так нагляден, как нерекурсивный вариант кода в программе prg_03.asm, но выглядит достаточно профессионально. Текст процедуры addNodeTree вынесен на дискету.
Работу процедуры addNodeTree можно проверить с помощью программы prgO2_ 13.asm (в ПРИМЕРе ей соответствует программа prgO2_14.asm).
В результате проведенных работ мы получили дублирование кода, строящего и дополняющего дерево. В принципе для строительства и включения в дерево достаточно одной процедуры addNodeTree. Но в учебных целях мы ничего изменять не будем, чтобы иметь два варианта строительства дерева — рекурсивный и не рекурсивный. При необходимости читатель сам определит, какой из вариантов более всего отвечает его задаче и в соответствии с этим доработает этот код.
Исключение узла из упорядоченного бинарного дерева
Эта процедура более сложная. Причиной тому то обстоятельство, что существует несколько вариантов расположения исключаемого узла в дереве: узел является листом, узел имеет одного потомка и узел имеет двух потомков. Самый непростой случай — последний. Процедура удаления элемента del NodeTree является рекурсивной и, более того, содержит вложенную процедуру del, которая также является рекурсивной. Текст процедуры del NodeTree вынесен на дискету.
Работу этой процедуры можно проверить с помощью программы prg02_13.asm (в ПРИМЕРе ей соответствует программа prg02_15.asm).
Графически процесс исключения из дерева выглядит так, как показано на рис. 2.20. Исключаемый узел помечен стрелкой.

Рис. 2.20. Исключение из дерева

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

Лексикографическое дерево

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

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

Для простоты преобразования положим, что каждое слово может встречаться в тексте не более 9 раз. Длина слова — не более 10 символов (для экономии места контроль количества вводимых символов не производится). Слова в файле разделяются одним пробелом. Также для сокращения текста программы считаем, что имя входного файла фиксировано — in.File.txt.
Программа построения лексикографического дерева prg_12_78.asm имеет достаточно большой размер, в связи с чем ее текст вынесен на дискету.
Бинарные деревья — не единственный вид деревьев, которые могут быть использованы в ваших программах. В литературе можно ознакомиться с представлениями деревьев, отличных от бинарных. Мы не будем развивать далее проблему представления деревьев, хотя, честно говоря, очень хочется. За кадром остались такие важные проблемы, как балансировка деревьев, работа с В-деревь-ями и т. д. После столь обстоятельного введения и наличия соответствующей литературы, вы сможете без особого труда решить эти и другие проблемы. Тем более, что на худой конец любое дерево можно преобразовать в бинарное и работать с ним, используя приемы, описанные в настоящем разделе.
В преддверии рассмотрения следующего материала отметим, что разработанная в этом разделе программа будет очень полезна в процессе построения различных транслирующих программ, частным случаем которых являются компиляторы. Лексикографические деревья можно с успехом использовать в процессе работы сканера, задачей которого, в частности, является выяснение принадлежности некоторого идентификатора к ключевым словам некоторого языка. Введите в файл infile.txt список ключевых слов (разделенных одним пробелом), запустите программу и в памяти вы получите лексикографическое дерево.

Элементы компиляции программ

Большинство людей считают компьютеры математическими машинами,
разработанными для выполнения численных расчетов. В действительности
же компьютеры представляют собой языковые машины: основа их
могущества заключается в способности манипулировать лингвистическими
знаками — символами, которым приписан некоторый смысл.
Терри Виноград

В процессе изложения материала данного раздела мы получили достаточные знания для того, чтобы с пользой применить их на примере достаточно сложной задачи. Одной из таких задач традиционно считается разработка компилятора (интерпретатора). Тем более что у нас есть для этого повод — необходимость создания препроцессора для новых команд микропроцессоров Pentium Pro/II/IH/IV (см. главу 10). Исходя из этого задачу будем решать поэтапно: на первом этапе разберемся с общими вопросами из теории компиляции, которые будут полезны в контексте решения нашей задачи, а затем, на втором этапе, разработаем сам препроцессор. В соответствии с этими этапами весь материал также будет разбит на две части и рассмотрен в разных главах настоящей книги. Но для того, чтобы все наше строение было логически связанным, мы сформулируем для каждого из этапов свои целевые установки. Цель первого этапа — научиться проводить распознавание и синтаксический разбор одиночных предложений, принадлежащих некоторому языку. Цель второго этапа — применить полученные знания для обработки некоторой программы на языке ассемблера, содержащей новые команды микропроцессоров Pentium Pro/II/III, о которых транслятор ассемблера «не знает». В результате этой обработки новые команды будут замещены эмулирующим кодом. Конечно, кто-то возразит — можно попытаться достать соответствующий «patch» к транслятору, что позволит ему непосредственно поддерживать новые команды. Или выбрать другой путь — использовать набор макрокоманд, предоставляемых фирмой Microsoft (защищенный, кстати, ее авторскими правами). Но, как быть тем, кто привык работать с ассемблерами других фирм? Более того, разработка данной задачи и использование ее результатов в своей практической работе ощутимо поднимает уровень профессиональной подготовки программиста. А это уже достижение одной из целей данной книги.
Теория компиляции разработана очень хорошо. В списке литературы вы сможете найти ссылки на некоторые источники, где приведено ее описание. Наша задача — сформировать некий подход, который бы на хорошем профессиональном уровне позволил вам решать определенный круг задач. Конечно же, мало кому придется разрабатывать свой транслятор, но практически всем приходилось или придется разрабатывать языковой интерфейс своей программы с пользователем. Ну и как ваша программа будет его обрабатывать? На основе каких-то символьных заготовок? Изучив предлагаемый материал, вы, например, самостоятельно сможете производить синтаксический разбор предложений, поступающих
на вход вашей программы, оптимальным образом анализировать содержимое нужных файлов и т. п.

Формальное описание языка программирования

Язык программирования является подмножеством естественного языка и предназначен для поддержки процесса общения человека с компьютером. В общем случае язык — это множество предложений, которые можно записать на нем. Отличие языка программирования от естественного — в его законченности или замкнутости. Под этим понимается, что теоретически можно перечислить все предложения, которые можно на нем составить. Для естественного языка это невозможно. В контексте нашего изложения под языком программирования будем понимать не только языки высокого уровня, но и языки командных процессоров и вообще любые наборы предложений, с помощью которых производится управление работой некоторой программы.
Теория компиляции базируется на том, что любой язык может быть описан формально.
Основа любого естественного языка — его алфавит, то есть множество символов букв. Вспомним, что обучение в школе начинается с букваря, то есть со знакомства с набором символов, из которых в дальнейшем будут строиться слова. Приступая к изучению языка программирования, программист также вначале знакомится с набором символов (букв, цифр, разделительных знаков), из которых строятся слова программы и объединяются затем в предложения программы. Для формального описания языка программирования также необходимо знать алфавит, но в этом случае его понятие отличается от того, к которому мы привыкли. К этому мы вернемся чуть позже. Для написания программы недостаточно знать только лишь один алфавит. Так, в школе после изучения алфавита дети начинают изучать предмет «Русский язык». Можно выделить по крайней мере две цели, которые при этом ставятся: во-первых, на основе алфавита и набора правил научить школьника правильно строить слова языка (которые составляют его лексику); во-вторых, научить его правильно составлять предложения из слов, то есть делать это так, чтобы его могли понимать окружающие. Для построения правильных предложений в любом языке существует набор правил, которые описывают синтаксис этого языка. Каждому правильному предложению языка приписывается некоторый смысл. Описание смысла предложений составляет семантику языка.
Естественный язык многозначен, и часто с его помощью одну и ту же мысль можно выразить несколькими синтаксически разными предложениями. Компьютер — не человек, и общение с ним (во всяком случае, пока) должно быть однозначным, то есть не может быть двух разных по написанию предложений, выполняющих одно действие. Применительно к компьютеру семантика языка программирования представляет собой описание того, как следует исполнять на машине конкретное предложение. Различие синтаксиса и семантики лучше всего иллюстрирует следующий классический пример. Имеются два одинаковых с точки зрения синтаксиса предложения:
Здесь I, J, К — целые, а X, Y, Z — вещественные числа. В машинном представлении для вычисления данных выражений будут использоваться не только разные команды, но и алгоритмы. Если вдруг перед нами будет поставлена задача перевода программы на другой язык программирования, то в той или иной степени будет меняться все — алфавит, лексика, синтаксис, но семантика в идеале должна остаться неизменной.
Таким образом, для формального описания языка необходимы по крайней мере два элемента — алфавит и набор правил (синтаксис) — для построения предложений языка. Существует еще несколько элементов формального описания, которые также важны для процесса однозначного построения и распознавания предложений языка. Знакомство с ними целесообразно вести в рамках такого понятия, как грамматика языка.
Грамматика языка представляет собой механизм порождения предложений языка и определяет форму (синтаксис) допустимых предложений языка. Это важное положение, запомните его. В своем изложении мы постараемся по возможности избежать «формализмов», которыми изобилует теория компиляции, хотя полностью сделать это нам не удастся. В частности, без этого трудно ввести понятие грамматики. Формально грамматику языка G можно определить как совокупность четырех объектов: G-{Vt. Vn. P. Z}
Эти объекты можно описать следующим образом.

Vt — множество терминальных символов грамматики. Кстати, в этом контексте слово «символ» не означает отдельную литеру. В контексте терминальных и нетерминальных символов символы — это ключевые слова, допустимые имена идентификаторов, знаки операций, разделительные знаки, то есть все отдельные объекты исходного текста программы, имеющие смысл для компилятора. По сути, множество терминальных символов представляет собой набор лексем, которые являются допустимыми словами языка, составляющими его лексику. Таким образом, важно понимать, что исходный текст программы состоит только из терминальных символов.
Vn — множество нетерминальных символов. Эти символы являются вспомогательными конструкциями, определенными внутри грамматики. К пояснению того, что представляют собой нетерминальные символы, мы вернемся чуть позже. Важно отметить, что множества Vt и Vn не пересекаются. Объединение множеств Vt и Vn составляет алфавит языка. Отметим, что введенное здесь понятие алфавита грамматики (а значит, и языка) отличается от того, что есть в букваре. Не забывайте об этом важном моменте при проведении дальнейших аналогий.
P- набор правил грамматики, определяющих синтаксис языка. Эти правила называются правилами вывода. Эти правила определяют возможность получения любого предложения языка.
Z- начальный символ языка. Он входит в множество Vn. Одна из его особенностей состоит в том, что он должен встретиться по крайней мере в левой части одного из синтаксических правил, входящих в множество Р. И именно это правило является первым в процессе вывода любого допустимого предложения языка.

Далее, если не оговорено особо, прописными буквами будем обозначать терминальные символы, а строчными — нетерминальные.
Поясним, как с помощью грамматики задается язык. Начнем с простого примера. Опишем грамматику G1nt языка целых чисел:

Glnt = {Vt=(0.1.2,3.4.5.6.7.8.9). VrH число, цифра). Р. г=(число)}.

Множество правил Р грамматики Gint выглядит так:

число::=цифра
число::=цифра число
цифра::=0
цифра::=1
цифра::=2
цифра::-3
цифра::=4
цифра::=5
цифра::=6
цифра::-7
цифра::-8
цифра::=9

Обычно подобные правила записывают короче:

число::= цифра | цифра число цифра::=0|1|2|3|4|5|6|7|8|9

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

число::= цифра (2.9)
число::= цифра число (2.10)

Сам процесс вывода предложения языка итеративный и состоит из одного или нескольких шагов. Например, рассмотрим процесс получения предложения 8745. Согласно сказанному выше, на первом шаге вывода можно использовать правило (2.9) или (2.10). Если использовать правило (2.9), то это означает, что предложение будет состоять из одной цифры. В нашем случае на первом шаге необходимо применить правило (2.10). Производя дальнейшие подстановки, можно получить предложение, состоящее из любого количества цифр. Заметьте, что на последнем шаге вместо правила (2.10) применяется правило (2.9), что в конечном итоге приводит к желаемому результату. Таким образом, предложение 8745 получается использованием правил вывода грамматики в следующей последовательности:

число => цифра число => 8 число => 8 цифра число => 87 число => 87 цифра число => 874 число => 874 цифра => 8745.

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

цифра число, 8 число, 8 цифра число, 87 число, 87 цифра число, 874 число, 874 цифра, 8745.

Предложением языка является только одна из этих сентенциальных форм — строка 8745.
На правила грамматики обычно накладываются определенные ограничения. В зависимости от этих ограничений языки делятся на 4 класса.

Класс 0. Грамматики без ограничений. Правила этих грамматик имеют форму: u=>w. При этом не накладывается каких-либо ограничений на строки и и v в левой и правой частях правил вывода. Используя языки этого класса, можно моделировать естественный язык.
Класс 1. Контекстно-чувствительные грамматики. Правила этих грамматик имеют форму: AuB=>AwB. Замена и на v возможна лишь в контексте строк А и В (отсюда и название). При этом: ueVn; we(VnuVt)*; A, Be(VnuVt)+. Символы * и + обозначают множество всех строк, выводимых в рамках данной грамматики, включая ("*") и исключая ("+") пустую строку.
Класс 2. Контекстно-свободные, или контекст}ю-нечувствительные, грамматики. Их правила имеют форму: u=>w, где ueVn, we(VnuVt)*. Название данного класса грамматик отражает тот факт, что и можно заменить на w, не обращая внимания на контекст. Другая особенность грамматик этого класса в том, что в правой части всех правил грамматики стоит только один нетерминал. Отметим, что языки программирования моделируются с использованием грамматик именно этого класса.
Класс 3. Регулярные, или автоматные, грамматики. Исходя из вида правил, которые используются в таких грамматиках, их делят на два подкласса.
Грамматика, выравненная вправо. Ее правила имеют форму: u=>Aw или и=>А, где AeVt, u и weVn.
Грамматика, выравненная влево. Ее правила имеют форму: u=>\vA или и=>А, где AeVt, u и weVn. Это очень важный класс грамматик, который наряду с грамматикой класса 2 используется для моделирования языков программирования. Заметим, что рассмотренная выше грамматика языка целых чисел как раз и является грамматикой класса 3. Чтобы убедиться в этом, необходимо лишь немного подправить правила:

число: ."¦ цифра
число: :*=0 число |1 число |2 число |3 число |4 число |5 число |б число |7 число
|8 число |9 число иифра::=0|1|2|3|4(5|6|7|8|9

Приведенная выше классификация языков была введена в 1959 году американским ученым-лингвистом Н. Хомским.
Выше, при изложении основ работы с двусвязными списками, мы ввели понятие конечного автомата. Язык, который воспринимает любой конечный автомат, относится к языкам класса 3, то есть является регулярным. Покажем это, сформулировав грамматику для языка вещественных чисел. Напомним соответствующее регулярное выражение: (+| -)dd*.dd*e(+| 0dd*, где d* обозначает цифру 0-9 или пусто.

Grea1-{Vt-(.. + . -. е. 0. 1, 2, 3. 4. 5. 6. 7. 8. 9). VrHreal. s. m, n. k, t). P. Z-(< real >)}.

Множество правил P грамматики Greal:

Попробуйте, используя данную грамматику, самостоятельно вывести следующие предложения языка вещественных чисел: 5.5, +0.6е-5. Покажите, что предложение «+.45е4» невыводимо в терминах данной грамматики. При необходимости посмотрите еще раз материал раздела «Сеть» данной главы, где было введено понятие конечного автомата и разработана программа, моделирующая его работу при распознавании строки с вещественным числом.
Анализ правил вывода грамматики Greal показывает, что генерируемый ею язык относится к языкам класса 3, а сама грамматика является грамматикой, выровненной вправо.
Рассмотрим еще одну грамматику для языка идентификаторов Gident.

G1dent-{Vt-(.. +. -. е. 0. 1. 2. 3. 4. 5. 6. 7. 8, 9). VrHreal. S. M. N. К. Т), Р, 2=(< real >)}

Множество правил Р грамматики Gident:

ident=>letter| ident letter | ident figure letter => A|B|C| ... X|Y|Z figure => 0|l|2|...8|9

Видно, что это тоже грамматика языка класса 3.
А теперь приведем пример грамматики, генерирующей язык класса 2. С ее помощью смоделируем псевдоязык, похожий на Pascal, который мы используем в нашей книге для пояснения некоторых алгоритмов:

Vt=(riPOrPAMMA, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ. КОН_ПРОГ, НАЧ_БЛОК. КОН_БЛОК. ".".ID. CHJNT. СН_ REAL. «:».«:». «/». REAL. INTJYTE. INT_WORD. INT_OWORD. «,».«:»». «=».«+».«-».«*». DIV. MOO. «(». «)». «[». «]». «<».«>», «==»,«>=».«=<». ЧИТАТЬ, ПИСАТЬ, ДЛЯ. ДОДЕЛАТЬ. ПОКА. Д08НИЗ, ЕСЛИ. ЕСЛИ. ДО. ТО. ПЕРЕЙТИ_НА. ПОВТОРИТЬ),
Vn»( prog, prog-name, dec-list, stmt-list, dec. id-list, type. var. varjnd. ind. label. go_to. stmt, assign, read, write, until, for. call_func. exp. term, factor, index-exp. body, condition. cond_op). P. Z-(< prog >) }

Множество правил Р грамматики G:

Посмотрим внимательно на правило вывода, в левой части которого стоит начальный символ языка prog. Правая часть этого правила представляет собой сентенциальную форму, содержащую все необходимые элементы программы. На примере этой грамматики хорошо видно, что представляет собой алфавит языка программирования. По сути это совокупность лексем, которые программист использует для написания программы и которые в терминах языка являются терминальными символами, а также нетерминалов, которые имеют смысл в рамках грамматики. Более того, к терминальным символам относятся также символы ID (идентификатор), CHINT (целое число) и CHREAL (вещественное число). В программе им соответствуют Совершенно разные сочетания символов букв, цифр и разделительных знаков, например идентификаторы — chl, sab, masl; целые числа — 1, 24, 98584; вещественные числа — +33.5, 0.95е-3. С точки зрения синтаксиса эти разные по написанию объекты являются терминальными символами — идентификатором, целым числом, вещественным числом. Это ключевой момент. Мы
к нему еще вернемся, а пока давайте посмотрим, каким превращениям подвергается исходный текст программы, для того чтобы превратиться в форму, пригодную для машинного исполнения.

Описание процесса трансляции программы

Транслятор представляет собой программу, выполняющую анализ исходного кода на некотором языке программирования и формирующую объектный модуль. Процесс преобразования исходного кода называется трансляцией. Вместо термина «транслятор», часто употребляется слово «компилятор», и соответственно процесс преобразования называется компиляцией. Не вдаваясь в описание лишних подробностей, будем считать эти названия синонимами и в дальнейшем изложении использовать их исходя из своих пристрастий.
Для многих транслятор представляется как некий черный ящик, которому программист много раз на день доверяет выстраданную им программу. При общении программиста с транслятором возможны два варианта исхода: удачный, при котором на выходе транслятора формируется объектный модуль, и неудачный, когда транслятор обнаруживает в программе различные ошибки. Давайте заглянем в черный ящик, именуемый транслятором, и посмотрим, каким образом он работает. Конечно же, нашему взгляду будут доступны только общие принципы его функционирования, но мы их рассмотрим с той степенью детализации, чтобы можно было самим разработать нечто подобное.
Трансляция программы производится в несколько этапов.

Лексический анализ.
Синтаксический анализ.
Генерация кода.

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

Лексический анализ

Цель лексического анализа — выделение и классификация лексем в тексте исходной программы. Программа, которая выполняет лексический анализ, называется сканером, или лексическим анализатором. Сканер производит посимвольное чтение файла с исходным текстом программы.
Полный набор лексем языка определен множеством терминальных символов в его грамматике. Среди них можно выделить изменяемые и неизменяемые лексемы. Неизменяемые лексемы в любой программе пишутся одинаково. Для грам матики псевдоязыка это такие лексемы, как: ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОН_ ПРОГ, НАЧ_БЛОК, КОН_БЛОК, «.», «;», «:», «/», REAL, INTBYTE, INT_WORD, INTDWORD, «,», «:=», «=», «+», «-», «*», DIV, MOD, «(», «)», «[», «]», «<», «>», «==», ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ. «За бортом» остались три терминальных символа — ID, CH_INT, CH_REAL. Эти терминальные символы соответствуют идентификаторам, целым и вещественным числам. Естественно, что даже в пределах одной программы они будут различны. Задачей сканера как раз и является распознавание изменяемых и неизменяемых терминальных символов. С позиции логики обработки сканером удобно все терминальные символы отнести к одному из следующих классов (применительно к нашей грамматике псевдоязыка):

идентификаторы — ID;
ключевые слова - ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧПРОГ, КОН_ПРОГ, НАЧБЛОК, КОН_ БЛОК, REAL, INTJYTE, INTWORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;
целые числа — CHINT;
вещественные числа — CH_REAL;
однолитерные разделители — «.», «,», «;», «:<@187>, «+»,«-», «*»,«/», «(»,«)», «=», «[», «]», «<», «>»;

В двулитерные разделители — «:=», «=», «>=», «=<».
Задача сканера — построить для каждого терминального символа его внутреннее представление. Делается это для того, чтобы убрать лишнюю информацию, подаваемую на вход синтаксического анализатора. Проведем аналогию. Все знают о твердом порядке слов в английском предложении. При этом не оговариваются конкретные слова, которые должны стоять на месте подлежащего, сказуемого, дополнения. Главное, чтобы слово, которое стоит, например, на месте подлежащего, было существительным или местоимением, то есть относилось к определенному классу. Сканер как раз и выполняет классификацию лексем, подаваемых на его вход. Он распознает, например, что очередная лексема является ключевым словом begin, после чего присваивает ей определенное целое значение и передает его далее. Если же сканер распознал на своем входе некоторый идентификатор, то он производит не просто замещение, но и некоторые другие действия. Чтобы подробнее разобраться со всем этим, необходимо понять состав и назначение структур данных, определенных внутри сканера.
Сканер работает с определенным набором таблиц, среди которых есть входные и выходные.
В общем случае сканер должен иметь две входные таблицы — таблицу лексем языка и таблицу классов литер. Таблица лексем языка содержит перечень всех лексем языка и соответствующих им целочисленных значений. Для нашей грамматики таблица может быть следующей:

Лексема	Внутренний код	Лексема	Внутренний код
ПРОГРАММА	1	*	23
		:=	24
НАЧ БЛОК	3	)	25
КОН_БЛОК	4	НАЧ_ПРОГ	26
REAL	5	КОН_ПРОГ	27
INT_BYTE	6	/	28
DIV	7	INT_WORD	29
ЧИТАТЬ	8	INT_DWORD	30
ПИСАТЬ	9	=	31
ДЛЯ	10	MOD	32
ДЕЛАТЬ	11	[	33
(	12	]	34
ТО	13	<	35
ID	14	>	36
CHJNT	15	==	37
CH_REAL	16	>=	38
	17	=<	39
>	18	до	40
¹	19	ПОКА	41
•	20	довниз	42
+	21	ЕСЛИ	43
-	22	до	44
		ПЕРЕЙТИ_НА*

Таблица классов литер используется только в процессе сканирования и предназначена для выяснения класса литеры, когда она выбирается сканером из входного потока. Лучше всего эту таблицу организовать в виде массива, элементы которого отражены на используемую кодовую таблицу (например, таблицу ASCII). Значение каждого элемента таблицы классов литер определяется классом литеры в кодовой таблице. В общем случае можно определить следующие классы литер:

d - цифра;
1 — буква;
b — литеры, которые игнорируются, к ним может относится, например, пробел;
s1 — одиночные разделители: «.», «:», «(«, «)», «*»;
s2 — особые одиночные разделители: «.», «+», «-»,«:», «=», «<», «>».

Последние разделители отличаются тем, что они могут быть как собственно одиночными разделителями, так и входить в состав литер лексем, состоящих из нескольких литер. Например, разделитель «:» является не только одиночным, но и первой литерой двухлитерного разделителя «:=», а литеры «.», «+» и «-» являются составной частью лексемы «вещественное число».
Количество выходных таблиц может быть различным и определяется сложностью входного языка. В минимальном варианте используют две или три таблицы: таблицу лексической свертки, таблицу идентификаторов и, возможно, таблицу констант. Рассмотрим пример программы на псевдоязыке:

ПРОГРАММА progl (1M14, #progl) ПЕРЕМЕННЫЕ (2)
INTBYTE 1 (6) (14. #i)
НАЧ_ПРОГ (26)
ДЛЯ i := О ТО 9 ДЕЛАТЬ (10Н14, #i)(24)(15. 0)(13)(15. 9Н11) ПИСАТЬ (i) (9)(12)(14, #i)(25)
КОНПРОГ (27)

Приведенная программа выводит на экран целые числа от 0 до 9, хотя в контексте нашего обсуждения это и не важно. После обработки сканером исходный текст программы преобразуется во внутреннее представление, которое показано справа для каждой строки. Становится понятным значение термина «лексическая свертка» — программа как бы сворачивается в некоторую унифицированную форму, теряя при этом свою индивидуальность. Каждая лексема замещена своим кодом. Идентификаторы замещены кортежами, первый элемент которых является кодом лексемы-идентификатора, а второй элемент — ссылкой на элемент таблицы идентификаторов, где содержится более подробная информация о данном идентификаторе. Ссылка может быть адресом элемента в таблице, но может быть удобнее, чтобы это было просто число, представляющее собой индекс в этой таблице. Это же касается и лексемы «целое число». Здесь возможны разные варианты: во-первых, можно организовать таблицу констант, подобную таблице идентификаторов; во-вторых, для простых применений константу можно разместить прямо в кортеже. В нашем примере для констант выбран второй вариант.
Можно предложить несколько способов организации таблицы идентификаторов. Самый простой и неэффективный — в виде массива указателей на списки переменной длины, элементы которого содержат символы идентификатора. Имена идентификаторов нужны лишь на этапе лексической свертки для выделения одинаковых идентификаторов. Важно понимать, что после выделения сканером идентификаторов и присвоения одинаковым из них ссылок на определенный элемент массива (таблицы) идентификаторов сами символьные имена уже не нужны. Если, конечно, не будет производиться формирование диагностических сообщений. Впоследствии эти указатели можно переориентировать для ссылок на ячейки с другой информацией, например с адресом области памяти, которая будет выделена для данного идентификатора на этапе генерации кода. Аналогично можно организовать и таблицы констант, если в этом возникнет необходимость. Это самые простые варианты организации подобных таблиц. Но исходя из опыта, полученного при изучении материала данной книги, можно организовать таблицу символов более эффективно — в виде лексикографического дерева или используя методы хэширования. Если используется лексическое дерево, то каждый узел этого дерева может состоять из следующих полей:

уникальный номер — номер, который на последующих этапах трансляции
будет идентифицировать данное символьное имя;
указатель на список, содержащий символы идентификатора;
указатель на список с номерами строк, в которых встретился данный идентификатор.

Впоследствии, когда имена идентификаторов не будут нужны, можно на основе этого дерева построить хэш-таблицу, доступ к элементам которой будет осуществляться на основе уникальных номеров. Кстати, для повышения эффек-
тивности процесса распознавания стоит все терминальные символы — ключевые слова языка, разделители и т. п. (за исключением id, chint и ch_rea1) — также свести в отдельное лексикографическое дерево или организовать хеш-таблицу.
Можно поступить по-другому. Этот вариант, который можно использовать для анализа ввода в командной строке и т. д., работает в случае, если сканер вызывается из синтаксического анализатора. Суть его в том, что сканер вызывается из синтаксического анализатора, когда последнему нужна очередная лексема. Сканер выделяет ее во входном потоке и выдает синтаксическому анализатору кортеж из двух элементов: кода лексемы и строки, содержащей саму лексему.
А как организовать сам процесс распознавания лексем входной программы? Для этого попробуем сформулировать некий обобщенный алгоритм построения сканера.

Выделить классы лексем.
Определить классы литер.
Определить условия выхода из сканера для каждого класса лексем.
Для каждого класса лексем поставить в соответствие грамматику класса 3.<
Для каждой грамматики, построенной на шаге 4, построить конечный автомат, который будет распознавать лексему данного класса.
Выполнить объединение («склеивание») конечных автоматов для всех классов лексем.
Составить матрицу переходов для «склеенного» конечного автомата.
«Навесить» семантику на дуги «склеенного» конечного автомата.
Выбрать коды лексической свертки для терминалов грамматики и формат таблицы идентификаторов.
Разработать программу сканера.

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

Выделение классов лексем

Эффективность этапа лексического анализа не в последнюю очередь определяется правильностью разбиения лексем входной программы на классы. Причем эти классы не должны пересекаться. В ходе сканирования каждый входной терминальный символ (лексема) должен быть отнесен к одному из классов. Как мы уже отмечали выше, для грамматики псевдоязыка можно определить следующие классы лексем:

идентификаторы — ID;
ключевые слова - ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОНПРОГ, НАЧ_БЛОК, КОН БЛОК, REAL, INTJYTE, INT_WORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;
целые числа — CH_INT;

«Навешивание» семантики на дуги «склеенного» конечного автомата
В ходе распознавания (перехода по дугам) требуется выполнять различные действия, например поиск соответствия введенной лексемы ключевому слову в таблице ключевых слов, поиск идентификатора в таблице идентификаторов, преобразования чисел и т. д. Поэтому на этом шаге необходимо определить набор переменных и состав процедур, работающих во время переходов из состояния в состояние (на дугах).
Все... После этого можно программировать сканер. В главе 10, посвященной командам ММХ- и ХММ-расширений, нами будет выполнена практическая работа в этом направлении.

Синтаксический анализ

После того как лексемы входного потока распознаны, транслятору необходимо удостовериться, что вся их совокупность является синтаксически правильной. Вопрос: зачем? Заглянем немного вперед и задумаемся о том, каким образом производится генерация кода. Если рассматривать этот вопрос схематично, то можно утверждать, что для каждого нетерминала грамматики существует некий шаблон кода, который подставляется в определенное место выходного кода. Настройка этого шаблона производится значениями лексем, распознанными сканером. Извлечь эту информацию можно, если соответствующая конструкция в исходном коде синтаксически правильна. В конечном итоге мы должны доказать, что вся программа синтаксически правильна.
Цель синтаксического анализа — доказать существование дерева грамматического разбора в контекстно-свободной грамматике G для входной цепочки s, состоящей из терминальных символов.
Существует много различных методов синтаксического анализа программ. Но главное понимать, что все они неявно стремятся доказать одно и тоже — существование синтаксического дерева для транслируемой программы. Ведь применительно к нашей грамматике не может блок описания переменных следовать где-то в середине или конце программы, за операторами, которые эти переменные используют. Кстати, посмотрите сейчас еще раз на правило грамматики, соответствующее начальному символу языка. В этом правиле определена общая структура программы и в ней видно место блока описаний переменных. Вместо списка стоит нетерминал. Можно нарисовать воображаемую дугу к правилу грамматики, соответствующему нетерминалу блока описания переменных, и т. д. То есть мы действительно начали строить грамматическое дерево. И если нам удастся его построить для данной программы, то последняя действительно синтаксически правильна. Если на каком-то шаге построения этого дерева у нас случится ошибка, допустим в том же блоке описания переменных программы вместо идентификатора будет стоять целое число, то дерево мы построить не сможем. То есть программа синтаксически неправильная. Можно формировать соответствующее диагностическое сообщение.
Таким образом, можно утверждать, что если возможно построение дерева трансляции для данного входного потока, то он синтаксически правилен. Понятно, что для другого текста программы дерево трансляции будет другое, но в лю-
бом случае листьями этого дерева будут лексемы программы, а корнем — начальный символ языка. Причем если совершить обход листьев дерева слева направо, то получим вытянутый в строку текст нашей программы.
Если судить по рисунку, то программа синтаксически правильная. Но каким бразом выясняет этот факт транслятор? Как отмечено выше, существует несколько методов выполнения синтаксического анализа. Все они делятся на два класса в зависимости от того, как они движутся по дереву трансляции во время разбора — сверху вниз или снизу вверх. Алгоритмы «сверху вниз» стремятся построить дерево трансляции начиная вывод от начального символа языка к анализируемой цепочке. И наоборот, алгоритмы «снизу вверх» строят дерево трансляции от анализируемой цепочки терминалов к начальному символу языка. Важно подчеркнуть, что на самом деле никакого дерева в памяти нет и не строится. Как показано выше, его структура заложена в правилах грамматики. Используя алгоритм конкретного метода синтаксического разбора и представленные определенным образом в памяти правила грамматики, мы и производим движение по воображаемому дереву трансляции.
На практике не исключены случаи комбинированного применения восходящих и нисходящих методов синтаксического анализа. Например, арифметические выражения удобно разбирать с помощью восходящих методов, а общий разбор программы делать нисходящими методами. В большинстве случаев достаточно одного универсального метода — метода рекурсивного спуска. Для краткости будем называть синтаксический анализатор распознавателем.

Метод рекурсивного спуска

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

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

dec-list => dec | dec-list ; dec id-HSts» ID I {. ID}
stmt-list => stmt | {: stmt} exp => term {+ term | - term}
term => factor {* factor | div factor}

Теперь для принятия решения о дальнейшем пути выполнения рекурсивной процедуры необходимо просматривать один символ вперед. Если он совпадает с тем, что в правиле, то процедура рекурсивно вызывается снова. Если этот символ любой другой, то производится возврат из этой процедуры. Таким образом, процесс написания программы неявно представляет собой строительство дерева разбора начиная от его корня — начального символа языка. То есть это действительно нисходящий метод.
Остается заметить еще одно достоинство метода рекурсивного спуска. Если очередная языковая конструкция распознана, то почему бы сразу в соответствующей рекурсивной процедуре не «навесить» семантику, то есть генерацию кода.
Но метод рекурсивного спуска не всегда применим. В сложных случаях, когда имеется скрытая левая рекурсия, необходимо применять более сложные методы для ее устранения или замены правой рекурсией.
После этого обсуждения мы готовы написать распознаватель, но делать этого не будем, так как цель, достижению которой был посвящен материал данного раздела, достигнута. Все остальное — техника программирования. Остается добавить, что разговор о проблемах трансляции мы продолжим в главе Программирование ХММ-расширения.