Построение таблицы идентификаторов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Построение таблицы идентификаторов



Введение

программа идентификатор произвольный

Учебная цель. Получение практических навыков построения таблицы идентификаторов разными способами и сравнение их эффективности.

Необходимо изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатах, присущих различным методам организации таблиц идентификаторов.

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



1. Теоретические сведения.

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

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

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

Компилятор может работать c одной или несколькими таблицам идентификаторов - их количество зависит от реализации компилятора. Например, можно организовывать различные таблицы идентификаторов для различных модулей исходной программы или для различных типов элементов входного языка.

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

· для переменных: имя переменной; тип данных переменной; область памяти, связанная с переменной;

· для констант: название константы (если оно имеется); значение константы; тип данных константы (если требуется);

· для функций: имя функции; количество и типы формальных аргументов функции; тип возвращаемого результата; адрес кода функции.

Приведенный выше состав хранимой информации, конечно же, является только примерным. Конкретное наполнение таблиц идентификаторов зависит от реализации компилятора.

Кроме того, не вся информация, хранимая в таблице идентификаторов, заполняется компилятором сразу - он может несколько раз выполнять обращение к данным в таблице идентификаторов на различных фазах компиляции. Например, имена переменных могут быть выделены на фазе лексического анализа, типы данных для переменных - на фазе синтаксического разбора, a область памяти связывается с переменной только на фазе подготовки к генерации кода.

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

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

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

Порядок выполнения работы

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

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

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

Лабораторная работа должна выполняться в следующем порядке:

1. Получить вариант задания у преподавателя.

2. Выбрать и описать хэш-функцию.

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

4. Написать и отладить программу в среде Qt-Creator.

5. Подготовить отчет, видеодемонстрациюи защитить ЛР.

Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

· Задание по лабораторной работе;

· Описание выбранной хэш-функции;

· Описание двух схем организации таблиц идентификаторов (в соответствии с вариантом задания) по шаблону - словесное описание идеи, блок-схему алгоритма помещения идентификатора в таблицу, блок-схему поиска идентификатора в таблице, программный код соответствующих функций;

· Программный код остальных частей программы;

· Описание нескольких тестовых примеров (мало идентификаторов, средне, много) и результатов их прогонки (принтскринами);

· Выводы о результатах сравнения эффективности методов в зависимости от степени заполненности таблицы идентификаторов;

· Список литературы.

Контрольные вопросы

· Что такое таблица символов и для чего она предназначена?

· Какая информация может храниться в таблице символов?

· Какие цели преследуются при организации таблицы символов?

· Какими характеристиками могут обладать лексические элементы исходнойпрограммы?

· Какие характеристики лексических элементов являются обязательными?

· Какие существуют способы организации таблиц символов?

· B чем заключается алгоритм логарифмического поиска?

· Какие преимущества алгоритм логарифмического поиска дает по сравнению с простым перебором и какие он имеет недостатки?

· Древовидная организация таблиц идентификаторов. B чем еепреимущества и недостатки?

· Что такое хэш-функция и для чего она используется?

· B чем суть хэш-адресации?

· Что такое коллизия?

· Почему происходит коллизия?

· Можно ли полностыю избежатьколлизий?

· Что такое рехэширование?

· Какие методы рехэширования существуют?

· Преимущества и недостатки организации таблиц идентификаторов с помощью хэш-ацресации и рехэширования.

· B чем заключается метод цепочек?

· Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.

· Как могут быть скомбинированы различные методы организации хэш-таблиц?

· Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью комбинированных методов.

Варианты заданий

В табл. 1.1 перечислены методы организации таблиц идентификаторов, используeмыйв заданиях.

Таблица 1.1. Методы организации таблиц идентификаторов

№метода	Способ разрешения коллизий
1	Простое рехэширование
2	Рехэширование с использованием псевдослучайных чисел
3	Рехэширование с помощью произведения
4	Метод цепочек
5	Простой список
6	Упорядоченный список
7	Бинарное дерево

В табл. 1.2 даны варианты заданий на основе методов организации таблиц идентификаторов. перечисленных в табл 1.1.

Таблица 1.2. Варианты заданий

№ варианта	Первый метод организации таблицы идентификаторов	Второй метод организации таблицы идентификаторов
1	1	5
2	2	6
3	3	7
4	4	5
5	1	6
6	2	7
7	3	5
8	4	6
9	1	7
10	2	5
11	3	6
12	4	7
13	1	5
14	2	6
15	3	7
16	4	5
17	1	6
18	2	7
19	3	5
20	4	6

2. Пример выполнения работы

Задание для примера

B качестве примера выполнения лабораторной работы возьмем сопоставлениедвух методов: хэш-адресации с рехэшированием на основе метода произведения и бинарного дерева.

Выбор и описание хэш-функции с рехэшированием

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

Будем считать, что прописные и строчные буквы в идентификаторе различны. В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows, тогда, если положить, чтострока из области определения хэш-функции содержит только цифры и буквы англпйского алфавтта, то минимальным значением хэш-фупкции будет сумма трех кодов цифры «0», aмаксимальнымзначением сумма трех кодов литеры «z».

Таким образом, область значений выбранной хэш-функции в терминах языка С может бытъ описана как:

((int)'0' + (int)'0' + (int)'0'). ((int)'z' + (int)'z' + (int)'z')

Для рехэширования с помощью произведения возьмем простейший генератор последовательности псевдослучайных чисел, построенный на основе формулы F= i*Н1 mod Н» где Н1, и Н2 - простые числа, выбранные таким образом, чтобы Н1 было в диапазоне от Н2/2 до Н2. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от НАSН_MIN до НАSН_МАХ, Н2 должно быть максимально близко к величине НАSН_МАХ-НАSН_MIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 - простое число, то возьмем Н2 = 223. В качестве Н1, возьмем 127: Н1 = 127. Длина таблицы идентификаторов будет иметь значение НАSН_МАХ-НАSН_MIN + 1=223-127+1=97 значений.

Опишем соответствующие константы:

REHASH1 = 127

RЕНАSН2 = 223

Область значений выбранной хэш-функции в терминах языка C++ может быть описана как:

((int)'0' + (int)'0' + (int)'0'). ((int)'z' + (int)'z' + (int)'z')

Сама функция хэш-функция без учета рехэширования будет вычисляться следующим образом:

(int (sName[0]) + int (sName[(sName.size()) / 2]) +

+ int (sName[sName.size() - 1])

Здесь sName - входная строка.

Хэш-функция с учетом рехэширования будет иметь вид:

int VarHash (string sName, int iNum)

{

int HASH_MIN = (int)'0' + (int)'0' + (int)'0';

int HASH_MAX = (int)'z' + (int)'z' + (int)'z';

int REHASH1 = 127;

int REHASH2 = 223;

int result;

result=(int (sName[0])+int (sName[(sName.size()) / 2])

+ int (sName[sName.size() - 1]) - HASH_MIN

+ iNum*REHASH1% REHASH2)

% (HASH_MAX - HASH_MIN + 1) + HASH_MIN;

if (result < HASH_MIN)

result = HASH_MIN;

returnresult;

}

программа идентификатор произвольный

Рисунок 1. Блок-схема хэш-функции

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

Таблица идентификаторов реализована в виде статического массива размером (HASH_MAX-HASH_MIN).

При поиске идентификатора, идентификатор, который мы ищем, пройдет ту же процедуру, что при заполнении и при встрече точно такого же идентификатора программа выдаст положительный результат («Идентификатор найден»), иначе, при сравнении идентификатора с пустой строкой, программа выдаст отрицательный результат («Идентификатор не найден») и прекратит поиск.

Рисунок 2. Участок блок-схемы записи в таблицу идентификаторов методом рехэширования с помощью произведения



Рисунок 3. Участок блок-схемы поиска идентификатора методом рехэширования с помощью произведения

Метод бинарного дерева

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



Рисунок 4. Блок-схема функции записи в таблицу идентификаторов методом бинарное дерево

При поиске идентификатора идентификатор, который мы ищем, пройдет ту же процедуру, что при заполнении, и при встрече точно такого же идентификатора программа выдаст положительный результат («Идентификатор найден»), иначе при сравнении идентификатора с пустой строкой, программа выдаст отрицательный результат («Идентификатор не найден») и прекратит поиск.

Рисунок 5. Блок-схема функции поиска идентификатора методом бинарное дерево



Таблица 3. Таблица имен переменных

Имя переменной	Тип переменной	Значение переменной
HASH_MIN	int	Минимальное значение хэш-функции
HASH_MAX	int	Максимальное значение хэш-функции
REHASH1	int	Переменная для рехэширования
REHASH2	int	Переменная для рехэширования
aMap	struct	Таблица идентификаторов метод рехэширование с помощью произведения
bMap	struct	Таблица идентификаторов метода бинарное дерево
aallCount	int	Всего сравнений метод рехэширование с помощью произведения
ballCount	int	Всего сравнений метода бинарное дерево
aMidCount	int	Среднее число сравнений метод рехэширование с помощью произведения
bMidCount	int	Среднее число сравнений метода бинарное дерево
vh	int	Результат хэш-функции
ss	string	Исходные данные

Организация интерфейса пользователя

Кроме перечисленных выше модулей необходим еше модуль, обеспечивающий интерфейс с пользователем. Этот модуль должен реализовать графическое окна - интерфейс в стиле Windowsна основе пакета QtCreator. Oн обеспечивает интерфейссредствами Graphical User Interface (GUI) в ОС типа Windows на основе стандартных органов управления из системных библиотек ОС.

Кроме описания интерфейсной формы и ее органов управления модуль организации пользовательского интерфейса содержит переменные (aallCount, ballCount, aMidCount, bMidCount), служащие для накопления статистических результатов по мере выполнения и поиска идентификаторов в таблицах, и также функцию для отображения накопленной статистической информации на экране.

Интерфейсная форма. описаниая в модуле, содержит следующие основные органы управления:

· поле ввода имени файла (EditFile),

· кнопка выбора имени файла из каталогов файловой системы (BtnFile),

· многострочное поле для отображения прочитанного файла (ListIdents);

· поле ввода имени искомого идентификатора (EditSearch),

· кнопка для поиска введенного идентификатора (BtnSearch), этой кнопкой однократно вызывается процедура поиска (SearchStr);

· кнопка автоматического поиска всех идентификаторов (BtnAHSearch) - этой кнопкой процедура поиска идентификаторов (SearchStr) вызывается циклически для всех считанных из файла идентификаторов (для всех, перечисленных в поле ListIdents);

· кнопкаa сброса накопленной статистической информации (BtnReset):

· поля для отображения статистической информации:

· кнопка завершения работы c программой (BtnExit).

Внешний вид этой формы приведен на рис. 6.

Рисунок 6. Интерфейсная форма программы



Литература

1. Системное программное обеспечение. Лабораторный практикум / Молчанов А.Ю. - СПБ.: Питер, 2005. - 284 с.:ил.

2. Алгоритмы: построение и анализ / Т. Кормен [и др.] - М.: Вильямс, 2005. -1296 с.

Размещено на Allbest.ru