Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

begin

if minEl <> nil then minEl.ClearAllInfo;

if maxEl <> nil then maxEl.ClearAllInfo;

ClearInfo;

end;

function TVarInfo.AddElCnt(const sAdd: string;

var iCnt: integer): TVarInfo;

{ Функция добавления элемента в бинарное дерево

с учетом счетчика сравнений }

var i: integer;

begin

Inc(iCnt); { Увеличиваем счетчик сравнений }

{ Сравниваем имена элементов (одной функцией!) }

i:= StrComp(PChar(Upper(sAdd)), PChar(Upper(sName)));

if i < 0 then

{ Если новый элемент меньше, смотрим ссылку на меньший }

begin { Если ссылка не пустая, рекурсивно вызываем

функцию добавления элемента }

if minEl <> nil then

Result:= minEl.AddElCnt(sAdd,iCnt)

else

begin { Если ссылка пустая, создаем новый элемент

и запоминаем ссылку на него }

Result:= TVarInfo.Create(sAdd);

minEl:= Result;

end;

end

else

{ Если новый элемент больше, смотрим ссылку на больший }

if i > 0 then

begin { Если ссылка не пустая, рекурсивно вызываем

функцию добавления элемента }

if maxEl <> nil then

Result:= maxEl.AddElCnt(sAdd,iCnt)

else

begin { Если ссылка пустая, создаем новый элемент

и запоминаем ссылку на него }

Result:= TVarInfo.Create(sAdd);

maxEl:= Result;

end;

end { Если имена совпадают, то такой элемент уже есть

в дереве – это текущий элемент }

else Result:= Self;

end;

function TVarInfo.AddElem(const sAdd: string): TVarInfo;

{ Функция добавления элемента в бинарное дерево }

var iCnt: integer;

begin Result:= AddElCnt(sAdd,iCnt); end;

function TVarInfo.FindElCnt(const sN: string;

var iCnt: integer): TVarInfo;

{ Функция поиска элемента в бинарном дереве

с учетом счетчика сравнений }

var i: integer;

begin

Inc(iCnt); { Увеличиваем счетчик сравнений }

{ Сравниваем имена элементов (одной функцией!) }

i:= StrComp(PChar(Upper(sN)), PChar(Upper(sName)));

if i < 0 then

{Если искомый элемент меньше, смотрим ссылку на меньший}

begin {Если ссылка не пустая, рекурсивно вызываем для нее

функцию поиска элемента, иначе – элемент не найден}

if minEl <> nil then Result:= minEl.FindElCnt(sN,iCnt)

else Result:= nil;

end

else

if i > 0 then

{Если искомый элемент больше, смотрим ссылку на больший}

begin {Если ссылка не пустая, рекурсивно вызываем для нее

функцию поиска элемента, иначе – элемент не найден}

if maxEl <> nil then Result:= maxEl.FindElCnt(sN,iCnt)

else Result:= nil;

end { Если имена совпадают, то искомый элемент найден }

else Result:= Self;

end;

function TVarInfo.FindElem(const sN: string): TVarInfo;

{ Функция поиска элемента в бинарном дереве }

var iCnt: integer;

begin Result:= FindElCnt(sN,iCnt); end;

end.

unit FncTree;

interface

{ Модуль, обеспечивающий работу с комбинированной таблицей

идентификаторов, построенной на основе хэш-функции и

бинарного дерева }

uses TblElem;

{ Функция начальной инициализации хэш-таблицы }

procedure InitTreeVar;

{ Функция освобождения памяти хэш-таблицы }

procedure ClearTreeVar;

{ Функция удаления дополнительной информации в таблице }

procedure ClearTreeInfo;

{ Добавление элемента в таблицу идентификаторов }

function AddTreeVar(const sName: string): TVarInfo;

{ Поиск элемента в таблице идентификаторов }

function GetTreeVar(const sName: string): TVarInfo;

{ Функция, возвращающая количество операций сравнения }

function GetTreeCount: integer;

{ Функция записи всех имен идентификаторов в одну строку }

function IdentList(const sLim,sInp,sOut: string): string;

implementation

const { Минимальный и максимальный элементы хэш-таблицы }

HASH_MIN = Ord(0 )+Ord(0 ); {(охватывают весь диапазон}

HASH_MAX = Ord('z')+Ord('z'); { значений хэш-функции)}

var { Массив для хэш-таблицы }

HashArray: array[HASH_MIN..HASH_MAX] of TVarInfo;

iCmpCount: integer; { Счетчик количества сравнений }

function GetTreeCount: integer;

begin Result:= iCmpCount; end;

function IdentList(const sLim,sInp,sOut: string): string;

{ Функция записи всех имен идентификаторов в одну строку }

var

i: integer; { счетчик идентификаторов }

sAdd: string; { строка для временного хранения данных }

begin

Result:= ; { Первоначально строка пуста }

for i:=HASH_MIN to HASH_MAX do

begin { Цикл по всем идентификаторам в таблице }

{ Если ячейка таблицы пустая, то добавлять не нужно, }

if HashArray[i] = nil then sAdd:=

{ иначе вычисляем добавочную часть строки }

else sAdd:= HashArray[i].GetElList(sLim,sInp,sOut);

if sAdd <> then

begin { Если добавочная часть строки не пуста,

то добавляем ее в общую строку через разделитель }

if Result <> then Result:= Result + sLim + sAdd

else Result:= sAdd;

end;

end{for};

end;

function VarHash(const sName: string): longint;

{ Хэш-функция – сумма кодов первого и среднего символов }

begin

Result:= (Ord(sName[1])

+ Ord(sName[(Length(sName)+1) div 2])

– HASH_MIN) mod (HASH_MAX-HASH_MIN+1)+HASH_MIN;

if Result < HASH_MIN then Result:= HASH_MIN;

end;

procedure InitTreeVar;

{Начальная инициализация хэш-таблицы – все элементы пусты}

var i: integer;

begin for i:=HASH_MIN to HASH_MAX do HashArray[i]:= nil;

end;

procedure ClearTreeVar;

{ Освобождение памяти для всех элементов хэш-таблицы }

var i: integer;

begin

for i:=HASH_MIN to HASH_MAX do

begin

HashArray[i].Free; HashArray[i]:= nil;

end;

end;

procedure ClearTreeInfo;

{ Удаление дополнительной информации для всех элементов }

var i: integer;

begin

for i:=HASH_MIN to HASH_MAX do

if HashArray[i] <> nil then HashArray[i].ClearAllInfo;

end;

function AddTreeVar(const sName: string): TVarInfo;

{ Добавление элемента в хэш-таблицу и дерево }

var iHash: integer;

begin

iCmpCount:= 0; { Обнуляем счетчик количества сравнений }

iHash:= VarHash(Upper(sName)); { Вычисляем хэш-адрес }

if HashArray[iHash] <> nil then

Result:= HashArray[iHash].AddElCnt(sName,iCmpCount)

else

begin

Result:= TVarInfo.Create(sName);

HashArray[iHash]:= Result;

end;

end;

function GetTreeVar(const sName: string): TVarInfo;

{ Поиск элемента в таблице идентификаторов }

var iHash: integer;

begin

iCmpCount:= 0; { Обнуляем счетчик сравнений }

iHash:= VarHash(Upper(sName)); { Вычисляем хэш-адрес }

if HashArray[iHash] = nil then Result:= nil

{ Если ячейка по адресу пуста – элемент не найден, }

else { иначе вызываем функцию поиска по дереву }

Result:= HashArray[iHash].FindElCnt(sName,iCmpCount)

end;

initialization

{Вызов начальной инициализации таблицы при загрузке модуля}

InitTreeVar;

finalization

{ Вызов освобождения памяти таблицы при выгрузке модуля }

ClearTreeVar;

end.

unit LexType; {!!! Зависит от входного языка!!!}

interface

{ Модуль, содержащий описание всех типов лексем }

type

TLexType = { Возможные типы лексем в программе }